Overriding Default UE4 Pathfinding Behavior Through RecastNavMesh

ModifiedNavigation

When creating my own topdown tile-based game, I found a wonderful tutorial by crussel which provides all of the essential implementation for creating your own pathfinding method: Neatly replacing NavMesh with A* in UE4 .

This tutorial will be expanding on crussel’s article with a complete walkthrough implementing tile-based A* pathfinding for UE4.19 and providing methods for debugging and profiling the new pathfinding system. If you want to inspect the finished result with an extended RecastNavMesh implementation, you can pull the source from my github page . Without further ado, let’s get started!

Getting Started

To start, create a new C++ Project from the Top Down template.

CreateProject

The existing movement implementation in this starter kit is that the player character navigates to the location you click. Default NavMesh pathfinding uses HPA* to find optimal nodes and then string pulling the route through them (if desired). For this tutorial we will be implementing a simple square tile A* pathfinding which is both cheaper to calculate and better suited to a top-down game using Tilemaps.

DefaultNavigation

To help visualize the tile-based movement I made a simple sprite for a tile grid in paint, imported it to unreal as a texture, created a TileSet from that texture and then a TileMap from the TileSet. By orienting the camera top down I can place this TileMap in the default map and align the blocks so that they neatly fit in the square bounds. This is necessary as this barebones A* implementation will assume that the entire game world is aligned to specific coordinates.

AligningCubes
Here I use the default Wireframe viewmode to pick out the blocks from the floor, but you can also switch to Lit or Unlit viewmode.

img4_AllSetUp
_

– An aside on getting the TileMap right –

The grid is made of 128×128 px tiles. We can adjust how big a Paper2d pixel is in relation to unreal world units (expressed in cm) by adjusting the Pixels Per Unreal Unit setting in our TileMap.

img5.1 PixelsPerUnrealUnit
Here I’ve set Pixels Per Unreal Unit to 1.28, which means for our 128x128px image, one tile will be 1m square in world space. The blocks in the Top Down Template are 2m square so I set the scale of this Tilemap to 2x.

Also take care that the Tile Size is correct in the TileSet and TileMap.

img5.2 TileSetSize

Since we’ve set up the tilegrid to be spaced 2m (200 units) apart, we will want to be finding the center position of every tile every 200m. To make our lives easier make sure that the TileMap X/Y coordinates are multiples of 200.

TileMapLocation

Extending RecastNavMesh

Unreal Engine 4 has greatly extensible behavior and one useful class that’s exposed to the user without rebuilding the source is RecastNavMesh. The RecastNavMesh class is a monolithic class that defines interactions with the unexposed Detour classes to build and display the navigation mesh, as well as providing implementations for pathfinding. Right click inside the C++ Classes folder of the content browser, check the tickbox to Show All Classes and create a child class of RecastNavMesh.

img5_NewRecastNavMesh

For our RecastNavMesh header file we will want to define a constructor and our own FindPath function. This function will need arguments of FNavAgentProperties and an FPathFindingQuery, and it should return an FPathFindingResult.


UCLASS()
class NAVMESHOVERRIDE_API ARecastNavMeshTilePathFinder : public ARecastNavMesh
{
    GENERATED_BODY()
    ARecastNavMeshTilePathFinder(const FObjectInitializer& ObjectInitializer);
    static FPathFindingResult FindPath(const FNavAgentProperties& AgentProperties, const FPathFindingQuery& Query);
};

Moving onto the .cpp file, let’s handle the constructor first. All that’s really happening here is setting FindPathImplementation.


ARecastNavMeshTilePathFinder::ARecastNavMeshTilePathFinder(const FObjectInitializer& ObjectInitializer)
	:ARecastNavMesh(ObjectInitializer)
{
	FindPathImplementation = FindPath;
	
}

For the FindPath function, since we’re overriding the default find path behavior we’ll go ahead and copy the FindPath definition of RecastNavMesh. Doing this we’re going to immediately notice some errors.


