explodorama / files / src / sim / autopilot.ts
autopilot.ts
| 1 | import { isDeadly, type Danger } from './danger' |
| 2 | import { autoMoveAction, playerPath, safeStep } from './path' |
| 3 | import { isValidTarget } from './actions' |
| 4 | import { cellAt, eq, flameSafe, idx, playerCanPass } from './state' |
| 5 | import { DIRS, DIR_LIST, type Action, type GameState, type Vec } from './types' |
| 6 | |
| 7 | /** Up to this many targets the cheapest order is searched exhaustively; beyond, nearest-first. */ |
| 8 | const SEARCH_MAX = 10 |
| 9 | |
| 10 | export interface AutopilotPlan { |
| 11 | /** What it is doing: gathering what lies about, waiting for crates to crumble or bombs to go off, or only the exit is left. */ |
| 12 | phase: 'gather' | 'crates' | 'bombs' | 'exit' |
| 13 | /** Where it is heading now (a coin, charge or gem; the exit), null while it waits for crates or bombs. */ |
| 14 | goal: Vec | null |
| 15 | /** The turn to take, null if there is none that is safe (boxed in, or no way). */ |
| 16 | action: Action | null |
| 17 | } |
| 18 | |
| 19 | /** |
| 20 | * What the autopilot gathers (Q73, user request, 2026-11-02): the place of every drop (coins, |
| 21 | * charges) and every gem lying on open floor. Not the exit: the walk ends there, and the last step |
| 22 | * picks up whatever lies on it. A gem still under a crate is not yet a target. |
| 23 | */ |
| 24 | export function autopilotTargets(s: GameState): Vec[] { |
| 25 | const out: Vec[] = [] |
| 26 | for (const p of [...s.drops.map((d) => d.pos), ...s.gems.filter((g) => cellAt(s, g.pos) === 'floor').map((g) => g.pos)]) { |
| 27 | if (!out.some((q) => eq(q, p))) out.push(p) |
| 28 | } |
| 29 | return out |
| 30 | } |
| 31 | |
| 32 | /** A walk from some tile: its length in turns, how often it turns a corner, and which targets lie on it. */ |
| 33 | interface Leg { |
| 34 | turns: number |
| 35 | corners: number |
| 36 | /** Bit mask of the targets stepped on along the way (the destination's included). */ |
| 37 | hits: number |
| 38 | } |
| 39 | |
| 40 | /** The cost of a leg as one number: turns first, corners only break ties between equal turns. */ |
| 41 | const legCost = (l: Leg): number => l.turns * 10000 + l.corners |
| 42 | |
| 43 | /** The walk from `from` to `to`, null if there is none (the open exit is only ever walked onto as the end). */ |
| 44 | function leg(s: GameState, from: Vec, to: Vec, targets: Vec[]): Leg | null { |
| 45 | const path = playerPath({ ...s, player: from }, to) |
| 46 | if (!path) return null |
| 47 | let corners = 0 |
| 48 | let hits = 0 |
| 49 | let at = from |
| 50 | let heading = '' |
| 51 | for (const p of path) { |
| 52 | const d = `${p.x - at.x},${p.y - at.y}` |
| 53 | if (heading && d !== heading) corners++ |
| 54 | heading = d |
| 55 | at = p |
| 56 | targets.forEach((t, i) => { |
| 57 | if (eq(t, p)) hits |= 1 << i |
| 58 | }) |
| 59 | } |
| 60 | return { turns: path.length, corners, hits } |
| 61 | } |
| 62 | |
| 63 | /** |
| 64 | * The next target: the first of the order that takes the fewest turns in all, ending at the exit |
| 65 | * (Pavel's choice, 2026-11-02: not plain nearest-first, which can zigzag). Distances are real walks |
| 66 | * (`playerPath`, as auto-move walks them); a target lying on the walk to another is collected on |
| 67 | * the way, free. Equal turns: fewer corners (counted inside each walk), then the smaller y, then |
| 68 | * the smaller x, so replays agree. Beyond `SEARCH_MAX` targets: the nearest, by the same tie-breaks. |
| 69 | * `targets` are all reachable from the player. |
| 70 | */ |
| 71 | function nextTarget(s: GameState, targets: Vec[]): Vec { |
| 72 | const n = targets.length |
| 73 | const first = targets.map((t) => leg(s, s.player, t, targets)!) |
| 74 | const byPlace = targets.map((_, i) => i).sort((a, b) => targets[a]!.y - targets[b]!.y || targets[a]!.x - targets[b]!.x) |
| 75 | if (n > SEARCH_MAX) { |
| 76 | let best = byPlace[0]! |
| 77 | for (const i of byPlace) if (legCost(first[i]!) < legCost(first[best]!)) best = i |
| 78 | return targets[best]! |
| 79 | } |
| 80 | const between = targets.map((a) => targets.map((b) => (a === b ? null : leg(s, a, b, targets)))) |
| 81 | const exits = targets.map((t) => leg(s, t, s.exit, targets)) |
| 82 | // With no way to the exit from anywhere (crates still crumbling), only the gathering is ordered. |
| 83 | const toExit = (i: number): number => (exits.every((e) => !e) ? 0 : exits[i] ? legCost(exits[i]!) : Infinity) |
| 84 | const full = (1 << n) - 1 |
| 85 | const memo = new Map<number, number>() |
| 86 | /** The cost of the cheapest finish from target `i` with `done` collected. */ |
| 87 | const rest = (done: number, i: number): number => { |
| 88 | if (done === full) return toExit(i) |
| 89 | const key = done * n + i |
| 90 | const known = memo.get(key) |
| 91 | if (known !== undefined) return known |
| 92 | let best = Infinity |
| 93 | for (let j = 0; j < n; j++) { |
| 94 | const l = between[i]![j] |
| 95 | if (done & (1 << j) || !l) continue |
| 96 | best = Math.min(best, legCost(l) + rest(done | l.hits | (1 << j), j)) |
| 97 | } |
| 98 | // Nothing left can be reached from here: go for the exit. |
| 99 | if (best === Infinity) best = toExit(i) |
| 100 | memo.set(key, best) |
| 101 | return best |
| 102 | } |
| 103 | let best = byPlace[0]! |
| 104 | let bestCost = Infinity |
| 105 | for (const i of byPlace) { |
| 106 | const cost = legCost(first[i]!) + rest(first[i]!.hits | (1 << i), i) |
| 107 | if (cost < bestCost) { |
| 108 | best = i |
| 109 | bestCost = cost |
| 110 | } |
| 111 | } |
| 112 | return targets[best]! |
| 113 | } |
| 114 | |
| 115 | /** |
| 116 | * The way out of a blast zone (Q101): the first step of the shortest walk to a tile that will not |
| 117 | * burn, over tiles the player can pass (not the open exit, which would end the level), the step |
| 118 | * itself one that `safeStep` and `isDeadly` allow. Null if there is none. |
| 119 | */ |
| 120 | function fleeAction(s: GameState, danger: Danger, zone: Set<number>): Action | null { |
| 121 | const key = (p: Vec) => idx(s, p) |
| 122 | const seen = new Set<number>([key(s.player)]) |
| 123 | const queue: { at: Vec; first: Action }[] = [] |
| 124 | const around = (p: Vec) => DIR_LIST.map((d) => ({ x: p.x + DIRS[d].x, y: p.y + DIRS[d].y })) |
| 125 | const open = (q: Vec) => !seen.has(key(q)) && playerCanPass(s, q) && !(s.status === 'playing' && eq(q, s.exit)) |
| 126 | for (const q of around(s.player)) { |
| 127 | if (!open(q)) continue |
| 128 | seen.add(key(q)) |
| 129 | const a: Action = { id: 'move', target: q } |
| 130 | if (isValidTarget(s, 'move', q) && safeStep(s, danger, q) && !isDeadly(s, a)) queue.push({ at: q, first: a }) |
| 131 | } |
| 132 | for (let i = 0; i < queue.length; i++) { |
| 133 | const { at, first } = queue[i]! |
| 134 | if (!zone.has(key(at))) return first |
| 135 | for (const q of around(at)) { |
| 136 | if (!open(q)) continue |
| 137 | seen.add(key(q)) |
| 138 | queue.push({ at: q, first }) |
| 139 | } |
| 140 | } |
| 141 | return null |
| 142 | } |
| 143 | |
| 144 | /** |
| 145 | * The autopilot's turn (Q73): once the last enemy is gone, walk to every coin, charge and gem |
| 146 | * lying about, then to the exit, one ordinary turn at a time, planned afresh each turn from the |
| 147 | * state at hand (flame, bombs and blocked tiles change the next step). Targets with no way to them |
| 148 | * are skipped. While a gem is still under a crate that is crumbling, or the way to the exit is |
| 149 | * shut by crates that are, it waits; so it does while every target is cut off by a bomb still |
| 150 | * ticking or flame still burning (both stop the walk until they are gone). It never steps onto a tile |
| 151 | * a bomb (or a falling ceiling) will burn before it is gone, even where Bomb Pass lets it walk |
| 152 | * through the bomb (Q101, bug mail 2026-11-03); standing in such a zone, it first walks out. Spikes are not part of the zone; they are crossed by timing. The step is auto-move's (`autoMoveAction`: a Run when owned, |
| 153 | * never onto the open exit early, only onto `safeStep` tiles). If there is none, it waits, unless |
| 154 | * waiting kills too: then `action` is null. |
| 155 | */ |
| 156 | export function autopilotPlan(s: GameState, danger: Danger): AutopilotPlan { |
| 157 | const reachable = autopilotTargets(s).filter((t) => playerPath(s, t)) |
| 158 | const wait: Action = { id: 'wait' } |
| 159 | const waitOrNull = (): Action | null => (isDeadly(s, wait) ? null : wait) |
| 160 | if (reachable.length === 0 && s.crumbling.length) { |
| 161 | const coveredGem = s.gems.some((g) => s.crumbling.some((c) => c.cell === idx(s, g.pos))) |
| 162 | // Nothing to fetch yet: a gem uncovered soon, a target still walled in, or no way to the exit. |
| 163 | if (coveredGem || autopilotTargets(s).length > 0 || !playerPath(s, s.exit)) return { phase: 'crates', goal: null, action: waitOrNull() } |
| 164 | } |
| 165 | // A bomb still ticking (or flame still burning) is a wall to the walk: what lies behind it is not lost, it waits. |
| 166 | if (reachable.length === 0 && (s.bombs.length > 0 || s.burning.length > 0) && (autopilotTargets(s).length > 0 || !playerPath(s, s.exit))) { |
| 167 | return { phase: 'bombs', goal: null, action: waitOrNull() } |
| 168 | } |
| 169 | const gathering = reachable.length > 0 |
| 170 | const goal = gathering ? nextTarget(s, reachable) : s.exit |
| 171 | // Everything that will burn if the player waits; harmless to a player who can't be hurt by flame. |
| 172 | // Spikes are left out: they are always up in one turn of two, so they stay in `now` or `next` for |
| 173 | // ever, and their timing is already `safeStep`'s (`danger.now`). |
| 174 | const spikeCells = new Set(s.spikes.map((sp) => sp.cell)) |
| 175 | const zone = flameSafe(s) ? new Set<number>() : new Set([...danger.now, ...danger.next, ...danger.later].filter((i) => !spikeCells.has(i))) |
| 176 | if (zone.has(idx(s, s.player))) { |
| 177 | const out = fleeAction(s, danger, zone) |
| 178 | if (out) return { phase: 'bombs', goal: null, action: out } |
| 179 | } |
| 180 | const action = autoMoveAction(s, goal, (p) => safeStep(s, danger, p) && !zone.has(idx(s, p))) |
| 181 | const usable = action && !isDeadly(s, action) ? action : waitOrNull() |
| 182 | const temporary = s.bombs.length > 0 || s.burning.length > 0 || s.smoldering.length > 0 || s.collapsing.length > 0 |
| 183 | if (!action && zone.size > 0 && temporary) return { phase: 'bombs', goal: null, action: usable } |
| 184 | return { phase: gathering ? 'gather' : 'exit', goal, action: usable } |
| 185 | } |