A few years back I wrote Neatly replacing NavMesh with A* in UE4 and ever since I’ve had a vague notion that it’s probably gone wildly out-of-date. As it happens I was recently working on another project that would benefit from A* and I noticed UE4 already has an A* implementation called FGraphAStar, so I thought I’d write a little updated post talking about both. (Fun fact: FGraphAStar was added about two months before I wrote the earlier post… the lesson here is: always search the codebase…)
I’ve put a simple demo project up at https://bitbucket.org/crussel/astar425. Left-click the ground and watch ConeMan A* pathfind like a winner.
ANavigationData Replacement
The process of replacing NavMesh hasn’t changed much so I won’t go over it again, though it is a little simpler to plug-in: you don’t need to edit DefaultEngine.ini manually, you can just add a default Agent to the supported agents list in Project Settings/Navigation System and set its NavigationClass to your NavMesh replacement.
FGraphAStar
There’s a comment above the definition in GraphAStar.h that tells us what we need to implement. FGraphAStar is a template struct where the template parameter class TGraph has to define a type and a couple of functions. The type, FNodeRef is just a value that uniquely-identifies a node in the graph – in my simple grid demo, it’s just an FIntPoint since a grid cell can be uniquely-identified by it’s coordinates. The functions needed are:
int32 GetNeighbourCount(FNodeRef NodeRef) const
This returns the maximum number of neighbours the given node could have. In my grid-based demo, I return 8 since I allow diagonal movement. Notice I return 8 even for an edge cell – trying to filter at this point just creates unnecessary clutter.
bool IsValidRef(FNodeRef NodeRef) const
Does the given NodeRef refer to a valid node? In my demo I just return whether the coordinates are on the grid.
FNodeRef GetNeighbour(const FNodeRef NodeRef, const int32 NeighbourIndex) const
Now things get interesting – return the Xth neighbour of the given node. In my demo I count the neighbours clockwise from postive Y (this is why trying to cater for edge cells in GetNeighbourCount would get messy: if I’m a corner cell and return 3 in that case, I need to check if I’m a corner cell here again to reinterpret NeighbourIndex correctly – but if I always have 8 neighbours, the values of NeighbourIndex always have the same meaning).
So that gets the basic structure of our node graph into A*. The rest is in the query filter, which defines the following:
float GetHeuristicCost(const FNodeRef StartNodeRef, const FNodeRef EndNodeRef) const
This is the cheaply-calculated estimated cost of pathing from StartNodeRef to EndNodeRef. For my grid demo I’m just returning the manhattan distance.
bool IsTraversalAllowed(const FNodeRef NodeA, const FNodeRef NodeB) const
Can you go from NodeA to NodeB? For the grid demo, if I only allowed 4-directional movement this would be trivial: yes, if node A and node B are both open. Since I allow diagonal movement I also make sure e.g. north and east are both clear before allowing a move north-east.
float GetTraversalCost(const FNodeRef StartNodeRef, const FNodeRef EndNodeRef) const
This is the real (i.e. not estimated) cost of travelling from StartNodeRef to the adjacent node EndNodeRef. A* finds the cheapest path, so this can be used to mark preferred routes e.g. if the current node is ‘road’, and left is ‘road’ but right is ‘swamp’ we might return 1 to go left and 2 to go right.
float GetHeuristicScale() const
The comment says “used as GetHeuristicCost’s multiplier”; I haven’t used it in the demo (I just return 1) since the environment is trivial enough that heuristics don’t really matter. In a more complex environment (and a more complex heuristic) the scale can be used to adjust how much A* relies on the heuristic – if you return zero, the heuristic is ignored completely, making A* completely accurate but much slower. As you increase the value A* will search fewer paths and possibly settle on one that’s suboptimal.
And that’s about it. Nice and simple, but then A* is.