FPathFindingResult ARecastNavMeshTilePathFinder::FindPath(const FNavAgentProperties& AgentProperties, const FPathFindingQuery& Query)
{
	SCOPE_CYCLE_COUNTER(STAT_Navigation_RecastPathfinding);

	const ANavigationData* Self = Query.NavData.Get();
	check(Cast(Self));

	const ARecastNavMesh* RecastNavMesh = (const ARecastNavMesh*)Self;
	if (Self == NULL || RecastNavMesh->RecastNavMeshImpl == NULL)
	{
		return ENavigationQueryResult::Error;
	}

	FPathFindingResult Result(ENavigationQueryResult::Error);

	FNavigationPath* NavPath = Query.PathInstanceToFill.Get();
	FNavMeshPath* NavMeshPath = NavPath ? NavPath->CastPath() : nullptr;

	if (NavMeshPath)
	{
		Result.Path = Query.PathInstanceToFill;
		NavMeshPath->ResetForRepath();
	}
	else
	{
		Result.Path = Self->CreatePathInstance(Query);
		NavPath = Result.Path.Get();
		NavMeshPath = NavPath ? NavPath->CastPath() : nullptr;
	}

	const FNavigationQueryFilter* NavFilter = Query.QueryFilter.Get();
	if (NavMeshPath && NavFilter)
	{
		NavMeshPath->ApplyFlags(Query.NavDataFlags);

		const FVector AdjustedEndLocation = NavFilter->GetAdjustedEndLocation(Query.EndLocation);
		if ((Query.StartLocation - AdjustedEndLocation).IsNearlyZero() == true)
		{
			Result.Path->GetPathPoints().Reset();
			Result.Path->GetPathPoints().Add(FNavPathPoint(AdjustedEndLocation));
			Result.Result = ENavigationQueryResult::Success;
		}
		else
		{
			Result.Result = RecastNavMesh->RecastNavMeshImpl->FindPath(Query.StartLocation, AdjustedEndLocation, *NavMeshPath, *NavFilter, Query.Owner.Get());

			const bool bPartialPath = Result.IsPartial();
			if (bPartialPath)
			{
				Result.Result = Query.bAllowPartialPaths ? ENavigationQueryResult::Success : ENavigationQueryResult::Fail;
			}
		}
	}

	return Result;
}

  1. First of all we’ll find an undefined error in the SCOPE_CYCLE_COUNTER line. This macro is used for performance profiling. We’ll need to put
    DECLARE_CYCLE_STAT(TEXT("Custom Pathfinding"), STAT_Navigation_CustomPathfinding, STATGROUP_Navigation)
    in our header and change the macro line to
    SCOPE_CYCLE_COUNTER(STAT_Navigation_CustomPathfinding);
    so that we can inspect the performance of our pathfinding implementation in the visual logger.
  2. Next we’ll find that RecastNavMeshImpl is undefined. Looking at the metadata reveals that “This is a pimpl-style arrangement used to tightly hide the Recast internals from the rest of the engine.” In any case we don’t need this nullptr check so we’ll remove it from the if statement.
  3. Finally at the bottom we’ll find another error with RecastNavMeshImpl being undefined, but in this case it is being used to find the path. Here is where we can override the default behavior of RecastNavMesh and implement our own pathfinding logic, so we can remove this line in its entirety.

Now the code should be looking like this:


DECLARE_CYCLE_STAT(TEXT("Custom Pathfinding"), STAT_Navigation_CustomPathfinding, STATGROUP_Navigation)

FPathFindingResult ARecastNavMeshTilePathFinder::FindPath(const FNavAgentProperties& AgentProperties, const FPathFindingQuery& Query)
{
	SCOPE_CYCLE_COUNTER(STAT_Navigation_CustomPathfinding);

	const ANavigationData* Self = Query.NavData.Get();
	check(Cast(Self));

	const ARecastNavMesh* RecastNavMesh = (const ARecastNavMesh*)Self;
	if (Self == NULL)
	{
		return ENavigationQueryResult::Error;
	}

	FPathFindingResult Result(ENavigationQueryResult::Error);

	FNavigationPath* NavPath = Query.PathInstanceToFill.Get();
	FNavMeshPath* NavMeshPath = NavPath ? NavPath->CastPath() : nullptr;

	if (NavMeshPath)
	{
		Result.Path = Query.PathInstanceToFill;
		NavMeshPath->ResetForRepath();
	}
	else
	{
		Result.Path = Self->CreatePathInstance(Query);
		NavPath = Result.Path.Get();
		NavMeshPath = NavPath ? NavPath->CastPath() : nullptr;
	}

	const FNavigationQueryFilter* NavFilter = Query.QueryFilter.Get();
	if (NavMeshPath && NavFilter)
	{
		NavMeshPath->ApplyFlags(Query.NavDataFlags);

		const FVector AdjustedEndLocation = NavFilter->GetAdjustedEndLocation(Query.EndLocation);
		if ((Query.StartLocation - AdjustedEndLocation).IsNearlyZero() == true)
		{
			Result.Path->GetPathPoints().Reset();
			Result.Path->GetPathPoints().Add(FNavPathPoint(AdjustedEndLocation));
			Result.Result = ENavigationQueryResult::Success;
		}
		else
		{
			//Our Implementation Here!
			const bool bPartialPath = Result.IsPartial();
			if (bPartialPath)
			{
				Result.Result = Query.bAllowPartialPaths ? ENavigationQueryResult::Success : ENavigationQueryResult::Fail;
			}
		}
	}

	return Result;
}

Implementing A* Algorithm

For implementing our custom pathfinding logic, we’ll be using a tile based A* search. If you’re curious how this form of pathfinding works, this web page explains it succinctly: Introduction to A* Pathfinding.

Thankfully we can steal borrow a lovely optimized algorithm from the internet. I’ve chosen this A* path search from activestate.com: A* Shortest Path Algorithm (Many thanks FB36).


const int n=60; // horizontal size of the map
const int m=60; // vertical size size of the map
static int map[n][m];
static int closed_nodes_map[n][m]; // map of closed (tried-out) nodes
static int open_nodes_map[n][m]; // map of open (not-yet-tried) nodes
static int dir_map[n][m]; // map of directions
const int dir=8; // number of possible directions to go at any position
// if dir==4
//static int dx[dir]={1, 0, -1, 0};
//static int dy[dir]={0, 1, 0, -1};
// if dir==8
static int dx[dir]={1, 1, 0, -1, -1, -1, 0, 1};
static int dy[dir]={0, 1, 1, 1, 0, -1, -1, -1};

