Previously, on Battlestar Galactica

This initial post lays the groundwork introducing Detour, Unreal, the problem space and an initial solution, start there if you’re new to making your own navmeshes in Unreal. It’s followed by a post showing how to make navmeshes from grids. We then moved on to converting a triangulation to a navmesh to reduce the number of polys needed.

Sample project available here as always.

This was going to be the post where I tied everything together and solved all the problems within UE4’s Detour wrapper, but unfortunately Detour fundamentally has no solution to the A star problems I’ve mentioned, and when given meshes that approximate an actual in game map instead of a toy, both the Recast generated navmesh and my own navmesh give poor enough results that I don’t consider Detour to be suitable for strategy games where the optimal solution is a requirement. On the bright side, having done all the work to understand Detour and the problem space, it was fairly easy to get a different solution in place, even if in the long run it’s likely going to need more maintenance.

Wrapping up the Detour experiments

At the end of the previous post I mentioned a couple of things that I hoped could improve Detour’s ability to find optimal paths, so before moving on let’s tackle those.

One big tile to avoid all the problems

The first idea was that by removing the tile seams, the number of polys is reduced and the number of strangely shaped polys is also reduced since everything is coming straight from the delaunay triangulation. The problem with this is that the verts are converted into a fixed interval coordinate system as mentioned way back in the first post of this series. unsigned short limits total size to 32768 * CellSize so increasing max tile sizes decreases accuracy since we’d have to increase CellSize to compensate. To get this up to 2km, we’d need the cell size increased to about 6 so our accuracy will drop by a factor of 6. This might be OK for some use cases since 1.0 is accurate to the centimetre which is likely overkill in a lot of cases.

Fortunately we don’t need any code to do this, just reduce the TileCount to 1 and increase the CellSize.

Adding heights

The second thought is that having height information might help Detour in assessing whether one triangle is closer than another to the goal. There’s a few different cases that need to be solved here:

• Points that lie on triangulation edges and intersect with the tile boundary can use the two points in the triangulation to determine the height of the new point
• Corner points that are inside a triangle need to use a barycentric calculation to determine their position.
• Everything else is a point already in the triangulation, and therefore already has a height

What surprised me after adding heights to the mesh was that the path provided was actually 2D and didn’t include the height changes along the path at all. The string pulling process within Detour that is responsible for taking the path corridor (a list of edges that are crossed) and making an optimal line along that corridor doesn’t include the intermediate points, so the height information is effectively lost. It’s possible to get this information back by storing the corridor along with the path, but it requires writing your own FindPathToLocationSynchronously or equivalent.

Our goal here is to set the flag bWantsPathCorridor so that the UNavigationPath returned by FindPath has all the edges that are crossed, and we can combine that with the path segments to project back onto the triangulation and get the heights. Fortunately there’s an enum that will handle setting that flag for us. There’s also one to skip string pulling ( ERecastPathFlags::SkipStringPulling), which would be useful if we wanted to just get the corridor from detour and then find the surface path and do string pulling all in one go, which would be a bit more efficient.

FPathFindingResult AManualDetourNavMesh::FindCorridorPathToLocation(FVector Start, FVector Goal, FPathFindingQuery& Query) const
{
	Query.NavDataFlags = ERecastPathFlags::GenerateCorridor;
	return FindPath(Query.NavAgentProperties, Query);
}

Once we have the corridor it’s a matter of walking along the corridor and seeing where the path segments intersect the corridor segments:

bool AManualDetourNavMesh::PathCorridorToSurfacePath(UPARAM(ref) const TArray<struct FNavPathPoint>& Path, UPARAM(ref) const TArray<FNavigationPortalEdge>& Corridor,UPARAM(ref)  TArray<FVector>& SurfacePath)
{
	int32 CurrentPathIdx = 0;
	int32 NextPathIdx = 1;
	int32 CurrentEdgeIdx = 0;

	if (Path.Num() == 0 || Corridor.Num() == 0)
	{
		return false;
	}

	SurfacePath.Reset(Path.Num() + Corridor.Num());
	SurfacePath.Add(Path[0].Location);

	while (Path.IsValidIndex(NextPathIdx))
	{
		// If there are still corridor edges to check, try that
		if (Corridor.IsValidIndex(CurrentEdgeIdx))
		{
			// If current to next intersects current edge, add intersection point
			FVector IntersectionPoint;
			if (FMath::SegmentIntersection2D(Corridor[CurrentEdgeIdx].Left, Corridor[CurrentEdgeIdx].Right, Path[CurrentPathIdx].Location, Path[NextPathIdx].Location, IntersectionPoint))
			{
				SurfacePath.Add(IntersectionPoint);
				CurrentEdgeIdx++;
			}
			// otherwise add the next point and move forward
			else {
				SurfacePath.Add(Path[NextPathIdx].Location);
				CurrentPathIdx++;
				NextPathIdx++;
			}
		}
		// If we've checked everything in the corridor, just add next point and move forward
		else {
			SurfacePath.Add(Path[NextPathIdx].Location);
			CurrentPathIdx++;
			NextPathIdx++;
		}
	}

	return (SurfacePath.Num() == Path.Num() + Corridor.Num());
}

