Pathfinding in RTS, why it’s a challenge

Neon Marble Rust is a Real-Time Strategy game, where there's lots of units, acting on their own, and they need to find a way to get from place to place. It was very important, from the beginning of development, that units occupy space on the map. Body-blocking adds a lot to the game's depth.

The Problem

Single agent path-finding is easy, dijkstra/a* does the trick. Multi- agent path-finding is much harder, NP-hard to find optimal solutions. Generally speaking, NP-hard means that for path-finding, the computation time required grows extremely fast as the number of agents increases. Something like O(2^n), which can become impossible to solve in real-time. Check out this paper for a much more detail: https://ojs.aaai.org/index.php/AAAI/article/view/7564

So, perfectly optimal paths are off the table, we need some heuristic. It's important to think about things from the player's perspective. RTS games can be frustrating, particularly if units don't do what the player expects. Players want predictable agents, they don’t need optimal agents.

Why Path-finding is hard

Looking at this diagram, we can see a base with 2 entrances and 2 units. The O unit is yours, and was ordered to go into the base. The X is an enemy unit, blocking one of the entrances. So what should your unit do? Should it go around the long way (green) or try to go the short way (blue).

If the enemy unit isn't moving, then it makes sense to go around. But, what if the enemy goes into the base, should your unit go the short way instead? Should your unit regularly check where that unit is? This can make your unit predictable, so what if the enemy unit is controlled by another player, and they try go back-and-forth in the entrance and so your unit gets stuck on the outside. When the X is in the entrance, the O starts to go around, when the X moves, the O tries to go back...

Our Solution

Flow-Fields help a lot with performance. The map is filled with 'nodes', and while the map loads, a flow field is generated for each node. The flow-field tells units how to get to the node. Flow Fields are useful when he unit is far away from the destination. Units can also do obstacle avoidance. While following the flow-field, they may run into other units. When they do, they look around their nearby area, and try to find an open space. This doesn't always work, so units can become impatient. If their impatience gets to a high enough amount, they will do path-finding. Note, if a unit is ordered to move, and they are the only unit selected, they will path-find right away (this was added in the most recent patch 0-1-11a).

Looking at that case in the diagram, with our solution, the unit will first try to go the blue path (flow-field). The X will block it, and the unit will look around for open space. This obstacle avoidance won't work, and so the unit will become impatient and find a path around (green path). Once the unit is on the green path, it just does that and doesn't try to improve it, so the other player can't take advantage. This isn't a perfect solution, but hopefully players can grow a sense of what units will try to do.