Procedural Generation

Overview

McRogueFace supports procedural content generation through its Grid and Entity systems. The engine provides the spatial containers and rendering, while Python scripts implement generation algorithms like Binary Space Partitioning, Wave Function Collapse, cellular automata, and noise-based terrain.

Related Pages:

• Grid-System - Spatial containers for generated content
• Entity-Management - Populating grids with entities
• AI-and-Pathfinding - Walkability and navigation for generated maps

Key Files:

• src/scripts/cos_level.py - BSP dungeon generation
• src/scripts/cos_tiles.py - Wave Function Collapse tile placement
• src/UIGrid.cpp - Grid manipulation API

---

Binary Space Partitioning (BSP)

Dungeon Layout Generation

BSP recursively divides space to create room layouts:

import random
import mcrfpy

class BinaryRoomNode:
    """Node in BSP tree representing a room"""
    def __init__(self, x, y, w, h):
        self.x = x
        self.y = y
        self.w = w
        self.h = h
        self.left = None
        self.right = None
    
    def split(self, min_size=8):
        """Split this room into two sub-rooms"""
        if self.w > self.h:
            direction = "vertical"
        elif self.h > self.w:
            direction = "horizontal"
        else:
            direction = random.choice(["vertical", "horizontal"])
        
        split_ratio = random.uniform(0.3, 0.7)
        
        if direction == "vertical" and self.w >= min_size * 2:
            split_x = int(self.w * split_ratio)
            self.left = BinaryRoomNode(self.x, self.y, split_x, self.h)
            self.right = BinaryRoomNode(self.x + split_x, self.y,
                                         self.w - split_x, self.h)
            return True
        elif direction == "horizontal" and self.h >= min_size * 2:
            split_y = int(self.h * split_ratio)
            self.left = BinaryRoomNode(self.x, self.y, self.w, split_y)
            self.right = BinaryRoomNode(self.x, self.y + split_y,
                                         self.w, self.h - split_y)
            return True
        
        return False
    
    def get_leaves(self):
        """Get all leaf rooms (no children)"""
        if self.left is None and self.right is None:
            return [self]
        leaves = []
        if self.left:
            leaves.extend(self.left.get_leaves())
        if self.right:
            leaves.extend(self.right.get_leaves())
        return leaves


def generate_bsp_dungeon(grid, num_splits=4):
    """Generate dungeon layout using BSP"""
    w, h = grid.grid_size
    root = BinaryRoomNode(0, 0, w, h)
    
    nodes = [root]
    for _ in range(num_splits):
        new_nodes = []
        for node in nodes:
            if node.split():
                new_nodes.extend([node.left, node.right])
            else:
                new_nodes.append(node)
        nodes = new_nodes
    
    rooms = root.get_leaves()
    
    # Carve rooms into grid
    for room in rooms:
        rx = room.x + 2
        ry = room.y + 2
        rw = room.w - 4
        rh = room.h - 4
        
        for x in range(rx, rx + rw):
            for y in range(ry, ry + rh):
                cell = grid.at(x, y)
                cell.walkable = True
                cell.transparent = True
                cell.tilesprite = 0  # Floor tile
    
    return rooms

See src/scripts/cos_level.py for the complete implementation used in "Crypt of Sokoban."

Connecting Rooms

After generating rooms, create corridors:

def carve_corridor(grid, x1, y1, x2, y2):
    """L-shaped corridor between two points"""
    for x in range(min(x1, x2), max(x1, x2) + 1):
        cell = grid.at(x, y1)
        cell.walkable = True
        cell.transparent = True
        cell.tilesprite = 0
    
    for y in range(min(y1, y2), max(y1, y2) + 1):
        cell = grid.at(x2, y)
        cell.walkable = True
        cell.transparent = True
        cell.tilesprite = 0


def connect_rooms(grid, rooms):
    """Connect all rooms with corridors"""
    for i in range(len(rooms) - 1):
        r1 = rooms[i]
        r2 = rooms[i + 1]
        x1 = r1.x + r1.w // 2
        y1 = r1.y + r1.h // 2
        x2 = r2.x + r2.w // 2
        y2 = r2.y + r2.h // 2
        carve_corridor(grid, x1, y1, x2, y2)

---

Wave Function Collapse (WFC)

Tile-Based Constraint Solving

WFC generates tilemap patterns that satisfy local constraints:

class TileRule:
    """Constraint: which tiles can appear adjacent"""
    def __init__(self, tile_id, north=None, south=None, east=None, west=None):
        self.tile_id = tile_id
        self.neighbors = {
            "north": north or [],
            "south": south or [],
            "east": east or [],
            "west": west or []
        }


