Skip to main content
Adding more details and an example
Source Link
DMGregory
  • 140.8k
  • 23
  • 257
  • 401

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 evaluratevaluate 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 fieldfields 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.

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 table that associates each cell with the next step toward the closest player object.

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. 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 evalurat per cell inspected.

Exactly where the break-even point hits, from individual A* being cheaper, to A* with memoization being cheaper, to flow field being cheaper, will depend on your implementation and the size of your map. But if you ever plan a big swarm of enemies in a confined area, one flow field will almost certainly be cheaper than iterated A*.

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.

Source Link
DMGregory
  • 140.8k
  • 23
  • 257
  • 401

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 table that associates each cell with the next step toward the closest player object.

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. 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 evalurat per cell inspected.

Exactly where the break-even point hits, from individual A* being cheaper, to A* with memoization being cheaper, to flow field being cheaper, will depend on your implementation and the size of your map. But if you ever plan a big swarm of enemies in a confined area, one flow field will almost certainly be cheaper than iterated A*.