fuzzyworld

basin / files / src / model / puzzle.test.ts

puzzle.test.ts

12.8 KB · history · blame

1import { describe, it, expect } from 'vitest';
2import {
3 generatePuzzle,
4 isSolutionSpring,
5 encodeConfig,
6 decodeConfig,
7 normalizeConfig,
8 randomConfig,
9 SIZE_MIN,
10 SIZE_MAX,
11 SPRINGS_MIN,
12 SPRINGS_MAX,
13 EROSION_MAX,
14 REACH_MIN,
15 REACH_MAX,
16 REACH_DEFAULT,
17} from './puzzle';
18import type { Config } from './puzzle';
19import { simulateFlows } from './flow';
20import { heightAt, isOceanEdge, ALL_OCEAN } from './heightmap';
21import type { Edges } from './heightmap';
22
23const SIZE = 12;
24const COUNT = 3;
25const CANYON: Edges = { n: 'wall', e: 'ocean', s: 'wall', w: 'ocean' };
26
27const cfg = (over: Partial<Config> = {}): Config => ({
28 size: SIZE,
29 springCount: COUNT,
30 edges: ALL_OCEAN,
31 erosion: 0,
32 reach: REACH_DEFAULT,
33 terrainSeed: 4242,
34 ...over,
35});
36
37describe('generatePuzzle', () => {
38 it('is deterministic in its config', () => {
39 const a = generatePuzzle(cfg());
40 const b = generatePuzzle(cfg());
41 expect(a.solution).toEqual(b.solution);
42 expect(Array.from(a.target)).toEqual(Array.from(b.target));
43 });
44
45 it('honours the requested size, edges, and spring count', () => {
46 for (const seed of [1, 7, 55, 1000, 999999]) {
47 const p = generatePuzzle(cfg({ size: 10, springCount: 4, edges: CANYON, terrainSeed: seed }));
48 expect(p.width).toBe(10);
49 expect(p.height).toBe(10);
50 expect(p.edges).toEqual(CANYON);
51 expect(p.solution).toHaveLength(4);
52
53 const seen = new Set<string>();
54 for (const s of p.solution) {
55 expect(s.x).toBeGreaterThan(0);
56 expect(s.y).toBeGreaterThan(0);
57 expect(s.x).toBeLessThan(9);
58 expect(s.y).toBeLessThan(9);
59 seen.add(`${s.x},${s.y}`);
60 }
61 expect(seen.size).toBe(4); // distinct
62 }
63 });
64
65 it("target marks exactly the solution flow's wet ocean-edge cells", () => {
66 for (const seed of [1, 7, 55, 1000, 999999]) {
67 const p = generatePuzzle(cfg({ edges: CANYON, terrainSeed: seed }));
68 const flow = simulateFlows(p.hm, p.solution);
69 for (let y = 0; y < SIZE; y++) {
70 for (let x = 0; x < SIZE; x++) {
71 const i = y * SIZE + x;
72 const shouldBeWet = isOceanEdge(p.edges, x, y, SIZE, SIZE) && flow.wet[i] === 1;
73 expect(p.target[i] === 1).toBe(shouldBeWet);
74 }
75 }
76 }
77 });
78
79 it('produces a non-empty target (the puzzle is solvable/visible)', () => {
80 for (const seed of [1, 7, 55, 1000, 999999]) {
81 const p = generatePuzzle(cfg({ terrainSeed: seed }));
82 expect(p.targetOutflow.length).toBeGreaterThan(0);
83 }
84 });
85
86 it('yields an unambiguous solution: no other spring set reproduces the target', () => {
87 // Brute-force every size-`springCount` set of interior cells and confirm the
88 // generator's solution is the *only* one whose outflow matches the target —
89 // i.e. the gold-edge hint pins down a single answer.
90 const size = 9;
91 const springCount = 2;
92 for (const seed of [1, 7, 55, 1000, 999999, 271828]) {
93 const p = generatePuzzle(cfg({ size, springCount, edges: ALL_OCEAN, terrainSeed: seed }));
94 const target = new Set(p.targetOutflow.map((c) => `${c.x},${c.y}`));
95
96 const interior: Array<{ x: number; y: number }> = [];
97 for (let y = 1; y < size - 1; y++) {
98 for (let x = 1; x < size - 1; x++) interior.push({ x, y });
99 }
100
101 const matches: Array<Set<string>> = [];
102 for (let a = 0; a < interior.length; a++) {
103 for (let b = a + 1; b < interior.length; b++) {
104 const set = [interior[a], interior[b]];
105 const out = simulateFlows(p.hm, set).outflow.map((c) => `${c.x},${c.y}`);
106 if (out.length === target.size && out.every((k) => target.has(k))) {
107 matches.push(new Set(set.map((c) => `${c.x},${c.y}`)));
108 }
109 }
110 }
111
112 expect(matches).toHaveLength(1);
113 expect(matches[0]).toEqual(new Set(p.solution.map((c) => `${c.x},${c.y}`)));
114 }
115 });
116});
117
118describe('isSolutionSpring', () => {
119 it('recognises solution cells and rejects others', () => {
120 const p = generatePuzzle(cfg({ terrainSeed: 321 }));
121 for (const s of p.solution) expect(isSolutionSpring(p, s)).toBe(true);
122
123 const solutionKeys = new Set(p.solution.map((s) => `${s.x},${s.y}`));
124 let checked = false;
125 for (let y = 1; y < SIZE - 1 && !checked; y++) {
126 for (let x = 1; x < SIZE - 1; x++) {
127 if (!solutionKeys.has(`${x},${y}`)) {
128 expect(isSolutionSpring(p, { x, y })).toBe(false);
129 checked = true;
130 break;
131 }
132 }
133 }
134 expect(checked).toBe(true);
135 });
136});
137
138describe('config code', () => {
139 it('round-trips through encode/decode', () => {
140 const configs: Config[] = [
141 cfg(),
142 cfg({ size: 5, springCount: 1, edges: { n: 'wall', e: 'wall', s: 'wall', w: 'ocean' } }),
143 cfg({ size: 20, springCount: 6, edges: CANYON, terrainSeed: 0xffffffff }),
144 cfg({ terrainSeed: 0 }),
145 cfg({ erosion: 1 }),
146 cfg({ erosion: EROSION_MAX, size: 16, springCount: 4 }),
147 ];
148 for (const c of configs) {
149 const code = encodeConfig(c);
150 expect(code).toHaveLength(9);
151 expect(decodeConfig(code)).toEqual(normalizeConfig(c));
152 }
153 });
154
155 it('returns null for codes of the wrong length or alphabet', () => {
156 for (const bad of ['', 'abc', 'AAAAAAAA', 'AAAAAAAAAA', '!!!!!!!!!', 'BQAr3k9 f']) {
157 expect(decodeConfig(bad)).toBeNull();
158 }
159 });
160
161 it('rejects the pre-reach 8-char code format (breaking format bump)', () => {
162 expect(decodeConfig('BQAr3kf9')).toBeNull();
163 });
164
165 it('normalises out-of-range and all-wall configs', () => {
166 const clamped = normalizeConfig(
167 cfg({ size: 999, springCount: 999, edges: { n: 'wall', e: 'wall', s: 'wall', w: 'wall' } }),
168 );
169 expect(clamped.size).toBe(SIZE_MAX);
170 expect(clamped.springCount).toBe(SPRINGS_MAX);
171 // All-wall is illegal (no exit) → at least one side forced ocean.
172 const sides = [clamped.edges.n, clamped.edges.e, clamped.edges.s, clamped.edges.w];
173 expect(sides).toContain('ocean');
174
175 const tiny = normalizeConfig(cfg({ size: -3, springCount: 0 }));
176 expect(tiny.size).toBe(SIZE_MIN);
177 expect(tiny.springCount).toBe(SPRINGS_MIN);
178 });
179
180 it('clamps erosion into range and defaults a missing value to 0', () => {
181 expect(normalizeConfig(cfg({ erosion: 999 })).erosion).toBe(EROSION_MAX);
182 expect(normalizeConfig(cfg({ erosion: -5 })).erosion).toBe(0);
183 // Older codes predate erosion, so decoding must land on a pristine board.
184 const legacy = cfg();
185 delete (legacy as Partial<Config>).erosion;
186 expect(normalizeConfig(legacy).erosion).toBe(0);
187 });
188
189 it('clamps reach into range and defaults a missing value to REACH_DEFAULT', () => {
190 expect(normalizeConfig(cfg({ reach: 999 })).reach).toBe(REACH_MAX);
191 expect(normalizeConfig(cfg({ reach: -5 })).reach).toBe(REACH_MIN);
192 const legacy = cfg();
193 delete (legacy as Partial<Config>).reach;
194 expect(normalizeConfig(legacy).reach).toBe(REACH_DEFAULT);
195 });
196});
197
198describe('erosion (aging)', () => {
199 it('leaves a pristine (erosion 0) board bit-for-bit unchanged', () => {
200 // Backward compatibility: adding the erosion axis must not consume rng when
201 // it is 0, so every previously-shared code reproduces its exact board.
202 const pristine = generatePuzzle(cfg({ erosion: 0, terrainSeed: 777 }));
203 const aged = generatePuzzle(cfg({ erosion: 5, terrainSeed: 777 }));
204 expect(Array.from(aged.hm.data)).not.toEqual(Array.from(pristine.hm.data));
205 });
206
207 it('keeps the drainage invariant and ocean edges at 0 after aging', () => {
208 for (const erosion of [1, 5, 10, EROSION_MAX]) {
209 for (const seed of [1, 42, 12345]) {
210 const p = generatePuzzle(cfg({ size: 14, erosion, edges: CANYON, terrainSeed: seed }));
211 // Ocean edges stay exactly 0 (the sea erosion washes out into).
212 for (let y = 0; y < 14; y++) {
213 for (let x = 0; x < 14; x++) {
214 if (isOceanEdge(p.edges, x, y, 14, 14)) expect(p.hm.data[y * 14 + x]).toBe(0);
215 }
216 }
217 // Every interior cell still drains out to an ocean edge.
218 for (let y = 1; y < 13; y++) {
219 for (let x = 1; x < 13; x++) {
220 const { outflow } = simulateFlows(p.hm, [{ x, y }]);
221 expect(outflow.length).toBeGreaterThan(0);
222 for (const o of outflow) expect(isOceanEdge(p.edges, o.x, o.y, 14, 14)).toBe(true);
223 }
224 }
225 }
226 }
227 });
228});
229
230describe('reach', () => {
231 it('biases spring elevation toward shore (low) or peak (high)', () => {
232 // Average solution height across many seeds should rise monotonically-ish
233 // from low reach (near shore) to high reach (near peak).
234 const meanHeight = (reach: number): number => {
235 let total = 0;
236 let n = 0;
237 for (const seed of [1, 2, 3, 4, 5, 6, 7, 8]) {
238 const p = generatePuzzle(cfg({ size: 16, springCount: 3, reach, terrainSeed: seed }));
239 for (const s of p.solution) {
240 total += heightAt(p.hm, s.x, s.y);
241 n++;
242 }
243 }
244 return total / n;
245 };
246
247 const low = meanHeight(REACH_MIN);
248 const high = meanHeight(REACH_MAX);
249 expect(low).toBeLessThan(high);
250 });
251
252 it('still produces a full, distinct spring set at both extremes', () => {
253 for (const reach of [REACH_MIN, REACH_MAX]) {
254 for (const seed of [1, 42, 12345]) {
255 const p = generatePuzzle(cfg({ size: 14, springCount: 4, reach, terrainSeed: seed }));
256 expect(p.solution).toHaveLength(4);
257 expect(new Set(p.solution.map((c) => `${c.x},${c.y}`)).size).toBe(4);
258 }
259 }
260 });
261});
262
263describe('springs never land on a shore (target-indicator) cell', () => {
264 const isShore = (c: { x: number; y: number }, edges: Edges, size: number): boolean =>
265 ([[c.x - 1, c.y], [c.x + 1, c.y], [c.x, c.y - 1], [c.x, c.y + 1]] as const).some(([nx, ny]) =>
266 isOceanEdge(edges, nx, ny, size, size),
267 );
268
269 it('holds across realistic (randomConfig-range) boards, including reach 0', () => {
270 // Reach 0 (shore-biased) is exactly the setting most likely to collide
271 // with the gold target indicator, which the renderer also draws on shore
272 // cells — so this is the sharpest check that the exclusion is working.
273 for (const seed of [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]) {
274 const size = 8 + (seed % 5) * 2; // 8..16
275 const p = generatePuzzle(cfg({ size, springCount: 4, reach: REACH_MIN, terrainSeed: seed }));
276 for (const s of p.solution) expect(isShore(s, p.edges, size)).toBe(false);
277 }
278 });
279
280 it('holds at every reach setting on a mid-sized board', () => {
281 for (let reach = REACH_MIN; reach <= REACH_MAX; reach++) {
282 const p = generatePuzzle(cfg({ size: 16, springCount: 3, reach, terrainSeed: 777 }));
283 for (const s of p.solution) expect(isShore(s, p.edges, 16)).toBe(false);
284 }
285 });
286
287 it('still fills springCount even when the non-shore interior is too small to avoid it', () => {
288 // size 5 → interior 3x3, only the centre cell is non-shore; springCount 6
289 // structurally can't be satisfied without some shore cells.
290 const p = generatePuzzle(cfg({ size: 5, springCount: 6, terrainSeed: 1 }));
291 expect(p.solution).toHaveLength(6);
292 expect(new Set(p.solution.map((c) => `${c.x},${c.y}`)).size).toBe(6);
293 });
294});
295
296describe('land sparsity', () => {
297 it('never leaves a board where land candidates fall short of springCount', () => {
298 // Heavy erosion can flatten most of the interior; generation must still
299 // land on a full, distinct spring set rather than crashing or degenerating.
300 for (const size of [5, 8, 12]) {
301 for (const springCount of [1, 4, 6]) {
302 for (const seed of [1, 2, 3, 4, 5]) {
303 const p = generatePuzzle(cfg({ size, springCount, erosion: EROSION_MAX, terrainSeed: seed }));
304 expect(p.solution).toHaveLength(Math.min(springCount, (size - 2) * (size - 2)));
305 expect(new Set(p.solution.map((c) => `${c.x},${c.y}`)).size).toBe(p.solution.length);
306 }
307 }
308 }
309 });
310
311 it('regression: the exact config that used to crash generation now succeeds', () => {
312 // size 8, springCount 4, erosion 7, seed 2521858826 — bestAny stayed null
313 // pre-fix because only 3 cells cleared the land threshold for 4 springs.
314 const p = generatePuzzle(cfg({ size: 8, springCount: 4, erosion: 7, terrainSeed: 2521858826 }));
315 expect(p.solution).toHaveLength(4);
316 });
317});
318
319describe('randomConfig', () => {
320 it('stays within bounds with at least one ocean side', () => {
321 for (let i = 0; i < 200; i++) {
322 const c = randomConfig();
323 expect(c.size).toBeGreaterThanOrEqual(SIZE_MIN);
324 expect(c.size).toBeLessThanOrEqual(SIZE_MAX);
325 expect(c.springCount).toBeGreaterThanOrEqual(SPRINGS_MIN);
326 expect(c.springCount).toBeLessThanOrEqual(SPRINGS_MAX);
327 const sides = [c.edges.n, c.edges.e, c.edges.s, c.edges.w];
328 expect(sides.some((s) => s === 'ocean')).toBe(true);
329 // A random config must always be buildable into a solvable puzzle.
330 expect(generatePuzzle(c).solution).toHaveLength(c.springCount);
331 }
332 });
333});