Castle of the Winds
Dungeon Generation

# Castle of the Winds — Dungeon Generation (reconstructed from seg11 disassembly)
# Algorithm by Rick Saada (SaadaSoft), 1993. Reverse-engineered for archival purposes.

import random
from collections import deque
from dataclasses import dataclass, field
from typing import Optional

# ── Tile constants (matching original byte encoding) ──────────────────────────
TILE_WALL     = 0x00
TILE_FLOOR    = 0x01
TILE_STAIR_DN = 0x12  # bits 1+4  (DS:0xCE2 tile type byte)
TILE_STAIR_UP = 0x13  # bits 0+1+4
FLAG_ROOM     = 0x20  # room interior  (tile flags byte)
FLAG_CORR     = 0x0C  # corridor
FLAG_DOOR     = 0x40  # door junction

MAP_W, MAP_H = 64, 64


# ── MS C rand() LCG — matches MSVC runtime seen in CotW data segment ──────────
class MSCRand:
    def __init__(self, seed: int = 12345):
        self.state = seed & 0xFFFFFFFF

    def next(self) -> int:
        self.state = (self.state * 214013 + 2531011) & 0xFFFFFFFF
        return (self.state >> 16) & 0x7FFF

    def rng(self, n: int) -> int:
        return self.next() % n


@dataclass
class Room:
    col: int; row: int; w: int; h: int
    cx: int = field(init=False)
    cy: int = field(init=False)
    def __post_init__(self):
        self.cx = self.col + self.w // 2
        self.cy = self.row + self.h // 2


class Dungeon:
    def __init__(self, w: int = MAP_W, h: int = MAP_H):
        self.w, self.h = w, h
        # 3 arrays mirror the original DS:0xCE2 layout: [type, flags, entity]
        self.tile_type   = bytearray(w * h)
        self.tile_flags  = bytearray(w * h)
        self.tile_entity = bytearray(w * h)

    def idx(self, r: int, c: int) -> int:
        return r * self.w + c

    def clear(self):
        # rep stosb DS:0xCE2, 0, 0x3000  (seg11:0x1B04)
        for arr in (self.tile_type, self.tile_flags, self.tile_entity):
            arr[:] = bytearray(len(arr))

    def can_place(self, col: int, row: int, w: int, h: int) -> bool:
        # seg11:0x164E — check area + 1-tile border for any non-zero tile
        for r in range(max(0, row - 1), min(self.h, row + h + 1)):
            for c in range(max(0, col - 1), min(self.w, col + w + 1)):
                if self.tile_type[self.idx(r, c)] != 0:
                    return False
        return True

    def draw_room(self, col: int, row: int, w: int, h: int):
        # seg11:0x0E30 — tile |= FLOOR; flags |= FLAG_ROOM
        for r in range(row, row + h):
            for c in range(col, col + w):
                i = self.idx(r, c)
                self.tile_type[i]  |= TILE_FLOOR
                self.tile_flags[i] |= FLAG_ROOM

    def draw_corridor(self, c1: int, r1: int, c2: int, r2: int):
        # seg11:0x1A88 — L-shaped corridor: horizontal then vertical
        # Only sets tiles that are currently wall (rooms take priority)
        for c in range(min(c1, c2), max(c1, c2) + 1):
            i = self.idx(r1, c)
            if not self.tile_type[i]:
                self.tile_type[i]  |= TILE_FLOOR
                self.tile_flags[i] |= FLAG_CORR
        for r in range(min(r1, r2), max(r1, r2) + 1):
            i = self.idx(r, c2)
            if not self.tile_type[i]:
                self.tile_type[i]  |= TILE_FLOOR
                self.tile_flags[i] |= FLAG_CORR

    def flood_fill_components(self) -> list[int]:
        # BFS to label every floor tile with a component ID
        comp = [-1] * (self.w * self.h)
        num  = 0
        dirs = [(-1,0),(1,0),(0,-1),(0,1)]
        for start_r in range(self.h):
            for start_c in range(self.w):
                si = self.idx(start_r, start_c)
                if not self.tile_type[si] or comp[si] != -1:
                    continue
                q = deque([(start_r, start_c)])
                comp[si] = num
                while q:
                    r, c = q.popleft()
                    for dr, dc in dirs:
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < self.h and 0 <= nc < self.w:
                            ni = self.idx(nr, nc)
                            if self.tile_type[ni] and comp[ni] == -1:
                                comp[ni] = num
                                q.append((nr, nc))
                num += 1
        return comp

    def ensure_connected(self, rooms: list[Room]):
        # Flood-fill, then bridge any room not reachable from room[0]
        comp = self.flood_fill_components()
        connected = {comp[self.idx(rooms[0].cy, rooms[0].cx)]}
        for i, b in enumerate(rooms[1:], 1):
            b_comp = comp[self.idx(b.cy, b.cx)]
            if b_comp not in connected:
                # Connect to the nearest already-connected room
                best = min(
                    (a for a in rooms
                     if comp[self.idx(a.cy, a.cx)] in connected),
                    key=lambda a: abs(a.cx - b.cx) + abs(a.cy - b.cy)
                )
                self.draw_corridor(best.cx, best.cy, b.cx, b.cy)
                connected.add(b_comp)


