RTS devlog #10: Following paths

In the last devlog I came up with a decent system for finding paths to a destination, producing a series of nodes for units to follow with path smoothing and spreading. An example of such a path, using the debug visualization of yellow squares for nodes joined by blue lines, is shown below.

This devlog covers getting units to follow the path. This is not as easy as it sounds.

It's been a few weeks since the last devlog - we've had a lot of work to do on Construct, and that remains my first priority, but I'm back to blogging on the RTS project again!

Naive path following

Units have a maximum speed they can drive at, and a rotate speed which determines how quickly they can turn. You might think all you need to do is something along the lines of: drive to the next node, and when you reach it, start driving towards the next node. This doesn't work very well though. Consider a turn through two nodes as shown below.

With this approach, the unit will follow the path shown with the green highlight.

You can see how the unit overshoots the first node significantly. Since it only starts turning when it reaches the first node, then as it's still driving forwards, its entire turn circle goes past the next path line until it's finally pointing towards the next node. By that point it's quite far off the path line, and the remainder of its movement is no longer parallel to the path line.

There are a few reasons this isn't good enough. The unit looks pretty stupid turning late like that, and players will notice. It also looks bad when following a series of nodes in quick succession, ending up weaving all over the place instead of a sensible "racing line". Worse still, the overshoot could run in to an obstacle and risk getting stuck - after all, the pathfinding algorithm might have taken that path to avoid an obstacle, and so units need to hew to the line closely to stick to the clear path.

Naturally the solution is to turn early so the turning circle fits the corner. The path we want looks like this.

This makes the unit look smarter, and picks a better "racing line" through a sequence of nodes. It still risks hitting an obstacle on the inside of the turn, as it's now essentially undershooting than overshooting, but in practice this is much less of a problem (obstacles have an extra border space around them and paths tend to be smoothed for gentle turns along the edges of obstacles).

This means the unit must start turning early, before it actually reaches the next node. The question is: how do we calculate when it should start turning?

It's worth adding Construct's Pathfinding behavior has a built-in movement that follows paths, but it uses a different algorithm. It has a kind of "follow the rabbit" system where a marker (the "rabbit") moves along the linear path lines a fixed distance ahead, and the moving object aims for that. This lets it undershoot corners in a similar manner, but it's not precise. For this project I wanted to figure out the exact solution - and perhaps in future that could also be retro-fitted to Construct's Pathfinding behavior.

Maths time

Knowing some geometric maths can be very helpful for game development, and this is a case where some maths knowledge comes in handy. Kids, this is why y'all should pay attention in math class. Let's get stuck in.

Here's a diagram of the problem we need to solve. There is a distance d before the point p1 at which the unit can begin turning early.

Notice in this diagram:

• We need to calculate the distance d.
• The green circle is the unit's turning circle, centered on point c.
• The mathematically inclined reader may notice this diagram has two tangent lines from point p1. This is symmetrical about the line from p1 to c, and there is a right-angle from where the tangents touch the circle to the center of the circle c.
• The angle α can be calculated as the angle between the lines p1 to p0 and p1 to p2.
• The distance d that we want to calculate is in fact the adjacent edge of a right-angle triangle with points p1, c and t with angle α÷2 and opposite length r (the radius of the turning circle).

The last point is the most important: we've managed to reduce the problem to finding the length of a right-angled triangle. The trigonometry I learned in school covered this, so at least there's not any crazy calculus going on.

Unfortunately this blog system doesn't support MathML, which recently got widespread support across browsers, so I'll have to make do with writing maths as text I'm afraid!

Calculating the turn circle

The first task is to calculate the radius of the turning circle. This depends on the unit's speed s in pixels per second, and its rotation speed q in radians per second.

Consider the time it takes the unit to turn a full circle t = 2π÷q. Since d = st, the distance it covers in this time is 2πs÷q, which is the circumference of the circle. Since the circumference c = 2πr, diving by 2π gives the radius r = s÷q.

In other words, just divide the speed by the rotation speed, and you get the radius of the turning circle! It works because the rotation speed is in units of radians per second.

