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

Related Issues:

#123 - Subgrid system for large worlds
#67 - Grid stitching for seamless chunks
#55 - Agent simulation demo

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"""
        # Choose split direction based on aspect ratio
        if self.w > self.h:
            direction = "vertical"
        elif self.h > self.w:
            direction = "horizontal"
        else:
            direction = random.choice(["vertical", "horizontal"])
        
        # Calculate split position (30-70%)
        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  # Can't split further
    
    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

# Generate dungeon layout
def generate_bsp_dungeon(grid, num_splits=4):
    w, h = grid.grid_size
    root = BinaryRoomNode(0, 0, w, h)
    
    # Split recursively
    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
    
    # Get leaf rooms
    rooms = root.get_leaves()
    
    # Carve rooms into grid
    for room in rooms:
        # Add margin
        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.tilesprite = 0  # Floor tile
                cell.color = (128, 128, 128, 255)
    
    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"""
    # Horizontal first
    for x in range(min(x1, x2), max(x1, x2) + 1):
        cell = grid.at((x, y1))
        cell.walkable = True
        cell.tilesprite = 0
    
    # Then vertical
    for y in range(min(y1, y2), max(y1, y2) + 1):
        cell = grid.at((x2, y))
        cell.walkable = 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]
        
        # Room centers
        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 can_place(self, grid, x, y):
        """Check if tile can be placed at (x, y)"""
        # Check each neighbor
        if y > 0:  # North
            north_tile = grid.at((x, y - 1)).tilesprite
            if north_tile not in self.neighbors["north"]:
                return False
        
        if y < grid.grid_size[1] - 1:  # South
            south_tile = grid.at((x, y + 1)).tilesprite
            if south_tile not in self.neighbors["south"]:
                return False
        
        # ... check east/west similarly
        return True

# Define tile rules (example: simple dungeon)
FLOOR = 0
WALL = 1
RULES = [
    TileRule(FLOOR, north=[FLOOR, WALL], south=[FLOOR, WALL],
             east=[FLOOR, WALL], west=[FLOOR, WALL]),
    TileRule(WALL, north=[WALL], south=[WALL], 
             east=[WALL], west=[WALL])
]

def wfc_generate(grid):
    """Generate tiles using Wave Function Collapse"""
    w, h = grid.grid_size
    
    # Track cells with multiple possibilities
    possibilities = {}
    for x in range(w):
        for y in range(h):
            possibilities[(x, y)] = [0, 1]  # Can be floor or wall
    
    # Iteratively collapse
    while possibilities:
        # Find cell with minimum entropy (fewest possibilities)
        min_cell = min(possibilities.keys(), 
                       key=lambda c: len(possibilities[c]))
        x, y = min_cell
        
        # Choose random tile from possibilities
        tile = random.choice(possibilities[min_cell])
        grid.at((x, y)).tilesprite = tile
        del possibilities[min_cell]
        
        # Update neighbor possibilities based on constraints
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = x + dx, y + dy
            if (nx, ny) in possibilities:
                # Filter based on placed tile's constraints
                # (simplified - real WFC is more complex)
                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
Special cardinal direction rules
Weighted tile selection
Multi-pass convergence

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):
            if random.random() < fill_probability:
                grid.at((x, y)).walkable = False
                grid.at((x, y)).tilesprite = 1  # Wall
            else:
                grid.at((x, y)).walkable = True
                grid.at((x, y)).tilesprite = 0  # Floor
    
    # Iterate cellular automata rules
    for _ in range(iterations):
        next_state = []
        for x in range(w):
            for y in range(h):
                # Count wall neighbors
                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  # Out of bounds = wall
                        elif not grid.at((nx, ny)).walkable:
                            wall_count += 1
                
                # Apply rule: become wall if 5+ neighbors are walls
                is_wall = wall_count >= 5
                next_state.append((x, y, is_wall))
        
        # Apply next state
        for x, y, is_wall in next_state:
            grid.at((x, y)).walkable = not is_wall
            grid.at((x, y)).tilesprite = 1 if is_wall else 0

Smoothing and Refinement

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):
        """Returns size of connected region"""
        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))
            
            # Add neighbors
            stack.extend([(cx-1, cy), (cx+1, cy), (cx, cy-1), (cx, cy+1)])
        
        return region
    
    # Find all regions
    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)
    
    # Keep only largest region, fill others
    if regions:
        largest = max(regions, key=len)
        for region in regions:
            if len(region) < min_size:
                for x, y in region:
                    grid.at((x, y)).walkable = False
                    grid.at((x, y)).tilesprite = 1

Noise-Based Terrain

Perlin/Simplex Noise

Generate heightmaps for terrain:

# Requires noise library: pip install noise
import noise

