A* (А-стар)

1function aStar(map: string[], start: P, goal: P): P[] | null {
2  const h = (p: P): number => Math.abs(p.r - goal.r) + Math.abs(p.c - goal.c)
3 
4  const open: P[] = [start]
5  const g = new Map<string, number>([ [key(start), 0] ])
6 
7  while (open.length > 0) {
8    // берём узел с минимальным f = g + h
9    let best = 0
10    for (let i = 1; i < open.length; i++) {
11      if (g.get(key(open[i]!))! + h(open[i]!) < g.get(key(open[best]!))! + h(open[best]!)) best = i
12    }
13    const cur = open.splice(best, 1)[0]!
14 
15    if (cur.r === goal.r && cur.c === goal.c) return reconstruct(cur)
16 
17    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
18      const nr = cur.r + dr, nc = cur.c + dc
19      if (nr < 0 || nr >= map.length || nc < 0 || nc >= map[0].length) continue
20      if (map[nr]![nc] === '#') continue
21 
22      const ng = g.get(key(cur))! + 1
23      if (ng < (g.get(key({ r: nr, c: nc })) ?? Infinity)) {
24        g.set(key({ r: nr, c: nc }), ng)
25        open.push({ r: nr, c: nc })
26      }
27    }
28  }
29  return null
30}
31 
32interface P { r: number; c: number }
33const key = (p: P): string => p.r + ':' + p.c