20
\$\begingroup\$

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?

\$\endgroup\$
  • 7
    \$\begingroup\$ As I described in the edit, "is this too heavy" is a question to ask your profiler, because it will depend on your implementation, target hardware, performance budget, and the context of your game — all stuff that you and your profiler know intimately but Internet strangers do not. If you want to get flocks pathfinding efficiently, we can suggest strategies to help with that, but only your own profiling can answer what's efficient enough for your needs. If you profile and identify a specific performance problem, we can also help you find how to solve that problem. \$\endgroup\$ – DMGregory Aug 20 at 15:15
  • 1
    \$\begingroup\$ How you implement them affects performance. For instance, only running A* on leaders & relying on flocking for followers. \$\endgroup\$ – Pikalek Aug 20 at 15:25
  • \$\begingroup\$ If your game is primarily based on fighting these enemies, the algorithm you take will have a massive impact on what the game feels like. So you should try different approaches, e.g. does it feel like the enemies know the level and the position of the player perfectly at all times and they track him like directed by an all-knowing AI ? - other approaches could be to let the enemies run in the general direction where the player made noise and only on direct line of sight run towards him, or shouting and informing other enemies where the player is... \$\endgroup\$ – Falco Aug 22 at 12:13
  • \$\begingroup\$ @Falco Since the game is no longer wave-based, and will be level-based, and since the enemies are zombies... I was considering making it so you either have to be seen or make noise for them to find you. So if you use a noisy weapon? It emits a sound in a range and all enemies in range path towards the location of the sound emitted, and will then path randomly around that area. \$\endgroup\$ – Darin Beaudreau Aug 22 at 17:04
50
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ This technique sounds really neat. I'll check it out. \$\endgroup\$ – Darin Beaudreau Aug 20 at 16:22
  • 15
    \$\begingroup\$ It's possible to use a hybrid algorithm that constructs a partial flow field without searching more of the map than repeated calls to A* would, and never searching the same position twice. The basic idea is to pick an arbitrary enemy and start an A* search from the player towards that enemy, marking cells as you encounter them just like in normal flow field generation. Once the search finds that enemy, pick another enemy (that you haven't found yet) as the target, re-sort the open set according to the new heuristic and continue searching. Stop when you've found all enemies. \$\endgroup\$ – Ilmari Karonen Aug 20 at 21:43
  • 1
    \$\begingroup\$ What about avoiding collisions? That's (somewhat) mentioned in the OP (avoiding clipping when they reach the player). Seems to me you would have to rerun the full djikstras every time anything moved (or add in some additional logic) \$\endgroup\$ – Mars Aug 21 at 7:07
  • 2
    \$\begingroup\$ @Mars The OP talks about flocking, so I would assume all of the individuals can move at the same speed; the only places where collisions are going to be an issue are bottlenecks, which require some of the flock to stop and wait. However, it doesn't really need to change the pathfinding - a simple queue would probably work well enough in most cases, and some path biasing (some pseudo-random selection of alternate paths with similar costs) will work to produce more natural looking flock flows that also avoid the whole flock trying to go through one particular single-tile gap :) \$\endgroup\$ – Luaan Aug 21 at 9:32
  • 3
    \$\begingroup\$ @Luaan In a tile based game, you'd be surprised how often collisions happen. Personally, I find the "queuing" option to be less than optimal. Also, if units can't pass through each other, you'll need to recalculate when units start getting into their final position and a bunch of other edge cases. Flocking is hard ;) \$\endgroup\$ – Mars Aug 21 at 12:53
8
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ With an infrequently-updating A* approach, it may be helpful to stagger your updates, maintaining a budget for how many enemies are allowed to re-path on a single frame. That way you can keep your peak pathfinding cost per frame capped, and more robustly handle many AI pathing by amortizing their total cost over several frames. An AI using a stale path for a frame or two when the budget for the frame has been exceeded, or falling back on dead reckoning if close, usually won't be disruptive. \$\endgroup\$ – DMGregory Aug 20 at 15:54
  • 2
    \$\begingroup\$ Probably stating the obvious here, but if you're going to only update some of your paths in a given frame, you might want a priority system based on distance to the player. It's likely more important for enemies near the player to update their paths, while it's probably OK for enemies far away to use a stale path. \$\endgroup\$ – A C Aug 21 at 14:54
4
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ So what's a good way to handle following the path, but not exactly? If I allow kiddy cornering, I need to be able to stop the enemies from colliding with the corner of an obstacle. Should I keep the flocking behavior for both enemies and obstacles and add A* to deal with those situations? \$\endgroup\$ – Darin Beaudreau Aug 21 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.