1import test from 'node:test';2import assert from 'node:assert/strict';3import { createGame } from '../src/engine.js';4import { createStateCodec } from '../src/solver/state-codec.js';5import { searchStates } from '../src/solver/search.js';67const level = {8 id: 'search-fixture', width: 4, height: 1,9 objects: [10 { id: 'player', kind: 'object', noun: 'MIAU', x: 0, y: 0 },11 { id: 'flag', kind: 'object', noun: 'FLAG', x: 3, y: 0 },12 ],13};1415function initialState() {16 return createGame(level).getState();17}1819function transition(snapshot, action) {20 if (action !== 'L' && action !== 'R') return { accepted: false };21 const state = structuredClone(snapshot);22 const player = state.objects.find(object => object.id === 'player');23 const nextX = player.x + (action === 'R' ? 1 : -1);24 if (nextX < 0 || nextX >= level.width) return { accepted: false };25 player.x = nextX;26 state.won = player.x === 3;27 return { accepted: true, state, meta: { action } };28}2930function options(overrides = {}) {31 return {32 initial: initialState(),33 codec: createStateCodec(level),34 actions: ['L', 'R'],35 transition,36 ...overrides,37 };38}3940test('returns the shortest path and reconstructs it from parent links', () => {41 const result = searchStates(options());42 assert.equal(result.status, 'solved');43 assert.deepEqual(result.path, ['R', 'R', 'R']);44 assert.equal(result.state.won, true);45 assert.ok(result.attempts > result.path.length);46});4748test('counts attempted transitions and stops at the configured cap', () => {49 const result = searchStates(options({ cap: 2 }));50 assert.equal(result.status, 'limit');51 assert.equal(result.attempts, 2);52 assert.equal(result.reason, 'attempts');53});5455test('limits retained frontier states without treating hash collisions as duplicates', () => {56 const result = searchStates(options({ maxVisited: 2, hash: () => 1 }));57 assert.equal(result.status, 'limit');58 assert.equal(result.reason, 'visited');59 assert.equal(result.visited, 2);60 assert.equal(result.attempts, 4);61 assert.throws(() => searchStates(options({ maxVisited: -1 })), /maxVisited/);62});6364test('prunes duplicate compact identities', () => {65 const result = searchStates(options({66 initial: { ...initialState(), objects: initialState().objects.map(object => object.id === 'flag' ? { ...object, x: 0 } : object) },67 isWin: () => false,68 transition: (snapshot, action) => {69 const result = transition(snapshot, action);70 if (result.state) result.state.won = false;71 return result;72 },73 }));74 assert.equal(result.status, 'exhausted');75 assert.equal(result.visited, 4);76 assert.equal(result.attempts, 8);77});7879test('keeps distinct states even when every compact hash collides', () => {80 const result = searchStates(options({ hash: () => 1 }));81 assert.equal(result.status, 'solved');82 assert.deepEqual(result.path, ['R', 'R', 'R']);83 assert.equal(result.visited, 3);84});8586test('reports a win at the initial state without encoding a terminal snapshot', () => {87 const initial = { ...initialState(), won: true };88 const result = searchStates(options({ initial }));89 assert.equal(result.status, 'solved');90 assert.deepEqual(result.path, []);91 assert.equal(result.attempts, 0);92});9394test('filters accepted transitions before they enter or solve the frontier', () => {95 const result = searchStates(options({96 filter: ({ action }) => action !== 'R',97 cap: 20,98 }));99 assert.equal(result.status, 'exhausted');100 assert.equal(result.visited, 1);101 assert.equal(result.attempts, 2);102});