nx_maze_gen.nx source

1// nx_maze_gen.nx -- LIB: three foundational rungs toward AUTONOMOUS S-class game emission, in pure-integer Nishi 2// (no float, no third-party): 3// procgen-solvable : mz_gen builds a maze by integer DFS recursive-backtracker -> a SPANNING TREE, so EVERY cell 4// is reachable BY CONSTRUCTION (an emitted level can never be unsolvable). 5// gate-solvable : mz_solve is a BFS solver that PROVES a start->exit path exists (returns its length) or 6// reports UNSOLVABLE (-1). The validation gate that makes "automatically emit a game" SAFE: 7// no emitted level ships unless the solver confirms it is winnable. 8// rules-engine : the maze is a grid with rules-as-data (wall bits per cell) + movement rules + win=reach-exit. 9// mz_seal isolates a cell (the gate's negative control: a deliberately-broken level the solver MUST catch). 10// Deterministic (LCG seed) -> reproducible emission. Cell = 4 wall bits N=1 E=2 S=4 W=8 (bit4=16 visited, scratch). 11// license_tier: ORIGINAL 12import "nx_syscalls.nx" 13const K_MAGIC_1103515245: i64 = 1103515245 14const K_MAGIC_12345: i64 = 12345 15const K_MAGIC_32767: i64 = 32767 16 17func mz_rng(seedbox: *i64) -> i64 { var x: i64 = seedbox[0]; x = x * K_MAGIC_1103515245 + K_MAGIC_12345; seedbox[0] = x; return (x >> 16) & K_MAGIC_32767 } 18 19// generate a perfect maze (spanning tree) into cells (w*h bytes). Every cell becomes reachable by construction. 20func mz_gen(seed: i64, w: i64, h: i64, cells: *u8) -> i64 { 21 var i: i64 = 0 22 while i < w*h { cells[i] = 15 as u8; i = i + 1 } 23 let seedbox: *i64 = sys_mmap(16) as *i64; seedbox[0] = seed 24 let stack: *i64 = sys_mmap(8 * (w*h + 8)) as *i64 25 let nb: *i64 = sys_mmap(8*4) as *i64; let nd: *i64 = sys_mmap(8*4) as *i64 26 var sp: i64 = 0 27 cells[0] = (cells[0] as i64 | 16) as u8 28 stack[sp] = 0; sp = sp + 1 29 while sp > 0 { 30 let cur: i64 = stack[sp-1] 31 let cx: i64 = cur % w; let cy: i64 = cur / w 32 var nc: i64 = 0 33 if cy > 0 { let nn: i64 = cur - w; if (cells[nn] as i64 & 16) == 0 { nb[nc] = nn; nd[nc] = 1; nc = nc + 1 } } 34 if cx < w-1 { let nn: i64 = cur + 1; if (cells[nn] as i64 & 16) == 0 { nb[nc] = nn; nd[nc] = 2; nc = nc + 1 } } 35 if cy < h-1 { let nn: i64 = cur + w; if (cells[nn] as i64 & 16) == 0 { nb[nc] = nn; nd[nc] = 4; nc = nc + 1 } } 36 if cx > 0 { let nn: i64 = cur - 1; if (cells[nn] as i64 & 16) == 0 { nb[nc] = nn; nd[nc] = 8; nc = nc + 1 } } 37 if nc == 0 { sp = sp - 1 } else { 38 let pick: i64 = mz_rng(seedbox) % nc 39 let nxt: i64 = nb[pick]; let dir: i64 = nd[pick] 40 cells[cur] = (cells[cur] as i64 & (255 - dir)) as u8 41 var opp: i64 = 0 42 if dir == 1 { opp = 4 } else { if dir == 2 { opp = 8 } else { if dir == 4 { opp = 1 } else { opp = 2 } } } 43 cells[nxt] = (cells[nxt] as i64 & (255 - opp)) as u8 44 cells[nxt] = (cells[nxt] as i64 | 16) as u8 45 stack[sp] = nxt; sp = sp + 1 46 } 47 } 48 i = 0 49 while i < w*h { cells[i] = (cells[i] as i64 & 15) as u8; i = i + 1 } 50 return 0 51} 52 53// BFS solver. Fills dist (w*h i64; -1 = unreachable). Returns dist[exit_c] (>=0 = solvable + path length, -1 = UNSOLVABLE). 54func mz_solve(cells: *u8, w: i64, h: i64, start: i64, exit_c: i64, dist: *i64, queue: *i64) -> i64 { 55 var i: i64 = 0 56 while i < w*h { dist[i] = 0 - 1; i = i + 1 } 57 var qh: i64 = 0; var qt: i64 = 0 58 dist[start] = 0; queue[qt] = start; qt = qt + 1 59 while qh < qt { 60 let cur: i64 = queue[qh]; qh = qh + 1 61 let cx: i64 = cur % w; let cy: i64 = cur / w 62 let cv: i64 = cells[cur] as i64 63 if (cv & 1) == 0 { if cy > 0 { let nn: i64 = cur - w; if dist[nn] == (0 - 1) { dist[nn] = dist[cur] + 1; queue[qt] = nn; qt = qt + 1 } } } 64 if (cv & 2) == 0 { if cx < w-1 { let nn: i64 = cur + 1; if dist[nn] == (0 - 1) { dist[nn] = dist[cur] + 1; queue[qt] = nn; qt = qt + 1 } } } 65 if (cv & 4) == 0 { if cy < h-1 { let nn: i64 = cur + w; if dist[nn] == (0 - 1) { dist[nn] = dist[cur] + 1; queue[qt] = nn; qt = qt + 1 } } } 66 if (cv & 8) == 0 { if cx > 0 { let nn: i64 = cur - 1; if dist[nn] == (0 - 1) { dist[nn] = dist[cur] + 1; queue[qt] = nn; qt = qt + 1 } } } 67 } 68 return dist[exit_c] 69} 70// count reachable cells in dist (dist != -1) -- a perfect maze => ALL w*h reachable (the by-construction proof). 71func mz_reachable(dist: *i64, n: i64) -> i64 { var c: i64 = 0; var i: i64 = 0; while i < n { if dist[i] != (0 - 1) { c = c + 1 } i = i + 1 } return c } 72 73// NEG-CONTROL: isolate cell c (all 4 of its walls + the facing wall of each neighbor) -> unreachable. The solver MUST catch this. 74func mz_seal(cells: *u8, w: i64, h: i64, c: i64) -> i64 { 75 cells[c] = 15 as u8 76 let cx: i64 = c % w; let cy: i64 = c / w 77 if cy > 0 { cells[c-w] = (cells[c-w] as i64 | 4) as u8 } 78 if cx < w-1 { cells[c+1] = (cells[c+1] as i64 | 8) as u8 } 79 if cy < h-1 { cells[c+w] = (cells[c+w] as i64 | 1) as u8 } 80 if cx > 0 { cells[c-1] = (cells[c-1] as i64 | 2) as u8 } 81 return 0 82} 83 84// render the maze as ASCII ((2h+1)x(2w+1)): '#'=wall, ' '=passage, 'S'=start, 'E'=exit. Returns length (NUL-terminated). 85func mz_ascii(cells: *u8, w: i64, h: i64, start: i64, exit_c: i64, buf: *u8) -> i64 { 86 var o: i64 = 0 87 var ry: i64 = 0 88 while ry < 2*h+1 { 89 var rx: i64 = 0 90 while rx < 2*w+1 { 91 var ch: i64 = 35 92 if (ry % 2) == 1 { 93 if (rx % 2) == 1 { 94 let cx: i64 = (rx-1)/2; let cy: i64 = (ry-1)/2; let c: i64 = cy*w + cx 95 ch = 32 96 if c == start { ch = 83 } 97 if c == exit_c { ch = 69 } 98 } else { 99 if rx == 0 { ch = 35 } else { if rx == 2*w { ch = 35 } else { 100 let cy: i64 = (ry-1)/2; let lcx: i64 = rx/2 - 1; let c: i64 = cy*w + lcx 101 if (cells[c] as i64 & 2) == 0 { ch = 32 } 102 } } 103 } 104 } else { 105 if (rx % 2) == 1 { 106 if ry == 0 { ch = 35 } else { if ry == 2*h { ch = 35 } else { 107 let cx: i64 = (rx-1)/2; let ty: i64 = ry/2 - 1; let c: i64 = ty*w + cx 108 if (cells[c] as i64 & 4) == 0 { ch = 32 } 109 } } 110 } 111 } 112 buf[o] = ch as u8; o = o + 1 113 rx = rx + 1 114 } 115 buf[o] = 10 as u8; o = o + 1 116 ry = ry + 1 117 } 118 buf[o] = 0 as u8 119 return o 120}