nx_procgen.nx source

1// nx_procgen.nx -- procedural DUNGEON/maze generation, pure-Nishi NO-FLOAT (seeded integer LCG, iterative DFS). 2// Closes the RESEARCHED->PRESENT gap the research census (GR-S-R5) named for P5 (procedural-generation src=13, 3// the highest-evidence unbuilt cell). Randomized-DFS "recursive backtracker" carves a PERFECT maze on a grid 4// (0=open 1=wall): fully connected by construction, exactly one path between any two open cells. Deterministic 5// (same seed -> same maze). Reusable: roguelike/dungeon levels, RTS maps, tower-defense paths. Composes with 6// nx_pathfind (A*) -- procgen generates, pathfinding verifies reachability. license_tier: ORIGINAL 7import "nx_syscalls.nx" 8const K_MAGIC_1103515245: i64 = 1103515245 9const K_MAGIC_12345: i64 = 12345 10 11func pg_rng(seed: *i64) -> i64 { seed[0] = (seed[0]*K_MAGIC_1103515245 + K_MAGIC_12345) & 0x7fffffff; return seed[0] } 12 13// carve a perfect maze into grid (w*h, ODD dims). all-walls -> iterative DFS from (1,1). `stack` = caller scratch 14// (w*h i64). Deterministic in `seedv`. After: open=0, wall=1, fully connected. Internal scratch via sys_mmap. 15func pg_maze(grid: *i64, w: i64, h: i64, seedv: i64, stack: *i64) -> i64 { 16 let n: i64 = w*h 17 var i: i64 = 0; while i < n { grid[i]=1; i=i+1 } 18 let seed: *i64 = sys_mmap(8) as *i64; seed[0] = seedv 19 let cnx: *i64 = sys_mmap(4*8) as *i64 // up to 4 candidate neighbour cells 20 let cwx: *i64 = sys_mmap(4*8) as *i64 // the wall cell between cur and each candidate 21 var sp: i64 = 0 22 grid[1*w + 1] = 0 23 stack[sp] = 1*w + 1; sp = sp + 1 24 while sp > 0 { 25 let cur: i64 = stack[sp-1] 26 let cx: i64 = cur % w 27 let cy: i64 = cur / w 28 var cc: i64 = 0 29 if cx+2 <= w-2 { if grid[cy*w + (cx+2)]==1 { cnx[cc]=cy*w+(cx+2); cwx[cc]=cy*w+(cx+1); cc=cc+1 } } // right 30 if cx-2 >= 1 { if grid[cy*w + (cx-2)]==1 { cnx[cc]=cy*w+(cx-2); cwx[cc]=cy*w+(cx-1); cc=cc+1 } } // left 31 if cy+2 <= h-2 { if grid[(cy+2)*w + cx]==1 { cnx[cc]=(cy+2)*w+cx; cwx[cc]=(cy+1)*w+cx; cc=cc+1 } } // down 32 if cy-2 >= 1 { if grid[(cy-2)*w + cx]==1 { cnx[cc]=(cy-2)*w+cx; cwx[cc]=(cy-1)*w+cx; cc=cc+1 } } // up 33 if cc > 0 { 34 let pick: i64 = pg_rng(seed) % cc 35 grid[cwx[pick]] = 0 36 grid[cnx[pick]] = 0 37 stack[sp] = cnx[pick]; sp = sp + 1 38 } else { 39 sp = sp - 1 40 } 41 } 42 return 0 43} 44 45func pg_count_open(grid: *i64, n: i64) -> i64 { var c: i64=0; var i: i64=0; while i<n { if grid[i]==0 { c=c+1 } i=i+1 } return c } 46 47// BFS flood from (sx,sy); returns # of open cells reachable. visited+queue = caller scratch (w*h i64 each). 48func pg_flood_count(grid: *i64, w: i64, h: i64, sx: i64, sy: i64, visited: *i64, queue: *i64) -> i64 { 49 let n: i64 = w*h 50 var i: i64 = 0; while i < n { visited[i]=0; i=i+1 } 51 let s: i64 = sy*w + sx 52 if grid[s] != 0 { return 0 } 53 var head: i64 = 0 54 var tail: i64 = 0 55 queue[tail]=s; tail=tail+1; visited[s]=1 56 var reached: i64 = 0 57 while head < tail { 58 let cur: i64 = queue[head]; head=head+1 59 reached = reached + 1 60 let cx: i64 = cur % w 61 let cy: i64 = cur / w 62 var d: i64 = 0 63 while d < 4 { 64 var nx: i64 = cx; var ny: i64 = cy 65 if d==0 { nx=cx+1 } 66 if d==1 { nx=cx-1 } 67 if d==2 { ny=cy+1 } 68 if d==3 { ny=cy-1 } 69 if nx>=0 { if nx<w { if ny>=0 { if ny<h { 70 let nb: i64 = ny*w+nx 71 if grid[nb]==0 { if visited[nb]==0 { visited[nb]=1; queue[tail]=nb; tail=tail+1 } } 72 } } } } 73 d = d + 1 74 } 75 } 76 return reached 77}