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.

Flood fill

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.

 
We still want a unit to get as close as it can to the goal though. If we know there isn't a path, we can still still use A* to find a path by ignoring all buildings and resources. Then we work our way backwards until we get to a node that belongs to the same zone as the unit is standing on.

The blue line shows the path taken to get as close as possible to the unreachable goal.

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.

Giving way for moving units

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.

 
Also, in the current build, if you have many units attempting to find a path to the same location, some units might not find a path and the performance will consequently freeze up. This is indirectly taken care of now because units who have reached their destination will start giving way.

Extra weights for paths taken through units

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.

Why was this work so important to get through?

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.

Are we done yet?

Some of you are probably screaming HPAA* or JPS A* after reading this!

To you, all we can say is, step by step..