Calculating the distance

Now we want the distance d, knowing that it is the adjacent edge of a right-angle triangle with angle α÷2 and opposite edge length r, which we just calculated from the turn circle.

If you ever learned "SOHCAHTOA", then the TOA part is relevant here: tan(angle) = opposite ÷ adjacent. Rearranging that to give the adjacent length, then adjacent = opposite ÷ tan(angle). Now we can drop in what we know about the situation with our unit's movement and get our final calculation which is d = r ÷ tan(α÷2).

There's another calculation to find the angle α from the points p0, p1 and p2. This requires a difference-between-angles function, which you can find in mathUtils.js.

Implementing the movement

The basic implementation of this is pretty straightforward. Start with the naive algorithm of just pointing at the next waypoint. However the "have I arrived yet" condition is changed from "am I at the point" to "am I within distance d of the point". If it's in that distance it can switch to the next waypoint along, and it will start turning towards that immediately.

The code for all this is in #TickStateMoving_MoreWaypoints() in the GameServer class MovableUnitPlatform. However there is a fair bit more to the path-following movement than just this calculation.

State machine

When units are instructed to move somewhere, they currently go through the following process:

1. If moving, come to a halt.
2. Rotate on the spot to point towards the first waypoint.
3. Start moving towards the waypoint, and any following waypoints after that.
4. When approaching the last waypoint, slow down to come to a rest on top of the final waypoint.

This is implemented using a Finite State Machine (FSM). This is a fancy way of saying the unit has a #moveState property which is a string with values like "stopped", "rotate-first" or "moving". The code has rules to move between these states, such as changing from "rotate-first" to "moving" once it has turned to point directly at the first waypoint. The code for all this happens in #TickMovement() and its related methods.

Edge cases

While developing this, some edge cases came up that needed special handling. These included:

• Sometimes the unit and its next two waypoints end up forming a straight line. In this case the turn distance calculation essentially fails (producing a near-zero, infinite, or NaN result). Therefore detecting a near-straight-line is another case where it switches to the next waypoint.
• Sometimes the target position could end up impossible to reach as it's inside the unit's turning circle. In this case it falls back to coming to a stop and rotating on-the-spot again.
• Sometimes the distance to the next waypoint is very short (i.e. p1 and p2 are closer than the distance d). This means by the time the unit finishes turning it's already overshot the next waypoint. I compensated for this by slowing the unit down to reduce the turn circle so d is at most half the distance from p1 to p2. It's not perfect (as the next turn could again be even tighter), but it seems to work well enough, and the stop fallback helps avoid impossible turns.
• Calculating the stopping distance to the last waypoint is tricky - the code calculates 0.5 * this.#maxSpeed * this.#maxSpeed / this.#maxDeceleration, but that only applies for a straight line - if the unit is turning then the calculation won't be right. I'm not sure what the best solution is for that, but again the stop fallback helps sort out the unit if it can't make the turn.

Result

The end result is units that follow their paths nicely, turning to keep themselves precisely on the path lines. It looks pretty smart and I think it's a good result! It also works for different driving speeds and rotate speeds, as it is all fed in to the calculations, so it should also work well for all kinds of different units ranging from fast light units to slow heavy units.

Conclusion

It's tempting to think that pathfinding is the hard bit, and following the resulting path nodes is easy. However like many things in programming, it turns out to be harder than it looks if you want to avoid the overshooting that happens with naive movement. There's some pure maths to just figure out the calculation, and then after that there's a few extra engineering hurdles to make sure it works well with things like floating point calculations and edge cases like all the points forming a straight line. Still, solving the necessary maths is satisfying, and I think this is a good basis for the path-following movement.

My next challenge will be crowd control - avoiding unit overlaps and traffic jams. That I expect to be a formidable challenge. So it may once again be several weeks before the next blog post, as I think I'll need to spend a while researching it and experimenting with a variety of algorithms. However as ever all the code is on GitHub, and I'll be sure to let you know what I figure out!