aStar<T> function

List<T> aStar<T>(Map<T, Map<T, num>> graph, T start, T goal, num heuristic(T node, T goal), { int maxIterations = 10000, })

A* pathfinding algorithm implementation

graph represents the graph as an adjacency list with edge weights start is the starting node goal is the target node heuristic estimates the cost from a node to the goal maxIterations prevents infinite loops (default: 10000)

Returns a list representing the optimal path from start to goal, or an empty list if no path exists.

Throws ArgumentError if start or goal nodes don't exist in the graph.

Implementation

List<T> aStar<T>(
  Map<T, Map<T, num>> graph,
  T start,
  T goal,
  num Function(T node, T goal) heuristic, {
  int maxIterations = 10000,
}) {
  // Input validation
  if (!graph.containsKey(start)) {
    throw ArgumentError('Start node $start not found in graph');
  }
  if (!graph.containsKey(goal)) {
    throw ArgumentError('Goal node $goal not found in graph');
  }

  // Early exit for same start/goal
  if (start == goal) return [start];

  // Priority queue for frontier (open set)
  final frontier = PriorityQueue<AStarNode<T>>((a, b) => a.compareTo(b));

  // Track g-scores (actual cost from start)
  final gScores = <T, num>{start: 0};

  // Track f-scores (g + heuristic)
  final fScores = <T, num>{start: heuristic(start, goal)};

  // Track parent nodes for path reconstruction
  final cameFrom = <T, T>{};

  // Closed set (already evaluated nodes)
  final closedSet = <T>{};

  // Initialize frontier with start node
  frontier.add(
    AStarNode<T>(node: start, gScore: 0, fScore: heuristic(start, goal)),
  );

  int iterations = 0;

  while (frontier.isNotEmpty && iterations < maxIterations) {
    iterations++;

    // Get node with lowest f-score
    final current = frontier.removeFirst();

    // Skip if already evaluated
    if (closedSet.contains(current.node)) continue;

    // Add to closed set
    closedSet.add(current.node);

    // Check if we reached the goal
    if (current.node == goal) {
      return _reconstructPath(cameFrom, current.node);
    }

    // Explore neighbors
    final neighbors = graph[current.node] ?? {};

    for (final entry in neighbors.entries) {
      final neighbor = entry.key;
      final edgeCost = entry.value;

      // Skip if already evaluated
      if (closedSet.contains(neighbor)) continue;

      // Calculate tentative g-score
      final tentativeGScore = gScores[current.node]! + edgeCost;

      // Check if this path is better than previous ones
      if (!gScores.containsKey(neighbor) ||
          tentativeGScore < gScores[neighbor]!) {
        // Update path information
        cameFrom[neighbor] = current.node;
        gScores[neighbor] = tentativeGScore;

        final fScore = tentativeGScore + heuristic(neighbor, goal);
        fScores[neighbor] = fScore;

        // Add to frontier
        frontier.add(
          AStarNode<T>(
            node: neighbor,
            parent: current.node,
            gScore: tentativeGScore,
            fScore: fScore,
          ),
        );
      }
    }
  }

  // No path found or max iterations exceeded
  if (iterations >= maxIterations) {
    throw StateError(
      'A* algorithm exceeded maximum iterations ($maxIterations)',
    );
  }

  return []; // No path found
}