HeuristicPathfinder<E> mixin Pathfinding

Visits a WeightedWalkable's nodes, finding a best path to a goal node.

Every algorithm that provides generalizable weighted path finding using heuristics can implement this interface to provide a consistent API for finding paths between nodes in a weighted graph-like structure (e.g., a graph, tree, or grid, or any WeightedWalkable implementation), or mix-in (with HeuristicPathfinder) to derive some default implementations by implementing only findBestPathExclusive.

Adapting to a BestPathfinder

HeuristicPathfinder is a specialization of BestPathfinder that uses a heuristic to guide the search for the best path, but as a result does not share the same type signature, as their are scenarios where it would be impossible to derive a heuristic, i.e. a non-target node:

// How would you derive a heuristic for this without specific code?
final goal = Goal.test((node) => node == node.terrain == Tile.water);

However, if you can guarantee that a heuristic can be derived, or have fallbacks for when it cannot, you can use HeuristicPathfinder as a BestPathfinder:

// Adapt A* to a BestPathfinder.
//
// When a `Goal.node` is used, `toNode` is used to derive the heuristic,
// otherwise `orElse` is used. You should consider creating a sealed class
// for your set of heuristics so pattern matching can be used.
final adapted = astar.asBestPathfinder(
  toNode: (target) => GridHeuristic.manhattan(target),
  orElse: (start, goal) => Heuristic.zero(),
);