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(),
);
Implemented types
Mixin applications

Properties

hashCode → int
The hash code for this object.
no setterinherited
runtimeType → Type
A representation of the runtime type of the object.
no setterinherited

Methods

asBestPathfinder<G extends Goal<E>>({required Heuristic<T> toNode<T extends E>(E), required Heuristic<T> orElse<T extends E>(E, G)}) → BestPathfinder<E>
Adapts this HeuristicPathfinder to a BestPathfinder.
findBestPath<T extends E>(WeightedWalkable<T> graph, T start, Goal<T> goal, Heuristic<T> heuristic, {Tracer<T>? tracer}) → (Path<T>, double)
Returns an optimal path (and it's total cost) in graph from start to a node that satisfies goal.
findBestPathExclusive<T extends E>(WeightedWalkable<T> graph, T start, Goal<T> goal, Heuristic<T> heuristic, {Tracer<T>? tracer}) → (Path<T>, double)
Returns an optimal path (and it's total cost) in graph from start to a node that satisfies goal.
noSuchMethod(Invocation invocation) → dynamic
Invoked when a nonexistent method or property is accessed.
inherited
toString() → String
A string representation of this object.
inherited

Operators

operator ==(Object other) → bool
The equality operator.
inherited