def generate_terrain(grid, scale=0.1, octaves=4):
    """Generate terrain using Perlin noise"""
    w, h = grid.grid_size
    
    for x in range(w):
        for y in range(h):
            # Sample noise
            value = noise.pnoise2(x * scale, y * scale, 
                                  octaves=octaves,
                                  persistence=0.5,
                                  lacunarity=2.0,
                                  repeatx=w,
                                  repeaty=h,
                                  base=0)
            
            # Map to tile types (-1 to 1 -> 0 to N)
            if value < -0.3:
                tile = 2  # Water
                walkable = False
            elif value < 0.0:
                tile = 0  # Grass
                walkable = True
            elif value < 0.3:
                tile = 1  # Forest
                walkable = True
            else:
                tile = 3  # Mountain
                walkable = False
            
            cell = grid.at((x, y))
            cell.tilesprite = tile
            cell.walkable = walkable

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):
            # Random walkable position in room
            x = random.randint(room.x, room.x + room.w - 1)
            y = random.randint(room.y, room.y + room.h - 1)
            
            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
    max_attempts = num_items * 10
    
    while placed < num_items and attempts < max_attempts:
        # Random room
        room = random.choice(rooms)
        x = random.randint(room.x, room.x + room.w - 1)
        y = random.randint(room.y, room.y + room.h - 1)
        
        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=256):
        self.chunk_size = chunk_size
        self.loaded_chunks = {}  # (cx, cy) -> Grid
    
    def get_chunk(self, chunk_x, chunk_y):
        """Load or generate chunk"""
        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):
        """Generate a single chunk"""
        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)
        )
        
        # Use chunk coordinates as seed for deterministic generation
        seed = hash((cx, cy))
        random.seed(seed)
        
        # Generate terrain for this chunk
        generate_terrain(grid, scale=0.1)
        
        return grid
    
    def unload_distant_chunks(self, player_chunk, radius=2):
        """Unload chunks far from player"""
        px, py = player_chunk
        to_unload = []
        
        for (cx, cy), chunk in self.loaded_chunks.items():
            if abs(cx - px) > radius or abs(cy - py) > radius:
                to_unload.append((cx, cy))
        
        for key in to_unload:
            del self.loaded_chunks[key]

Issue #123 and Issue #67 track official subgrid and chunk stitching support.

Performance Considerations

Batch Grid Updates

Set many cells efficiently:

# SLOW: Individual cell updates
for x in range(100):
    for y in range(100):
        cell = grid.at((x, y))
        cell.tilesprite = compute_tile(x, y)

# FASTER: Minimize Python/C++ crossings
tiles = []
for x in range(100):
    for y in range(100):
        tiles.append(compute_tile(x, y))

# Then set in batch (when batch API available - see [[Performance-and-Profiling]])
for i, (x, y) in enumerate(coords):
    grid.at((x, y)).tilesprite = tiles[i]

Generation Timing

Generate during scene transitions or in background:

def start_generation():
    """Begin procedural generation"""
    mcrfpy.createScene("loading")
    mcrfpy.setScene("loading")
    
    # Start generation timer
    mcrfpy.setTimer("generate", generate_world, 10)

def generate_world(ms):
    """Generate incrementally"""
    global generation_step
    
    if generation_step == 0:
        rooms = generate_bsp_dungeon(grid)
    elif generation_step == 1:
        connect_rooms(grid, rooms)
    elif generation_step == 2:
        wfc_generate_tiles(grid)
    elif generation_step == 3:
        place_entities(grid)
    else:
        # Done!
        mcrfpy.setScene("game")
        mcrfpy.delTimer("generate")
        return
    
    generation_step += 1

Examples and Demos

Complete Dungeon Generator

import mcrfpy
import random

def create_procedural_dungeon():
    """Complete dungeon generation pipeline"""
    # Create grid
    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. Tile placement with WFC
    wfc_generate_tiles(grid)
    
    # 4. Smooth with cellular automata
    smooth_edges(grid)
    
    # 5. 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)
    
    # 6. Place enemies
    place_entities(grid, rooms[1:], entity_density=0.05)
    
    # 7. 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
mcrfpy.createScene("game")
mcrfpy.setScene("game")
grid, player = create_procedural_dungeon()
ui = mcrfpy.sceneUI("game")
ui.append(grid)

See src/scripts/cos_level.py and src/scripts/cos_tiles.py for production examples from "Crypt of Sokoban."

API Reference

See docs/api_reference_dynamic.html for Grid and Entity APIs.

Key Grid Methods:

grid.at((x, y)) - Get cell for modification
grid.grid_size - Get dimensions
grid.entities - Entity collection

Key Cell Properties:

cell.tilesprite - Tile index
cell.walkable - Pathfinding flag
cell.color - RGBA tint

Navigation:

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