Implementing A* Pathfinding Algorithm

const aStar = (grid, start, end) => {
  const openSet = [start];
  const cameFrom = new Map();
  const gScore = new Map().set(start, 0);
  const fScore = new Map().set(start, heuristic(start, end));

  while (openSet.length > 0) {
    const current = openSet.reduce((a, b) => fScore.get(a) < fScore.get(b) ? a : b);
    if (current === end) return reconstructPath(cameFrom, current);

    openSet.splice(openSet.indexOf(current), 1);
    const neighbors = getNeighbors(current, grid);

    for (const neighbor of neighbors) {
      const tentativeGScore = gScore.get(current) + 1;
      if (tentativeGScore < (gScore.get(neighbor) || Infinity)) {
        cameFrom.set(neighbor, current);
        gScore.set(neighbor, tentativeGScore);
        fScore.set(neighbor, gScore.get(neighbor) + heuristic(neighbor, end));
        if (!openSet.includes(neighbor)) openSet.push(neighbor);
      }
    }
  }
  return null;
};

function manhattanDistance(x1, y1, x2, y2) {
  return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}

// Example usage
const distance = manhattanDistance(1, 2, 4, 6);
console.log(distance); // Output: 7

const calculateHeuristic = (node, goal) => {
  const dx = Math.abs(node.x - goal.x);
  const dy = Math.abs(node.y - goal.y);
  return Math.sqrt(dx * dx + dy * dy);
};

// Example usage
const startNode = { x: 0, y: 0 };
const goalNode = { x: 3, y: 4 };
console.log(calculateHeuristic(startNode, goalNode)); // Output: 5

function manhattanDistance(nodeA, nodeB) {
  return Math.abs(nodeA.x - nodeB.x) + Math.abs(nodeA.y - nodeB.y);
}

function euclideanDistance(nodeA, nodeB) {
  return Math.sqrt(
    Math.pow(nodeA.x - nodeB.x, 2) + Math.pow(nodeA.y - nodeB.y, 2)
  );
}

function manhattanDistance(nodeA, nodeB) {
  return Math.abs(nodeA.x - nodeB.x) + Math.abs(nodeA.y - nodeB.y);
}

// Consistent check:
// h(n) ≤ c(n, n') + h(n')
// Manhattan distance satisfies this property

const openSet = new PriorityQueue();
const closedSet = new Set();

// Initialize
openSet.enqueue(startNode, startNode.f);

while (!openSet.isEmpty()) {
  const currentNode = openSet.dequeue();
  closedSet.add(currentNode);

  if (currentNode === goalNode) {
    // Path found
    return reconstructPath(currentNode);
  }

  for (const neighbor of getNeighbors(currentNode)) {
    if (!closedSet.has(neighbor)) {
      const tentativeG = currentNode.g + distance(currentNode, neighbor);
      
      if (tentativeG < neighbor.g) {
        neighbor.parent = currentNode;
        neighbor.g = tentativeG;
        neighbor.f = neighbor.g + neighbor.h;

        if (!openSet.contains(neighbor)) {
          openSet.enqueue(neighbor, neighbor.f);
        } else {
          openSet.update(neighbor, neighbor.f);
        }
      }
    }
  }
}

const pq = new PriorityQueue();
pq.insert({ node: 'A', fScore: 5 }, 5);
const next = pq.extractMin(); // Returns { node: 'A', fScore: 5 }

const reconstructPath = (cameFrom, current) => {
  const path = [current];
  while (cameFrom.has(current)) {
    current = cameFrom.get(current);
    path.push(current);
  }
  return path.reverse();
};

function bidirectionalAStar(graph, startNode, goalNode) {
  const forwardOpenSet = new PriorityQueue();
  const backwardOpenSet = new PriorityQueue();
  const forwardClosedSet = new Set();
  const backwardClosedSet = new Set();

  // Initialize forward search
  forwardOpenSet.enqueue(startNode, heuristic(startNode, goalNode));
  const forwardCameFrom = new Map();
  const forwardGScore = new Map();
  forwardGScore.set(startNode, 0);

  // Initialize backward search
  backwardOpenSet.enqueue(goalNode, heuristic(goalNode, startNode));
  const backwardCameFrom = new Map();
  const backwardGScore = new Map();
  backwardGScore.set(goalNode, 0);

  while (!forwardOpenSet.isEmpty() && !backwardOpenSet.isEmpty()) {
    const currentForward = forwardOpenSet.dequeue();
    const currentBackward = backwardOpenSet.dequeue();

    if (forwardClosedSet.has(currentForward) || backwardClosedSet.has(currentBackward)) {
      continue;
    }

    forwardClosedSet.add(currentForward);
    backwardClosedSet.add(currentBackward);

    // Check for intersection
    if (forwardClosedSet.has(currentBackward) || backwardClosedSet.has(currentForward)) {
      const intersectionNode = findIntersection(forwardClosedSet, backwardClosedSet);
      return reconstructPath(intersectionNode, forwardCameFrom, backwardCameFrom);
    }

    // Expand forward search
    for (const neighbor of graph.getNeighbors(currentForward)) {
      if (!forwardClosedSet.has(neighbor)) {
        const tentativeGScore = forwardGScore.get(currentForward) + graph.getDistance(currentForward, neighbor);
        if (tentativeGScore < (forwardGScore.get(neighbor) || Infinity)) {
          forwardCameFrom.set(neighbor, currentForward);
          forwardGScore.set(neighbor, tentativeGScore);
          const fScore = tentativeGScore + heuristic(neighbor, goalNode);
          forwardOpenSet.enqueue(neighbor, fScore);
        }
      }
    }

    // Expand backward search
    for (const neighbor of graph.getNeighbors(currentBackward)) {
      if (!backwardClosedSet.has(neighbor)) {
        const tentativeGScore = backwardGScore.get(currentBackward) + graph.getDistance(currentBackward, neighbor);
        if (tentativeGScore < (backwardGScore.get(neighbor) || Infinity)) {
          backwardCameFrom.set(neighbor, currentBackward);
          backwardGScore.set(neighbor, tentativeGScore);
          const fScore = tentativeGScore + heuristic(neighbor, startNode);
          backwardOpenSet.enqueue(neighbor, fScore);
        }
      }
    }
  }

  return null; // No path found
}

function aStar(grid, start, end) {
  const openSet = [new Node(start.x, start.y, 0, heuristic(start, end))];
  const closedSet = [];

  while (openSet.length > 0) {
    openSet.sort((a, b) => a.f - b.f);
    const current = openSet.shift();

    if (current.x === end.x && current.y === end.y) {
      return reconstructPath(current);
    }

    closedSet.push(current);

    const neighbors = getNeighbors(current, grid);
    for (const neighbor of neighbors) {
      if (closedSet.includes(neighbor)) continue;

      const tentativeG = current.g + 1;
      if (tentativeG < neighbor.g || !openSet.includes(neighbor)) {
        neighbor.parent = current;
        neighbor.g = tentativeG;
        neighbor.h = heuristic(neighbor, end);
        neighbor.f = neighbor.g + neighbor.h;

        if (!openSet.includes(neighbor)) {
          openSet.push(neighbor);
        }
      }
    }
  }

  return null;
}

function jump(node, direction) {
  const next = node.move(direction);
  if (!isValid(next)) return null;
  if (isGoal(next)) return next;
  
  // Check for jump points in the direction
  if (hasObstacle(next, direction)) {
    return next;
  }
  
  // Continue in same direction
  return jump(next, direction);
}