AI Path-finding and Navigation in Hexters

In its core, Hexters is a strategy game with multiple more or less autonomous AI units navigating in a terrain, doing various things like hauling resources, constructing buildings and fighting off enemies. This post is my attempt to shed some light how we have implemented things regarding path-finding and things related to it.

Path-finding is needed not only for the units move around but also to make reachability queries such as “can I reach this resource”, “where should I flee to” and so on. Let’s first focus on basic navigation and path-finding.

First Attempt: Triangulation using Fixed Distance Fields

The go-to way of implementing path-finding is to use A* algorithm. But instead blindly going with that, I wanted to investigate how other people have done navigation in strategy games. I quickly came across the concept of distance fields (DF in short) used in games such as Supreme Commander 2 (flow fields) and potential fields like in here.

The core idea is to have distance field being generated outwards from the target point your trying to find your way to, and then use that distance field gradient to move towards the lower potential (potential being distance to the target). It’s important to note the fact that a distance field is effectively an exhausted navigation graph search. The problem here is that doing an exhausted search is actually quite expensive, something you wan’t to avoid at all costs with A* – so it takes a bit of time to generate a single distance field. If you have multiple units moving to a same single point, it’s great. Each of them can share that distance field.

But if you have multiple units moving to multiple points, you effectively need one distance field per unit. Not only it is time consuming to generate each distance field but it also takes some space. If you grid is 400×400 (which we might have for a larger map), then each unit needs to have 640k bytes (assuming DF uses 32-bit floats). With tens or hundreds of units you quickly run into quite considerable space requirements: 100 units = 64MB. Not that much in modern standards, maybe, but still something to think about (especially if you’re developing console – which we’re not though).

The biggest issue is the time it takes to generate a DF. This can take hundreds of milliseconds, depending on the efficiency of the implementation. Even something like 10 ms would mean that it cannot be done in the main thread, at least not in one go. Which means multi-threading, and further complications. A lot of effort to move one unit just few blocks.

After thinking about all this for a while, it struck me. What if we could use some fixed distance fields generated on certain positions on the map, and combine few of the DF to generate procedural DF which could then direct the unit in correct place? Similar way they do positioning using GSM tower triangulation. This way I could reuse some fixed amount of DF generated ahead of time (or incrementally during gameplay).

Example level showcasing distance field triangulation

After a while I got it working quite nicely. However, it wasn’t without problems. There were two things: navigation code became quite a complex beast and it wasn’t accurate. Because of the complex nature of the algorithm, it became increasingly difficult to debug path finding issues. And there were a lot of them. Accuracy problems caused the navigation to end up in local minimums, not being able to proceed.

A Hexter stuck in local minimum

In the end it was too complicated. Great idea, but needed better execution. I definitely learned a lot from distance fields, and I’m still confident my novel DF triangulation has its uses (maybe better heuristics for A*?)

Back To Basics: A* Path Finding

So back to A* it was. I had basic implementation working in quite short time, as I was able to reuse some of the code from the DF implementation such as the code for progressing from tile to another. We could have used some of the existing A* implementations for Unity, but I preferred using my own, as it would allow maximum flexibility what comes to the extending and understanding the system. A* is simple and well understood algorithm, so working with it was straightforward.

However, the enemy of A* performance is exhausted searches. Under normal conditions, A* can be really fast thanks to good heuristics. Exhausted search happens when there simply is no path between two points you’re trying to connect or if the path is inconvenient for A* (need of back tracking), effectively the search filling up the search space until no more space to search (or fixed limit is hit). Or maybe it finds the route, but it’s unbearable expensive.

A search that reached max search limit without reaching destination. Hexters are trying to get to the other side of the mountain.

To combat this, I implemented hierarchical A* where the search would first be done on a high level node network, connecting regions of the map together. This search, even if exhausted, is really really fast. Then, an actual A* search is made from the current position to the center of next region. Once the unit reaches the next region, we target region after that. With this, we get both accurate and fast searches, no matter how complex the map is.

This hierarchical A* is generated by producing expanding regions from certain points of interest in the map (buildings). Each region is expanded until it’s large enough, and new region is spawned on the edge. Each path tile is then assigned to the closest region. In some sense it generates a Voronoi diagram out of the path tiles. Each region is then connected to the neighbouring regions, forming a node graph.

A test level with a bridge and connected regions visualized

Reachability

Robust and effective A* path-finding system is great to have, but even it doesn’t work well if you need to query hundreds or even thousands of paths in short amount of time. When shelling out tasks for Hexters, the AI system needs to know which resources and workplaces are reachable by each Hexter and how far away, so that they are not given resources which they are unable to fetch.

For this we’re using the regions presented above. When querying whether to path tiles are connected, we check in which region they reside in. Then we check a lookup table for those two regions, and if the search was done in the past, we already have the results. If no results, we do the path-find, and cache the results. This makes it possible to have lightning fast reachability queries for the AI.

When ever the path finding data changes (see Dynamic Environment below), we invalidate this cached data to force recalculation of reachabilities.

Dynamic Environment

In Hexters, the environment is mostly considered static. The only dynamic things are fog of war (FOW), perimeter and certain dynamic path connectors such as bridges and teleporters.

In path-finding perspective, each path tile is either discovered or undiscovered in FOW. Undiscovered tiles are not visited (no paths through FOW).

A vehicle going from point A to B. Direct route would go through FOW, but path found avoids going into FOW.

Perimeter is the edge of your colony/infrastructure. During the night, Hexters prefer to stay inside the perimeter, so at those times we actually penalize path tiles outside the perimeter.

A Hexter going to decomission a node during night time. The orange line depicts the assigned task destination and is the shortest path, but the actual path is staying within the perimeter. Notice how the path-find is initially searching point in the region center instead of final destination.

Dynamic path connectors like the bridges make things a bit more complicated. Each path connector has a volume which it occupies in the path tile space, and enter/exit connectors. When A* data is generated, special jump node connections are inserted in the data. When doing a search, these special node connectors are then visited IF the owning path volume is considered enabled (bridge is built, teleporter is powered etc). Dynamic path connectors also affect the high level hierarchical A* to allow reachablility checks and A* searches to pass through them.

A bridge with path volume and its jump nodes. When bridge construction is finished, those jump nodes are activated, allowing Hexters to navigate on the bridge.

Other things like other units or enemies or vehicles do not block the path find, to keep things simplified. They do affect local obstacle avoidance (which infact is a bit broken right now, but that’s another story).

Conclusion

Navigation is a core feature of any strategy game, and ours is no different. Considerable amount of time has been put on developing these things, yet it’s one of those things that people expect to be working and it’s like a sore thumb when it’s not working. There are still things to do, but personally I’m really satisfied how it all has been working out.

Thanks for reading!

Sampsa

Leave a Reply