route.test.js (10724B)
1 const { describe, it } = require('node:test'); 2 const assert = require('node:assert/strict'); 3 const { 4 turnHeading, 5 getRelativeMove, 6 classifyIntersection, 7 getLegalMoves, 8 buildIsland, 9 extendRouteOnGraph, 10 OPPOSITE, 11 HEADING_TO_CARD, 12 pickRandomRouteStart, 13 bfsRoadPath, 14 bfsRoadDistances, 15 pathToRouteSteps, 16 pickFireDestination, 17 headingFromTo, 18 isDecisionCell, 19 createSeededRng, 20 CARD_TO_HEADING, 21 } = require('../../games/fire-truck/lib.js'); 22 23 const fixedRng = { pick: arr => arr[0], next: () => 0.25 }; 24 25 describe('turnHeading()', () => { 26 it('handles left, right, and straight', () => { 27 assert.equal(turnHeading('north', 'left'), 'west'); 28 assert.equal(turnHeading('north', 'right'), 'east'); 29 assert.equal(turnHeading('east', 'straight'), 'east'); 30 assert.equal(turnHeading('south', 'left'), 'east'); 31 }); 32 }); 33 34 describe('getRelativeMove()', () => { 35 it('maps heading changes to child-friendly move labels', () => { 36 assert.equal(getRelativeMove('north', 'west'), 'left'); 37 assert.equal(getRelativeMove('north', 'east'), 'right'); 38 assert.equal(getRelativeMove('east', 'east'), 'straight'); 39 }); 40 }); 41 42 describe('classifyIntersection()', () => { 43 it('classifies 4-way and t intersections', () => { 44 assert.equal(classifyIntersection({ N: true, E: true, S: true, W: true }).kind, 'four'); 45 assert.equal(classifyIntersection({ N: true, E: true, S: true, W: false }).kind, 't'); 46 assert.equal(classifyIntersection({ N: true, E: false, S: true, W: false }).kind, 'straight'); 47 assert.equal(classifyIntersection({ N: true, E: true, S: false, W: false }).kind, 'corner'); 48 }); 49 }); 50 51 describe('getLegalMoves()', () => { 52 it('returns relative options from approach heading', () => { 53 const fourWay = { exits: { N: true, E: true, S: true, W: true } }; 54 assert.deepEqual(getLegalMoves(fourWay, 'north').sort(), ['left', 'right', 'straight']); 55 56 const t = { exits: { N: false, E: true, S: true, W: true } }; 57 assert.deepEqual(getLegalMoves(t, 'north').sort(), ['left', 'right']); 58 }); 59 }); 60 61 describe('buildIsland()', () => { 62 it('is deterministic with seed', () => { 63 const opts = { seed: 123, routeCount: 30 }; 64 const a = buildIsland(opts); 65 const b = buildIsland(opts); 66 assert.deepEqual(a.roads.map(c => ({ x: c.x, y: c.y, exits: c.exits })), 67 b.roads.map(c => ({ x: c.x, y: c.y, exits: c.exits }))); 68 assert.deepEqual(a.route.map(s => ({ x: s.x, y: s.y, headingIn: s.headingIn, headingOut: s.headingOut, move: s.move })), 69 b.route.map(s => ({ x: s.x, y: s.y, headingIn: s.headingIn, headingOut: s.headingOut, move: s.move }))); 70 }); 71 72 it('route steps stay on graph', () => { 73 const island = buildIsland({ seed: 42, routeCount: 50 }); 74 for (const step of island.route) { 75 const decision = island.grid[step.y][step.x]; 76 const approach = island.grid[step.approachY][step.approachX]; 77 const exit = island.grid[step.exitY][step.exitX]; 78 79 assert.equal(decision.type, 'road'); 80 assert.equal(approach.type, 'road'); 81 assert.equal(exit.type, 'road'); 82 83 const backCard = HEADING_TO_CARD[OPPOSITE[step.headingIn]]; 84 assert.equal(decision.exits[backCard], true, 'decision must have exit back to approach'); 85 assert.equal(decision.exits[HEADING_TO_CARD[step.headingOut]], true, 'decision must have exit toward headingOut'); 86 87 assert.equal(getRelativeMove(step.headingIn, step.headingOut), step.move); 88 } 89 }); 90 91 it('route starts correctly', () => { 92 const island = buildIsland({ seed: 7, routeCount: 10, routeStart: { x: 3, y: 2, heading: 'east' } }); 93 assert.deepEqual(island.routeStart, { x: 3, y: 2, heading: 'east' }); 94 assert.equal(island.route[0].headingIn, 'east'); 95 96 // Walk from routeStart toward first decision to ensure it's all road 97 let x = island.routeStart.x; 98 let y = island.routeStart.y; 99 const target = island.route[0]; 100 while (x !== target.x || y !== target.y) { 101 assert.equal(island.grid[y][x].type, 'road'); 102 x += 1; // heading is east 103 } 104 }); 105 106 it('extension continues smoothly', () => { 107 const island = buildIsland({ seed: 99, routeCount: 20 }); 108 const ext = extendRouteOnGraph(island, island.route, 20); 109 assert.equal(ext.length, 20); 110 assert.equal(ext[0].index, island.route.length); 111 112 const last = island.route[island.route.length - 1]; 113 const firstExt = ext[0]; 114 assert.equal(firstExt.headingIn, last.headingOut); 115 }); 116 }); 117 118 describe('pickRandomRouteStart()', () => { 119 it('returns a road cell with a valid exit heading', () => { 120 const island = buildIsland({ seed: 1, routeCount: 10 }); 121 const start = pickRandomRouteStart(island.roads, createSeededRng(42)); 122 const cell = island.grid[start.y][start.x]; 123 assert.equal(cell.type, 'road'); 124 const meta = cell.meta || classifyIntersection(cell.exits); 125 assert.ok(meta.degree >= 2); 126 const card = HEADING_TO_CARD[start.heading]; 127 assert.equal(cell.exits[card], true); 128 }); 129 }); 130 131 describe('headingFromTo()', () => { 132 it('derives heading between adjacent cells', () => { 133 assert.equal(headingFromTo({ x: 1, y: 1 }, { x: 2, y: 1 }), 'east'); 134 assert.equal(headingFromTo({ x: 1, y: 1 }, { x: 0, y: 1 }), 'west'); 135 assert.equal(headingFromTo({ x: 1, y: 1 }, { x: 1, y: 2 }), 'south'); 136 assert.equal(headingFromTo({ x: 1, y: 1 }, { x: 1, y: 0 }), 'north'); 137 }); 138 }); 139 140 describe('bfsRoadPath()', () => { 141 it('finds a valid road path', () => { 142 const island = buildIsland({ seed: 5, routeCount: 10 }); 143 // Pick two distinct road cells 144 const start = island.roads[0]; 145 const target = island.roads.find(c => c !== start && Math.abs(c.x - start.x) + Math.abs(c.y - start.y) > 5); 146 assert.ok(target, 'need a distinct road cell for target'); 147 const path = bfsRoadPath(island.grid, start, target); 148 assert.ok(path); 149 assert.ok(path.length > 0); 150 assert.equal(path[0], start); 151 assert.equal(path[path.length - 1], target); 152 for (const cell of path) { 153 assert.equal(cell.type, 'road'); 154 } 155 for (let i = 1; i < path.length; i++) { 156 const dx = path[i].x - path[i - 1].x; 157 const dy = path[i].y - path[i - 1].y; 158 assert.ok(Math.abs(dx) + Math.abs(dy) === 1); 159 } 160 }); 161 162 it('returns single cell when start === target', () => { 163 const island = buildIsland({ seed: 5, routeCount: 10 }); 164 const cell = island.grid[3][3]; 165 const path = bfsRoadPath(island.grid, cell, cell); 166 assert.deepEqual(path, [cell]); 167 }); 168 }); 169 170 describe('pathToRouteSteps()', () => { 171 it('emits steps only at decision cells', () => { 172 const island = buildIsland({ seed: 6, routeCount: 10 }); 173 const start = island.grid[island.routeStart.y][island.routeStart.x]; 174 const end = island.route[island.route.length - 1]; 175 const target = island.grid[end.y][end.x]; 176 const path = bfsRoadPath(island.grid, start, target); 177 const steps = pathToRouteSteps(island.grid, path, 0); 178 for (const step of steps) { 179 const cell = island.grid[step.y][step.x]; 180 assert.ok(isDecisionCell(cell)); 181 assert.equal(step.move, getRelativeMove(step.headingIn, step.headingOut)); 182 } 183 }); 184 185 it('returns empty array for short paths', () => { 186 const island = buildIsland({ seed: 6, routeCount: 10 }); 187 const cell = island.grid[3][3]; 188 assert.deepEqual(pathToRouteSteps(island.grid, [cell], 0), []); 189 assert.deepEqual(pathToRouteSteps(island.grid, [cell, island.grid[3][4]], 0), []); 190 }); 191 }); 192 193 describe('pickFireDestination()', () => { 194 it('returns adjacent road and building cells', () => { 195 const island = buildIsland({ seed: 8, routeCount: 10 }); 196 const dest = pickFireDestination(island, createSeededRng(42)); 197 assert.ok(dest); 198 assert.ok(dest.roadCell); 199 assert.ok(dest.buildingCell); 200 const dx = Math.abs(dest.roadCell.x - dest.buildingCell.x); 201 const dy = Math.abs(dest.roadCell.y - dest.buildingCell.y); 202 assert.equal(dx + dy, 1); 203 assert.equal(dest.roadCell.type, 'road'); 204 assert.equal(dest.buildingCell.type, 'building'); 205 }); 206 207 it('respects targetDistance within variance', () => { 208 const island = buildIsland({ seed: 8, routeCount: 10 }); 209 const fromCell = island.grid[island.routeStart.y][island.routeStart.x]; 210 const dists = bfsRoadDistances(island.grid, fromCell); 211 for (let seed = 1; seed <= 5; seed++) { 212 const dest = pickFireDestination(island, createSeededRng(seed), { 213 fromCell, 214 targetDistance: 20, 215 variance: 5, 216 }); 217 assert.ok(dest, `seed ${seed}: dest should exist`); 218 const d = dists.get(dest.roadCell); 219 assert.ok(d != null, 'destination must be reachable'); 220 assert.ok(d >= 15 && d <= 25, `seed ${seed}: distance ${d} should be in [15,25]`); 221 } 222 }); 223 224 it('falls back to closest when no candidates in range', () => { 225 const island = buildIsland({ seed: 8, routeCount: 10 }); 226 const fromCell = island.grid[island.routeStart.y][island.routeStart.x]; 227 const dest = pickFireDestination(island, createSeededRng(1), { 228 fromCell, 229 targetDistance: 1000, 230 variance: 0, 231 }); 232 assert.ok(dest, 'should return a fallback result rather than null'); 233 assert.equal(dest.roadCell.type, 'road'); 234 }); 235 }); 236 237 describe('bfsRoadDistances()', () => { 238 it('assigns distance 0 to start cell and positive distances to others', () => { 239 const island = buildIsland({ seed: 5, routeCount: 10 }); 240 const start = island.roads[0]; 241 const dists = bfsRoadDistances(island.grid, start); 242 assert.equal(dists.get(start), 0); 243 for (const [cell, d] of dists) { 244 assert.ok(d >= 0, 'all distances non-negative'); 245 } 246 }); 247 248 it('neighbors are at most 1 hop from each other', () => { 249 const island = buildIsland({ seed: 5, routeCount: 10 }); 250 const start = island.roads[0]; 251 const dists = bfsRoadDistances(island.grid, start); 252 for (const [cell] of dists) { 253 if (cell.type !== 'road') continue; 254 const d = dists.get(cell); 255 for (const card of ['N', 'E', 'S', 'W']) { 256 if (!cell.exits[card]) continue; 257 const { dx, dy } = { N: { dx: 0, dy: -1 }, E: { dx: 1, dy: 0 }, S: { dx: 0, dy: 1 }, W: { dx: -1, dy: 0 } }[card]; 258 const neighbor = island.grid[cell.y + dy] && island.grid[cell.y + dy][cell.x + dx]; 259 if (!neighbor || !dists.has(neighbor)) continue; 260 assert.ok(Math.abs(dists.get(neighbor) - d) <= 1, 'adjacent cells differ by at most 1'); 261 } 262 } 263 }); 264 265 it('covers all road cells (connected graph)', () => { 266 const island = buildIsland({ seed: 5, routeCount: 10 }); 267 const start = island.roads[0]; 268 const dists = bfsRoadDistances(island.grid, start); 269 assert.equal(dists.size, island.roads.length); 270 }); 271 });