RTS devlog #10: Following paths

13
Official Construct Team Post
Ashley's avatar
Ashley
  • 22 Feb, 2023
  • 1,800 words
  • ~7-12 mins
  • 3,362 visits
  • 1 favourites

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.

A path for a unit to follow.A path for a unit to follow.

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 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!

Subscribe

Get emailed when there are new posts!

  • 9 Comments

  • Order by
Want to leave a comment? Login or Register an account!
  • Thanks for explaining how pathfinding behavior works.

  • Really interesting, it's nice that this project allows you to experiment potential enhancements for C3 behaviors.

    Hope those pathfindings and future "crowd control" things you're working on will make it into the Engine.

    Regarding crowd control (avoiding unit overlaps and traffic jams), this is a feature a bunch of the most experienced C3 dev tried to do since Vampire Survivors turned this into a highly requested feature for some indie games. There is no good way to do it right now, and it's a big challenge in any engine.

    So if C3 had a great Crowd Control feature it would be a strong USP. Some of the issues I can think of would be what if Object with higher speed have lower speed Objects moving in the same direction in front of them. Should the low speed Object get pushed from behind (based on a weight ?). The C3 user should probably have some kind of control on that traffic jam behavior.

  • Is this going to be added as a Behavior? I really hope so because I have been asking for RTS behaviors for a long time.

  • I do not currently use the pathfinding behavior but it is awesome to see this amount of polish for the feature.

    Worse still, the overshoot could run in to an obstacle and risk getting stuck

    The same could be true for "undershoot" too, if it turns a corner it will start steering before it reaches the path point and might steer right into a tree or the corner of a wall.

    If you plan to bring this feature into C3, which I hope because it does look nice and smooth, I would love to see an on/off switch for this. It would be even better if we were able to override the turn radius.

    Because in my experience getting stuck on corners was actually a much bigger and more common problem with pathfinding in C3 than bumping into something because of a too wide turn.

  • I have developed my own RTS (Nuke them all) with the tools of Construct 3 :) Thank you guys!

  • I love to read this blog series where you basically confirm that features and plugins are lacking and are too basic to attract or offer users (game players) decent smooth playable logic, something else then very basic. Which they might expect.

    There have been countless discussions on forum on this kind of subject: where to draw lines on each plugin features? And outcome has always been essentially it's pointless to add very specific features and engine is made to offer "general" features. And in this blog series you start showing off how rudimentary some of the features are.

    This development step which involes pathfinding in this case, is very basic and every user who ever have used it in C3, have gone though same steps as you are going though and without ability to change anything.

    Overall there is hope new lines are drawn and more features are includes in C3. And overall other plugins which are not used in this "RTS Tank game" are also reviewer and new lines are drawn.

  • On traffic jams: you may want to investigate flow field pathfinding. I first remember reading about it in the Planetary Annihilation dev blog, but there are other posts on it floating around.

  • Thanks Ashley, helpful to see these blogs. And looking forward to the finished result too!