class node
{
    // current position
    int xPos;
    int yPos;
    // total distance already travelled to reach the node
    int level;
    // priority=level+remaining distance estimate
    int priority;  // smaller: higher priority

    public:
        node(int xp, int yp, int d, int p)
            {xPos=xp; yPos=yp; level=d; priority=p;}

        int getxPos() const {return xPos;}
        int getyPos() const {return yPos;}
        int getLevel() const {return level;}
        int getPriority() const {return priority;}

        void updatePriority(const int & xDest, const int & yDest)
        {
             priority=level+estimate(xDest, yDest)*10; //A*
        }

        // give better priority to going strait instead of diagonally
        void nextLevel(const int & i) // i: direction
        {
             level+=(dir==8?(i%2==0?10:14):10);
        }

        // Estimation function for the remaining distance to the goal.
        const int & estimate(const int & xDest, const int & yDest) const
        {
            static int xd, yd, d;
            xd=xDest-xPos;
            yd=yDest-yPos;         

            // Euclidian Distance
            d=static_cast(sqrt(xd*xd+yd*yd));

            // Manhattan distance
            //d=abs(xd)+abs(yd);

            // Chebyshev distance
            //d=max(abs(xd), abs(yd));

            return(d);
        }
};

// Determine priority (in the priority queue)
bool operator b.getPriority();
}

// A-star algorithm.
// The route returned is a string of direction digits.
string pathFind( const int & xStart, const int & yStart,
                 const int & xFinish, const int & yFinish )
{
    static priority_queue pq[2]; // list of open (not-yet-tried) nodes
    static int pqi; // pq index
    static node* n0;
    static node* m0;
    static int i, j, x, y, xdx, ydy;
    static char c;
    pqi=0;

    // reset the node maps
    for(y=0;ygetPriority(); // mark it on the open nodes map

    // A* search
    while(!pq[pqi].empty())
    {
        // get the current node w/ the highest priority
        // from the list of open nodes
        n0=new node( pq[pqi].top().getxPos(), pq[pqi].top().getyPos(),
                     pq[pqi].top().getLevel(), pq[pqi].top().getPriority());

        x=n0->getxPos(); y=n0->getyPos();

        pq[pqi].pop(); // remove the node from the open list
        open_nodes_map[x][y]=0;
        // mark it on the closed nodes map
        closed_nodes_map[x][y]=1;

        // quit searching when the goal state is reached
        //if((*n0).estimate(xFinish, yFinish) == 0)
        if(x==xFinish && y==yFinish)
        {
            // generate the path from finish to start
            // by following the directions
            string path="";
            while(!(x==xStart && y==yStart))
            {
                j=dir_map[x][y];
                c='0'+(j+dir/2)%dir;
                path=c+path;
                x+=dx[j];
                y+=dy[j];
            }

            // garbage collection
            delete n0;
            // empty the leftover nodes
            while(!pq[pqi].empty()) pq[pqi].pop();
            return path;
        }

        // generate moves (child nodes) in all possible directions
        for(i=0;igetLevel(),
                             n0->getPriority());
                m0->nextLevel(i);
                m0->updatePriority(xFinish, yFinish);

                // if it is not in the open list then add into that
                if(open_nodes_map[xdx][ydy]==0)
                {
                    open_nodes_map[xdx][ydy]=m0->getPriority();
                    pq[pqi].push(*m0);
                    // mark its parent node direction
                    dir_map[xdx][ydy]=(i+dir/2)%dir;
                }
                else if(open_nodes_map[xdx][ydy]>m0->getPriority())
                {
                    // update the priority info
                    open_nodes_map[xdx][ydy]=m0->getPriority();
                    // update the parent direction info
                    dir_map[xdx][ydy]=(i+dir/2)%dir;

                    // replace the node
                    // by emptying one pq to the other one
                    // except the node to be replaced will be ignored
                    // and the new node will be pushed in instead
                    while(!(pq[pqi].top().getxPos()==xdx &&
                           pq[pqi].top().getyPos()==ydy))
                    {
                        pq[1-pqi].push(pq[pqi].top());
                        pq[pqi].pop();
                    }
                    pq[pqi].pop(); // remove the wanted node

                    // empty the larger size pq to the smaller one
                    if(pq[pqi].size()>pq[1-pqi].size()) pqi=1-pqi;
                    while(!pq[pqi].empty())
                    {
                        pq[1-pqi].push(pq[pqi].top());
                        pq[pqi].pop();
                    }
                    pqi=1-pqi;
                    pq[pqi].push(*m0); // add the better node instead
                }
                else delete m0; // garbage collection
            }
        }
        delete n0; // garbage collection
    }
    return ""; // no route found
}

First of all we’ll move some predefined stuff to the header of our RecastNavMesh:


const static int n = 32; // horizontal size of the map
const static int m = 32; // vertical size size of the map
const static int dir = 4;
const static int dx[dir] = { 1, 0, -1, 0 };
const static int dy[dir] = { 0, 1, 0, -1 };

