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.

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.

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.

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.

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 surpr