def wfc_generate(grid):
    """Generate tiles using Wave Function Collapse"""
    w, h = grid.grid_size
    
    possibilities = {}
    for x in range(w):
        for y in range(h):
            possibilities[(x, y)] = [0, 1]
    
    while possibilities:
        min_cell = min(possibilities.keys(),
                       key=lambda c: len(possibilities[c]))
        x, y = min_cell
        
        tile = random.choice(possibilities[min_cell])
        grid.at(x, y).tilesprite = tile
        del possibilities[min_cell]
        
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = x + dx, y + dy
            if (nx, ny) in possibilities:
                possibilities[(nx, ny)] = [
                    t for t in possibilities[(nx, ny)]
                    if can_coexist(tile, t)
                ]

See src/scripts/cos_tiles.py for the complete WFC implementation with 9-cell constraint matching and weighted tile selection.

---

Cellular Automata

Cave Generation

Classic cellular automata for organic caves:

import random

def generate_cave(grid, fill_probability=0.45, iterations=5):
    """Generate cave using cellular automata"""
    w, h = grid.grid_size
    
    # Initialize with random noise
    for x in range(w):
        for y in range(h):
            cell = grid.at(x, y)
            if random.random() < fill_probability:
                cell.walkable = False
                cell.transparent = False
                cell.tilesprite = 1  # Wall
            else:
                cell.walkable = True
                cell.transparent = True
                cell.tilesprite = 0  # Floor
    
    # Iterate cellular automata rules
    for _ in range(iterations):
        next_state = []
        for x in range(w):
            for y in range(h):
                wall_count = 0
                for dx in [-1, 0, 1]:
                    for dy in [-1, 0, 1]:
                        if dx == 0 and dy == 0:
                            continue
                        nx, ny = x + dx, y + dy
                        if nx < 0 or nx >= w or ny < 0 or ny >= h:
                            wall_count += 1
                        elif not grid.at(nx, ny).walkable:
                            wall_count += 1
                
                is_wall = wall_count >= 5
                next_state.append((x, y, is_wall))
        
        for x, y, is_wall in next_state:
            cell = grid.at(x, y)
            cell.walkable = not is_wall
            cell.transparent = not is_wall
            cell.tilesprite = 1 if is_wall else 0

Region Cleanup

def remove_small_regions(grid, min_size=10):
    """Flood-fill to remove disconnected small regions"""
    w, h = grid.grid_size
    visited = set()
    
    def flood_fill(x, y):
        stack = [(x, y)]
        region = []
        while stack:
            cx, cy = stack.pop()
            if (cx, cy) in visited:
                continue
            if cx < 0 or cx >= w or cy < 0 or cy >= h:
                continue
            if not grid.at(cx, cy).walkable:
                continue
            visited.add((cx, cy))
            region.append((cx, cy))
            stack.extend([(cx-1, cy), (cx+1, cy), (cx, cy-1), (cx, cy+1)])
        return region
    
    regions = []
    for x in range(w):
        for y in range(h):
            if (x, y) not in visited and grid.at(x, y).walkable:
                region = flood_fill(x, y)
                regions.append(region)
    
    if regions:
        largest = max(regions, key=len)
        for region in regions:
            if region is not largest and len(region) < min_size:
                for x, y in region:
                    cell = grid.at(x, y)
                    cell.walkable = False
                    cell.transparent = False
                    cell.tilesprite = 1

---

Visual Layers for Generated Content

GridPoint properties (walkable, transparent, tilesprite) handle world state. For visual styling, use layers:

# Create grid with explicit layers
grid = mcrfpy.Grid(grid_size=(50, 50), pos=(0, 0), size=(800, 600), layers=[])

# Background colors layer
bg = mcrfpy.ColorLayer(name="background", z_index=-2)
grid.add_layer(bg)
bg.fill(mcrfpy.Color(20, 20, 30, 255))  # Dark blue

# Tile sprites layer (requires a texture)
# tiles = mcrfpy.TileLayer(name="terrain", z_index=-1, texture=tileset)
# grid.add_layer(tiles)

# Fog overlay (above entities)
fog = mcrfpy.ColorLayer(name="fog", z_index=1)
grid.add_layer(fog)
fog.fill(mcrfpy.Color(0, 0, 0, 255))  # Start fully hidden

# After generating rooms, color the background
for room in rooms:
    for x in range(room.x + 2, room.x + room.w - 2):
        for y in range(room.y + 2, room.y + room.h - 2):
            bg.set((x, y), mcrfpy.Color(128, 128, 128, 255))

---

Populating Generated Worlds

Entity Placement

Place entities in generated content:

def place_entities(grid, rooms, entity_density=0.05):
    """Place enemies in rooms"""
    for room in rooms:
        room_area = room.w * room.h
        num_entities = int(room_area * entity_density)
        
        for _ in range(num_entities):
            x = random.randint(room.x + 2, room.x + room.w - 3)
            y = random.randint(room.y + 2, room.y + room.h - 3)
            
            if grid.at(x, y).walkable:
                enemy = mcrfpy.Entity(
                    grid_pos=(x, y),
                    sprite_index=random.randint(10, 15)
                )
                grid.entities.append(enemy)


