RTS devlog #9: Extreme pathfinding

It's been a few weeks since the last devlog. However I've spent a fair bit of time working on pathfinding and path following - and improving Construct along the way! This is a complex part of the project and will take multiple blog posts, so here I'm going to focus on just pathfinding. It gets tricky when you start looking for paths for hundreds of units!

Here's the problem. I've thrown in some rocks to act as obstacles.

Some rocks acting as obstacles for movement.

Now suppose you have a unit one side of a rock and you tell it to move to the other side of the rock - or a long way away with lots of various obstacles along the path. How do you find a route for it?

The answer is to use a pathfinding algorithm. Construct's existing Pathfinding behavior has an extremely well-optimised implementation of the A* pathfinding algorithm (helped by the extraordinary performance of JavaScript). Not only that, but Construct's implementation is also already multithreaded. For example if you have a 4-core CPU, then it can distribute pathfinding work across all 4 cores and calculate multiple paths in parallel for even more absurd levels of performance - which we'll need if we want to find paths for 1000 units at once. So it's already a good fit for this project.

Even more multithreading

Collisions require synchronous (i.e. instant) responses so for this project the GameServer thread didn't have any easy way to access Construct's built-in collision engine and had to resort to a separate implementation. However Construct's pathfinding calculations are already asynchronous (i.e. running for a period of time in the background) and they already get dispatched to other web workers to run them on other threads. This means we can use Construct's pathfinding from GameServer. It just means connecting up GameServer to the host's Construct runtime and getting it to perform pathfinding calculations for it. So now our diagram of threads on the host looks like this.

Threading model with four pathfinding workers.

This is a slight simplification, but it helps illustrate what is going on. There's 7 threads there (each represented by an orange box), which will definitely make full use of everyone's multi-core CPUs! This will also help ensure we can scale the game up to ridiculous levels and keep everything running well.

There are two small downsides to this approach. First of all is the host player is also responsible for all the pathfinding calculations in the game, as they also host GameServer. This could take up a lot of CPU time. However these pathfinding jobs are all run in separate workers, so it shouldn't jank their local gameplay. The second is this does now tie in GameServer to the Construct runtime, which limits the scope to host a GameServer on a dedicated server with something like node.js. Ah well - everything is a trade-off, and this way we get to re-use (and improve!) the existing features in Construct.

Basic pathfinding implementation

In GameServer, serverPathfinding.js has a small class that handles pathfinding from the view of the server. This mainly just forwards calls to the host's GameClient so it can perform the work. There's a new async messaging system so a message can be sent and then read back the response conveniently with await. Moving units now uses pathfinding to find a route to the intended destination, returning a list of waypoints (aka path nodes) to move along. On the client pathfindingController.js handles actually finding paths with Construct's Pathfinding behavior.

Construct's pathfinding implementation is based on a grid. Each cell can be marked an obstacle, causing paths to navigate around it, or have a cost added to it, causing paths to avoid it if it's worth saving the cost.

I can't emphasise enough how helpful it is during development to visualize the paths that are found. Debugging a list of node co-ordinates doesn't really tell you anything useful. So the client also creates a few objects to illustrate where paths are found, and uses a tilemap to mark obstacle cells in red, as extra debugging tools. This means I can now clearly see what is happening. Here is a unit that has found a path around a rock. You can clearly see what the pathfinding algorithm has done, placing some points to navigate around the cells marked as obstacles.

Pathfinding a route for a unit around a rock.

The unit can now move to each waypoint in turn. That has its own complications though, so I'm saving all that for another blog post!

It's also worth pointing out the cell size has quite a significant impact both on performance and the kinds of paths that are found. I've also added a cell border to extend the obstacle area slightly beyond the edges of the rock, ensuring paths are kept away from the very edges of the obstacle, since that could cause units to overlap the obstacle as they move along the path. These are things that may need fine-tuning later, but I think I picked reasonable values for now.

Fine-tuning paths

I quite quickly found that paths often had lots of fairly sharp turns. The paths can use diagonals, but this often results in lots of nodes with lots of 45° or 90° turns. An example of such a path is shown below.

