// examples/dungeon_explorer.tin - Procedural Dungeon Generator & Auto-Explorer // // Showcases: // - User-defined `struct` types with methods and O(1) structural hashing // - `std/grid` for 2D tile carving and rendering // - `union_find` (Kruskal's MST) from `std/search` to connect dungeon rooms // - Multi-objective state-space `bfs` over `ExplorerState(pos, has_key, gold_mask)` import "std/grid" as grid from "std/search" import union_find, bfs, astar // Deterministic LCG pseudo-random generator struct Rng(state) { fn next(self) { self.state = (self.state * 1103515245 + 12345) & 0x7fffffff self.state } fn range(self, low, high) { low + (self.next() % (high - low)) } } struct Room(id, x, y, w, h) { fn center(self) { vec2(self.x + self.w / 2, self.y + self.h / 2) } fn intersects(self, other, pad = 1) { !(self.x + self.w + pad <= other.x || other.x + other.w + pad <= self.x || self.y + self.h + pad <= other.y || other.y + other.h + pad <= self.y) } } // Composite search state: hashed in O(1) via Tinsel's struct prototype protocol struct ExplorerState(pos, has_key, gold_mask) let default_seed = 42 let seed = if args.len() > 0 { to_int(args[0]) } else { default_seed } let rng = Rng(seed) let map_w = 54 let map_h = 22 let dungeon = grid.new(map_w, map_h, '#') // 1. Place non-overlapping rectangular rooms let rooms = [] for attempt in 0..80 { if rooms.len() >= 9 { break } let rw = rng.range(5, 10) let rh = rng.range(4, 7) let rx = rng.range(2, map_w - rw - 2) let ry = rng.range(2, map_h - rh - 2) let candidate = Room(rooms.len(), rx, ry, rw, rh) let mut overlaps = false for existing in rooms { if candidate.intersects(existing, 2) { overlaps = true break } } if !overlaps { rooms.push(candidate) for y in ry..(ry + rh) { for x in rx..(rx + rw) { dungeon[vec2(x, y)] = '.' } } } } // 2. Connect rooms via Kruskal's Minimum Spanning Tree (`union_find`) let edges = [] for i in 0..rooms.len() { for j in (i + 1)..rooms.len() { let c1 = rooms[i].center() let c2 = rooms[j].center() edges.push([c1 <-> c2, i, j]) } } let sorted_edges = edges.sort_by(e -> e[0]) let uf = union_find(0..rooms.len()) let corridors = [] for edge in sorted_edges { let (_, u, v) = edge if uf.union(u, v) { corridors.push([u, v]) } } // Carve L-shaped corridors between connected room centers fn carve_corridor(g, p1, p2) { let mut x = p1.x let mut y = p1.y while x != p2.x { g[vec2(x, y)] = '.' x += if p2.x > x { 1 } else { -1 } } while y != p2.y { g[vec2(x, y)] = '.' y += if p2.y > y { 1 } else { -1 } } g[p2] = '.' } for pair in corridors { let c1 = rooms[pair[0]].center() let c2 = rooms[pair[1]].center() carve_corridor(dungeon, c1, c2) } // 3. Place start (`@`), key (`K`), treasures (`$`), locked exit door (`D`), and stairs (`>`) let start_pos = rooms[0].center() let key_pos = rooms[2].center() let exit_room = rooms[rooms.len() - 1] let exit_pos = exit_room.center() // Place treasures in intermediate rooms let gold_positions = [] let gold_index = {} for i in 1..(rooms.len() - 1) { if i != 2 && gold_positions.len() < 4 { let pos = rooms[i].center() gold_index[pos] = gold_positions.len() gold_positions.push(pos) dungeon[pos] = '$' } } let all_gold_mask = (1 << gold_positions.len()) - 1 // Surround the exit stairs with a locked door barrier (`D`) so the key is required for n in dungeon.neighbors8(exit_pos) { if dungeon[n] == '.' { dungeon[n] = 'D' } } dungeon[start_pos] = '@' dungeon[key_pos] = 'K' dungeon[exit_pos] = '>' // 4. Run multi-objective BFS to collect all gold, grab the key, unlock the door, and exit let initial_state = ExplorerState(start_pos, false, 0) let goal_state_fn = s -> s.pos == exit_pos && s.has_key && s.gold_mask == all_gold_mask let result = bfs( initial_state, s -> { let next_states = [] for next_pos in dungeon.neighbors4(s.pos) { let tile = dungeon[next_pos] if tile == '#' { continue } if tile == 'D' && !s.has_key { continue } let next_key = s.has_key || next_pos == key_pos let next_mask = if gold_index.has(next_pos) { s.gold_mask | (1 << gold_index[next_pos]) } else { s.gold_mask } next_states.push(ExplorerState(next_pos, next_key, next_mask)) } next_states }, goal_state_fn ) assert(result.found, "explorer must find a valid complete dungeon solution") // Overlay the explorer's footsteps (`·`) onto a copy of the dungeon for display let display = dungeon.clone() for step_state in result.path { let p = step_state.pos if display[p] == '.' { display[p] = '+' } } println(f"=== Procedural Dungeon Explorer (seed={seed}) ===") println(f"Rooms: {rooms.len()} | MST Corridors: {corridors.len()} | Treasures: {gold_positions.len()} | Optimal Quest Steps: {result.cost}") println(display) // 5. Independent Property-Based Verification of the Quest Solution // Verify by replaying the path step-by-step on the raw dungeon grid: assert(result.path.len() - 1 == result.cost, "path length must match reported BFS cost") assert(result.path[0].pos == start_pos, "path must start at @") assert(result.path[result.path.len() - 1].pos == exit_pos, "path must end at >") let mut held_key = false let collected_gold = {} for i in 0..result.path.len() { let p = result.path[i].pos let tile = dungeon[p] assert(tile != '#', "explorer must never walk through a wall") if tile == 'D' { assert(held_key, "explorer must not pass through locked door D before picking up key K") } if p == key_pos { held_key = true } if gold_index.has(p) { collected_gold[p] = true } if i > 0 { let prev = result.path[i - 1].pos assert((prev <-> p) == 1, "each step in path must move to an orthogonal neighbor") } } assert(held_key, "explorer must have collected the key") assert(collected_gold.len() == gold_positions.len(), "explorer must have collected every treasure") if seed == default_seed { assert(rooms.len() == 7) assert(corridors.len() == 6) assert(gold_positions.len() == 4) assert(result.cost == 103) } result.cost