Flood fill to find shortest path which satisfies constraint

General
1

Having used the AB pathfinder and the Random path a lot, I’ve been thinking for a while about how useful it would be to be able to flood fill in order to find the shortest path to a node which satisfies some constraint. For example: an entity is in a room that is on fire and wants to escape. It could use this pathfinder to create the shortest path to a node which is not on fire. Or, conversely, an entity wants to get within a certain range of some type of object (without knowing precisely which object would be the easiest to reach) - again it could use this kind of pathfinder.

Is there a way of doing this with any of the existing pathfinders? I guess this is just Dijkstra’s algorithm which terminates when it finds a path to a node which satisfies the condition? If that’s not possible using the existing pathfinders, how hard would it be to write a custom pathfinder that does this?

Thanks!

  • A* version: [enter version here] 5.4.4
  • Unity version: [enter version here] 6.3
2

Hi

Yes, you could use pathEndingCondition ABPath - A* Pathfinding Project

var path = ABPath.Construct(agent.position, agent.position, null);
path.heuristic = Heuristic.None; // Use Dijkstra
path.endingCondition = new MyCustomEndingCondition(...);
AstarPath.StartPath(path); // or use Seeker.StartPath, or ai.SetPath

See also PathEndingCondition - A* Pathfinding Project

3

That’s great, I will try that. Thanks Aron.