Lots of diagonal turns along the edge of an obstacle.

This becomes a problem for unit movement, as it means lots of steering, and may cause units to slow down as they brake to make all these turns in quick succession. Ideally the path would be a smoother sweep along the edge of the path. How can this be achieved?

It turns out the solution was there all along. Construct has long allowed for direct movement to the destination if the entire box around the start and end positions is completely clear of obstacles, since in that case it's safe to just move directly to the destination. However this direct movement approach can be extended to anywhere along the path. If any set of 3 or more nodes is entirely clear of obstacles in their surrounding box, then the middle nodes can just be skipped and allow the path to go directly across the box area. This turns out to be a surprisingly effective solution! Take a look at the image below. This shows the same path, but with dotted green boxes around the nodes that have a completely clear box around them. These can then be skipped, and the light green line shows the simplified route.

Skipping nodes where the box around a group of nodes is completely clear.

The eagle-eyed viewer may also notice that the green lines across the lower two boxes are in a perfectly straight line. This allows a further simplification of the path, as the middle node becomes redundant. So this approach has reduced the number of nodes from 7 to 3, and look at the resulting path: it's a nice gentle sweep around the edge of the obstacle with only small turning adjustments necessary. This works much better when units come to drive along the path.

Spreading out paths

Now a nice smooth path can be calculated for each unit to its destination. This brings up the next problem: bottlenecks. Suppose you move a large group of units past an obstacle. The pathfinding algorithm will tend to send a lot of them the same way, such as directly along the edge of an obstacle. The image below demonstrates this.

A potential bottleneck as many units try to go the same way.

You can see dozens of units are all planning to move through exactly the same section of path around the left side of the rock. I haven't yet got round to actually stopping units driving through each other, but when I do, this will clearly be a problem. It will likely cause a long traffic jam as units filter through one by one. That's not a sensible thing to happen when the player may urgently need to move units as battles happen around the map. There needs to be some way to spread out paths to avoid lots of units trying to go exactly the same way. How to do that?

Adding cell costs

A good way to go seems to be making use of cell costs. As mentioned earlier, cells that are not obstacles can have a cost added to them, which essentially discourages finding a path through those cells unless it is a significant short-cut. If a cost is added to all the cells along a path, then the next path should tend to avoid going exactly the same way. The image below shows the cells along a unit's path in green, and those cells would have a small extra cost associated with them.

Adding a path cost to the cells along a found path (highlighted green).

At first I considered adding a cost all the way along the path, and leaving the cost in place until the unit arrived at its destination. However I realised this would probably have unwanted effects. A group of units could take a minute or two to arrive at their destination, but that would leave a large cost around the start of their route for some time even when they're near the end. That could end up with weird results like units steering around empty spaces just because there used to be some units there and they're still moving.

I also thought about someone commanding units to move to the same place one by one. This spreads all their movements out over time. That seems unlikely to be a problem, as even if all the units are given the same path, units will likely move along them at different times and so avoid bumping in to each other.

This made me realise: the only problem is simultaneously moving a whole group of units. In other words, if I select 100 units and tell them to move somewhere, it should try to spread out those 100 paths - and then that's it. There shouldn't be any impact to any paths found after that. This actually makes the implementation simpler too, as the effect is transient to a group of paths found at the same time.

Spreading path groups

So when you move 100 units, it should bundle those 100 paths it finds in to a "path group", and try to spread them out. A good way to implement this is to create a temporary new grid of cells, accumulate all the costs in them as the paths are found, and then at the end discard that grid. That means the paths in the group will be spread out but there will be no permanent change to the pathfinding map afterwards.

After experimenting with this I found paths were still found very close together, and so it was useful to spread out the cost to cover additional adjacent cells. With a "spread" of 3 (meaning each cell adds cost to a 3x3 area around it) the area with a cost added to it looks like this.

Enlarging the area of the path that adds a cost, using the cell spread.

That discourages finding a path immediately adjacent to that one, which helps spread out the next path further. Now, limiting this to running on one worker (more on that shortly...) it works out nicely! Unit paths tend to get spread out, so they travel in a wider group around obstacles, reducing the number of units contending for the exact same paths.