def generate(
    level:       int = 1,
    max_rooms:   int = 12,
    corr_chance: int = 70,   # % chance to draw corridor between consecutive rooms
    seed:        Optional[int] = None,
) -> Dungeon:
    rng = MSCRand(seed if seed is not None else random.randint(0, 0xFFFF))
    d   = Dungeon()
    d.clear()

    rooms: list[Room] = []
    prev: Optional[Room] = None

    for _ in range(max_rooms * 3):
        if len(rooms) >= max_rooms:
            break
        # rand(W/3) + rand(W/3)  — biases towards map centre (seg11:0x0BCE)
        col = rng.rng(MAP_W // 3) + rng.rng(MAP_W // 3) + 1
        row = rng.rng(MAP_H // 3) + rng.rng(MAP_H // 3) + 1
        w   = rng.rng(8) + 4
        h   = rng.rng(8) + 4

        if col + w >= MAP_W - 1 or row + h >= MAP_H - 1:
            continue
        if not d.can_place(col, row, w, h):
            continue

        d.draw_room(col, row, w, h)
        room = Room(col, row, w, h)
        rooms.append(room)

        if prev and rng.rng(100) < corr_chance:
            d.draw_corridor(prev.cx, prev.cy, room.cx, room.cy)

        prev = room

    if len(rooms) > 1:
        d.ensure_connected(rooms)

    # Place stairs — down in first room, up in last (levels 1-3 skip up stairs)
    if rooms:
        r0 = rooms[0]
        d.tile_type[d.idx(r0.row + 1, r0.col + 1)] = TILE_STAIR_DN
        if level > 3 and len(rooms) > 1:
            rL = rooms[-1]
            d.tile_type[d.idx(rL.row + 1, rL.col + 1)] = TILE_STAIR_UP

    return d


def print_map(d: Dungeon):
    GLYPH = {
        TILE_WALL:     '█',
        TILE_FLOOR:    '·',
        TILE_STAIR_DN: '>',
        TILE_STAIR_UP: '<',
    }
    for r in range(d.h):
        row_str = []
        for c in range(d.w):
            t = d.tile_type[d.idx(r, c)]
            f = d.tile_flags[d.idx(r, c)]
            if t == TILE_STAIR_DN:          row_str.append('>')
            elif t == TILE_STAIR_UP:        row_str.append('<')
            elif f & FLAG_DOOR:             row_str.append('+')
            elif f & FLAG_ROOM:             row_str.append('.')
            elif f & FLAG_CORR:             row_str.append('#')
            else:                           row_str.append(' ')
        print(''.join(row_str))


if __name__ == '__main__':
    dungeon = generate(level=5, max_rooms=12, corr_chance=70, seed=42)
    print_map(dungeon)