Pathfinding #1

Hi, Badump here.

About pathfinding…

Didn't I promise that like a month or 2 ago… anyways here it cometh.

  1. Introduction, goals, and problems

  2. Traditional methods comparisons

  3. First try

  4. Implementation

  5. Surprising problems

  6. Performance

  7. Take two

  8. The idea

  9. What we kept

  10. How the surprising problems were solved

  11. Formations

  12. Goals.

  13. Implementation

  14. Problems

  15. Obstacle avoidance(How it forced pathfinding to change)

  16. Unit movement

  17. Goals

  18. Implementation

  19. Bandwidth considerations

  20. Clusters

  21. Feels like choose 2 of 3 scenario

  22. Overall performance, and where are the issues

  23. Organization

Introduction, goals, and problems

As everyone probably knows by now, Sanctuary aims to be playable at scales of thousands to tens of thousands of units, being able to run smoothly won't mean anything if when you give orders to units they form a train so long that you think we are on a ringworld, not a Dyson sphere. So what can we do? Make the units move in a blob? Without any other rules, it is ineffective.

So units must also have at least some basic organization so that in case your artillery/shields are faster than your tanks they don't single-file to their doom. So in general that part is gonna be handled by the formation code.

Now, when it comes to how units move, we have a lot of different behaviors to introduce, from hover tanks that can go over water, to dive bombers, and anything in between. Quite a lot of things to be honest.

And the actual pathfinding code must be able to handle large maps and tens of thousands of units. The issue is that all of these conditions must be met simultaneously. Not to mention the fact that the pathfinding must actually work in tandem with the other 2 features, all of which add to the complexity of the challenge.

And this last nail in the coffin is the reason why we couldn't just plop in some existing solution.

Traditional methods comparisons

So when you say pathfinding, what comes to mind first? A*? Flowfields?

That paper from developers of Castle Story about Hierarchical pathfinding that you can find https://www.gdcvault.com/play/1025320/Hierarchical-Dynamic-Pathfinding-for-Large ? (I am going to refer to it as Hpa*)

No matter what you guessed, what comes to mind is at least a path between A and B that avoids obstacles. And without going into details on how it works, the most popular algorithm for doing that exact thing is A*. It is reasonably efficient but unfortunately has a nasty thing about having cases where the performance goes down as the square of the map size. So if the map is 5x5 let's say the performance loss is "25", but if the map is 40x40, then the performance loss is "1600".

The performance loss is our imaginary unit that is inversely proportional to framerate

We have another issue on our hands; the issue that unit counts tend to go up as the map size increases. So Having 2 players each with 50 units on 5x5 map results in 2 * 50 * 25 = 2500. And having 16 players on 40x40 each with 500 units results in, 1600 * 10 * 500 = 8 000 000. As you can see the lag tends to go up very very fast as the scale goes up.

Now let's see how we can fight that problem. There are 3 obvious solutions.

  1. Reduce the computational cost of each calculation(Aka we speed up everything by 10x)

  2. Reduce unit and/or player count

  3. Have smaller maps.

Now let's go over each one.

The issue with the first solution is that even if we make it 10x as fast, 8 000 000 / 10 = 800 000, the computational cost would still be way too great. We need to make it another 100x faster so it can be in the same order of magnitude as the first example.

The issue with the second solution is that it goes against the whole point of Sanctuary, while we aren’t aiming for “scale above all”, we are also not aiming for gameplay consisting exclusively of micromanagement.

And the issue with the third solution is that it is actually the biggest driver of performance issues. So reducing the map size would be the most performance-improving feature. But you cannot really have a lot of units in small maps, therefore it isn't suited to our use case.

Anyways it seems we need a solution that combines the advantages of 2 and 3 but without actually paying the price. Now, what could help us do that?

Let's start with the aforementioned flowfields. What are they? And how they help.

Well as the name suggests, they are fields, more specifically fields that span the whole map.

As you can see on the images, the flow field creates arrows that point to the most optimal path to the target location, no matter where you are. So imagine that you are a player in a labyrinth, and on the floor, there are flow field arrows. As long as you follow them, you will always reach the destination.

Unless there are no arrows, which is what happens when there is no path to the destination

You should now have an idea of the way it works. The question now is: "what are its performance implications?" Well, remember how in our previous example, each unit must calculate its own path to the goal? Well, that is no more. Now each unit has a constant cost of just looking up the flow field at its current position. Meaning that there is practically no cost to actually having more units. So you can effectively have an unlimited amount of units in the game and not see any performance drop due to pathfinding.

Sounds amazing! Let's get started... Not so fast! There is something I haven’t yet told you about flowfields, that might change what calculations we need to do. Remember the original calculations were total units * map size squared.

Here is a question: where is each unit going? What is their target location? Remember how I said that flowfields are leading toward a single location. Well, what happens if you give 2 units different positions to go toward. What if you gave each of those units a different target location. Well in that case you are doing no better than A*, and in fact much worse, because flowfields are slower than A* for a single unit.

Realistically we did massively reduce our effective unit count for the purpose of the calculations but it is not exactly 1, not it is small enough to be negligible. Especially when AI gets involved, with its 100000 APM. Anyways we can’t really do much more on reducing per unit cost, so let’s try the other approach, and see what it does for us.

And neither solution is any good for answering whether I can reach the target at all. Both will waste time, even if a unit can in no way reach the target location. Imagine islands.

Hierarchical pathfinding (I recommend reading the presentation, it is really good!). Come back here when you are done.

And in case you need a TLDR:

The goal of Hpa* is to allow having big worlds, like sizes so big, that you won’t even have the time to worry about pathfinding for more than 1 unit, and handle terrain that is constantly changing.

Now that I said changing terrain, how do you think the aforementioned methods would handle building a wall or plopping a big factory, and blocking unit paths? (hint they don't)

Well here comes Hpa* to save us. Because of the way that the map is preprocessed it allows us to only update the parts of the map that were changed, and each time we query the pathfinding we get an up-to-date path. Which is a big improvement over A*, now instead of having to path over the whole map. we only need to path over small segments and reach the destination.

Well, unfortunately, is that while it helps a lot computing less, the computations we do are much more expensive, so Hpa* only pays off on big maps. The smaller the map is the worse it performs. And the cost is constant over the entire time a unit is pathfinding. That is not exactly good, but not too bad either. Still, pathfinding for 10s of thousands of units gets expensive. Anyways I did start with it as the first take on pathfinding so let's see what happened.

First try