Pathfinding topic

Pathfinding algorithms and utilities structured over Walkable and WeightedWalkables.

---

Table of Contents:

• Finding a Path
• Directed Graphs
• Weighted Graphs
  • Heuristics
  • Picking a Heuristic
  • Writing a Heuristic

---

Finding a Path

Pathfinding algorithms are implemented as a Pathfinder interface (or mixin), which is a function that takes a Walkable, a start node, and teh concept of a Goal (which can be a single node, a set of nodes, or a function that determines if a node is a goal):

final graph = Walkable.linear(['a', 'b', 'c']);

final path = breadthFirstSearch(graph, 'a', Goal.node('c'));
print(path); // Path(['a', 'b', 'c'])

Directed Graphs

Every Graph (and Walkable) implementation is always directed (even undirected graphs are represented as directed graphs with two edges for each undirected edge), so every Pathfinder algorithm is designed to work with any graph type without adaptation:

• BFS, breadthFirstSearch: explore nearest successors first, then widen the search.
• DFS, depthFirstSearch: explore a path as far as possible before backtracking.
• IDDFS, iterativeDepthFirstSearch: explore longer and longer paths at the cost of similar reexaminations.

Weighted Graphs

While breadth-first search finds the shortest path in an unweighted graph, it is not guaranteed to find the shortest path in a weighted graph, where edges have a non-uniform cost. Weighted searches use the BestPathfinder, of which the only implementation is dijkstra:

• Dijkstra, dijkstra: find the shortest path in a weighted graph.

Note

Dijkstra's algorithm is exhaustive, and can be slow for large graphs.

Heuristics

Some graph algorithms can optimize on Dijkstra's algorithm by using a heuristic to guide the search, which is an estimate of minimum cost to reach the target node or goal. The canonical heuristic search algorithm is astar, which implements HeuristicPathfinder:

• A*, astar: find the shortest path in a weighted graph using a heuristic.

However, as with Dijkstra's algorithm, A* can be slow for large graphs. Other heuristic search algorithms are available:

• Greedy, greedy: find the shortest path in a weighted graph using a heuristic, with a focus on speed.
• Fringe, fringe: find the shortest path in a weighted graph using a heuristic, with a focus on performance.

Picking a Heuristic

A heuristic is a function that takes a node and returns an estimate of the minimum cost to reach the goal.

For grid-based graphs, built-in GridHeuristic implementations are available:

• Manhattan, GridHeuristic.manhattan: estimate the minimum cost to reach the goal using the Manhattan distance.
• Diagonal, GridHeuristic.diagonal: estimate the minimum cost to reach the goal using the Diagonal distance.
• Chebyshev, GridHeuristic.chebyshev: estimate the minimum cost to reach the goal using the Chebyshev distance.
• Euclidean, GridHeuristic.euclidean: estimate the minimum cost to reach the goal using the Euclidean distance.

The heuristics can be further tweaked by applying a ratio, which is a multiplier applied to the heuristic value. For example, a ratio of 1.0 is the default heuristic, a ratio of 0.0 is equivalent to Dijkstra's algorithm, and a much higher ratio approaches a greedy search.

final heuristic = GridHeuristic.manhattan(ratio: 2.0);

Writing a Heuristic

When tweaking heuristics, or writing your own, following guidelines can help optimize the search.

Given h(n), the heuristic, and g(n), the (unknown) actual cost:

Heuristic	Optimality Guarantee	Performance
h(n) == 0	Yes ^1	Potentially slower
h(n) <= g(n)	Yes	Varies (slower with lower h(n))
h(n) == g(n)	Yes	Fastest possible
h(n) > g(n)	No	Faster
h(n) > g(n), always	No ^2	Very fast

^1: Abecomes Dijsktra's algorithm. ^2: A becomes Greedy Best-First Search.

For example, the Manhattan heuristic is h(n) = |x1 - x2| + |y1 - y2|, which is admissible (never overestimates the cost as long as the standard moves are 1.0), and consistent (the cost of moving from n to n' is always less than or equal to h(n) - h(n')).

Other heuristics may not be admissible or consistent, but can still be useful.

See also: www.redblobgames.com/pathfinding/a-star/introduction.html#heuristics.

Classes

Astar<E>

Pathfinding algorithm that finds an optimal shortest path using a heuristic.

BreadthFirstSearch<E>

Pathfinding algorithm that search the shallowest nodes in a graph first.

DepthFirstSearch<E>

Pathfinding algorithm that explores the graph in depth first order.

Dijkstra<E>

Pathfinding algorithm that finds the best path in a weighted graph.

FringeAstar<E>

Pathfinding algorithm that finds an optimal shortest path using a heuristic.

Goal<T>

Represents a goal in a pathfinding algorithm.

GreedyBestFirstSearch<E>

Pathfinding algorithm that chooses the locally optimal path at each step.

GridHeuristic

A heuristic that estimates the minimum total cost of reaching a Pos goal.

Heuristic<T>

A heuristic estimates the minimum total cost of reaching a Goal.

Path<T>

A representation of a path in a graph.

Mixins

BestPathfinder<E>

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

HeuristicPathfinder<E>

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

Pathfinder<E>

Visits a Walkable's node, finding one or more paths to a goal node.

Constants

astar → const Astar<Object?>

Pathfinding algorithm that finds an optimal shortest path using a heuristic.

breadthFirstSearch → const BreadthFirstSearch<Object?>

Pathfinding algorithm that search the shallowest nodes in a graph first.

depthFirstSearch → const DepthFirstSearch<Object?>

Pathfinding algorithm that explores the graph in depth first order.

dijkstra → const Dijkstra<Object?>

Pathfinding algorithm that finds the best path in a weighted graph.

fringeAstar → const FringeAstar<Object?>

Pathfinding algorithm that finds an optimal shortest path using a heuristic.

greedyBestFirstSearch → const GreedyBestFirstSearch<Object?>

Pathfinding algorithm that chooses the locally optimal path at each step.

Functions

countPaths<T>(WalkableBase<T> walkable, {required T start, required Goal<T> goal, Tracer<T>? tracer}) → int

Counts the total number of paths from start to a goal in a walkable.