def place_items(grid, rooms, num_items=10):
    """Place items in random locations"""
    placed = 0
    attempts = 0
    
    while placed < num_items and attempts < num_items * 10:
        room = random.choice(rooms)
        x = random.randint(room.x + 2, room.x + room.w - 3)
        y = random.randint(room.y + 2, room.y + room.h - 3)
        
        if grid.at(x, y).walkable:
            item = mcrfpy.Entity(
                grid_pos=(x, y),
                sprite_index=random.randint(20, 25)
            )
            grid.entities.append(item)
            placed += 1
        
        attempts += 1

---

Large World Generation

Chunk-Based Generation

For worlds larger than memory allows:

class ChunkManager:
    """Generate chunks on-demand"""
    def __init__(self, chunk_size=64):
        self.chunk_size = chunk_size
        self.loaded_chunks = {}
    
    def get_chunk(self, chunk_x, chunk_y):
        key = (chunk_x, chunk_y)
        if key not in self.loaded_chunks:
            self.loaded_chunks[key] = self._generate_chunk(chunk_x, chunk_y)
        return self.loaded_chunks[key]
    
    def _generate_chunk(self, cx, cy):
        grid = mcrfpy.Grid(
            grid_size=(self.chunk_size, self.chunk_size),
            pos=(cx * self.chunk_size * 16, cy * self.chunk_size * 16),
            size=(self.chunk_size * 16, self.chunk_size * 16)
        )
        
        seed = hash((cx, cy))
        random.seed(seed)
        generate_cave(grid)
        
        return grid
    
    def unload_distant_chunks(self, player_chunk, radius=2):
        px, py = player_chunk
        to_unload = [
            key for key in self.loaded_chunks
            if abs(key[0] - px) > radius or abs(key[1] - py) > radius
        ]
        for key in to_unload:
            del self.loaded_chunks[key]

---

Incremental Generation with Timers

Generate during scene transitions to avoid frame drops:

generation_step = [0]
rooms = [None]

def start_generation(grid):
    """Begin incremental procedural generation"""
    scene = mcrfpy.Scene("loading")
    mcrfpy.current_scene = scene
    
    def generate_world(timer, runtime):
        if generation_step[0] == 0:
            rooms[0] = generate_bsp_dungeon(grid)
        elif generation_step[0] == 1:
            connect_rooms(grid, rooms[0])
        elif generation_step[0] == 2:
            place_entities(grid, rooms[0])
        else:
            timer.stop()
            game_scene = mcrfpy.Scene("game")
            game_scene.children.append(grid)
            mcrfpy.current_scene = game_scene
            return
        
        generation_step[0] += 1
    
    mcrfpy.Timer("gen_step", generate_world, 10)

---

Complete Dungeon Generator

import mcrfpy
import random

def create_procedural_dungeon():
    """Complete dungeon generation pipeline"""
    grid = mcrfpy.Grid(grid_size=(100, 100), pos=(0, 0), size=(1024, 768))
    
    # 1. Generate layout with BSP
    rooms = generate_bsp_dungeon(grid, num_splits=4)
    
    # 2. Connect rooms
    connect_rooms(grid, rooms)
    
    # 3. Place player in first room
    first_room = rooms[0]
    player = mcrfpy.Entity(
        grid_pos=(first_room.x + first_room.w // 2,
                  first_room.y + first_room.h // 2),
        sprite_index=1
    )
    grid.entities.append(player)
    
    # 4. Place enemies
    place_entities(grid, rooms[1:], entity_density=0.05)
    
    # 5. Place exit in last room
    last_room = rooms[-1]
    exit_entity = mcrfpy.Entity(
        grid_pos=(last_room.x + last_room.w // 2,
                  last_room.y + last_room.h // 2),
        sprite_index=99
    )
    grid.entities.append(exit_entity)
    
    return grid, player


# Use it
game_scene = mcrfpy.Scene("game")
grid, player = create_procedural_dungeon()
game_scene.children.append(grid)
mcrfpy.current_scene = game_scene

See src/scripts/cos_level.py and src/scripts/cos_tiles.py for production examples.

---

API Reference

Grid Construction:

• mcrfpy.Grid(grid_size=(w, h), pos=(x, y), size=(pw, ph)) - Create grid

Cell Properties (GridPoint):

• cell.walkable - Pathfinding flag (bool)
• cell.transparent - FOV flag (bool)
• cell.tilesprite - Tile sprite index (int, legacy)

Visual Layers:

• mcrfpy.ColorLayer(name="...", z_index=N) - Color overlay layer
• mcrfpy.TileLayer(name="...", z_index=N, texture=tex) - Tile sprite layer
• grid.add_layer(layer) - Attach layer to grid
• layer.set((x, y), value) - Set cell value
• layer.fill(value) - Fill all cells

Entity Placement:

• mcrfpy.Entity(grid_pos=(x, y), sprite_index=N) - Create entity
• grid.entities.append(entity) - Add to grid

---

Navigation:

• Home - Documentation hub
• Grid-System - Spatial container details
• Entity-Management - Populating worlds with entities
• AI-and-Pathfinding - Navigation in generated worlds