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.

Frost Giants tech demo showing ~1k agents pathing through a maze, with physics & fog of war

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.

The new maze map for path & movement testing

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.

From ‘Pathing it’s not a solved Problem’ Starcraft 2 showing vertices expanded by unit radius to create inner waypoints.

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.

From Efficient Triangulation-Based Pathfinding by Douglas Jon Demyen, 2006

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.

Graphic 1 illustrating how the expanded vertex offsets are calculated. Watch the video to see the steps in order.

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.

Three different sized agents taking different routes to the same goal

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.

600 agents of different sizes pathing through the maze

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:

References

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

12 Comments

  1. This is an excellent blog post, thanks so much for sharing your knowledge!
    I’m curious, how much time did you spend on research and implementing your “RTS Pathfinding” series so far? I’d guess like 200 hours.

    1. Thanks! I’ve spent far more time on this than I originally intended. Some RTS games have solved most of these problems (maybe SC2), others might get around pathfinding by simplifying the game/map. I’m definitely guilty of going down a tech rabbit hole with this stuff, but it’s fun.

  2. Hello,
    Nice article! I’m curious, how do you detect/resolve collisions between units and terrain?

    1. Hi Artem, I’m just using a physics engine. Units and terrain have 2d rigidbodies so that units can’t walk through things.

  3. notice at step 3
    “Normalise both neighbour edges and then average them to get what I’ve labelled as the ‘Average neighbour edge’ in graphic 1″
    and then get ” perpendicular of the average neighbour edge ” (it’s be bisector of neighbour edge I think)and scale it by unit width to get true apex .
    the bisector vector here aren’t always the unit vector .I think you mean normalized vector rather than average, is it?
    After read the original paper you refernced with I think the funnel algorithm you used should be simplified version from what that paper descripted. I suppose this version should be good enough for game Ai.
    by the way excellent work here. Great work

    1. Hi Wang, thanks for the comment. Yes you’re right I should have said normalized rather than average. I’ll update the article.

  4. Excellent post, quick question, lets say you have a long triangle and it has left, mid and right vertex. u want to go from near the left end to the right end. But the agent radius is blocked by the middle vertex, but if you do an Astar from a neighboring node, u can infact arrive at the right end. How do u deal with this case?

    1. That’s a good question. I can’t remember trying that or encountering it as a problem whilst making the prototype RTS game in practice. However, I assume the agent would think it can reach the location due to the node being reachable like you say, and get stuck!

      1. Thnx for the reply. Got another question.

        The tunnels with expanded vertices sometimes end up intersecting with each other because the ANE sort of change their directions. That sometimes ends up with weird paths after running in the Modifed funnel algorithm (Since tunnels intersecting messes up with left and right Funnel border crossing over each other step). How did u solve that edge case?

        1. I don’t recall coming across that edge case so I’m not sure if I’ve solved it. If you have a video/image showing this you can message me @jdtec01 on Twitter and I might be able to comment further.
          It might be that the discrete range of agent radius & tunnel widths I tested with just didn’t show up this problem.

Comments are closed.