A* (A-Star) Pathfinding

Speed:

SlowFast

Start

End

Wall

Visited

Current

Path

Operation Logs

No operations yet

Algorithm Info

Time Complexity: O(E) for grid graphs, E = edges

Space Complexity: O(V) for open set and visited set

Optimal: Yes (with admissible heuristic)

Complete: Yes (will find solution if one exists)

How it works: Uses both distance from start (g) and heuristic estimate to end (h), exploring most promising paths first.

Best for: Weighted/unweighted grids, games, navigation, robotics, optimal pathfinding.

Heuristic: Manhattan distance (for grid graphs without diagonals)

Implementation

function astarPathfinding(grid, start, end) {
  const openSet = [start];
  start.g = 0;
  start.f = heuristic(start, end);

  while (openSet.length > 0) {
    // Find node in openSet with lowest f
    let current = openSet.reduce((a, b) => a.f < b.f ? a : b);

    if (current === end) {
      return reconstructPath(end);
    }

    openSet.splice(openSet.indexOf(current), 1);
    current.visited = true;

    for (const neighbor of getNeighbors(current)) {
      if (neighbor.wall || neighbor.visited) continue;
      const tentativeG = current.g + 1;
      if (tentativeG < neighbor.g) {
        neighbor.parent = current;
        neighbor.g = tentativeG;
        neighbor.f = tentativeG + heuristic(neighbor, end);
        if (!openSet.includes(neighbor)) openSet.push(neighbor);
      }
    }
  }
  return null;
}

function heuristic(a, b) {
  return Math.abs(a.row - b.row) + Math.abs(a.col - b.col);
}