A* pathfinding.

// A* on a tile map. A character moves up, right, down, or left; every move costs 1.
// '#' is a wall and '.' is open floor.
export const MAX_WIDTH = 32;
export const MAX_HEIGHT = 24;

export type Tile = { x: number; y: number };
// How far the goal still looks: nothing (plain Dijkstra), Manhattan distance, or twice that.
export type Estimate = 'none' | 'manhattan' | 'double';
export type Search = { cost: number | null; path: Tile[]; expanded: Tile[] };

export type TileErrorCode = 'bad-map' | 'bad-estimate' | 'off-map' | 'on-wall';

export class TileError extends Error {
	readonly code: TileErrorCode;
	constructor(code: TileErrorCode, message: string) {
		super(message);
		this.name = 'TileError';
		this.code = code;
	}
}

type Entry = { f: number; h: number; at: number };

// Smaller f first; then smaller h, the tile that looks closer; then reading order, row by row.
const ahead = (a: Entry, b: Entry) =>
	a.f < b.f || (a.f === b.f && (a.h < b.h || (a.h === b.h && a.at < b.at)));

// A binary min-heap: the frontier of tiles reached but not yet expanded.
class Frontier {
	#items: Entry[] = [];
	get size() {
		return this.#items.length;
	}
	push(entry: Entry) {
		const items = this.#items;
		items.push(entry);
		for (let i = items.length - 1; i > 0;) {
			const parent = (i - 1) >> 1;
			if (!ahead(items[i], items[parent])) break;
			[items[i], items[parent]] = [items[parent], items[i]];
			i = parent;
		}
	}
	pop(): Entry {
		const items = this.#items;
		const top = items[0];
		const last = items.pop()!;
		if (items.length > 0) {
			items[0] = last;
			for (let i = 0; ;) {
				let best = i;
				for (const child of [2 * i + 1, 2 * i + 2])
					if (child < items.length && ahead(items[child], items[best])) best = child;
				if (best === i) break;
				[items[i], items[best]] = [items[best], items[i]];
				i = best;
			}
		}
		return top;
	}
}

const MOVES = [
	[0, -1],
	[1, 0],
	[0, 1],
	[-1, 0]
];

export function estimate(kind: Estimate, from: Tile, goal: Tile): number {
	const distance = Math.abs(from.x - goal.x) + Math.abs(from.y - goal.y);
	return kind === 'none' ? 0 : kind === 'manhattan' ? distance : 2 * distance;
}

