Introducing the back end of Empires and Tribes: Pathfinding II

As the world of Empires and Trips grows, the demands on background algorithms become more complex. The pathfinding algorithm, for example, determines the shortest path of a unit from point A to point B. The more units on the road in the world, the more search queries there are and the higher the computing effort. Until now, path calculation has been solved using the classical A* algorithm. Advantage: relatively straightforward programming (good for me). Disadvantage: with longer paths the algorithm consumes more and more computing time. Simply put, A* calculates all the most promising routes to reach your goal. 

From the starting point, it moves forward in small steps towards the goal, bypasses obstacles, compares all possibilities to reach the goal and looks for the shortest way out. With the length of the path, however, the possibilities to reach the goal increase immeasurably and thus also the computing power. This is where a relatively new approach of the so-called jump point search, or JPS+, comes into play. A wonderful explanation by Steve Rabin on the subject can be found here: https://www.gdcvault.com/play/1022094/JPS-Over-100x-Faster-than The JPS+ algorithm searches for the most likely routes to the destination just like A*, but also uses the possibility to skip certain routes.

For example, if we want to cross a large free area, we don't have to calculate every single point, but can jump straight from point A to point B, because we know that the area is free. Well, we know that... That is the crux of the system. The crucial point for JPS+ is to calculate the environment in advance and save all parameters such as obstacles, distances to the next obstacle, etc.. Sounds great in the idea, but the problem is that we can't change the environment dynamically. But that's exactly what we need in Empires and Tribes when we build a new wall, for example. So I spent the last few weeks writing an update function for JPS+ to do all the necessary precalculations in the fastest possible time. Whew! 10-20ms needs the update now, but I think that should be acceptable. After I have done a few re-calculations, I hope that I will be able to present a stress test of the system in the next update.

AI Castle Siege

The work has paid off: Our new pathfinding algorithm allows us to build more complex castles with several inner courtyards and to defend or attack strategically important positions, like gates, towers, etc. The basis for tactically demanding sieges has been created! Check out our new video which features two opposing AI players fighting for supremacy within the walls of one of their castles.

Having fun with colors: Improving the Pathfinding System

The previous pathfinding system has been pretty straightforward, as it simply divided the terrain in walkable and unwalkable tiles. Rivers and buildings for example have been marked as unwalkable, to prevent your soldiers from crossing the deep water or from walking through walls. This works pretty well for 90 percent of the terrain, but we'll run into trouble as soon as we're introducing more complex areas like keeps with different courts. Your pikeman for example may stand inside the courtyard of your keep, surrounded by walkable tiles. As the gates to the outside are closed he should not be able to protect the villagers which are attacked by an enemy raid, although this happens in an area of walkable tiles, too. What, if the main gates of this court are closed, but are still opened at an adjacent courtyard? No question, get there and beat the hell out of them.

In order to make this possible, we need a system that understands whether areas are connected or separated by buildings or walls. More precisely: whether point B can be reached from point A after the construction of a wall.

For this purpose a specially written pathfinder is activated, which travels along the wall tiles until it has found the target point. As soon as a certain maximum of steps is exceeded by not finding the target point, it terminates the try, compares the two separated areas of point A and B and marks the smaller one as closed courtyard. 

In the next step, we want to include gates that allow us to open or close the courtyards. As soon as a gate is built on a previously defined closed area, the Pathfinder will be activated again, assigning different ID's to the areas and storing them with the ID of the gate in a separate script. When opening or closing the gate, we only have to compare the ID's and activate or deactivate the corresponding tiles.

In the last step we check if different courtyards are connected by gates. As soon as a gate is closed or opened, all adjacent courtyards are updated. A connection between two courtyards is only finally declared closed once there is no longer any way over all other gate connections.

Finally, this enables us to build architecturally complex castles with different atriums, courtyards and gatehouses and to conquer or defend them in tactically challenging sieges.