findBestPathExclusive<T extends E> method

  1. @override
(Path<T>, double) findBestPathExclusive<T extends E>(
  1. WeightedWalkable<T> graph,
  2. T start,
  3. Goal<T> goal,
  4. Heuristic<T> heuristic, {
  5. Tracer<T>? tracer,
})
override

Returns an optimal path (and it's total cost) in graph from start to a node that satisfies goal.

Unlike findBestPath, this method does not check if the goal is initially satisfied by the start node, although it may be satisfied by the start node if it is an eventual successor of itself (i.e. a cycle in the graph).

If the path is not found, the total cost will be double.infinity.

If no path can be found, Path.notFound is returned.

A node will never be included in the path more than once, as determined by Object.== on the node, unless the source node is also a successor of itself, in which case it will be included twice (once at the beginning and once at the end), otherwise it will only be included at the start.

Impassable Nodes

There are two ways to represent impassable nodes in a graph:

  • Omit the node from the graph entirely, i.e. no edge leads to it;
  • Calculate the weight of the edge to the node as double.infinity.

Tracing

May provide a tracer to capture finer-detail events during the traversal.

If omitted, no tracing is performed.

Example

final graph = WeightedWalkable.from({
  'a': [('b', 1.0), ('c', 2.0)],
  'b': [('c', 3.0)],
  'c': [('a', 4.0)],
});

final (path, cost) = astar.findBestPathExclusive(graph, 'a', Goal.node('d'));
print(path); // Path(['a', 'c', 'd'])
print(cost); // 6.0

Implementation

@override
(Path<T> path, double cost) findBestPathExclusive<T extends E>(
  WeightedWalkable<T> graph,
  T start,
  Goal<T> goal,
  Heuristic<T> heuristic, {
  Tracer<T>? tracer,
}) {
  final initialNode = start;
  final path = <T>[];
  final visited = HashSet<T>();
  var totalCost = 0.0;

  while (true) {
    // Edge-case: Don't revisit the initial node unless it's the goal.
    if (path.length == 1 && !goal.success(initialNode)) {
      visited.add(initialNode);
    }
    final neighbors = [
      for (final next in graph.successors(start))
        if (next.$2 < double.infinity)
          (
            next.$1,
            next.$2,
            heuristic.estimateTotalCost(next.$1),
          ),
    ];
    if (neighbors.isEmpty) {
      break;
    }

    // Find the neighbor with the lowest estimated cost.
    neighbors.sort((a, b) => a.$3.compareTo(b.$3));

    double? nextWeight;
    for (final (next, weight, heuristic) in neighbors) {
      if (!visited.add(next)) {
        tracer?.onSkip(next);
        continue;
      }

      path.add(start);
      tracer?.onVisit(start);

      start = next;
      nextWeight = weight;
      tracer?.pushScalar(TraceKey.heuristic, heuristic);
      break;
    }

    if (nextWeight == null) {
      break;
    }
    totalCost += nextWeight;
    if (goal.success(start)) {
      path.add(start);
      return (Path(path), totalCost);
    }
  }

  return (Path.notFound, double.infinity);
}