create a 2d pathfinding algorithm in javascript

index.tsx
function astar(start, end, grid) {
  // The set of nodes already evaluated
  const closedSet = new Set();

  // The set of discovered nodes that haven't been evaluated yet
  const openSet = new Set([start]);

  // A map of nodes to their parent nodes, used to reconstruct the path afterwards
  const cameFrom = new Map();

  // A map of nodes to the cost so far from the start node
  const gScore = new Map([[start, 0]]);

  // A map of nodes to the predicted total cost of reaching the end node from the start node,
  // taking into account the cost so far and the estimated remaining cost
  const fScore = new Map([[start, heuristic(start, end)]]);

  while (openSet.size > 0) {
    // Find the node in the open set with the lowest fScore
    const current = [...openSet].reduce((a, b) => fScore.get(a) < fScore.get(b) ? a : b);

    // If we've reached the end node, reconstruct the path from cameFrom and return it
    if (current === end) {
      return reconstructPath(cameFrom, end);
    }

    openSet.delete(current);
    closedSet.add(current);

    // Consider all the neighbors of the current node
    for (const neighbor of getNeighbors(current, grid)) {
      // Ignore nodes already evaluated
      if (closedSet.has(neighbor)) {
        continue;
      }

      // Tentatively set the gScore for this neighbor node
      const tentativeGScore = gScore.get(current) + 1;

      // Add the neighbor node to the open set if it's not already there
      if (!openSet.has(neighbor)) {
        openSet.add(neighbor);
      } else if (tentativeGScore >= gScore.get(neighbor)) {
        // If we've already found a better path to this neighbor node, skip it
        continue;
      }

      // This path is the best yet, so record it
      cameFrom.set(neighbor, current);
      gScore.set(neighbor, tentativeGScore);
      fScore.set(neighbor, gScore.get(neighbor) + heuristic(neighbor, end));
    }
  }

  // If we've exhausted all options and haven't found a path, return null
  return null;
}

// Calculate a heuristic value for the distance between two nodes
function heuristic(a, b) {
  return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}

// Get the neighbors of a node in a grid
function getNeighbors(node, grid) {
  const neighbors = [];

  for (const [dx, dy] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
    const x2 = node.x + dx;
    const y2 = node.y + dy;

    if (x2 < 0 || x2 >= grid.width || y2 < 0 || y2 >= grid.height) {
      continue;
    }

    const neighbor = grid.nodes[y2][x2];

    if (!neighbor) {
      continue;
    }

    neighbors.push(neighbor);
  }

  return neighbors;
}

// Reconstruct the path from the starting node to the given node using the cameFrom map
function reconstructPath(cameFrom, node) {
  const path = [node];

  while (cameFrom.has(node)) {
    node = cameFrom.get(node);
    path.unshift(node);
  }

  return path;
}
2875 chars
99 lines

index.tsx
const grid = {
  width: 10,
  height: 10,
  nodes: [
    [{x: 0, y: 0}, {x: 1, y: 0}, /* ... */, {x: 9, y: 0}],
    [{x: 0, y: 1}, {x: 1, y: 1}, /* ... */, {x: 9, y: 1}],
    /* ... */
    [{x: 0, y: 9}, {x: 1, y: 9}, /* ... */, {x: 9, y: 9}]
  ]
};

const start = grid.nodes[0][0];
const end = grid.nodes[9][9];

const path = astar(start, end, grid);
352 chars
16 lines