export function readMap(rows: readonly string[]): { width: number; height: number } {
	const height = rows.length;
	const width = rows[0]?.length ?? 0;
	if (height < 1 || height > MAX_HEIGHT || width < 1 || width > MAX_WIDTH)
		throw new TileError('bad-map', `maps are 1 to ${MAX_WIDTH} wide and 1 to ${MAX_HEIGHT} tall`);
	for (const row of rows)
		if (row.length !== width || !/^[.#]+$/.test(row))
			throw new TileError('bad-map', 'every row has the same width and uses only . and #');
	return { width, height };
}

// The tile must be a whole-number position on the map, on open floor.
export function openTile(rows: readonly string[], tile: Tile, name: string): void {
	const { width, height } = readMap(rows);
	const { x, y } = tile;
	if (!Number.isInteger(x) || !Number.isInteger(y) || x < 0 || y < 0 || x >= width || y >= height)
		throw new TileError('off-map', `the ${name} is off the map`);
	if (rows[y][x] === '#') throw new TileError('on-wall', `the ${name} is on a wall`);
}

function check(rows: readonly string[], kind: Estimate, start: Tile, goal: Tile): number {
	const { width } = readMap(rows);
	if (kind !== 'none' && kind !== 'manhattan' && kind !== 'double')
		throw new TileError('bad-estimate', 'the estimate is none, manhattan, or double');
	openTile(rows, start, 'start');
	openTile(rows, goal, 'goal');
	return width;
}

// Expand tiles in order of f = g + h: g is the moves taken so far, h the estimate still to go.
// An expanded tile is never expanded again, so its g must already be its best.
export function findPath(
	rows: readonly string[],
	start: Tile,
	goal: Tile,
	kind: Estimate = 'manhattan'
): Search {
	const width = check(rows, kind, start, goal);
	const tile = (at: number): Tile => ({ x: at % width, y: Math.floor(at / width) });
	const first = start.y * width + start.x;
	const target = goal.y * width + goal.x;
	const g = new Map<number, number>([[first, 0]]);
	const via = new Map<number, number>();
	const done = new Set<number>();
	const frontier = new Frontier();
	const h0 = estimate(kind, start, goal);
	frontier.push({ f: h0, h: h0, at: first });
	const expanded: Tile[] = [];
	while (frontier.size > 0) {
		const { at } = frontier.pop();
		if (done.has(at)) continue; // a stale entry: this tile was already expanded
		done.add(at);
		const here = tile(at);
		expanded.push(here);
		if (at === target) {
			const path = [here];
			for (let step = at; via.has(step); step = via.get(step)!) path.push(tile(via.get(step)!));
			return { cost: g.get(at)!, path: path.reverse(), expanded };
		}
		for (const [dx, dy] of MOVES) {
			const next = { x: here.x + dx, y: here.y + dy };
			if (next.x < 0 || next.y < 0 || next.x >= width || next.y >= rows.length) continue;
			if (rows[next.y][next.x] === '#') continue;
			const n = next.y * width + next.x;
			const offer = g.get(at)! + 1;
			// Only a strictly shorter offer wins, and an expanded tile gets no offers at all.
			if (!done.has(n) && offer < (g.get(n) ?? Infinity)) {
				g.set(n, offer);
				via.set(n, at);
				const h = estimate(kind, next, goal);
				frontier.push({ f: offer + h, h, at: n }); // an older, worse entry stays and is skipped
			}
		}
	}
	return { cost: null, path: [], expanded };
}

// A* on a tile map. A character moves up, right, down, or left; every move costs 1.
// '#' is a wall and '.' is open floor.
const (
	MaxWidth  = 32
	MaxHeight = 24
)

type Tile struct{ X, Y int }

// Estimate is how far the goal still looks: "none" (plain Dijkstra), "manhattan", or "double".
type Estimate string

type Search struct {
	Found    bool
	Cost     int
	Path     []Tile
	Expanded []Tile
}

type TileError struct{ Code, Message string }

func (e *TileError) Error() string { return e.Message }

type entry struct{ f, h, at int }

// frontier is a min-heap for container/heap: smaller f first; then smaller h, the tile that
// looks closer; then reading order, row by row.
type frontier []entry

func (q frontier) Len() int { return len(q) }
func (q frontier) Less(i, j int) bool {
	if q[i].f != q[j].f {
		return q[i].f < q[j].f
	}
	if q[i].h != q[j].h {
		return q[i].h < q[j].h
	}
	return q[i].at < q[j].at
}
func (q frontier) Swap(i, j int) { q[i], q[j] = q[j], q[i] }
func (q *frontier) Push(x any)   { *q = append(*q, x.(entry)) }
func (q *frontier) Pop() any {
	old := *q
	last := old[len(old)-1]
	*q = old[:len(old)-1]
	return last
}

var moves = [4][2]int{{0, -1}, {1, 0}, {0, 1}, {-1, 0}}

func estimateOf(kind Estimate, from, goal Tile) int {
	distance := abs(from.X-goal.X) + abs(from.Y-goal.Y)
	switch kind {
	case "none":
		return 0
	case "manhattan":
		return distance
	}
	return 2 * distance
}

func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}

func readMap(rows []string) (width, height int, err error) {
	height = len(rows)
	if height > 0 {
		width = len(rows[0])
	}
	if height < 1 || height > MaxHeight || width < 1 || width > MaxWidth {
		return 0, 0, &TileError{"bad-map", fmt.Sprintf("maps are 1 to %d wide and 1 to %d tall", MaxWidth, MaxHeight)}
	}
	for _, row := range rows {
		if len(row) != width {
			return 0, 0, &TileError{"bad-map", "every row has the same width and uses only . and #"}
		}
		for i := 0; i < len(row); i++ {
			if row[i] != '.' && row[i] != '#' {
				return 0, 0, &TileError{"bad-map", "every row has the same width and uses only . and #"}
			}
		}
	}
	return width, height, nil
}

// openTile checks that a tile is on the map and on open floor.
func openTile(rows []string, t Tile, name string) error {
	width, height, err := readMap(rows)
	if err != nil {
		return err
	}
	if t.X < 0 || t.Y < 0 || t.X >= width || t.Y >= height {
		return &TileError{"off-map", "the " + name + " is off the map"}
	}
	if rows[t.Y][t.X] == '#' {
		return &TileError{"on-wall", "the " + name + " is on a wall"}
	}
	return nil
}

func check(rows []string, kind Estimate, start, goal Tile) (int, error) {
	width, _, err := readMap(rows)
	if err != nil {
		return 0, err
	}
	if kind != "none" && kind != "manhattan" && kind != "double" {
		return 0, &TileError{"bad-estimate", "the estimate is none, manhattan, or double"}
	}
	if err := openTile(rows, start, "start"); err != nil {
		return 0, err
	}
	if err := openTile(rows, goal, "goal"); err != nil {
		return 0, err
	}
	return width, nil
}

// FindPath expands tiles in order of f = g + h: g is the moves taken so far, h the estimate
// still to go. An expanded tile is never expanded again, so its g must already be its best.
func FindPath(rows []string, start, goal Tile, kind Estimate) (Search, error) {
	width, err := check(rows, kind, start, goal)
	if err != nil {
		return Search{}, err
	}
	tile := func(at int) Tile { return Tile{at % width, at / width} }
	first, target := start.Y*width+start.X, goal.Y*width+goal.X
	g := map[int]int{first: 0}
	via := map[int]int{}
	done := map[int]bool{}
	h0 := estimateOf(kind, start, goal)
	q := &frontier{{h0, h0, first}}
	var expanded []Tile
	for q.Len() > 0 {
		at := heap.Pop(q).(entry).at
		if done[at] {
			continue // a stale entry: this tile was already expanded
		}
		done[at] = true
		here := tile(at)
		expanded = append(expanded, here)
		if at == target {
			path := []Tile{here}
			for step, ok := via[at]; ok; step, ok = via[step] {
				path = append([]Tile{tile(step)}, path...)
			}
			return Search{true, g[at], path, expanded}, nil
		}
		for _, m := range moves {
			next := Tile{here.X + m[0], here.Y + m[1]}
			if next.X < 0 || next.Y < 0 || next.X >= width || next.Y >= len(rows) || rows[next.Y][next.X] == '#' {
				continue
			}
			n := next.Y*width + next.X
			offer := g[at] + 1
			// Only a strictly shorter offer wins, and an expanded tile gets no offers at all.
			if current, reached := g[n]; !done[n] && (!reached || offer < current) {
				g[n] = offer
				via[n] = at
				h := estimateOf(kind, next, goal)
				heap.Push(q, entry{offer + h, h, n}) // an older, worse entry stays and is skipped
			}
		}
	}
	return Search{false, 0, nil, expanded}, nil
}