UCLASS()
class NAVMESHOVERRIDE_API ARecastNavMeshTilePathFinder : public ARecastNavMesh
{
	...

};

Note here I’ve set dir=4 as this pathfinder will only be using cardinal directions. This pathfinder also supports 8 directional movement but if you’re doing that make sure to use the right defintions for dx and dy.
Next we’ll throw in the class definition for Node in the .cpp:


...
class node
{
	// current position
	int xPos;
	int yPos;
	// total distance already traveled to reach the node
	int level;
	// priority=level+remaining distance estimate
	int priority;  // smaller: higher priority

public:
	node(int xp, int yp, int d, int p)
	{
		xPos = xp; yPos = yp; level = d; priority = p;
	}

	int getxPos() const { return xPos; }
	int getyPos() const { return yPos; }
	int getLevel() const { return level; }
	int getPriority() const { return priority; }

	void updatePriority(const int & xDest, const int & yDest)
	{
		priority = level + estimate(xDest, yDest) * 10; //A*
	}

	// give better priority to going strait instead of diagonally
	void nextLevel(const int & i) // i: direction
	{
		level += (dir == 8 ? (i % 2 == 0 ? 10 : 14) : 10);
	}

	// Estimation function for the remaining distance to the goal.
	const int & estimate(const int & xDest, const int & yDest) const
	{
		static int xd, yd, d;
		xd = xDest - xPos;
		yd = yDest - yPos;

		// Euclidean Distance
		//d = static_cast(sqrt(xd*xd + yd * yd));

		// Manhattan distance
		d = abs(xd) + abs(yd);

		// Chebyshev distance
		//d=max(abs(xd), abs(yd));

		return(d);
	}
};

