⭐ A* (A-Star) Pathfinding Algorithm

class AStarPathfinder {
  constructor(maze, heuristic = 'manhattan') {
    this.maze = maze;
    this.width = maze[0].length;
    this.height = maze.length;
    this.heuristic = this.getHeuristicFunction(heuristic);
  }

  findPath(start, goal) {
    const openSet = new PriorityQueue();
    const closedSet = new Set();
    const gScore = new Map();
    const fScore = new Map();
    const cameFrom = new Map();

    const startKey = `${start.x},${start.y}`;
    const goalKey = `${goal.x},${goal.y}`;

    gScore.set(startKey, 0);
    fScore.set(startKey, this.heuristic(start, goal));
    openSet.enqueue(start, fScore.get(startKey));

    while (!openSet.isEmpty()) {
      const current = openSet.dequeue();
      const currentKey = `${current.x},${current.y}`;

      if (currentKey === goalKey) {
        return this.reconstructPath(cameFrom, current);
      }

      closedSet.add(currentKey);

      for (const neighbor of this.getNeighbors(current)) {
        const neighborKey = `${neighbor.x},${neighbor.y}`;
        
        if (closedSet.has(neighborKey)) continue;

        const tentativeGScore = gScore.get(currentKey) + this.getDistance(current, neighbor);

        if (!gScore.has(neighborKey) || tentativeGScore < gScore.get(neighborKey)) {
          cameFrom.set(neighborKey, current);
          gScore.set(neighborKey, tentativeGScore);
          fScore.set(neighborKey, tentativeGScore + this.heuristic(neighbor, goal));

          if (!openSet.contains(neighbor)) {
            openSet.enqueue(neighbor, fScore.get(neighborKey));
          }
        }
      }
    }

    return null; // No path found
  }

  getHeuristicFunction(type) {
    switch (type) {
      case 'manhattan':
        return (a, b) => Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
      case 'euclidean':
        return (a, b) => Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));
      case 'chebyshev':
        return (a, b) => Math.max(Math.abs(a.x - b.x), Math.abs(a.y - b.y));
      default:
        return (a, b) => Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
    }
  }

  getNeighbors(node) {
    const neighbors = [];
    const directions = [
      { x: 0, y: -1 }, // Up
      { x: 1, y: 0 },  // Right
      { x: 0, y: 1 },  // Down
      { x: -1, y: 0 }  // Left
    ];

    for (const dir of directions) {
      const newX = node.x + dir.x;
      const newY = node.y + dir.y;

      if (this.isValidMove(node.x, node.y, newX, newY)) {
        neighbors.push({ x: newX, y: newY });
      }
    }

    return neighbors;
  }

  isValidMove(fromX, fromY, toX, toY) {
    // Check bounds
    if (toX < 0 || toX >= this.width || toY < 0 || toY >= this.height) {
      return false;
    }

    // Check wall between cells (maze-specific logic)
    const fromCell = this.maze[fromY][fromX];
    
    if (toX > fromX && fromCell.right) return false; // Moving right
    if (toX < fromX && fromCell.left) return false;  // Moving left
    if (toY > fromY && fromCell.bottom) return false; // Moving down
    if (toY < fromY && fromCell.top) return false;   // Moving up

    return true;
  }

  reconstructPath(cameFrom, current) {
    const path = [current];
    let currentKey = `${current.x},${current.y}`;

    while (cameFrom.has(currentKey)) {
      current = cameFrom.get(currentKey);
      path.unshift(current);
      currentKey = `${current.x},${current.y}`;
    }

    return path;
  }
}