Path Finding in BarbearianOne key element in the game is that there area a lot of units, and they might be all moving at the same time in the worst case. To enable this, they need to have a very fast path finding method. I thought I'd write how it works in my game.
Disclaimer: This is not a guide on how to do a great job at this, this is just how I did it.
The ProblemMy gameplay level is 2D grid and I need to know how to get from point A to point B.
Some options I thought about
a) No path-finding at all. Just go towards target with some obstacle avoidance and get stuck if there's a problem. Many simple games work fine like this.
b) Do full A* pathfinding when needed (slow to do all paths separately, annoying to do a cache, maybe...)
c) Some kind of vector pathfinding graph. Complicated. Still needs some processing per unit (never seriously looked into it though)
d) Some kind of dynamic flow fields (never really crossed my mind back then, only later noticed that it might be interesting... probably not suitable to this game though)
e) Calculate ALL THE PATHS
I chose to try option E, because I liked the simple and elegant implementation (+ performance was guaranteed without trickery).
The SolutionFor every tile, I store a full Djikstra search, i.e. I store a direction you need to walk towards if going to any other selected tile. The code interface takes a source tile and a destination tile, and the function returns the direction where the next tile you need to walk to is. (Can also return 'path is blocked' or 'path is not yet calculated')
Visualization of one cached path table
Pseudo code struct Path_Grid
{
uint Get_Pathing_Direction(vec2 tile) const
{
uint entry = m_pathing_grid[tile];
entry >>= (tile.x % 2) * 4;
entry &= 0xf;
return entry;
}
// 4 bits per entry (neighbour idx, or no path) (X rows contain two entries per cell)
Grid<uint8> m_pathing_grid;
}
Path_Grid Get_Path_Grid(vec2 tile)
{
if (cached(tile)) return cached_grids[tile];
else { prioritize(tile); return not_found; }
}
Path Get_Direction(vec2 source_tile, vec2 target_tile)
{
return Get_Path_Grid(target_tile).Get_Pathing_Direction(source_tile);
}
void Frame_Update()
{
fetch next uncached grid and fill it with Djikstra etc.
}
This happens very often in a frame, so it needs to be fast. With this system, it's just table lookups. Note that when we calculate a full path grid, we calculate all paths from every cell to one
target cell.
Problems- Memory usage is high and grows exponentially with level size.
I store 4 bits of information per tile (walk direction) and I need to store (64x64)^2 of them in the worst case (my max level size for now), so that takes 8MB. Problem is that it grows exponentially if I make the levels larger, so mobile device memories will fill up quite fast.
- It's slow to calculate the full path table cache
I optimized my Djikstra search to the point where it's fast enough, but filling the whole cache takes some time no matter what you do. And my cache invalidates when the level collisions change (could probably do something more intelligent there, but it's not worth the extra code)
I get by this by only doing one full search per frame (which is about the max CPU budget I can spend on this on my lowest mobile target) and prioritizing whatever is currently needed. Sometimes units need to think a few frames before they get their paths, but it's unnoticeable in the game. When there's been no queries for uncached paths, the system continues filling the other path tables until full.
Filling the cache: red squares are the target tiles that have path cache filled for them
Extra Complications- Some tiles are split in half, i.e. half of it is water and half of it is ground. I just flag these as 'unwalkable' so pathing avoids them. If the unit wonders there regardless, I have filled the path tables so that after the Djikstra fill, I do an extra fill that adds directions away from blocked/unwalkable tiles to the nearest properly pathed tile. (See the 'OUT' tile in the info pic)
- I also store a bit of extra information for if the path to target is 'long' (arbitrary constant). As the path query doesn't give instant answer to how long the path to target is without recursing through the path, this extra bit will allow me to do super simple tests to see if it's worth the trouble to start attacking something (for example if the player is behind a wall really close, but actually walking there would take a long way, then the enemy just does nothing instead of aggroing)
Future Improvements- Path tables for all tiles are allocated in memory, even though most of them will never be used. Memory usage could be optimized by making a more intelligent allocator and dropping the the ones least likely to be used by some heuristics.
- Some kind of hierarchial path finding system would probably allow me to reduce the exponential memory requirements and grow level sizes, but I haven't really given it much thought as I've so far managed with this.
--
That's about it. On top of that there's some simple steering behaviour (+ army formation movement too). One thing of note is that there is no obstacle avoidance. The enemies just ignore trees for example and trust that the collision engine will push them away. All colliders are round and things are spaced sparsely enough, so there should be no 'collision traps'. That doesn't always work out, but it's good enough for now at least (the gameplay doesn't require infallible pathing).
If anyone found this interesting, let me know so I know if it's worth writing more of these some day.
Community
