Posted October 24, 2018 by LincRead
#pathfinding #flood fill #a* #tech
Pathfinding is one of those concepts we as players don't tend to put a lot of thought into. Unless it's broken!
For RTS games decent pathfinding has always been really important. Actually, it's critical for the fun factor, so if we can't get pathfinding right we might as well throw in the towel.
Because we're so early in development it's not that noticeable, but the game's current pathfinding doesn't exactly scream polish. It finds paths all right. The problem is when it doesn't. We use A*, probably the most used algorithm to find paths in video games. What A* is not good at is figuring out when a path doesn't exist. What happens when a path doesn't exist is that the algorithm goes through every single node it can reach before giving up. Even if only a single unit can't find a path this might still lead to noticeable performance hicks. When multiple units can't find a path the game freezes.
The first step we took to improve performance was to flood fill the entire map. This might create several zones that are not connected to each other. Flood filling is fast and is re-done whenever a resource gets depleted or a building is placed or destroyed.
On the image below you can see that certain tiles are rendered brown instead of green, since they belong to a different zone. When you try to move a unit from one zone to another, the game already knows from little information that a path doesn't exist. Thus, A* doesn't have to look through tons of nodes before reaching the same conclusion. This is a huge performance win.
If an obstruction is placed in the middle of a path, so that there are suddenly no paths to be found anymore, we can safely stop when reaching the obstruction, and assume it's the shortest path.
Another huge improvement to pathfinding is that units who are moving can ask idle units to give space. On the image under, in the current build, units are not able to get through the gang of units. The A* will run ballistic and create frequent performance hicks.
In the upcoming build idle units will give way so that units can pass, like shown below.
Additionally, we've added a movement penalty cost for finding paths through units who stand still. So your units will first and foremost attempt to find paths around these. More often than not, only when a unit can't find a path will it start asking idle units to give way.
Finding paths through units who are standing still, but who are also active, like fighting or chopping wood, give the largest penalty cost. Your units will therefore try hard to avoid them. However, in rare cases, units will have no other choice than the wait for the blocking unit to finish its task and move away.
In addition to improving performance we also fixed some bugs that happen rarely, but that are very noticeable when they do. For example, placing a building in a unit's path won't get the unit to change path in the current build, and the unit will actually proceed to walk through the building like it doesn't exist! This was fixed for the next update.
If you're one of the fine folks playing multiplayer you're probably missing base defence structures. Walls were a very important asset for the ancient civilisations and we're definitely going to add them at some point. Because of the recent work we've done on pathfinding adding walls won't break the game.
Lastly, we have as a goal to add team games before Christmas, and boosting performance will make these more enjoyable.
Some of you are probably screaming HPAA* or JPS A* after reading this!
To you, all we can say is, step by step..