Neatly replacing NavMesh with A* in UE4

[ Update: Builtin A* Pathfinding in Unreal Engine 4.25 ]

I’ve been working on a tile-based game recently, and I wanted to use A* for pathfinding (NavMesh is overkill, and not a great fit). I could’ve just written an A* pathfinder and custom AI code that uses it, but I wondered if there might be a better way – ideally I’d like to just replace NavMesh with my pathfinder, and have the standard AIController/PathFollowingComponent code work with it seamlessly.

I came across MieszkoZ’ answer to this question, which got me started – turns out not only is it possible, it’s pretty simple (with a couple of caveats!)

A New Pathfinding Class

NavMesh is contained in a class called ARecastNavMesh, a subclass of ANavigationData. In theory all you need to do is create your own subclass and plug it into the engine. It’s worth looking at the source for ARecastNavMesh to see how it does things – the key function is FindPath:

static FPathFindingResult FindPath(const FNavAgentProperties& AgentProperties, const FPathFindingQuery& Query);

What’s a little odd is that FindPath isn’t virtual, it’s static. Comments in ANavigationData and ARecastNavMesh explain it’s for performance reasons: Epic are concerned that if a lot of agents call the pathfinder in the same frame the vtable lookups will be too slow, so instead the function is declared static and stored in a function pointer, ANavigationData::FindPathImplementation.

Another effect of FindPath being static is that it has no this pointer. Thankfully there is a weak pointer to this in Query.NavData, so you can Get() that and use it instead.

FindPath is expected to return an FPathFindingResult struct, which contains a success/failure enum and an FNavigationPath. FindPath‘s Query parameter may contain an FNavigationPath for you to use (if Query.PathInstanceToFill is valid) or you’ll have to create a new one using ANavigationData::CreatePathInstance.

All of which is much easier to say in code! So here’s a template FindPath based on ARecastNavMesh::FindPath [updated for 4.12]:

FPathFindingResult AAStarNavigationData::FindPath(const FNavAgentProperties& AgentProperties, const FPathFindingQuery& Query)
{
	const ANavigationData* Self = Query.NavData.Get();
	AAStarNavigationData* AStar = const_cast<AAStarNavigationData*>(dynamic_cast(Self));
	check(AStar != nullptr);

	if (AStar == nullptr)
	{
		return ENavigationQueryResult::Error;
	}

	FPathFindingResult Result(ENavigationQueryResult::Error);
	Result.Path = Query.PathInstanceToFill.IsValid() ? Query.PathInstanceToFill : Self->CreatePathInstance(Query);

	FNavigationPath* NavPath = Result.Path.Get();

	if (NavPath != nullptr)
	{
		if ((Query.StartLocation - Query.EndLocation).IsNearlyZero())
		{
			Result.Path->GetPathPoints().Reset();
			Result.Path->GetPathPoints().Add(FNavPathPoint(Query.EndLocation));
			Result.Result = ENavigationQueryResult::Success;
		}
		else if(Query.QueryFilter.IsValid())
		{
			// **** run your pathfinding algorithm from Query.StartLocation to Query.EndLocation here
			// add each point on the path with:
			// NavPath->GetPathPoints().Add(FNavPathPoint(WORLD_POSITION));
			// NOTE: the path must contain at least 2 non-start path points

			// if your algorithm can only find a partial path call NavPath->SetIsPartial(true),
			// but remember to check if partial paths are acceptable to the caller (Query.bAllowPartialPaths)
			// - if they aren't you should return ENavigationQueryResult::Fail

			NavPath->MarkReady();
			Result.Result = ENavigationQueryResult::Success;
		}
	}

	return Result;
}

Connect your pathfinding algorithm, assign FindPath to FindPathImplementation in the constructor, and you’re done!

Plugging In

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

In your map, create a NavMeshBounds as normal, and an instance of your pathfinder will be automatically added (instead of ARecastNavMesh-Default).

Now any AIController::MoveToLocation calls will automatically use your new pathfinder.

Other Changes for Tile-Based Games

There are three things about the default behaviour of an AI controller that don’t feel right to me in a tile-based game:

1. Characters accelerate and brake as they run around, so they overshoot corners and bump into things
2. Characters turn immediately in the direction of movement
3. Characters get ‘close enough’ to their destination, and stop

So I also do the following:

1. In the CharacterMovement component, set Requested Move Use Acceleration to false (or just lower the character’s max walk speed)
2. In CharacterMovement, set Orient Rotation to Movement to true and Rotation Rate (Yaw) to 1440
3. In calls to MoveToLocation, set the Acceptance Radius to 0 and Stop on Overlap to false

Which gives me characters neatly running around a tile-based world, not bumping into things, and stopping exactly where I want them. Marv!