Efficiently pathfinding many flocking enemies around obstacles

Question

I'm working on trying to improve the pathfinding for my game's enemies. Right now, they basically just constantly move towards the player's exact position by calculating the angle between themselves and the players and moving in that direction. I also have a flocking algorithm which prevents the enemies from stacking on top of each other, so they will form up into groups rather than clip through each other.

However, now that I've added a tile-based map, I need the enemies to also be able to path around obstacles and walls for example. I initially tried adding a separation value to "non-walkable" tiles so that the flocking algorithm would consider the walls and obstacles as objects to move away from. I have yet to work out whether or not this is feasible because my initial test showed the enemies hitting an invisible "wall" where there are no non-walkable tiles, yet for some reason, they hit it and start spazzing out.

I was wondering if it might be too performance heavy to calculate a path to the player using A* and then use the flocking algorithm to prevent clumping. Originally my game was going to be a wave-based shooter, but I've decided instead to make it level-based in the vein of Hotline Miami, so it's likely I'll have fewer enemies, with the occasional horde, and just make them stronger.

Is this a viable solution? I'm using Java with Slick2D as my game engine. Or is there a better solution / algorithm that tackles both these problems?

Answer 1

This sounds like a use case for Flow Fields.

In this technique, you do a single pathfinding query outward from your player object(s), marking each cell you encounter with the cell you reached it from.

If all your tiles/edges have equal traversal cost, then you can use a simple breadth-first search for this. Otherwise, Dijkstra's algorithm (like A* with no goal/heuristic) works.

This creates a flow field: a lookup table that associates each cell with the next step toward the closest player object from that position.

Now your enemies can each look up their current position in the flow field to find the next step in their shortest obstacle-avoiding path to the closest player object, without each doing their own pathfinding query.

This scales better and better the more enemies you have in your flock. For a single enemy, it's more expensive than A* because it searches the whole map (though you can early-out once you've reached all pathfinding agents). But as you add more enemies, they get to share more and more of the pathfinding cost by computing shared path segments once rather than over and over. You also gain an edge from the fact that BFS/Dijkdtra's are simpler than A*, and typically cheaper to evaluate per cell inspected.

Exactly where the break-even point hits, from individual A* being cheaper, to A* with memoization being cheaper (where you re-use some of the results for a past pathfinding query to speed up the next one), to flow fields being cheaper, will depend on your implementation, the number of agents, and the size of your map. But if you ever plan a big swarm of enemies approaching from multiple directions in a confined area, one flow field will almost certainly be cheaper than iterated A*.

As an extreme example, you can see a video here with 20 000 agents all simultaneously pathfinding on a reasonably small grid.

Answer 2

A* is not performance heavy. I would approach this situation by varying the algorithms. Do A* from time to time and in between check whether the next step is free to step onto or you need evasion.

For example, track the players distance from the A* target location, if it's above a threshold recalculate a* and then just do update movements. Most games use a combination of way points, e.g. a simplified grid for path finding and a logic that handles the movement between waypoints with evasion steering algorithms using raycasts. The agents try to run to a distant waypoint by maneuvering around obstacles in their proximity is the best approach in my opinion.

It's best to work with finite state machines here and read the book "Programming Game AI By Example" by Mat Buckland. The book offers proven techniques for your problem and details the math required. Source code from the book is available on the web; the book is in C++ but some translations (including Java) are available.

Answer 3

Not only is it feasible, I believe it was done in a commercial game in the 90s - BattleZone (1998).

That game had 3D units with free non-tile-based movement, and tile-based base construction.

This is how it seemed to work:

First, A* or something similar (likely a variation of A* with strict limits on how long a path it can find, so it never takes too many resources to run but doesn't always find a path all the way to the destination) would be used to find a path for a hovertank to get to its destination without getting stuck in tile-based obstacles.

Then the tank would fly around untiled space as if it was attracted to the centre of a nearby tile in its path, and repulsed by obstacles, other nearby tanks, etc.