{ grid: "empty"|"wall"|"start"|"end"[][], start: [r,c], end: [r,c] }
1function AStar(grid, start, end):2 openSet = {start}3 gScore[start] = 04 fScore[start] = heuristic(start, end)5 while openSet not empty:6 current = node in openSet with lowest fScore7 if current == end:8 return reconstructPath()9 move current to closedSet10 for each neighbor of current:11 tentative_g = gScore[current] + 112 if tentative_g < gScore[neighbor]:13 update cameFrom, gScore, fScore14 add neighbor to openSet
1function astar(grid: number[][], start: [number,number], end: [number,number]) {2 const open = new Set<string>([key(start)]);3 const gScore = new Map<string, number>([[key(start), 0]]);4 const fScore = new Map<string, number>([[key(start), manhattan(start, end)]]);5 const cameFrom = new Map<string, string>();67 while (open.size > 0) {8 const current = [...open].reduce((a, b) =>9 (fScore.get(a) ?? Infinity) < (fScore.get(b) ?? Infinity) ? a : b10 );11 if (current === key(end)) return reconstructPath(cameFrom, current);12 open.delete(current);1314 for (const [dr, dc] of [[0,1],[0,-1],[1,0],[-1,0]]) {15 const [nr, nc] = [r + dr, c + dc];16 if (outOfBounds(nr, nc) || grid[nr][nc] === 1) continue;17 const tg = (gScore.get(current) ?? Infinity) + 1;18 if (tg < (gScore.get(key([nr,nc])) ?? Infinity)) {19 cameFrom.set(key([nr,nc]), current);20 gScore.set(key([nr,nc]), tg);21 fScore.set(key([nr,nc]), tg + manhattan([nr,nc], end));22 open.add(key([nr,nc]));23 }24 }25 }26 return null;27}