RTS Pathfinding 3: Variable agent size, smoke tests & Navmesh fixes

It seemed the two previous articles weren’t enough to get this topic covered, and they’ll probably be more to talk about in the future. I was planning to move onto more general RTS gameplay tasks next, such as attacking. But after running my old group pathing in maze test I saw that things weren’t working so well anymore. Bugs had crept in. Later on I realised that variable agent sized pathing wasn’t really fit for purpose using the edge lengths to determine max unit size that can move along a path (described in RTS pathfinding 2).

First of all, smoke tests that are easy & quick to run were needed so that it’s quick to check if things have broken. I was inspired by seeing Frost Giants pathing tech demo and wanted to try and achieve something similar. Secondly, I needed a robust solution for supporting variable sized units on the navmesh. Unity/Detour achieves this by creating multiple navmeshes for each unit size, but that doesn’t really scale well when there’s lots of different sizes & the navmesh needs to change semi-regularly.

Maze Test Map

I built a more challenging pathfinding environment with multiple routes for differently sized agents. I added narrow shortcut routes that smaller units could take advantage of & the new editor to place prefab rock obstacles to create the maze. A clearing in the centre on a raised cliff area was added to serve as a pathing goal for units to cluster around. This was all quite straightforward until I came to build the navmesh and noticed a new error. An obstacle triangle had extended across open ground and an edge was missing in the navmesh. Getting a bug in the CDT (constrained delaunay triangulation) is not a new thing, but they are becoming less & less frequent as I expose it to more tests & new maps. It’s generally fairly robust these days.

Navmesh precision bug

Debugging the navmesh at the specific area revealed that a vertex was merged in error due to a loss of precision. There were two rocks, each with a vertex very very close to each other. This was causing issues for the limited fixedpoint precision. I’d had an idea earlier about helping to alleviate or maybe even solve some of these precision issues by snapping input navmesh vertices to a grid. This would ensure a minimum distance between the vertices, which I hoped would cut-down precision issues. It seemed to work. I experimented with the grid scale and 0.1 of a in-game unit/metre seemed to work very well and didn’t give any noticeable precision loss to the human eye.

Low hanging fruit optimisation

Before proceeding with higher volume tests I needed to remove some simple performance problems first. I disabled mesh animation for now, the current prototype animation is using CPU skinning & is not especially performant. In the future I would aim to implement a bespoke GPU skinning solution that is suitable for animating thousands of characters. Drawing all the units as simple cylinders for clarity of monitoring pathing and movement would be better for now.
I checked my draw calls and moved some things around to enable better batching. I created a second copy of the navmesh data which was better prepared for use by other systems (only contained the relevant external data and had some post-processing on it that the other systems required). I used staggered updates with some systems such as unit raycasts & enemy scanning.

Navmesh paths for variable sized agents

In RTS Pathfinding 2, I mentioned about using triangle edge lengths along a path to determine the max radius. I knew at the time it wasn’t completely reliable but it kind of worked at the time. I must have had a very limited test suite back then because it’s now obvious to me that it won’t work in quite a few situations. I went back to researching how others had achieved variable agent sizes on a single navmesh. In the GDC presentation: Pathing it’s not a solved problem, James Anhalt demonstrated how Starcraft2 created paths along a tunnel inside the expanded vertices. I could see that this was what I needed, but the video was light on implementation details.

There were two parts to solve:

1) The A* search needed to know the width of tunnels in the navmesh in order to know if an agent is small enough to fit through the gaps

2) The actual path points needed to be offset inside the tunnel appropriately so that the agent can centre itself over waypoints.

Triangle Widths

Eventually I found ‘Efficient Triangulation-Based Pathfinding’ [1], which contains a method for calculating what they refer to as the ‘triangle width’. The triangle width is the maximum width of the corridor passing between two edges on a triangle face in the navmesh. Each triangle face three possible triangle widths, one for each pair of edges.
I will not go into the details of calculating the triangle width as the authors did a great job in their paper. The relevants parts are 3.1 Width calculation & Algorithm 3, which shows a psuedo code implementation.

Once you have the triangle width you can use it in an A* search to know the maximum corridor size between adjacent nodes and thus; if an agent of a given size can pass through. That was part 1 solved.

Expanded vertices

1) Create two lists of vertices, one containing the left vertices & the other with the right vertices through the tunnel. Do not allow duplicates in the vertex lists. Create another list at the same time containing vertex indices for each edge. A vertex index may be used by multiple (greater than 2) edges. The start position for both left & right lists should be added at the start and have a zero length edge added comprised of these vertex indices.

2) Now that we have two lists of consecutive vertices we can calculate the ‘vertex neighbour edges’ for each vertex. These are shown for the highlighted vertex in the graphic 1.

3) Normalise both neighbour edges and then average them to get what I’ve labelled as the ‘Average neighbour edge’ in graphic 1.

4) The perpendicular of the average neighbour edge set to the length of the radius for the unit gives the expanded vertex position for the path.

5) Build a new portal edge list from the expanded vertex list

6) Run funnel algorithm on the new edge list to get the final path!

If the above instructions aren’t clear, I’d suggest looking at the paper itself, which talks about this more, or simply looking at graphic 1 above, and working out for yourself rather than rigidly follow the above text steps (there’s probably more than one way to do it).

Testing

To facilitate faster & easier testing I implemented support for my own basic script system. In this case, a script is basically just a text file with specific commands in that the app can read in and run. A start-up script may be defined the the app config file or loaded using the console.

A snippet from the test_move script that automatically deploys, selects and moves units:

map: test_move
sim_time_acceleration: 1
random_unit_deployment_count: 500

#
# maze pathing marines lower/mid-left to upper/mid-right
#
deploy_request: step 4, prefab sm_marine, position 66.5 0.5 144.5, player_id 1, count 28
select: player_id 1, step 16, origin 66.0 144.0, radius 25
move_selected: step 20, position 430 0 340

As I make changes and add new features going forward, I can quickly run these test scripts to check that everything appears correct. Ideally I’d add some success criteria too, but for now it’s a lot better than nothing for continuous integration testing. The game simulation can now be run with time acceleration applied which means tests can be blasted through quickly. The time acceleration steps the sim multiple times rather than changing the time delta, so the simulation checksum result at the end should be identical.

For now I’ve added a stress/smoke test with about 600 units of varying individual and group size around the maze map. The test_move script handles creating these units, selecting them all and requesting they all path to the map centre.

After all that there were a few more performance and physics issues to fix. I also adjusted some boid behaviours slightly so that larger units would be less likely to avoid smaller units. I’m sure they’ll be small pathing/movement adjustments and features that come up in the future. There are lots of ways the performance could be increased further too. But for now, the pathing and movement is working quite nicely as a proof of concept.

Drop any comments or questions to me on:

• Twitter: https://twitter.com/jdtec01
• E-mail: jon.dickison@gmail.com

References

[1] Efficient Triangulation-Based Pathfinding, Douglas Jon Demyen, 2006