fuzzyworld

explodorama / files / src / sim / levelgen.ts

levelgen.ts

11.0 KB · history · blame

1import { stream } from './rng'
2import { DIR_LIST, isSolid, type Cell, type Dir, type EnemyKind, type GemColor, type PowerUp, type Spike, type Vec } from './types'
3
4/**
5 * The board: a wall all round and a pillar at every even (x, y). It grows with the level (PLAN.md
6 * §19.2; user request, 2026-10-24: later levels felt too small), past the fixed view (render/
7 * camera.ts), which then follows the player. Odd sizes, so the pillars meet the walls evenly.
8 * (One size, 9 × 11, from 2026-10-23 until then.) The sizes were fitted with the balance lab
9 * (2026-10-25): up to 15 × 21 at first, late levels took its careful bot 100–145 turns; up to
10 * 13 × 17 they take about 75–95, in the 80–120 aimed at.
11 */
12const BOARD_SIZES: readonly { from: number; width: number; height: number }[] = [
13 { from: 1, width: 9, height: 11 },
14 { from: 4, width: 11, height: 13 },
15 { from: 8, width: 11, height: 15 },
16 { from: 12, width: 13, height: 15 },
17 { from: 16, width: 13, height: 17 },
18]
19
20/** The board's size on `level`: the last size whose first level it has reached. */
21export function boardSize(level: number): { width: number; height: number } {
22 const size = BOARD_SIZES.filter((b) => b.from <= level).at(-1)!
23 return { width: size.width, height: size.height }
24}
25
26/** The first level's board, the smallest (and every board until 2026-10-25). */
27export const LEVEL_WIDTH = BOARD_SIZES[0]!.width
28export const LEVEL_HEIGHT = BOARD_SIZES[0]!.height
29export const START: Vec = { x: 1, y: 1 }
30/** Share of the open tiles that get a soft block. */
31export const BLOCK_DENSITY = 0.25
32/** No enemy starts this close (Manhattan distance) to the player, and the exit isn't this close either. */
33export const SAFE_DISTANCE = 4
34/** The run's last level; clearing it wins (PLAN.md §11). */
35export const LAST_LEVEL = 20
36
37/**
38 * Which enemy types a level can have (PLAN.md §10): Blobs only at first, then one new type every
39 * 3 levels, so all seven are met by level 19 of the 20 (every 6 levels while there were three).
40 */
41export const ENEMY_ORDER: readonly EnemyKind[] = ['blob', 'seeker', 'drifter', 'sprinter', 'ghost', 'wisp', 'hunter']
42export const NEW_ENEMY_EVERY = 3
43
44export function enemyKinds(level: number): EnemyKind[] {
45 return ENEMY_ORDER.slice(0, 1 + Math.floor((level - 1) / NEW_ENEMY_EVERY))
46}
47
48/**
49 * How dangerous each type is, for the level's crowding (PLAN.md §19.2, "concentration"): first
50 * guesses, a Blob 1, to be fitted with the balance lab (how often each type kills the bots).
51 */
52export const ENEMY_THREAT: Record<EnemyKind, number> = {
53 blob: 1, seeker: 1.4, drifter: 1.1, sprinter: 1.6, ghost: 1.7, wisp: 1.3, hunter: 2,
54}
55
56/**
57 * The level's crowding: threat (the enemies' ENEMY_THREAT added up) per open tile (floor and
58 * crates, wherever an enemy could be), rising from 1 per 26 tiles on level 1 (2 Blobs on its 51
59 * tiles, as before) to 1 per 9 on level 20, and on past it, more slowly, toward 1 per 8. Fitted
60 * with the balance lab (2026-10-25): sparser late levels left long hunts for the last enemy.
61 */
62export function concentration(level: number): number {
63 const first = 1 / 26
64 const last = 1 / 9
65 if (level <= LAST_LEVEL) return first + ((last - first) * (level - 1)) / (LAST_LEVEL - 1)
66 return Math.min(1 / 8, last + 0.001 * (level - LAST_LEVEL))
67}
68
69/** At least this many enemies on any level. */
70const MIN_ENEMIES = 2
71
72/**
73 * The turn budget for the par bonus: 10, plus 0.3 a tile for getting about (open tiles: floor and
74 * crates), plus 8 an enemy. On level 1's 9 × 11 board (51 open tiles, 2 enemies) it is 41, as it
75 * was (25 + 8 an enemy) while every board was that size.
76 */
77export function parFor(openTiles: number, enemies: number): number {
78 return 10 + Math.round(0.3 * openTiles) + 8 * enemies
79}
80
81/** A gem's colour is only how it looks. */
82export const GEM_COLORS: readonly GemColor[] = ['blue', 'green', 'red', 'yellow']
83
84export interface EnemyStart {
85 kind: EnemyKind
86 pos: Vec
87 dir: Dir
88}
89
90export interface Layout {
91 width: number
92 height: number
93 cells: Cell[]
94 start: Vec
95 /** Always under a soft block. */
96 exit: Vec
97 /** Under a different soft block. */
98 powerUp: PowerUp
99 enemies: EnemyStart[]
100 par: number
101 /** The board's objects on floor (PLAN.md §19.3): cell indices, and spikes with their phase. */
102 bushes: number[]
103 oil: number[]
104 spikes: Spike[]
105}
106
107export function generateLevel(seed: number, level: number): Layout {
108 const { width, height } = boardSize(level)
109 const density = BLOCK_DENSITY
110 const rng = stream(seed, 'levelgen', level)
111 const cells: Cell[] = []
112 for (let y = 0; y < height; y++) {
113 for (let x = 0; x < width; x++) {
114 const border = x === 0 || y === 0 || x === width - 1 || y === height - 1
115 const pillar = x % 2 === 0 && y % 2 === 0
116 cells.push(border || pillar ? 'wall' : 'floor')
117 }
118 }
119 // The start and the two tiles beside it stay clear, so the first bomb has somewhere to go
120 // and the player somewhere to hide from it.
121 const clear = new Set([key(START), key({ x: START.x + 1, y: START.y }), key({ x: START.x, y: START.y + 1 })])
122 for (let y = 0; y < height; y++) {
123 for (let x = 0; x < width; x++) {
124 const i = y * width + x
125 if (cells[i] === 'floor' && !clear.has(key({ x, y })) && rng.next() < density) cells[i] = 'block'
126 }
127 }
128
129 const far = (i: number) => Math.abs((i % width) - START.x) + Math.abs(Math.floor(i / width) - START.y) > SAFE_DISTANCE
130 const at = (i: number): Vec => ({ x: i % width, y: Math.floor(i / width) })
131 // A small board can, rarely, have too few crates far enough away for the exit and the
132 // power-up: turn far floor tiles into crates until there are two.
133 for (let n = cells.filter((c, i) => c === 'block' && far(i)).length; n < 2; n++) {
134 const floors = cells.flatMap((c, i) => (c === 'floor' && far(i) ? [i] : []))
135 cells[floors[rng.int(floors.length)]!] = 'block'
136 }
137 const blocks = cells.flatMap((c, i) => (c === 'block' && far(i) ? [i] : []))
138 const exit = at(blocks.splice(rng.int(blocks.length), 1)[0]!)
139
140 const open = cells.flatMap((c, i) => (c === 'floor' && far(i) ? [i] : []))
141 const openTiles = cells.filter((c) => c !== 'wall').length
142 const kinds = enemyKinds(level)
143 const enemies: EnemyStart[] = []
144 // Enemies until their threat reaches the level's concentration times its open tiles.
145 const threat = concentration(level) * openTiles
146 let total = 0
147 while ((total < threat || enemies.length < MIN_ENEMIES) && open.length) {
148 const i = open.splice(rng.int(open.length), 1)[0]!
149 const kind = kinds[rng.int(kinds.length)]!
150 enemies.push({ kind, pos: at(i), dir: DIR_LIST[rng.int(4)]! })
151 total += ENEMY_THREAT[kind]
152 }
153 // Any other block, near the start or not, so an early gem is possible.
154 const others = cells.flatMap((c, i) => (c === 'block' && !(i % width === exit.x && Math.floor(i / width) === exit.y) ? [i] : []))
155 const powerUp = { pos: at(others[rng.int(others.length)]!), color: GEM_COLORS[rng.int(GEM_COLORS.length)]! }
156 const objects = placeObjects(seed, level, width, height, cells, [exit, powerUp.pos], enemies.map((e) => e.pos))
157 return { width, height, cells, start: { ...START }, exit, powerUp, enemies, par: parFor(openTiles, enemies.length), ...objects }
158}
159
160/**
161 * The first level each board object can turn up on (PLAN.md §19.3; first guesses, 2026-10-25):
162 * one new kind every few levels, as enemies come, so each is met on its own first.
163 */
164export const OBJECTS_FROM = { bush: 2, metal: 3, oil: 5, spikes: 8, barrel: 11 } as const
165
166/**
167 * The board's objects, from their own random stream, after everything else, so a level's crates
168 * and enemies are where they would be without them: bushes in clumps, metal crates and oil barrels
169 * in place of some crates (never the exit's or the gem's, and a metal crate only where every tile
170 * stays reachable), oil spills, single spikes; none in the start's corner, nor under an enemy.
171 */
172function placeObjects(seed: number, level: number, width: number, height: number, cells: Cell[], keep: Vec[], enemies: Vec[]) {
173 const rng = stream(seed, 'objects', level)
174 const fromStart = (i: number) => Math.abs((i % width) - START.x) + Math.abs(Math.floor(i / width) - START.y)
175 const kept = new Set(keep.map((p) => p.y * width + p.x))
176 const taken = new Set(enemies.map((p) => p.y * width + p.x))
177 const free = (i: number) => cells[i] === 'floor' && !taken.has(i) && fromStart(i) > 2
178 const neighbours = (i: number) => [i - 1, i + 1, i - width, i + width].filter((j) => j >= 0 && j < cells.length && Math.abs((j % width) - (i % width)) <= 1)
179 const freeTiles = () => cells.flatMap((_, i) => (free(i) ? [i] : []))
180 const pick = (from: number[]) => from.splice(rng.int(from.length), 1)[0]
181 const floorCount = cells.filter((c) => c === 'floor').length
182 const bushes: number[] = []
183 const oil: number[] = []
184 const spikes: Spike[] = []
185
186 // A clump: a tile, then a few touching ones.
187 const clump = (into: number[], size: number) => {
188 const start = pick(freeTiles())
189 if (start === undefined) return
190 const group = [start]
191 taken.add(start)
192 for (let k = 1; k < size; k++) {
193 const next = group.flatMap(neighbours).filter(free)
194 const j = pick(next)
195 if (j === undefined) break
196 group.push(j)
197 taken.add(j)
198 }
199 into.push(...group)
200 }
201 if (level >= OBJECTS_FROM.bush) for (let n = Math.round((floorCount * 0.06) / 3); n > 0; n--) clump(bushes, 2 + rng.int(3))
202 if (level >= OBJECTS_FROM.oil) for (let n = 1 + Math.floor(level / 7); n > 0; n--) clump(oil, 3 + rng.int(3))
203 if (level >= OBJECTS_FROM.spikes) {
204 for (let n = 2 + Math.floor(level / 8); n > 0; n--) {
205 const i = pick(freeTiles())
206 if (i === undefined) break
207 taken.add(i)
208 spikes.push({ cell: i, phase: rng.int(2) })
209 }
210 }
211 // Crates that may become something else: not the exit's or the gem's, not by the start.
212 const crates = () => cells.flatMap((c, i) => (c === 'block' && !kept.has(i) && fromStart(i) > 3 ? [i] : []))
213 if (level >= OBJECTS_FROM.metal) {
214 const pool = crates()
215 for (let n = Math.round(pool.length * 0.12); n > 0 && pool.length; n--) {
216 const i = pick(pool)!
217 cells[i] = 'metal'
218 // Every open tile must stay reachable from the start, crates burnt away.
219 if (!allReachable(cells, width, height)) cells[i] = 'block'
220 }
221 }
222 if (level >= OBJECTS_FROM.barrel) {
223 const pool = crates()
224 for (let n = 1 + Math.floor(level / 8); n > 0 && pool.length; n--) cells[pick(pool)!] = 'barrel'
225 }
226 return { bushes, oil, spikes }
227}
228
229/** Whether every tile that isn't solid can be reached from the start, crates and barrels gone. */
230function allReachable(cells: Cell[], width: number, height: number): boolean {
231 const open = (i: number) => !isSolid(cells[i]!)
232 const start = START.y * width + START.x
233 const seen = new Set([start])
234 const queue = [start]
235 for (let k = 0; k < queue.length; k++) {
236 const i = queue[k]!
237 for (const j of [i - 1, i + 1, i - width, i + width]) {
238 if (j < 0 || j >= width * height || seen.has(j) || !open(j)) continue
239 seen.add(j)
240 queue.push(j)
241 }
242 }
243 return seen.size === cells.filter((_, i) => open(i)).length
244}
245
246function key(p: Vec): string {
247 return `${p.x},${p.y}`
248}