Which gives us a nice surface path like this:

A better test harness

To go onto a slight tangent, I wanted to improve the test harness to look a bit more like a real map, so instead of being an open field it has a set of pseudorandom obstacles.

The process for this is

• Divide the map into chunks
• put an obstacle in each chunk
• put a height change in a largeish radius around each obstacle

Final? Results

Unfortunately even with heights added and no tiling, Detour is just not using a reliable heuristic in its A star implementation.

Ultimately there is a tradeoff between having an accurate heuristic, which would progressively build a string pulled path, and a low cost heuristic, which does a best effort guess on which neighbouring triangle is closer to the goal. Many months ago I played around with an algorithm that focuses on having an accurate heuristic called Triangulated Polygon A-star (TPAStar), so I ported that across to Unreal to see how it fared.

Pretty good, but let’s see what tradeoffs we have to make to get that result.

TPAStar

There’s an implementation at https://github.com/grgomrton/tpastar in C# which comes with a handy little test harness.

When I initially ported this across to Unreal and tried it on my triangulation, the pathfinder was failing to complete and stuck in an infinite loop. I realised this is because the algorithm cannot handle interior vertices within its triangulation, and sure enough adding triangles to the C# program to creat interior vertices had the same effect there, so it wasn’t that I’d messed up the port. In addition, the implementation is 2D. I could potentially change this but with the restriction of having no interior vertices, there’s not much point having heights anyway.

Implementation

I modified the algorithm slightly to account for the interior vertex problem by only searching neighbours that are set to pathable, but this still leaves interior vertices where there’s traversable height changes. Lacking a better idea I created a second navmesh without any height information and without any of the height changes, so that TPAStar could work on its own navmesh without interior vertices. It might be tempting to think that with this restriction, Detour would also give optimal results, but the last example I showed of detour has no interior vertices and it still got the path wrong:

While removing the neighbours that aren’t pathable might seem attractive to save space, the neighbours will be needed later.

Surface projection

After getting the path from TPAStar using the 2D Triangulation, we can use the regular one with height information to do a similar surface projection procedure to what we did with Detour. We find the start and end triangle using barycentric point in triangle tests, then walk along the path adding points as we intersect segments, and moving to the next triangle as we move across each edge.

While it might seem like this is the entire solution, unfortunately it’s very common that there is no edge from one triangle in the path to the next triangle. This may sound impossible, but in fact every time an obstacle is traversed the path will go exactly to one of the points on the triangulation, and from there could go to any triangle connected to that point, not just neighbours of the current triangle.

The solution to this is to walk around the point when this situation is detected, and this is where the impassable triangles might be needed. Delaunator stores triangle connections as half edges, so the way to walk around a point is to take an edge that point into it and do this:

	int32 Incoming = StartEdge;
	do {
		int32 Tri = Triangulation.TriangleOfEdge(Incoming);
		
		// Move to the next triangle around this point
		int32 Outgoing = Triangulation.NextHalfedge(Incoming);
		Incoming = Triangulation.HalfEdges[Outgoing];
	} while (Incoming != -1 && Incoming != StartEdge);

Results

The following two screenshots show the difference between the two algorithms, with Manual Detour and Recast Detour both giving good but not quite straight paths, and TPAStar giving a perfect result. Recast is not going over the sloped section and is instead treating it as an obstacle, but this isn’t actually the relevant bit to look at - the path isn’t straight in the middle so even if the mesh settings were changed a bit it’s clear that it’s not going to find optimal paths reliably.

In a real test within Maladius, the 2D and 3D navmeshes look like this:

With a few thousand triangles in each navmesh. Pathfinding results seem good!

Path test 1 took 0.001 seconds and Path test 2 took just under 0.003 seconds.

Further Work

The performance can probably be improved quite a bit by pre-allocating space for the double linked lists that TPAStar uses heavily. This would also help with the other obvious improvement which would be moving navigation requests to a worker thread and having a queue to avoid stalling the game thread during times of high load.

I think for now I’m going to take a break from pathfinding and do something else. I hope this series of posts is helpful to anyone looking to tinker with Unreal’s Navigation systems.