ARecastNavMeshTilePathFinder::ARecastNavMeshTilePathFinder(const FObjectInitializer& ObjectInitializer)
	:ARecastNavMesh(ObjectInitializer)
{
        ...

Adapting this code is going to be a little tricky because it uses std::priority_queue which isn’t available in UE4 C++11. Thankfully we can replicate the behavior of std::priority_queue by using heap sorted TArrays: Analogue-of-priority-queue (Answerhub to the rescue, thank you Steve Robb).

To sort the TArray by priority we’ll want to define a predicate that compares the priority of one element vs. another. Since the elements of this TArray are going to be instances of the node class we’ll be creating a predicate that compares the priority of node a versus node b. This goes below the Node class definition:


...
class node
{
	...

};

// Determine priority (in the priority queue)
struct nodePredicate
{
	bool operator()(const node & a, const node & b) const
	{
		return a.getPriority() < b.getPriority();
	}
};

ARecastNavMeshTilePathFinder::ARecastNavMeshTilePathFinder(const FObjectInitializer& ObjectInitializer)
	:ARecastNavMesh(ObjectInitializer)
{
        ...

Now we can move to the line we deleted earlier where FindPath looks to RecastNavMeshImpl to get an FPathFindingResult. Here we can dump the entire A-star algorithm which is going to generate a ton of errors.


FPathFindingResult ARecastNavMeshTilePathFinder::FindPath(const FNavAgentProperties& AgentProperties, const FPathFindingQuery& Query)
{
	SCOPE_CYCLE_COUNTER(STAT_Navigation_CustomPathfinding);

	const ANavigationData* Self = Query.NavData.Get();
	check(Cast(Self));

	const ARecastNavMesh* RecastNavMesh = (const ARecastNavMesh*)Self;
	if (Self == NULL)
	{
		return ENavigationQueryResult::Error;
	}

	FPathFindingResult Result(ENavigationQueryResult::Error);

	FNavigationPath* NavPath = Query.PathInstanceToFill.Get();
	FNavMeshPath* NavMeshPath = NavPath ? NavPath->CastPath() : nullptr;

	if (NavMeshPath)
	{
		Result.Path = Query.PathInstanceToFill;
		NavMeshPath->ResetForRepath();
	}
	else
	{
		Result.Path = Self->CreatePathInstance(Query);
		NavPath = Result.Path.Get();
		NavMeshPath = NavPath ? NavPath->CastPath() : nullptr;
	}

	const FNavigationQueryFilter* NavFilter = Query.QueryFilter.Get();
	if (NavMeshPath && NavFilter)
	{
		NavMeshPath->ApplyFlags(Query.NavDataFlags);

		const FVector AdjustedEndLocation = NavFilter->GetAdjustedEndLocation(Query.EndLocation);
		if ((Query.StartLocation - AdjustedEndLocation).IsNearlyZero() == true)
		{
			Result.Path->GetPathPoints().Reset();
			Result.Path->GetPathPoints().Add(FNavPathPoint(AdjustedEndLocation));
			Result.Result = ENavigationQueryResult::Success;
		}
		else
		{
			// A-star algorithm.
			// The route returned is a string of direction digits.
			string pathFind( const int & xStart, const int & yStart,
                 const int & xFinish, const int & yFinish )
			{
				static priority_queue pq[2]; // list of open (not-yet-tried) nodes
				static int pqi; // pq index
				static node* n0;
				static node* m0;
				static int i, j, x, y, xdx, ydy;
				static char c;
				pqi=0;

				// reset the node maps
				for(y=0;ygetPriority(); // mark it on the open nodes map

					// A* search
					while(!pq[pqi].empty())
					{
						// get the current node w/ the highest priority
						// from the list of open nodes
						n0=new node( pq[pqi].top().getxPos(), pq[pqi].top().getyPos(),
							pq[pqi].top().getLevel(), pq[pqi].top().getPriority());

						x=n0->getxPos(); y=n0->getyPos();

						pq[pqi].pop(); // remove the node from the open list
						open_nodes_map[x][y]=0;
						// mark it on the closed nodes map
						closed_nodes_map[x][y]=1;

						// quit searching when the goal state is reached
						//if((*n0).estimate(xFinish, yFinish) == 0)
						if(x==xFinish && y==yFinish)
						{
							// generate the path from finish to start
							// by following the directions
							string path="";
							while(!(x==xStart && y==yStart))
							{
								j=dir_map[x][y];
								c='0'+(j+dir/2)%dir;
								path=c+path;
								x+=dx[j];
								y+=dy[j];
							}

							// garbage collection
							delete n0;
							// empty the leftover nodes
							while(!pq[pqi].empty()) pq[pqi].pop();
							return path;
						}

						// generate moves (child nodes) in all possible directions
						for(i=0;igetLevel(),
									n0->getPriority());
								m0->nextLevel(i);
								m0->updatePriority(xFinish, yFinish);

								// if it is not in the open list then add into that
								if(open_nodes_map[xdx][ydy]==0)
								{
									open_nodes_map[xdx][ydy]=m0->getPriority();
									pq[pqi].push(*m0);
									// mark its parent node direction
									dir_map[xdx][ydy]=(i+dir/2)%dir;
								}
								else if(open_nodes_map[xdx][ydy]>m0->getPriority())
								{
									// update the priority info
									open_nodes_map[xdx][ydy]=m0->getPriority();
									// update the parent direction info
									dir_map[xdx][ydy]=(i+dir/2)%dir;

									// replace the node
									// by emptying one pq to the other one
									// except the node to be replaced will be ignored
									// and the new node will be pushed in instead
									while(!(pq[pqi].top().getxPos()==xdx &&
										pq[pqi].top().getyPos()==ydy))
									{
										pq[1-pqi].push(pq[pqi].top());
										pq[pqi].pop();
									}
									pq[pqi].pop(); // remove the wanted node

									// empty the larger size pq to the smaller one
									if(pq[pqi].size()>pq[1-pqi].size()) pqi=1-pqi;
									while(!pq[pqi].empty())
									{
										pq[1-pqi].push(pq[pqi].top());
										pq[pqi].pop();
									}
									pqi=1-pqi;
									pq[pqi].push(*m0); // add the better node instead
								}
								else delete m0; // garbage collection
							}
						}
						delete n0; // garbage collection
					}
					return ""; // no route found
				}

			const bool bPartialPath = Result.IsPartial();
			if (bPartialPath)
			{
				Result.Result = Query.bAllowPartialPaths ? ENavigationQueryResult::Success : ENavigationQueryResult::Fail;
			}
		}
	}

	return Result;
}

Minor Changes

We will fix it from top to bottom, starting by removing the brackets and arguments for pathFind (since this is already wrapped in a function). We will also be replacing the line

static priority_queue pq[2];

with

TArray pq[2];

With this done we need to define the starting node n0. Notice earlier I set the variables n and m in the header to be equal to 32. These numbers define the width and height of the tile search space. We can do relative tile searching by always starting at the tile 16×16.

n0 = new node(16, 16, 0, 0);

Method Names With TArray

We’ve probably also noticed that the methods
.size, .pop(), .top(), .empty(), and .push(node)
are undefined for TArray so we need to replace these with
.Num(), .HeapPopDiscard(nodePredicate(), true), .HeapTop(), .Num()==0 and .HeapPush(node, nodePredicate()).

All that remains is getting the values for xFinish and yFinish, and fiddling with the code so that it returns a properly formatted FPathFindingResult instead of a string.

Resolving xFinish And YFinish

Since we’re starting at the relative position tile of 16×16, we can resolve the final tile location by subtracting the start world location gridsnapped to 200 (as every tile is 2m apart) from the end world location gridsnapped to 200 and getting the tile offset of that, then adding 16×16.

FVector EndTile = (Query.EndLocation.GridSnap(200) - Query.StartLocation.GridSnap(200)) / 200 + FVector(16.f, 16.f, 0.f);

Then just replace the references to xFinish and yFinish with EndTile.X and EndTile.Y respectively.

Formatting The Result

To get the result formatted correctly we’ll modify the code that builds a string describing the path to instead add path locations to the Result member. First we’ll create an FVector PathLocation that expresses the coordinates of a point in tile space as world space coordinates. The first location is always the end location so we’ll write it as

FVector PathLocation = Query.EndLocation.GridSnap(200); 

From there, since every tile is 2m apart we can just add 200 to PathLocation for every tile move the pathfinder makes and add that new PathLocation to the result. This code is self explanatory:


// quit searching when the goal state is reached
				if (x == EndTile.X && y == EndTile.Y)
				{
					Result.Path->GetPathPoints().Add(FNavPathPoint(PathLocation));
					// generate the path from finish to start
					// by following the directions
					while (!(x == 16 && y == 16))
					{
						j = dir_map[x][y];
						switch (j) {
						case 0:
							PathLocation += FVector(200, 0, 0);
							break;
						case 1:
							PathLocation += FVector(0, 200, 0);
							break;
						case 2:
							PathLocation += FVector(-200, 0, 0);
							break;
						case 3:
							PathLocation += FVector(0, -200, 0);
							break;
						}
						Result.Path->GetPathPoints().Add(FNavPathPoint(PathLocation));
						x += dx[j];
						y += dy[j];
					}

					// garbage collection
					delete n0;
					// empty the leftover nodes
					while (!(pq[pqi].Num() == 0)) pq[pqi].HeapPopDiscard(nodePredicate(), true);
					Algo::Reverse(Result.Path->GetPathPoints());
					Result.Path->MarkReady();
					Result.Result = ENavigationQueryResult::Success;
					return Result;
				}

I highlighted an important step in this code which is reversing the path result. Since A* builds the path from the end to the beginning we need to reverse the result so that it’s in the right order.

Our Naive A* Pathfinder

This pathfinding function still needs some work but we should now be able to assign it to a nav agent and get some things moving.


// Fill out your copyright notice in the Description page of Project Settings.

#include "RecastNavMeshTilePathFinder.h"

DECLARE_CYCLE_STAT(TEXT("Custom Pathfinding"), STAT_Navigation_CustomPathfinding, STATGROUP_Navigation)

class node
{
	// current position
	int xPos;
	int yPos;
	// total distance already traveled to reach the node
	int level;
	// priority=level+remaining distance estimate
	int priority;  // smaller: higher priority

public:
	node(int xp, int yp, int d, int p)
	{
		xPos = xp; yPos = yp; level = d; priority = p;
	}

	int getxPos() const { return xPos; }
	int getyPos() const { return yPos; }
	int getLevel() const { return level; }
	int getPriority() const { return priority; }

	void updatePriority(const int &amp; xDest, const int &amp; yDest)
	{
		priority = level + estimate(xDest, yDest) * 10; //A*
	}

	// give better priority to going strait instead of diagonally
	void nextLevel(const int &amp; i) // i: direction
	{
		level += (dir == 8 ? (i % 2 == 0 ? 10 : 14) : 10);
	}

	// Estimation function for the remaining distance to the goal.
	const int &amp; estimate(const int &amp; xDest, const int &amp; yDest) const
	{
		static int xd, yd, d;
		xd = xDest - xPos;
		yd = yDest - yPos;

		// Euclidean Distance
		//d = static_cast(sqrt(xd*xd + yd * yd));

		// Manhattan distance
		d = abs(xd) + abs(yd);

		// Chebyshev distance
		//d=max(abs(xd), abs(yd));

		return(d);
	}
};

// Determine priority (in the priority queue)
struct nodePredicate
{
	bool operator()(const node &amp; a, const node &amp; b) const
	{
		return a.getPriority() <b>CastPath() : nullptr;

	if (NavMeshPath)
	{
		Result.Path = Query.PathInstanceToFill;
		NavMeshPath-&gt;ResetForRepath();
	}
	else
	{
		Result.Path = Self-&gt;CreatePathInstance(Query);
		NavPath = Result.Path.Get();
		NavMeshPath = NavPath ? NavPath-&gt;CastPath() : nullptr;
	}

	const FNavigationQueryFilter* NavFilter = Query.QueryFilter.Get();
	if (NavMeshPath &amp;&amp; NavFilter)
	{
		NavMeshPath-&gt;ApplyFlags(Query.NavDataFlags);

		const FVector AdjustedEndLocation = NavFilter-&gt;GetAdjustedEndLocation(Query.EndLocation);
		if ((Query.StartLocation - AdjustedEndLocation).IsNearlyZero() == true)
		{
			Result.Path-&gt;GetPathPoints().Reset();
			Result.Path-&gt;GetPathPoints().Add(FNavPathPoint(AdjustedEndLocation));
			Result.Result = ENavigationQueryResult::Success;
		}
		else
		{
			static int map[n][m];
			static int closed_nodes_map[n][m]; // map of closed (tried-out) nodes
			static int open_nodes_map[n][m]; // map of open (not-yet-tried) nodes
			static int dir_map[n][m]; // map of directions

									  // A-star algorithm.
			FVector PathLocation = Query.EndLocation.GridSnap(200);
			FVector EndTile = (Query.EndLocation.GridSnap(200) - Query.StartLocation.GridSnap(200)) / 200 + FVector(16.f, 16.f, 0.f);

			TArray pq[2]; // list of open (not-yet-tried) nodes
			static int pqi; // pq index
			static node* n0;
			static node* m0;
			static int i, j, x, y, xdx, ydy;
			static char c;
			pqi = 0;

			// reset the node maps
			for (y = 0; y getPriority(); // mark it on the open nodes map

			// A* search
			while (!(pq[pqi].Num() == 0))
			{
				// get the current node w/ the highest priority
				// from the list of open nodes
				n0 = new node(pq[pqi].HeapTop().getxPos(), pq[pqi].HeapTop().getyPos(),
					pq[pqi].HeapTop().getLevel(), pq[pqi].HeapTop().getPriority());

				x = n0-&gt;getxPos(); y = n0-&gt;getyPos();

				pq[pqi].HeapPopDiscard(nodePredicate(), true); // remove the node from the open list
				open_nodes_map[x][y] = 0;
				// mark it on the closed nodes map
				closed_nodes_map[x][y] = 1;

				// quit searching when the goal state is reached
				if (x == EndTile.X &amp;&amp; y == EndTile.Y)
				{
					Result.Path-&gt;GetPathPoints().Add(FNavPathPoint(PathLocation));
					// generate the path from finish to start
					// by following the directions
					while (!(x == 16 &amp;&amp; y == 16))
					{
						j = dir_map[x][y];
						switch (j) {
						case 0:
							PathLocation += FVector(200, 0, 0);
							break;
						case 1:
							PathLocation += FVector(0, 200, 0);
							break;
						case 2:
							PathLocation += FVector(-200, 0, 0);
							break;
						case 3:
							PathLocation += FVector(0, -200, 0);
							break;
						}
						Result.Path-&gt;GetPathPoints().Add(FNavPathPoint(PathLocation));
						x += dx[j];
						y += dy[j];
					}

					// garbage collection
					delete n0;
					// empty the leftover nodes
					while (!(pq[pqi].Num() == 0)) pq[pqi].HeapPopDiscard(nodePredicate(), true);
					Algo::Reverse(Result.Path-&gt;GetPathPoints());
					Result.Path-&gt;MarkReady();
					Result.Result = ENavigationQueryResult::Success;
					return Result;
				}


				FVector TileStartLocation = FVector(Query.StartLocation.X, Query.StartLocation.Y, 0.f).GridSnap(200.f) + FVector(0.f, 0.f, Query.StartLocation.Z) + FVector(n0-&gt;getxPos()-16, n0-&gt;getyPos()-16, 0) * 200;
				// generate moves (child nodes) in all possible directions
				for (i = 0; i getLevel(),
							n0-&gt;getPriority());
						m0-&gt;nextLevel(i);
						m0-&gt;updatePriority(EndTile.X, EndTile.Y);

						// if it is not in the open list then add into that
						if (open_nodes_map[xdx][ydy] == 0)
						{
							open_nodes_map[xdx][ydy] = m0-&gt;getPriority();
							pq[pqi].HeapPush(*m0, nodePredicate());
							// mark its parent node direction
							dir_map[xdx][ydy] = (i + dir / 2) % dir;
						}
						else if (open_nodes_map[xdx][ydy] &gt; m0-&gt;getPriority())
						{
							// update the priority info
							open_nodes_map[xdx][ydy] = m0-&gt;getPriority();
							// update the parent direction info
							dir_map[xdx][ydy] = (i + dir / 2) % dir;

							// replace the node
							// by emptying one pq to the other one
							// except the node to be replaced will be ignored
							// and the new node will be pushed in instead
							while (!(pq[pqi].HeapTop().getxPos() == xdx &amp;&amp;
								pq[pqi].HeapTop().getyPos() == ydy))
							{
								pq[1 - pqi].HeapPush(pq[pqi].HeapTop(), nodePredicate());
								pq[pqi].HeapPopDiscard(nodePredicate(), true);
							}
							pq[pqi].HeapPopDiscard(nodePredicate(), true); // remove the wanted node

																		   // empty the larger size pq to the smaller one
							if (pq[pqi].Num() &gt; pq[1 - pqi].Num()) pqi = 1 - pqi;
							while (!(pq[pqi].Num() == 0))
							{
								pq[1 - pqi].HeapPush(pq[pqi].HeapTop(), nodePredicate());
								pq[pqi].HeapPopDiscard(nodePredicate(), true);
							}
							pqi = 1 - pqi;
							pq[pqi].HeapPush(*m0, nodePredicate()); // add the better node instead
						}
						else delete m0; // garbage collection
					}
				}
				delete n0; // garbage collection
			}
			return Result; // no route found
		}

		const bool bPartialPath = Result.IsPartial();
		if (bPartialPath)
		{
			Result.Result = Query.bAllowPartialPaths ? ENavigationQueryResult::Success : ENavigationQueryResult::Fail;
		}
	}

	return Result;
}




Hooking Our RecastNavMesh Into The Engine

Making our character use our new RecastNavMesh class is pretty straightforward. From crussel’s tutorial:
“To plug your new pathfinder into the engine, you need to edit Config/DefaultEngine.ini. Find the section called:
[/Script/Engine.NavigationSystem]
And add the line:
RequiredNavigationDataClassNames=/Script/ProjectName.NavigationClass

From here we can add a new Navigation Agent by going to our Project Settings and going to the Navigation System settings in the Engine Category. Here we click the + by Supported Agents and set the Navigation Data Class of the new Agent to use our extended RecastNavmesh.

Agents

Finally make sure to delete the old navmesh in the World Outliner and regenerate paths under Build settings. If done correctly you should now be moving! There’s still work to be done with this pathfinder however.

Navigation Path Validation

In regards to my definition of the current A* Pathfinder as naive, it needs to be addressed that it does not validate whether the tiles it is pathing to are navigable. If you tested the pathfinder after doing the setup in the last segment you will have probably noticed the character getting stuck against the blocks.
There’s a handful of ways to go about verifying path points depending on the game. A game without complex geometry can likely get by through merely checking whether there is navmesh under each path point.


...
				// generate moves (child nodes) in all possible directions
				for (i = 0; i GetModifiedQueryExtent(Query.NavData->GetDefaultQueryExtent());
					FNavLocation OutLocation;
					bool InBounds = Query.NavData->ProjectPoint(TileLocation, OutLocation, Extent, Query.QueryFilter, Query.Owner.Get());

					if (!(xdxn - 1 || ydym - 1 || map[xdx][ydy] == 1
						|| closed_nodes_map[xdx][ydy] == 1 || InBounds))
						...

I’ve included a code snippet of this solution, however, it will not work for this tutorial due to the way the Recast system builds the navmesh.

RecastQuirk

In the image above I show that due to the way space partitioning is handled by the Recast navmeshing system, navmesh islands can generate inside geometry that would otherwise normally block anything from existing inside. This poses an issue for merely testing whether navmesh lies underneath a tile as it may exist in unreachable space.

Instead we can utilize the NavMeshRaycast function of ARecastNavMesh to determine whether adjacent tiles are reachable.


...
// generate moves (child nodes) in all possible directions
				for (i = 0; i NavMeshRaycast(Query.NavData.Get(), TileStartLocation, TileLocation, HitLocation, Query.QueryFilter, Query.Owner.Get());
					
					if (!(xdxn - 1 || ydym - 1 || map[xdx][ydy] == 1
						|| closed_nodes_map[xdx][ydy] == 1 ||Reachable))
					...

There’s probably faster ways to do this check by leveraging dtNavMeshQuery methods, so expect to see a sequel to this article aimed at optimization! Particularly it would improve performance to check if the desired end and start location are reachable, and implement handling for partial paths.
In any case, implementing this NavMeshRaycast check will ensure that our character doesn’t try to path through solid objects.

Debugging, Profiling, More To Come!

This article has taken significantly longer to write than I first anticipated, so this section is just a stub to be revisited in a following article.
For debugging purposes there’s a variety of approaches so I’ll be listing some without any particular order.

Gameplay Debugger

If your character isn’t moving on the navmesh as expecting (idling when it shouldn’t be, failing to take a path which it should) you can use the Gameplay Debugger to view its AI state and other info. While using Play In Editor (PIE), you can use the default bound key ” to toggle the Gameplay Debugger.

GameplayDebugger

The Gameplay Debugger isn’t particularly useful for this example as the navigation implementation doesn’t use an AIController to issue movement commands to the Character but instead the NavigationSystem itself. This is a workaround to needing two controllers to issue navigation commands to a Character (as a PlayerController cannot use NavigateTo methods). Because of this the Gameplay Debugger can’t show the AI state as there isn’t an AIController.

Debugging Inside MyRecastNavMesh

In our RecastNavMesh class we can access the NavData member of our Query and use the method Query.NavData->DrawDebugPath to have the engine draw boxes and links to all of the nav locations.

We can also directly use DrawDebugBox to highlight areas that our Pathfinder checks to get an idea of how it branches.


bool Reachable = Cast(Query.NavData.Get())->NavMeshRaycast(Query.NavData.Get(), TileStartLocation, TileLocation, HitLocation, Query.QueryFilter, Query.Owner.Get());
					if (Reachable)
					{
						DrawDebugBox(Query.NavData->GetWorld(), TileLocation, FVector(50.f,50.f, 250.f), FColor::Red, false, 0.5f);
					}
					else
					{
						DrawDebugBox(Query.NavData->GetWorld(), TileLocation, FVector(50.f, 50.f, 250.f) / 2.f, FColor::Green, false, 0.5f);
					}

Visual Logger

We can access the Visual Logger under the Windows->Developer Tools tabs in the main viewport.

VisualLogger

With the Visual Logger we can simply hit the start button and it will record info on various gameplay events, one of which is the navigation system. Looking to the Visual Log can help inform why Navigation Queries are failing.

VisualLogger2

Profiling

The Profiling viewport is nested under the Window->Developer Tools->Session Frontend tabs in the main viewport. In the Session Frontend viewport we can find the Profiling tab.

Profiler

The Profiling system in UE4 provides verbose information on thread times and function calls, and serves as an excellent tool for optimizing games in the late stages of development. While running our game we can hit the Data Preview and Live Preview buttons to watch the Profiling info in real time. Under the Navigation category we can find our Custom Pathfinding Cycle Counter defined earlier in the tutorial.

Profiler2

Closing Remarks

I hope this article has proven useful in getting to know more about the navigation system of Unreal Engine! Once again, If you want to inspect the example project directly, you can pull the source from my github page . If you have any questions or find any issues with the article, please comment below or email me directly:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s