HPA* for the path finding in Tankolini Napierdolki

Who said Habr isn’t a cake? 🎂

While everyone is putting neural network drips, we remember the old school and do it the way the grandfathers taught us. Today we’ll figure out how to turn a few pixels into real Terminators — without terabytes of training data and huge electricity bills.

Pathfinding is the head of everything. Without it, our bots won’t even move from their spot and won’t reach the needed point on the map. There are many pathfinding algorithms, but for Tankolini Napierdolki we chose HPA* (Hierarchical Pathfinding A*).

Under the cut — lots of pictures, examples, and visualizations. Let’s go!

Stage 1. Finding obstacles

There we see the original map

In the game it’s possible to create maps yourself in a small editor, so it makes complete sense to process the map right after creation and use ready-made routes for every bot.

Here we load the map into memory. The main idea is that we only have impassable blocks. Unlike other games such as StarCraft, where there can be many different types of obstacles, everything is simple and clear for us.

Our task is to redraw the original map so that the bots clearly see the places that cannot be passed. In our case the final obstacle map looks almost the same as the original.

Stage 2. Building the walkability map

And this is already the map where we can walk

This is more interesting. Here, with a few clever manipulations, we can significantly reduce the number of available pixels. And this has a very good effect on performance.

Fewer elements — less to calculate, the path search becomes faster and shorter. Here’s another example.

Map “Town” with walkability display

For walkability we take the size of our moving object and add it to the obstacles. In our case the tanks occupy 3×3 cells, so we add 3 points to the right and down for each obstacle. It turns out something like a “shadow”.

As you can see, on the right and bottom of the map we have 2 squares filled. In theory, we could already stop at this stage, apply regular A* — and everything would work. But we go further.

Of course, in our case the map is simple. If different levels of walkability are needed, other tricks are applied. For example, several walkability maps are built for objects of different widths or different movement speeds.

Stage 3. Dividing the map into sectors

Map divided into sectors

In our case 64×64 maps are perfectly divided into 8×8 sectors. This is well suited for storing the map in binary form, where 0 means passage exists and 1 means it doesn’t.

Of course, you can take a different cell size, but 8×8 is a perfectly reasonable compromise: the data is convenient to store, and at the same time pathfinding inside each segment remains as simple as possible.

Stage 4. Finding portals

All possible portals on the map

Portals are certain sections on the borders of our zones through which you can move from one zone to another. This can be either two neighboring pixels or a whole group of pixels.

For simplicity it’s better to combine several neighboring pixels into one group. For example, we can have a pair of pixels [23, 45] and [24, 45], while at the same time there are larger groups, for example [0-7, 7] and [0-7, 8].

Stage 5. Finding paths between portals

All possible paths between portals

Since there are a lot of portal options, I drew thin lines, but with sufficient zoom you can clearly trace how the paths run between them.

Our task is to take each individual sector and find routes between all portals inside it. For example, for sector [0-7, 0-7] we have two groups of portals: 3 pixels high on the right [7, 0-2] and 7 pixels at the bottom [0-6, 7]. Between these groups there will be only one route, because we consider each portal group as a single point.

At the same time we try to pass through the central points of the group. If you lay the route at the beginning or end of the group, the bot’s behavior looks strange.

Stage 5-1. The A* algorithm

g = path traveled, h = heuristic |dx|+|dy| from the current point to the finish

But how did we lay the route between these points? Here we apply the A* algorithm. There are enough articles on Habr about how it works, so we won’t go deep. For example, this one: Introduction to the A* algorithm.

The main idea of A* is this: we take some starting point and start moving in the direction that is closer to the finish. To understand where the finish is, we use a heuristic function (in our case Manhattan distance |dx| + |dy| is enough). At the same time we remember the number of steps we have already taken from the start.

For convenience we use a priority queue, where the element with the smallest sum of the distance traveled and the heuristic estimate is always on top (because there may be obstacles on the way). Thus the queue always contains the point that is currently closest to the finish. We add all neighboring walkable points to the queue and extract the highest-priority element. As a result, if a path exists, we will definitely find the shortest one.

Important point: in the A* algorithm it is very important to accurately define the heuristic function. The more accurate it is, the more naturally the bot will search for the path. In our case we took into account that turning a tank is a separate action, and extra turns are undesirable (otherwise the route turns into a staircase). To avoid this, we add +1 to the cost if a turn is required on the path. As a result the route becomes a little less optimal in distance, but much more similar to the actions of a real player.

Stage 6. Pathfinding on the map

Built route between two points

Here it’s already a matter of technique. We apply the same A* algorithm, but only for passage between portals. Since we have pre-calculated all routes between all portals inside each sector, all we have left to do is take the ready-made routes between two portals and connect them into a full path.

There is only one nuance: the start and end points usually do not lie exactly on the already built routes. Therefore we solve the problem head-on — for the start and final points we build the shortest path to the nearest portal using the same A*.

As a result the entire final path consists of three stages:

1. Build a path from the starting point to the nearest portal (A')
2. Build a path from the nearest portal to the final point (B')
3. Build a path between the portals (A' → B')
4. Glue everything together into a single route.

Conclusion

The solution is actually quite comprehensive and is not always used. There are many situations where the task can be solved by other, simpler methods. We may talk about them in future articles.

You can see how all this works live in our Tankolini Napierdolki. When registering via Telegram you get a bonus of 1000 points that can be exchanged for tickets to paid tournaments.

Right now we have free qualifying tournaments for weekly battles with prize funds. Fun atmosphere, memes, and fully custom maps — everything we love.

Also join our Telegram channel and follow the news about giveaways.

---

My original article was written on the Habr: https://habr.com/ru/articles/1042938/