countPaths<T> function Pathfinding

int countPaths<T>(
  1. WalkableBase<T> walkable, {
  2. required T start,
  3. required Goal<T> goal,
  4. Tracer<T>? tracer,
})

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

There must be no loops in the graph, or a CycleException may be thrown.

Example

On a 8x8 chess board, find total paths from the top-left to bottom-right:

final graph = Grid.filled(8, 8, empty: 0, fill: 1);

final paths = countPaths(
  graph.asUnweighted(),
  start: graph.topLeft,
  goal: Goal.node(graph.bottomRight),
);

print(paths); // 3432

Implementation

int countPaths<T>(
  WalkableBase<T> walkable, {
  required T start,
  required Goal<T> goal,
  Tracer<T>? tracer,
}) {
  return _cachedCountPaths(
    walkable.asUnweighted(),
    start: start,
    goal: goal,
    tracer: tracer,
    cache: HashMap<T, int>(),
  );
}