Paths in the same group getting spread out.

The path simplification makes the lines look a bit chaotic, but the point is that the units will use a wider area to travel in, and therefore reduce contention when trying to move. For example if lots of units have to get through a gap, they will tend to use the full width of the gap, rather than all trying to squeeze down the nearest edge of the gap in single file. Like I said I haven't yet got units to avoid each other yet, but I'm sure this will work better for that, as it gives them more space to work with.

Web workers

One significant complication is that each web worker for pathfinding keeps its own copy of the pathfinding map, and therefore tracks cell costs individually. That means one worker adding a cost along a path won't affect the others, and so the other workers will still happily find exactly the same path.

The web platform does allow for memory shared between workers with SharedArrayBuffer. However since the Spectre class of security vulnerabilities it has required a strict security configuration to work. So strict, in fact, that I don't think it's actually possible to get it to work in Construct's preview mode - Construct previews your project in a popup window, but the security restrictions to allow SharedArrayBuffer block any communication with the popup window, which will break the preview. Deploying any games using it will also require the right server configuration, which makes it a pain to use in a general purpose engine like Construct - you can't assume everyone who uses it will set up their server correctly.

So I went with a different solution. First of all I added an option to limit how many workers can find paths. If you're on a 16-core machine then in theory it could find 16 identical paths before it starts to spread them out, but if it is limited to just 4 workers, then it will spread them out sooner - at the cost of less parallelism. Second I multiplied the cost added by the number of workers: if there is one worker it adds the basic path cost, but if you have 4 workers each worker adds 4x the path cost, to compensate for the possibility the other workers found paths down the same route. Finally I added some extra code to scramble the order pathfinding jobs are sent. If adjacent units send their pathfinding jobs at the same time, then they are likely to use the same paths. However if units far apart send their pathfinding jobs at the same time, then they are more likely to find different paths, or at least drive down the same path at different times, helping to spread them out.

The end looks different but achieves largely the same result, so I think it works OK.

Spreading out paths in the same group over 4 workers.

It's a shame to lose some potential extra multicore performance, but I suspect excluding low-power "efficiency" cores, systems with more than 4 cores probably aren't that prevalent anyway (Firefox's hardware data seems to support this). And there's still the browser main thread, Construct runtime thread, GameServer thread, and probably a couple more internal browser threads - so it's probably enough to keep 8 cores warm anyway! I'm interested in having an alternative SharedArrayBuffer path too, but I think we'd either need to do some serious rearchitecting in the Construct editor, or need browsers to relax their restrictions, for that to be feasible. Right now I don't think it's worth the trouble.

Conclusion

I've got a high-performance multi-threaded A* pathfinding implementation up and running for Command & Construct, all based on Construct's built-in Pathfinding behavior. The paths are simplified to produce fewer nodes with gentler turns between them, which is helpful when units drive along them. It can spread paths out when moving lots of units to avoid contention, which will definitely be helpful when it comes to getting units to avoid each other. That did impose some limits on parallelism, but it will probably still make full use of CPUs with up to 6-8 cores, which seems to cover most devices anyway. JavaScript is so fast that with our well-optimised A* implementation it can often find even long paths in just a few milliseconds, and multithreading helps it burn through the calculations needed to move large groups of units, so overall it's another good showcase of the extreme performance you can get from browsers.

The options to further simplify the path nodes, and the new path groups feature to spread out paths, are both new features I've added to Construct's Pathfinding behavior and will be available in an upcoming release. I also added another option to customise the move cost for the A* algorithm to allow fine-tuning the relative effect of other path costs. It's a great example of how this project is helping add cool new features to Construct! I'm also very pleased with the usability of the path groups feature - it comes down to just "start group" and "stop group" actions or methods, with some settings to tweak how the spreading happens. It's super easy to use! I think that's another sign I got the feature right.

As we're close to a stable release of Construct, these new pathfinding features won't appear until the next beta release cycle, which will take a couple of weeks. I haven't updated the Command & Construct GitHub code yet, as there's not much point sharing code nobody else can run yet. Watch this space and the code will be up there soon.

Update January 31st: the code is now available! It was added in this commit.