Unity NavMesh uses Recast navigation under-the-hood which is a very good general solution for navigation. However, for the particular needs of the type of lockstep multiplayer RTS I’m interested in, I ran into a couple of issues.
Firstly, dynamic updates of the Unity NavMesh are slow. Unitys default NavMesh was taking ~30-50ms to add a single box obstacle into a ~50 vert mesh. This is after fiddling with the tiling & various settings, a few experiments & posting on the forum for help. Recast constructs a ‘voxel mould’ which makes it very adaptable to different shapes and meshes. I imagine it probably scales quite well in the worst case with more complex meshes, but that is not really a problem that needed solving for a low-poly RTS navmesh.
Secondly, AFAIK it’s not cross-platform deterministic. This would be required for a lockstep multiplayer RTS where all clients need to rebuild the navmesh locally.
Why not use a grid? Well, I could. But it’s slow in comparison to a navmesh for path searches, and a bit cumbersome with its low resolution model of the world. Although it’s worth mentioning that for beginners a grid is far easier to code & makes dynamic updates straight-forward and quick.
Edges of a Terrain chasm
The terrain can be shaped to influence the pathing, so I needed a solution that could generate a navmesh on terrain, much like Unitys built-in solution. This needn’t be especially fast as the terrain isn’t going to change shape whilst the game is been played. I carved out a deep chasm in the map editor as a test sample for the navmesh generation.
First, I detected an outline of the chasm by scanning the heightmap for changes in height from cell to cell over a certain threshold.
The most obvious potential problem here is that the heightmap outline has quite a few points and consists of several severe square corners. I don’t need this many points and ideally I would have far less so that the navmesh is simpler when building & using for navigation. The outline should be as simple as possible without being ‘wrong’, in so much as giving a jarring or unexpected experience to the player when a unit paths around it.
I saw a very quick and easy way to immediately get rid of some points, which was to replace corners consisting of 2 edges of 1 cell length with a single horizontal edge.
The next thing would help navigation by giving units a bit of extra room around the terrain chasm was a polygon line expansion. I started by offsetting all polygon line segments by their perpendicular vector * the expansion radius, and then calculating the ray intersection points of neighbour lines (4).
This left some special cases where lines went inwards of the polygon outline as can be seen in (4). To solve this I check all line segments for intersections against each other. If two lines intersect, then the vertices between the 2 lines are removed and replaced with the intersection point, the result of this step is displayed in (5). The vertex count was now 52.
Following corner removal & the outline expansion I applied a Douglas Peucker line simplification to further reduce the vertex count to 30. The Delaunay triangulation now had less processing to do and yet the outline of the chasm looked pretty reasonable. The expansion distance from the original height cells outline is 2 units giving it a fairly wide birth of the drop on most edges.
Why Dynamic?
One of the other main reasons for embarking on a custom navmesh was to have a faster solution for dynamic updates at runtime. I had seen that StarCraft2 achieved this by building a ‘base’ navmesh with all the static obstacles features in the level, and then each time a new dynamic obstacle is added to the navmesh they would rebuild the entire mesh by resetting to the base navmesh and inserting all dynamic obstacles. At least that’s my understanding of what they did based on listening to James Anhalt’s GDC talk AI-Navigation Its Not a solved problem.
There seemed room for improvement here. If my interpretation is correct SC2 was re-calculating several duplicate parts of the navmesh each time they add/remove a dynamic obstacle, when only a small subset need be updated. My plan was therefore to limit my navmesh updates to this smaller triangle subset around the obstacle that is been added/removed. After finally getting dynamic updates of the navmesh subsets working; I can definitely see why SC2 team accepted the presumably slightly slower but simpler solution of rebuilding the navmesh completely from an intermediate base state. Updating a subset of the navmesh dynamically, including the ability to remove as well as add obstacles is quite a hard problem to solve robustly and is fraught with edge cases and math precision issues (using a Q48.16 fixed point number type certainly didn’t help here, either). I easily spent more time on just the dynamic subset updating than I did getting a single navmesh to generate across the map. I’ll elaborate more on that later.
Delaunay Triangulation
The first goal was to get a constrained delaunay triangulation building across the entire map. I won’t go into details here as there is lots of easily searchable information available already, eg. here’s a great introduction to constrained delaunay triangulation in C# by Eric Nordeus, alternatively, here is another implementation by QThund.
Sometimes there were overlapping obstacles in the map. When this happened I would first process them using boolean operations to get the union of the polygons. I won’t talk further about this either as there is information available elsewhere including open source implementations such as Clipper lib.
Inserting obstacles
My idea was to find the triangles in the existing mesh that intersect with an obstacle to be inserted, and then generate a delaunay triangulation for this subset of triangles with the addition of the new obstacle. Next, the outline of the subset would be carved out of the base mesh & the updated subset merged into the base mesh.
Removing obstacles
To remove an obstacle I would find all the triangles with centre points that intersected the obstacle, create a set of all the vertices in these triangles, and then additionally get all triangles that use any of these vertices. This extended triangle set defined the subset of the mesh that would need to be regenerated when the obstacle was removed.
Edge cases & additional complexities
The basic ideas described above worked quite well but there were additional complexities I encountered, such as ensuring that other obstacles that overlapped the extended triangle set continued to have their edge constraints respected in the new mesh generation.
After getting obstacle insertion on a subset of the navmesh working, I was slightly disheartened to see a less than ideal triangulation that included long & very thin strips. Thankfully I realised this was only because the delaunay triangulation hadn’t been run across the mesh as a whole. Running the edge flipping algorithm across the entire mesh isn’t too expensive if ~98% of the edges are already in the correct state so after obstacle insertion/removal I would run the delaunay algorithm across the entire mesh once more to help keep the mesh triangulation in a better state.
After getting dynamic delaunay working I expanded the testing include a dynamic spinning obstacle rect. To simulate a dynamic obstacle I would insert the obstacle at a different transformation each frame (and destroy the previous frames version of the obstacle), eg. frame1: {add rect1}, frame2: {add rect2, remove rect1}. The rect would be rotated slightly each iteration and positioned at the latest cursor location, but otherwise the same size. This turned out to be a good basic test as it showed up lots of edge cases and bugs.
Dynamic updating of the navmesh is a challenging engineering task. There were a lot of edge-cases, many math precision issues and compromises to overcome. It required a lot of careful step by step debugging using verbose visualisation to stay on top of what was happening. This in turn made it one of the most rewarding projects to work on once it was finally working in a robust manner.
Marking Obstacles
Having got a pretty robust fixed-point dynamic navmesh working I was happy to move onto the easier task; using the data in a practical way for pathfinding. To begin with, I needed to flag triangles that were underneath obstacles. This is done with a simple intersection test between the triangle centre & an obstacle polygon in updated subsets of the navmesh.
Triangle Spatial Partition
Before a path can be found we need to know which triangles the start and end positions of the path are in. There could be thousands of triangles across the map, and we don’t want to do an intersection test for everyone of them, so a cell based spatial partition map is used to keep this reasonably cheap to query. Each corner of a triangles AABB bounds are added to a multi-map. For large triangles, where the corners don’t include all the grid cells that the triangle area covers, the bounds of the triangle are iterated over by the grid cell width. I imagine there are better spatial partitioning solutions than this for triangles, but it was still an order of magnitude performance increase, easy to write-up and can always be looked into later if required.
Triangle A* Search
With the start and end triangles found, the triangle navmesh data could now be leveraged to get neighbours and write a basic heuristic for an A* algorithm (I used triangle centre distance for now). The A* search & triangle spatial partition were blessedely easy & quick to code up compared to the dynamic constrained delaunay code. The result of this stage gave me a nice path of triangles from the start position to the goal.
Simple Stupid Funnel Algorithm
The above image shows a path of 14 nodes (triangles) to navigate around two obstacles across a direct 55m distance. This is a decent gain compared to a grid which would require possibly ~55 nodes or more (and that is just the path, not to mention the exponential increase in size of the A* open list), assuming each cell is 1 square metre. Also, as previously mentioned, the other benefit with triangles is that they allow for far more precision relative to the obstacle outlines, compared to a grid.
However, you can’t path based on triangles alone. A path of positions is required for units to be able to follow. This is where the simple stupid funnel algorithm, a type of ‘string pulling’ algorithm, comes in. A list of portal edges is collected by finding the shared edge between each adjacent triangle in the list and then SSF algorithm is used to find the corners in the path.
Variable agent size
One of the nice properties of using constrained triangle edges for the portals is that the maximum agent size that can pass through is known by the length of the edge portal. I added an extra parameter to the A* search so that it would ignore edges with shorter lengths than the agent diameter.
The edges on path were now always long enough for an agent to pass through, however, the path positions can’t be right on the boundary of an obstacle, this would only work for zero size agents. To fix this I narrowed the portal edges by the radius of the agent on both ends so that the path corners were adjusted to be away from obstacles.
It should be noted I’m not sure this will work perfectly on all corners of the navmesh. I can already see a corner when the agent has a radius of 4 where it’s not quite far enough away from an obstacle between path nodes. My hope is that by allowing a little extra buffer on the radius size that this isn’t really an issue in practice.
MapLocation & RayCast
It’s often very useful to be able to get the nearest location available on a navmesh One use-case I had for this was when moving a group of units to a destination, their individual goal positions may vary slightly to within a ‘soft’ / group radius of the final path waypoint – I need to make sure these spread positions aren’t inside an obstacle. The MapLocation function does this by looking up triangles intersecting a circle of specified radius around the target position. It uses the spatial grid to test against only nearby circles. If the target position is inside an obstacle it will map to the nearest valid (not intersecting an obstacle) navmesh location.
Navmesh raycast can be useful for a few things too, including LOS (line of sight) queries. Agents periodically do LOS checks with waypoints further along the path to see if they can skip positions. In addition if an agent has LOS with a destination from the start then a path query may be avoided altogether.
Soft & hard waypoint radius
For groups of agents moving together along the same path it was useful to introduce the concept of a ‘soft’ radius. The soft radius is the maximum radius around a waypoint that may be compressed down to a hard radius depending on obstacles around a waypoint. The hard radius is the minimum radius that must exist along a waypoint on a path request. The hard radius limits the edges that can be traversed in a path request and is set to the largest units radius. The soft radius is set depending on the group size and can be useful to stop a large number of smaller units all competing for the exact same waypoint position.
The soft radius extents are set based on the portal edge length. This method is working fairly well for now. Previously I was setting the soft radius extents after the SSFD string pulling and raycasting either way into navmesh obstacles to determine the extents, however, I found this to be far more error prone, particularly in a maze like structure, compared to using the path portal edges.
Closing Notes
There’s quite a bit of work in the form of maths & problem solving that goes into making a custom navmesh. However, it’s very useful (and probably necessary for some types of games) to be able to have full control of the inner workings when compared to a black-box solution. There is still probably lots of low hanging optimisation that could be done but even in the Unity editor with non-bursted C#, the navmesh updates ~50-100* than Unitys built-in solution for a single obstacle insertion. It’s worth saying again that this doesn’t mean the constrained delaunay navmesh is better in all situations, just that it’s a more well-suited tool for this particular task.
Drop any comments or questions to me on:
- Twitter: https://twitter.com/jdtec01
- E-mail: jon.dickison@gmail.com