# Procedural Dungeon & Map Generator > Implements deterministic 2D tilemap generation with Binary Space Partitioning for rectangular rooms, A* grid pathfinding for corridor carving between room centers, and a Cellular Automata cave smoother using BFS connected-component flood-fill to keep a single reachable region, emitting a grid, ASCII map and JSON statistics. - Skill: `rmazrim/procedural-dungeon-map-generator` (Agent Skill) - Install (CLI): `npx skillmds@latest add rmazrim/procedural-dungeon-map-generator` - Raw SKILL.md: https://api.skillmd.com/api/skills/rmazrim/procedural-dungeon-map-generator/raw - Safety review: pending - Works with: Claude Code, Claude.ai, OpenAI Codex - Category: Web & Frontend - Author: RMAzrim (https://skillmd.com/u/rmazrim) - Updated: 2026-09-22 - Page: https://skillmd.com/skills/rmazrim/procedural-dungeon-map-generator --- # Procedural Dungeon & Map Generator ## 1. System Architecture & Prerequisites This skill is a pure-stdlib procedural tilemap generator. It ships three independent but composable algorithm families in one module: - **`BSPTree`** - Binary Space Partitioning. The map rectangle is recursively split (axis chosen by aspect ratio, otherwise random; cut point uniform within the allowed band) down to a target leaf size. Each leaf stamps one `Room`. Sibling subtrees are joined with L-shaped corridors so the room graph stays connected. - **`AStar`** - grid pathfinder with a Manhattan heuristic. Walls are traversable at a configurable `wall_cost`, so the search reuses existing floor but cuts through rock when needed. Used to carve extra corridors between distant rooms in `generate_dungeon`. - **`cellular_automata_cave`** - organic caves: random noise smoothed by a neighbour-majority rule over `iters` generations, then a BFS connected-component flood-fill (`connected_components`) converts every floor region except the largest into walls, guaranteeing one reachable region. Public API: `generate_dungeon(width, height, seed)`, `generate_bsp_rooms(width, height, seed)`, `cellular_automata_cave(width, height, fill, iters, wall_threshold)` and the `to_ascii(grid)` renderer. Everything is deterministic for a given seed. Prerequisites: **Python 3.9+** only. Standard library modules used are `random`, `math`, `collections.deque`, `dataclasses`, `heapq` and `json`. No third-party packages are required. ## 2. Input/Output Data Contracts ### 2.1 Input JSON Schema - generation options ```json { "$schema": "http://json-schema.org/draft-07/schema#", "type": "object", "title": "DungeonGeneratorInput", "properties": { "width": { "type": "integer", "minimum": 8, "default": 44 }, "height": { "type": "integer", "minimum": 8, "default": 26 }, "seed": { "type": "integer", "default": 1337 }, "min_leaf": { "type": "integer", "minimum": 4, "default": 8 }, "min_room": { "type": "integer", "minimum": 2, "default": 4 }, "margin": { "type": "integer", "minimum": 0, "default": 1 }, "fill": { "type": "number", "minimum": 0, "maximum": 1, "default": 0.45 }, "iters": { "type": "integer", "minimum": 0, "default": 4 }, "wall_threshold": { "type": "integer", "minimum": 0, "maximum": 8, "default": 5 }, "connect_all": { "type": "boolean", "default": true } } } ``` ### 2.2 Output data contract - `generate_dungeon` return dict ```json { "grid": { "description": "2D list of ints, grid[Y][X]; 0=floor, 1=wall, 2=door", "type": "array", "items": { "type": "array", "items": { "enum": [0, 1, 2] } } }, "rooms": { "description": "List of Room dataclass instances (x, y, w, h, center)", "type": "array" }, "seed": { "type": "integer" }, "stats": { "type": "object", "properties": { "width": { "type": "integer" }, "height": { "type": "integer" }, "tiles": { "type": "integer" }, "rooms": { "type": "integer" }, "floor": { "type": "integer" }, "walls": { "type": "integer" }, "doors": { "type": "integer" }, "connectivity": { "enum": ["verified by BFS", "split"] } } } } ``` ### 2.3 Output artifacts | Artifact | Path | Format | | ------------------------ | ------------------------------------------------------------- | ------ | | Reference implementation | `skills/procedural-dungeon-generator/dungeon_gen.py` | Python | | Console report | `to_ascii(grid)` text + JSON stats, printed by `main()` | stdout | ## 3. Production Reference Implementation ```python """dungeon_gen.py - deterministic procedural 2D tilemap generator. Implements three composable algorithm families: * BSP room layout - a binary space partitioning tree subdivides the map, each leaf stamps a Room, sibling subtrees are joined with L-shaped corridors. * A* corridor carving - grid search with a Manhattan heuristic and a configurable wall cost for cutting through rock. * Cellular automata - smoothed random noise plus BFS connected-component flood-fill that retains only the largest walkable region. Grid encoding: 0 = floor, 1 = wall, 2 = door. Pure stdlib: random, math, collections, dataclasses, heapq, json. Run directly: python dungeon_gen.py """ from __future__ import annotations import heapq import json import random from collections import deque from dataclasses import dataclass from typing import Dict, List, Optional, Sequence, Tuple FLOOR = 0 WALL = 1 DOOR = 2 LEGEND = {FLOOR: ".", WALL: "#", DOOR: "+"} Point = Tuple[int, int] @dataclass class Room: """An axis-aligned rectangle of floor tiles.""" x: int y: int w: int h: int @property def center(self) -> Point: return (self.x + self.w // 2, self.y + self.h // 2) @property def area(self) -> int: return self.w * self.h def contains(self, px: int, py: int) -> bool: """True when (px, py) lies strictly inside this room.""" return self.x <= px < self.x + self.w and self.y <= py < self.y + self.h def intersects(self, other: "Room") -> bool: """True when two room bodies overlap by more than a shared edge.""" ox0 = max(self.x, other.x) oy0 = max(self.y, other.y) ox1 = min(self.x + self.w, other.x + other.w) oy1 = min(self.y + self.h, other.y + other.h) return ox1 - ox0 > 1 and oy1 - oy0 > 1 @dataclass class BSPTree: """Binary space partitioning node over a rectangular map region.""" x: int y: int w: int h: int depth: int = 0 left: Optional["BSPTree"] = None right: Optional["BSPTree"] = None room: Optional[Room] = None @property def is_leaf(self) -> bool: return self.left is None and self.right is None def split(self, rng: random.Random, min_leaf: int) -> bool: """Recursively subdivide the node until leaves reach ``min_leaf``. Returns True when this node itself was split on this call. """ if not self.is_leaf or self.w < min_leaf * 2 or self.h < min_leaf * 2: return False if self.w > self.h and self.w >= int(self.h * 1.2): split_vertical = True elif self.h > self.w and self.h >= int(self.w * 1.2): split_vertical = False else: split_vertical = rng.random() < 0.5 if split_vertical: cut = rng.randint(min_leaf, self.w - min_leaf) self.left = BSPTree(self.x, self.y, cut, self.h, self.depth + 1) self.right = BSPTree(self.x + cut, self.y, self.w - cut, self.h, self.depth + 1) else: cut = rng.randint(min_leaf, self.h - min_leaf) self.left = BSPTree(self.x, self.y, self.w, cut, self.depth + 1) self.right = BSPTree(self.x, self.y + cut, self.w, self.h - cut, self.depth + 1) self.left.split(rng, min_leaf) self.right.split(rng, min_leaf) return True def create_rooms(self, rng: random.Random, margin: int, min_w: int, min_h: int) -> None: """Stamp one random room into every leaf that is big enough.""" if self.is_leaf: inner_w = self.w - 2 * margin inner_h = self.h - 2 * margin if inner_w < min_w or inner_h < min_h: return room_w = rng.randint(min_w, inner_w) room_h = rng.randint(min_h, inner_h) ox = rng.randint(0, inner_w - room_w) + margin oy = rng.randint(0, inner_h - room_h) + margin self.room = Room(self.x + ox, self.y + oy, room_w, room_h) return if self.left is not None: self.left.create_rooms(rng, margin, min_w, min_h) if self.right is not None: self.right.create_rooms(rng, margin, min_w, min_h) def rooms(self) -> List[Room]: """All rooms stamped onto leaves, depth-first.""" out: List[Room] = [] self._collect_rooms(out) return out def _collect_rooms(self, out: List[Room]) -> None: if self.room is not None: out.append(self.room) if self.left is not None: self.left._collect_rooms(out) if self.right is not None: self.right._collect_rooms(out) def _pick_room(self) -> Optional[Room]: """Deepest room in this subtree, or None when there is none.""" if self.room is not None: return self.room for child in (self.left, self.right): if child is not None: found = child._pick_room() if found is not None: return found return None def carve_corridors(self, grid: List[List[int]]) -> None: """Join every sibling subtree pair with an L-corridor (spanning tree).""" if self.left is not None and self.right is not None: self.left.carve_corridors(grid) self.right.carve_corridors(grid) a = self.left._pick_room() b = self.right._pick_room() if a is not None and b is not None: carve_l(grid, a.center, b.center) def carve_h(grid: List[List[int]], x0: int, x1: int, y: int) -> None: """Knock out an inclusive horizontal floor run on row ``y``.""" lo, hi = (x0, x1) if x0 <= x1 else (x1, x0) for x in range(lo, hi + 1): if grid[y][x] == WALL: grid[y][x] = FLOOR def carve_v(grid: List[List[int]], y0: int, y1: int, x: int) -> None: """Knock out an inclusive vertical floor run on column ``x``.""" lo, hi = (y0, y1) if y0 <= y1 else (y1, y0) for y in range(lo, hi + 1): if grid[y][x] == WALL: grid[y][x] = FLOOR def carve_l(grid: List[List[int]], a: Point, b: Point) -> None: """L-shaped corridor: horizontal leg at a's row, vertical leg at b's column.""" carve_h(grid, a[0], b[0], a[1]) carve_v(grid, a[1], b[1], b[0]) def stamp_room(grid: List[List[int]], room: Room) -> None: """Write every tile of ``room`` into ``grid`` as floor.""" for y in range(room.y, room.y + room.h): for x in range(room.x, room.x + room.w): grid[y][x] = FLOOR def generate_bsp_rooms( width: int, height: int, seed: int, min_leaf: int = 8, min_room: int = 4, margin: int = 1, connect_all: bool = True, ) -> Dict[str, object]: """BSP rectangular-room layout. Splits the map into leaves, stamps a room per leaf, then optionally connects all rooms with L-corridors via room centers. Returns a dict with ``grid``, ``rooms``, ``tree`` and ``seed`` keys. """ rng = random.Random(seed) grid: List[List[int]] = [[WALL] * width for _ in range(height)] tree = BSPTree(0, 0, width, height) tree.split(rng, min_leaf) tree.create_rooms(rng, margin, min_room, min_room) rooms = tree.rooms() if connect_all: tree.carve_corridors(grid) for room in rooms: stamp_room(grid, room) return {"grid": grid, "rooms": rooms, "tree": tree, "seed": seed} class AStar: """Grid pathfinder used to carve corridors between distant rooms. Walls are traversable at a configurable ``wall_cost`` so the search prefers existing floor but cuts through rock when required. Ties on the heap are broken by an insertion counter, keeping results fully deterministic. """ def __init__(self, grid: List[List[int]], wall_cost: int = 8) -> None: self.grid = grid self.wall_cost = wall_cost @staticmethod def _h(a: Point, b: Point) -> int: return abs(a[0] - b[0]) + abs(a[1] - b[1]) def cost(self, x: int, y: int) -> int: return self.wall_cost if self.grid[y][x] == WALL else 1 def _neighbors(self, x: int, y: int): ht, wt = len(self.grid), len(self.grid[0]) for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)): nx, ny = x + dx, y + dy if 0 <= nx < wt and 0 <= ny < ht: yield nx, ny def find(self, start: Point, goal: Point) -> Optional[List[Point]]: """Return the optimal path (list of (x, y), start included) or None.""" if start == goal: return [start] start_key = (start[0], start[1]) goal_key = (goal[0], goal[1]) open_heap = [(self._h(start, goal), 0, start_key)] counter = 1 came_from: Dict[Tuple[int, int], Tuple[int, int]] = {} g_score: Dict[Tuple[int, int], int] = {start_key: 0} closed: set = set() while open_heap: _, _, current = heapq.heappop(open_heap) if current == goal_key: path = [current] while current in came_from: current = came_from[current] path.append(current) path.reverse() return [(x, y) for (x, y) in path] if current in closed: continue closed.add(current) cur_g = g_score[current] for nx, ny in self._neighbors(*current): nxt = (nx, ny) if nxt in closed: continue tentative = cur_g + self.cost(nx, ny) if tentative < g_score.get(nxt, 10 ** 9): came_from[nxt] = current g_score[nxt] = tentative heapq.heappush(open_heap, (tentative + self._h(nxt, goal_key), counter, nxt)) counter += 1 return None def _adjacent_to_room(grid: List[List[int]], x: int, y: int, rooms: Sequence[Room]) -> bool: ht, wt = len(grid), len(grid[0]) for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)): nx, ny = x + dx, y + dy if 0 <= nx < wt and 0 <= ny < ht: for r in rooms: if r.contains(nx, ny): return True return False def carve_astar_corridor(grid: List[List[int]], start: Point, goal: Point, rooms: Sequence[Room], pathfinder: AStar) -> int: """Carve an A* corridor from ``start`` to ``goal``; returns door count. Wall tiles on the path that sit right before re-entering a room become doors instead of plain floor. """ path = pathfinder.find(start, goal) if path is None: return 0 doors = 0 for (x, y) in path: if grid[y][x] == WALL: inside = any(r.contains(x, y) for r in rooms) if not inside and _adjacent_to_room(grid, x, y, rooms): grid[y][x] = DOOR doors += 1 else: grid[y][x] = FLOOR return doors def cellular_automata_cave( width: int, height: int, fill: float = 0.45, iters: int = 4, wall_threshold: int = 5, seed: int = 0, ) -> List[List[int]]: """Organic cave map from smoothed random noise. ``fill`` is the initial wall probability, ``iters`` the number of smoothing generations and ``wall_threshold`` the neighbour wall count needed for a cell to remain wall. The result then keeps only the largest reachable component so the map is never split into islands. """ rng = random.Random(seed) grid: List[List[int]] = [ [WALL if rng.random() < fill else FLOOR for _ in range(width)] for _ in range(height) ] for _ in range(iters): grid = _automata_step(grid, wall_threshold) _keep_largest_component(grid) return grid def _automata_step(grid: List[List[int]], wall_threshold: int) -> List[List[int]]: ht, wt = len(grid), len(grid[0]) out: List[List[int]] = [[WALL] * wt for _ in range(ht)] for y in range(ht): for x in range(wt): walls = 0 for dy in (-1, 0, 1): for dx in (-1, 0, 1): if dx == 0 and dy == 0: continue nx, ny = x + dx, y + dy if nx < 0 or nx >= wt or ny < 0 or ny >= ht: walls += 1 elif grid[ny][nx] == WALL: walls += 1 out[y][x] = WALL if walls >= wall_threshold else FLOOR return out def connected_components(grid: List[List[int]]) -> List[List[Point]]: """Orthogonal BFS flood-fill grouping every floor tile into a component.""" ht, wt = len(grid), len(grid[0]) seen = [[False] * wt for _ in range(ht)] comps: List[List[Point]] = [] for y in range(ht): for x in range(wt): if grid[y][x] != FLOOR or seen[y][x]: continue seen[y][x] = True queue = deque([(x, y)]) cells: List[Point] = [] while queue: cx, cy = queue.popleft() cells.append((cx, cy)) for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)): nx, ny = cx + dx, cy + dy if (0 <= nx < wt and 0 <= ny < ht and not seen[ny][nx] and grid[ny][nx] == FLOOR): seen[ny][nx] = True queue.append((nx, ny)) comps.append(cells) return comps def _keep_largest_component(grid: List[List[int]]) -> None: """Convert every floor component except the largest back into walls.""" comps = connected_components(grid) if not comps: return largest = max(comps, key=len) for comp in comps: if comp is largest: continue for (x, y) in comp: grid[y][x] = WALL def _is_single_component(grid: List[List[int]]) -> bool: comps = connected_components(grid) return sum(1 for c in comps if c) <= 1 def generate_dungeon(width: int, height: int, seed: int) -> Dict[str, object]: """Full pipeline entry point. Builds a BSP room layout, connects leaves with L-corridors, then uses A* to carve extra corridors between several room pairs. Returns a dict with ``grid`` (0 floor, 1 wall, 2 door), ``rooms``, ``tree``, ``seed`` and ``stats``. """ rng = random.Random(seed) base = generate_bsp_rooms(width, height, seed, connect_all=True) grid: List[List[int]] = base["grid"] rooms: List[Room] = base["rooms"] if len(rooms) >= 2: pathfinder = AStar(grid, wall_cost=8) order = list(rooms) rng.shuffle(order) for a, b in zip(order, order[1:]): carve_astar_corridor(grid, a.center, b.center, rooms, pathfinder) floor = sum(row.count(FLOOR) for row in grid) walls = sum(row.count(WALL) for row in grid) doors = sum(row.count(DOOR) for row in grid) stats = { "width": width, "height": height, "tiles": width * height, "seed": seed, "rooms": len(rooms), "floor": floor, "walls": walls, "doors": doors, "connectivity": "verified by BFS" if _is_single_component(grid) else "split", } return { "grid": grid, "rooms": rooms, "tree": base["tree"], "seed": seed, "stats": stats, } def to_ascii(grid: List[List[int]]) -> str: """Render the grid as text: '.' = floor, '#' = wall, '+' = door.""" return "\n".join("".join(LEGEND.get(cell, "?") for cell in row) for row in grid) def main(width: int = 44, height: int = 26, seed: int = 1337) -> None: """Print the BSP dungeon, its JSON stats, and the cave variant.""" dungeon = generate_dungeon(width, height, seed) print("BSP + A* dungeon (seed=%d, %dx%d)" % (seed, width, height)) print(to_ascii(dungeon["grid"])) print(json.dumps(dungeon["stats"], indent=2, sort_keys=True)) cave = cellular_automata_cave(width, height, seed=seed) print("\nCellular-automata cave (seed=%d)" % seed) print(to_ascii(cave)) if __name__ == "__main__": main() ``` ## 4. Execution Protocol & Step-by-Step Workflow 1. **Copy the module.** Place `dungeon_gen.py` in the project's `scripts` or `procedural/` package. No dependency install step is required. 2. **Generate a full dungeon.** Call `data = generate_dungeon(44, 26, seed=1337)`. The returned dict contains `grid` (0/1/2 tile matrix), `rooms`, `tree`, `seed` and `stats`. 3. **Inspect floors, walls, doors.** Sum the tile counts from `stats` and assert `floor + walls + doors == width * height`. 4. **Read the map.** Print `to_ascii(data["grid"])` for a human-readable pass; the `+` cells are doors carved by A* near room entrances. 5. **Tune the layout.** Raise `min_leaf` for fewer, larger rooms; raise `wall_cost` on `AStar` if corridors should hug rooms instead of tunneling. 6. **Generate caves instead.** Call `cave = cellular_automata_cave(width, height, fill=0.45, iters=4, wall_threshold=5, seed=seed)`. Raise `fill` for more wall, raise `iters` for rounder blobs. 7. **Verify reachability.** Run `connected_components(grid)`; the largest component must contain every floor tile on a correctly generated map. 8. **Determinism audit (agent).** Regenerate with the same seed twice and `diff` the ASCII outputs; they must be byte-identical. ## 5. Edge Cases & Error Handling - **Map too small to split.** When `width < min_leaf * 2` (or height), the root stays a leaf, `split()` returns False, and a single room is stamped if the leaf fits — no crash. - **Leaf too small for a room.** `create_rooms` returns silently when a leaf cannot fit `min_room + 2 * margin`; `_pick_room` walks up the subtree so corridor carving always finds a real anchor. - **Barren grid for caves.** If every tile becomes wall, `comps` is empty, `_keep_largest_component` returns early and the map stays all-walls; the caller should raise `fill`/re-seed rather than path-find a corpse. - **A* unreachable goal.** `find` returns `None` and `carve_astar_corridor` returns 0 doors; generation continues without corrupting existing rooms. - **Index safety in carving.** Corridor legs clamp runs with `lo/hi` ordering and rooms pre-validate `contains`, so no partial corridor exceeds the grid. - **Reproductibility guarantees.** A single seeded `random.Random` feeds all random draws (split cuts, room offsets/shuffles, noise) and heap ties are ordered by insertion counter, so identical seeds always yield identical grids and stats. - **Connectivity contract.** `_is_single_component` uses the same BFS as the cave generator; a `"split"` verdict in `stats` flags degenerate input (e.g. `min_room` larger than every leaf) for the caller to adjust.