Procedural generation

Procedural Generation

Triggers

• procedural generation
• procedural content
• pcg
• noise function
• perlin noise
• simplex noise
• worley noise
• voronoi noise
• terrain generation
• dungeon generation
• cave generation
• wave function collapse
• wfc
• l-system
• lindenmayer
• markov chain
• roguelike level
• infinite world
• minecraft-style
• seeded random
• cellular automata
• bsp dungeon
• fractal
• fbm
• octaves
• generate level
• random dungeon
• no man's sky
• spelunky generation
• dwarf fortress
• randomized content

Patterns

Layered Noise for Natural Terrain

Combine multiple octaves of noise for realistic terrain

Creating heightmaps, terrain, natural-looking surfaces

# LAYERED NOISE (FRACTAL BROWNIAN MOTION)

"""
The key insight: Nature has detail at every scale.
Mountains have foothills, which have boulders, which have pebbles.
FBM simulates this by summing noise at different frequencies.

Critical parameters:
- Octaves: Number of layers (6-8 typical, more = more detail = slower)
- Persistence: Amplitude reduction per octave (0.5 = each octave half as strong)
- Lacunarity: Frequency increase per octave (2.0 = each octave twice as detailed)

Tuning guide:
- persistence 0.3-0.4: Smooth, rolling hills
- persistence 0.5: Standard terrain
- persistence 0.6-0.7: Jagged, aggressive terrain
"""

class FractalNoise:
    def __init__(self, seed: int):
        self.noise = PerlinNoise(seed)

    def fbm(self, x: float, y: float,
            octaves: int = 6,
            persistence: float = 0.5,
            lacunarity: float = 2.0,
            scale: float = 1.0) -> float:
        """
        Fractal Brownian Motion - the workhorse of terrain generation.
        Returns value in [-1, 1] range.
        """
        total = 0.0
        amplitude = 1.0
        frequency = scale
        max_value = 0.0

        for i in range(octaves):
            total += self.noise.get(x * frequency, y * frequency) * amplitude
            max_value += amplitude
            amplitude *= persistence
            frequency *= lacunarity

        return total / max_value

    def ridged_fbm(self, x: float, y: float, **kwargs) -> float:
        """
        Ridged noise - abs(noise) creates ridge-like features.
        Great for mountain ranges.
        """
        value = self.fbm(x, y, **kwargs)
        return 1.0 - abs(value)

    def turbulence(self, x: float, y: float, **kwargs) -> float:
        """
        Turbulence - sum of absolute noise values.
        Creates billowy, cloud-like patterns.
        """
        total = 0.0
        amplitude = 1.0
        frequency = kwargs.get('scale', 1.0)

        for i in range(kwargs.get('octaves', 6)):
            total += abs(self.noise.get(x * frequency, y * frequency)) * amplitude
            amplitude *= kwargs.get('persistence', 0.5)
            frequency *= kwargs.get('lacunarity', 2.0)

        return total

# Domain Warping - the secret to organic-looking terrain
"""
Domain warping feeds noise output back as input coordinates.
This creates swirling, organic shapes that break up grid artifacts.

The "double warp" technique from Inigo Quilez:
1. Warp coordinates with one noise function
2. Warp again with the result
3. Sample final terrain with warped coordinates
"""

class DomainWarpedTerrain:
    def __init__(self, seed: int):
        self.noise = FractalNoise(seed)
        self.warp_noise = FractalNoise(seed + 1000)

    def get_height(self, x: float, y: float) -> float:
        # First warp layer
        warp_x1 = self.warp_noise.fbm(x, y, octaves=3)
        warp_y1 = self.warp_noise.fbm(x + 5.2, y + 1.3, octaves=3)

        # Second warp layer (warped warp!)
        warp_x2 = self.warp_noise.fbm(
            x + 4.0 * warp_x1,
            y + 4.0 * warp_y1,
            octaves=3
        )
        warp_y2 = self.warp_noise.fbm(
            x + 4.0 * warp_x1 + 1.7,
            y + 4.0 * warp_y1 + 9.2,
            octaves=3
        )

        # Final terrain sample with warped coordinates
        return self.noise.fbm(
            x + 4.0 * warp_x2,
            y + 4.0 * warp_y2,
            octaves=6,
            persistence=0.5
        )

Generate-Validate-Fallback Loop

Never show invalid content to players

Any procedural content that could be unplayable

# THE GENERATE-VALIDATE-FALLBACK PATTERN

"""
This is THE most important pattern in production PCG.
Every shipped game uses some version of this.

The loop:
1. Generate content with a seed
2. Validate all requirements are met
3. If invalid, try next seed
4. After N attempts, use hand-crafted fallback

Critical insight: Validation is CHEAP compared to player frustration.
Even if 10% of seeds fail, checking 10-20 seeds is instant.
"""

class ValidatedDungeonGenerator:
    def __init__(self, base_seed: int):
        self.base_seed = base_seed
        self.max_attempts = 100
        self.fallback_count = 0

    def generate(self, params: DungeonParams) -> Dungeon:
        for attempt in range(self.max_attempts):
            seed = self.base_seed + attempt
            dungeon = self._raw_generate(params, seed)

            validation = self._validate(dungeon, params)
            if validation.passed:
                # Log successful seed for debugging
                logger.info(f"Seed {seed} passed after {attempt + 1} attempts")
                return dungeon

            # Log WHY it failed - invaluable for tuning
            logger.debug(f"Seed {seed} failed: {validation.reason}")

        # Fallback to guaranteed-valid content
        self.fallback_count += 1
        logger.warning(f"Using fallback (total: {self.fallback_count})")
        return self._get_fallback(params)

    def _validate(self, dungeon: Dungeon, params: DungeonParams) -> ValidationResult:
        """
        Check ALL requirements. Order matters - check cheap things first.
        """
        # 1. Basic structure (cheap)
        if not dungeon.spawn_point:
            return ValidationResult(False, "No spawn point")

        if not dungeon.exit_point:
            return ValidationResult(False, "No exit")

        # 2. Size requirements (cheap)
        floor_count = dungeon.count_floor_tiles()
        if floor_count < params.min_floor_tiles:
            return ValidationResult(False, f"Too small: {floor_count}")

        if floor_count > params.max_floor_tiles:
            return ValidationResult(False, f"Too large: {floor_count}")

        # 3. Connectivity (moderate cost - flood fill)
        if not self._is_connected(dungeon):
            return ValidationResult(False, "Disconnected areas exist")

        # 4. Reachability (moderate cost - pathfinding)
        if not self._is_reachable(dungeon, dungeon.spawn_point, dungeon.exit_point):
            return ValidationResult(False, "Exit not reachable from spawn")

        # 5. Game-specific requirements (potentially expensive)
        if params.require_treasure_room:
            if not self._has_treasure_room(dungeon):
                return ValidationResult(False, "No treasure room")

        # 6. Difficulty validation (expensive - may involve simulation)
        if params.validate_difficulty:
            difficulty = self._estimate_difficulty(dungeon)
            if not params.min_difficulty <= difficulty <= params.max_difficulty:
                return ValidationResult(False, f"Difficulty {difficulty} out of range")

        return ValidationResult(True, "All checks passed")

    def _is_connected(self, dungeon: Dungeon) -> bool:
        """Flood fill from spawn to verify all floor tiles reachable."""
        visited = set()
        stack = [dungeon.spawn_point]

        while stack:
            pos = stack.pop()
            if pos in visited:
                continue
            if not dungeon.is_walkable(pos):
                continue

            visited.add(pos)
            for neighbor in dungeon.get_neighbors(pos):
                stack.append(neighbor)

        return len(visited) == dungeon.count_floor_tiles()

Seed-Based Reproducibility

Identical seeds produce identical results, always

Any procedural system that needs debugging or sharing

# DETERMINISTIC SEEDED GENERATION

"""
Without seed reproducibility, PCG debugging is impossible.
Players can't share interesting worlds. QA can't reproduce bugs.

Requirements for true reproducibility:
1. NEVER use Math.random() or unseeded random
2. Use integer math where possible (floats differ across platforms)
3. Order of random calls must be deterministic
4. No external dependencies (time, user input) during generation
"""

# HIGH-QUALITY SEEDED PRNG
class SplitMix64:
    """
    SplitMix64: Fast, high-quality PRNG used by Java's SplittableRandom.
    Better statistical properties than LCG or xorshift alone.
    """

    def __init__(self, seed: int):
        # Use BigInt for 64-bit precision in JavaScript
        self.state = seed & 0xFFFFFFFFFFFFFFFF

    def next_u64(self) -> int:
        self.state = (self.state + 0x9E3779B97F4A7C15) & 0xFFFFFFFFFFFFFFFF
        z = self.state
        z = ((z ^ (z >> 30)) * 0xBF58476D1CE4E5B9) & 0xFFFFFFFFFFFFFFFF
        z = ((z ^ (z >> 27)) * 0x94D049BB133111EB) & 0xFFFFFFFFFFFFFFFF
        return (z ^ (z >> 31)) & 0xFFFFFFFFFFFFFFFF

    def next_float(self) -> float:
        """Returns float in [0, 1)"""
        return self.next_u64() / 0x10000000000000000

    def next_int(self, min_val: int, max_val: int) -> int:
        """Returns int in [min_val, max_val] inclusive"""
        range_size = max_val - min_val + 1
        return min_val + (self.next_u64() % range_size)

    def shuffle(self, array: list) -> list:
        """Fisher-Yates shuffle - deterministic with seed"""
        result = array.copy()
        for i in range(len(result) - 1, 0, -1):
            j = self.next_int(0, i)
            result[i], result[j] = result[j], result[i]
        return result

# COORDINATE-BASED HASHING
"""
For infinite worlds, you can't pre-generate everything.
Use coordinate hashing to get deterministic values per-location.
"""

def coord_hash(x: int, y: int, seed: int) -> int:
    """
    Hash coordinates to get a deterministic value.
    Based on Squirrel3 by Squirrel Eiserloh (GDC 2017).
    """
    NOISE1 = 0xB5297A4D
    NOISE2 = 0x68E31DA4
    NOISE3 = 0x1B56C4E9

    n = seed
    n ^= x * NOISE1
    n ^= y * NOISE2
    n *= NOISE3
    n ^= n >> 8
    n *= NOISE1
    n ^= n >> 8
    n *= NOISE3
    n ^= n >> 8
    return n & 0xFFFFFFFF

def coord_float(x: int, y: int, seed: int) -> float:
    """Get deterministic float [0,1) for coordinate."""
    return coord_hash(x, y, seed) / 0x100000000

# SEEDED NOISE CLASS
class SeededNoise:
    """Perlin noise with guaranteed reproducibility."""

    def __init__(self, seed: int):
        self.seed = seed
        # Generate permutation table deterministically
        rng = SplitMix64(seed)
        p = list(range(256))
        self.perm = rng.shuffle(p) * 2  # Double for wraparound

Wave Function Collapse (WFC)

Constraint-based generation from example patterns

Generating content that matches specific aesthetic patterns, tilemap generation

# WAVE FUNCTION COLLAPSE - THE REAL IMPLEMENTATION

"""
WFC is powerful but overhyped. Use it when:
- You have example images/patterns to learn from
- You need local consistency (each tile fits neighbors)
- You want specific aesthetics from examples

DON'T use it when:
- You need global structure (WFC is local-only)
- Performance is critical (it's slow)
- You can achieve the same with simpler rules

The algorithm:
1. Each cell starts with all tiles possible
2. Find cell with lowest entropy (fewest possibilities)
3. Collapse it to one random valid tile
4. Propagate constraints to neighbors
5. Repeat until done or contradiction
"""

class WaveFunctionCollapse:
    def __init__(self, tileset: Tileset):
        self.tileset = tileset
        self.adjacency_rules = self._extract_adjacency(tileset)

    def _extract_adjacency(self, tileset: Tileset) -> dict:
        """
        Learn which tiles can be adjacent from examples.
        Or define rules manually for more control.
        """
        rules = {tile.id: {
            'north': set(),
            'south': set(),
            'east': set(),
            'west': set()
        } for tile in tileset.tiles}

        # Learn from example image
        for example in tileset.examples:
            for y in range(example.height):
                for x in range(example.width):
                    tile = example.get(x, y)
                    if y > 0:
                        rules[tile]['north'].add(example.get(x, y-1))
                    if y < example.height - 1:
                        rules[tile]['south'].add(example.get(x, y+1))
                    if x > 0:
                        rules[tile]['west'].add(example.get(x-1, y))
                    if x < example.width - 1:
                        rules[tile]['east'].add(example.get(x+1, y))

        return rules

    def generate(self, width: int, height: int, seed: int) -> Optional[Grid]:
        rng = SplitMix64(seed)

        # Initialize: all tiles possible everywhere
        grid = [[set(self.tileset.tile_ids) for _ in range(width)]
                for _ in range(height)]

        # History for backtracking
        history = []
        backtracks = 0
        max_backtracks = width * height * 2

        while True:
            # Find cell with minimum entropy > 1
            min_entropy = float('inf')
            min_cells = []

            for y in range(height):
                for x in range(width):
                    entropy = len(grid[y][x])
                    if entropy == 0:
                        # Contradiction! Backtrack
                        if not history:
                            return None  # Can't backtrack further

                        backtracks += 1
                        if backtracks > max_backtracks:
                            return None

                        # Restore previous state
                        snapshot = history.pop()
                        grid = self._clone_grid(snapshot['grid'])

                        # Remove the choice that led to contradiction
                        bad_choice = snapshot['choice']
                        grid[snapshot['y']][snapshot['x']].discard(bad_choice)

                        min_cells = []  # Re-scan
                        break

                    if 1 < entropy < min_entropy:
                        min_entropy = entropy
                        min_cells = [(x, y)]
                    elif entropy == min_entropy:
                        min_cells.append((x, y))
                else:
                    continue
                break

            if not min_cells:
                # All cells collapsed - done!
                return [[next(iter(cell)) for cell in row] for row in grid]

            # Choose random cell among minimum entropy cells
            x, y = min_cells[rng.next_int(0, len(min_cells) - 1)]
            possibilities = list(grid[y][x])

            # Weight by tile frequency for more natural results
            weights = [self.tileset.get_weight(t) for t in possibilities]
            choice = self._weighted_choice(possibilities, weights, rng)

            # Save state before collapsing (for backtracking)
            history.append({
                'grid': self._clone_grid(grid),
                'x': x, 'y': y,
                'choice': choice
            })

            # Collapse
            grid[y][x] = {choice}

            # Propagate constraints
            self._propagate(grid, x, y)

    def _propagate(self, grid: list, start_x: int, start_y: int):
        """Propagate constraints using worklist algorithm."""
        width = len(grid[0])
        height = len(grid)

        worklist = [(start_x, start_y)]

        while worklist:
            x, y = worklist.pop()
            current = grid[y][x]

            neighbors = [
                (x, y-1, 'north', 'south'),
                (x, y+1, 'south', 'north'),
                (x-1, y, 'west', 'east'),
                (x+1, y, 'east', 'west')
            ]

            for nx, ny, direction, reverse in neighbors:
                if not (0 <= nx < width and 0 <= ny < height):
                    continue

                neighbor = grid[ny][nx]
                if len(neighbor) <= 1:
                    continue

                # Find what's allowed based on current cell
                allowed = set()
                for tile in current:
                    allowed.update(self.adjacency_rules[tile][direction])

                # Constrain neighbor
                new_neighbor = neighbor & allowed
                if new_neighbor != neighbor:
                    grid[ny][nx] = new_neighbor
                    worklist.append((nx, ny))

L-Systems for Organic Structures

Grammar-based generation for plants, trees, branching structures

Creating trees, plants, rivers, coral, lightning, branching patterns

# L-SYSTEMS (LINDENMAYER SYSTEMS)

"""
L-systems are parallel rewriting systems that model growth.
Perfect for: trees, plants, rivers, blood vessels, lightning.

Key concepts:
- Alphabet: symbols (F = forward, + = turn right, - = turn left)
- Axiom: starting string
- Rules: how symbols transform each iteration
- Interpretation: how to draw the final string

The magic: simple rules create complex, natural-looking structures.
"""

class LSystem:
    def __init__(self, axiom: str, rules: dict, angle: float = 25):
        self.axiom = axiom
        self.rules = rules
        self.angle = angle

    def generate(self, iterations: int) -> str:
        """Apply rules iteratively to produce final string."""
        current = self.axiom
        for _ in range(iterations):
            next_str = ""
            for char in current:
                next_str += self.rules.get(char, char)
            current = next_str
        return current

    def interpret(self, string: str, start_pos: tuple, start_angle: float) -> list:
        """
        Turtle graphics interpretation.
        Returns list of line segments for rendering.
        """
        lines = []
        stack = []  # For branching ([, ])

        x, y = start_pos
        angle = start_angle
        step = 10

        for char in string:
            if char == 'F':  # Draw forward
                new_x = x + step * math.cos(math.radians(angle))
                new_y = y + step * math.sin(math.radians(angle))
                lines.append(((x, y), (new_x, new_y)))
                x, y = new_x, new_y

            elif char == 'f':  # Move forward without drawing
                x += step * math.cos(math.radians(angle))
                y += step * math.sin(math.radians(angle))

            elif char == '+':  # Turn right
                angle += self.angle

            elif char == '-':  # Turn left
                angle -= self.angle

            elif char == '[':  # Save state (branch start)
                stack.append((x, y, angle, step))

            elif char == ']':  # Restore state (branch end)
                x, y, angle, step = stack.pop()

            elif char == '>':  # Decrease step (taper)
                step *= 0.9

            elif char == '<':  # Increase step
                step *= 1.1

        return lines

# CLASSIC L-SYSTEM EXAMPLES

# Simple tree
simple_tree = LSystem(
    axiom="F",
    rules={"F": "F[+F]F[-F]F"},
    angle=25
)

# More natural tree (stochastic L-system)
class StochasticLSystem(LSystem):
    """L-system with random rule selection."""

    def __init__(self, axiom: str, rules: dict, angle: float, seed: int):
        super().__init__(axiom, rules, angle)
        self.rng = SplitMix64(seed)

    def generate(self, iterations: int) -> str:
        current = self.axiom
        for _ in range(iterations):
            next_str = ""
            for char in current:
                if char in self.rules:
                    options = self.rules[char]
                    if isinstance(options, list):
                        # Multiple rules with weights
                        choice = self._weighted_choice(options)
                        next_str += choice
                    else:
                        next_str += options
                else:
                    next_str += char
            current = next_str
        return current

# Natural-looking tree with randomness
natural_tree = StochasticLSystem(
    axiom="X",
    rules={
        "X": [
            ("F[+X][-X]FX", 0.4),      # Standard branching
            ("F[+X]F[-X]+X", 0.3),      # Asymmetric
            ("F[-X]+X", 0.15),          # Single branch
            ("F[+X]", 0.15)             # Other single branch
        ],
        "F": "FF"
    },
    angle=25,
    seed=12345
)

# Bracketed OL-system for bush
bush = LSystem(
    axiom="F",
    rules={"F": "FF+[+F-F-F]-[-F+F+F]"},
    angle=22.5
)

# Dragon curve (fractal)
dragon = LSystem(
    axiom="FX",
    rules={"X": "X+YF+", "Y": "-FX-Y"},
    angle=90
)

Markov Chains for Names and Text

Generate plausible names, words, text based on statistical patterns

Fantasy names, procedural dialogue, generated descriptions

# MARKOV CHAINS FOR NAME/TEXT GENERATION

"""
Markov chains generate sequences where each element depends on previous N elements.
Perfect for: character names, place names, procedural dialogue, item descriptions.

Order matters:
- Order 1: Each letter depends on previous letter (often nonsense)
- Order 2-3: Sweet spot for names (captures syllable patterns)
- Order 4+: More "real" but needs more training data
"""

class MarkovNameGenerator:
    def __init__(self, order: int = 2):
        self.order = order
        self.chains = {}  # prefix -> [possible next chars]
        self.starters = []  # Valid starting sequences

    def train(self, names: list[str]):
        """Learn patterns from example names."""
        for name in names:
            # Pad with start/end markers
            padded = '^' * self.order + name.lower() + '$'

            # Extract starting sequences
            self.starters.append(padded[:self.order + 1])

            # Build transition chains
            for i in range(len(padded) - self.order):
                prefix = padded[i:i + self.order]
                next_char = padded[i + self.order]

                if prefix not in self.chains:
                    self.chains[prefix] = []
                self.chains[prefix].append(next_char)

    def generate(self, rng, min_length: int = 3, max_length: int = 12) -> str:
        """Generate a new name."""
        for attempt in range(100):  # Avoid infinite loops
            # Start with a random starter
            current = rng.choice(self.starters)
            name = current[self.order:]  # Remove padding

            while len(name) < max_length:
                prefix = current[-self.order:]

                if prefix not in self.chains:
                    break

                next_char = rng.choice(self.chains[prefix])

                if next_char == '$':  # End marker
                    if len(name) >= min_length:
                        return name.capitalize()
                    break

                name += next_char
                current = prefix + next_char

            if min_length <= len(name) <= max_length:
                return name.capitalize()

        return "Unknown"  # Fallback

# TRAINING EXAMPLE

# Fantasy names trained on real name patterns
fantasy_generator = MarkovNameGenerator(order=2)
fantasy_generator.train([
    "Aragorn", "Legolas", "Gandalf", "Frodo", "Samwise",
    "Thorin", "Bilbo", "Galadriel", "Eowyn", "Faramir",
    "Boromir", "Celeborn", "Elrond", "Arwen", "Gimli"
])

# Generate new names
rng = SplitMix64(42)
new_names = [fantasy_generator.generate(rng) for _ in range(10)]
# Might produce: "Frothrin", "Legandor", "Arondil", etc.

# HIGHER-ORDER CHAINS FOR DESCRIPTIONS

class TextMarkovGenerator:
    """Word-level Markov chain for longer text."""

    def __init__(self, order: int = 2):
        self.order = order
        self.chains = {}
        self.starters = []

    def train(self, texts: list[str]):
        for text in texts:
            words = text.split()
            if len(words) < self.order + 1:
                continue

            self.starters.append(tuple(words[:self.order]))

            for i in range(len(words) - self.order):
                prefix = tuple(words[i:i + self.order])
                next_word = words[i + self.order]

                if prefix not in self.chains:
                    self.chains[prefix] = []
                self.chains[prefix].append(next_word)

    def generate(self, rng, max_words: int = 30) -> str:
        if not self.starters:
            return ""

        current = list(rng.choice(self.starters))
        result = list(current)

        for _ in range(max_words - self.order):
            prefix = tuple(current[-self.order:])

            if prefix not in self.chains:
                break

            next_word = rng.choice(self.chains[prefix])
            result.append(next_word)
            current = current[1:] + [next_word]

            # Stop at sentence end
            if next_word.endswith('.'):
                break

        return ' '.join(result)

Cellular Automata for Caves

Use simple rules to generate organic cave structures

Cave systems, organic shapes, erosion simulation

# CELLULAR AUTOMATA FOR CAVE GENERATION

"""
Cellular automata apply simple local rules repeatedly to create complex patterns.
The 4-5 rule is classic for caves:
- If a cell has 4+ wall neighbors, it becomes wall
- If a cell has 5+ wall neighbors, it stays wall

Pros: Very fast, organic-looking results
Cons: Can create disconnected areas (need flood fill validation)
"""

class CaveGenerator:
    def __init__(self, seed: int):
        self.rng = SplitMix64(seed)

    def generate(self, width: int, height: int,
                fill_probability: float = 0.45,
                iterations: int = 5,
                birth_limit: int = 4,
                death_limit: int = 3) -> list:
        """
        Generate cave using cellular automata.

        Parameters:
        - fill_probability: Initial chance of wall (0.45-0.55 typical)
        - iterations: Smoothing passes (4-6 typical)
        - birth_limit: Neighbors needed to become wall
        - death_limit: Neighbors needed to stay floor
        """

        # Initialize with random walls
        grid = [[1 if self.rng.next_float() < fill_probability else 0
                for _ in range(width)]
                for _ in range(height)]

        # Ensure border is always wall
        for y in range(height):
            grid[y][0] = 1
            grid[y][width - 1] = 1
        for x in range(width):
            grid[0][x] = 1
            grid[height - 1][x] = 1

        # Apply cellular automata rules
        for _ in range(iterations):
            grid = self._step(grid, birth_limit, death_limit)

        return grid

    def _step(self, grid: list, birth: int, death: int) -> list:
        """Apply one step of cellular automata."""
        height = len(grid)
        width = len(grid[0])
        new_grid = [[0] * width for _ in range(height)]

        for y in range(height):
            for x in range(width):
                neighbors = self._count_neighbors(grid, x, y)

                if grid[y][x] == 1:  # Currently wall
                    # Wall survives if enough neighbors
                    new_grid[y][x] = 1 if neighbors >= death else 0
                else:  # Currently floor
                    # Floor becomes wall if enough neighbors
                    new_grid[y][x] = 1 if neighbors >= birth else 0

        return new_grid

    def _count_neighbors(self, grid: list, x: int, y: int) -> int:
        """Count wall neighbors in 3x3 area."""
        count = 0
        height = len(grid)
        width = len(grid[0])

        for dy in range(-1, 2):
            for dx in range(-1, 2):
                if dx == 0 and dy == 0:
                    continue

                nx, ny = x + dx, y + dy

                # Treat out-of-bounds as wall
                if nx < 0 or nx >= width or ny < 0 or ny >= height:
                    count += 1
                elif grid[ny][nx] == 1:
                    count += 1

        return count

    def ensure_connected(self, grid: list, min_size: int = 100) -> list:
        """
        Find largest connected floor region, fill others.
        CRITICAL: Without this, players can spawn in isolated caves.
        """
        height = len(grid)
        width = len(grid[0])
        visited = [[False] * width for _ in range(height)]

        regions = []

        # Find all connected floor regions
        for y in range(height):
            for x in range(width):
                if grid[y][x] == 0 and not visited[y][x]:
                    region = self._flood_fill(grid, visited, x, y)
                    regions.append(region)

        if not regions:
            return grid  # All walls - regenerate

        # Keep largest region, fill others
        regions.sort(key=len, reverse=True)
        keep = set(regions[0])

        for y in range(height):
            for x in range(width):
                if grid[y][x] == 0 and (x, y) not in keep:
                    grid[y][x] = 1  # Fill disconnected areas

        return grid

BSP Dungeon Generation

Binary Space Partitioning for structured dungeon layouts

Roguelike dungeons, room-and-corridor layouts

# BINARY SPACE PARTITIONING (BSP) DUNGEONS

"""
BSP recursively divides space into rooms connected by corridors.

Pros:
- Guaranteed connectivity (siblings always connect)
- Structured feel (rooms don't overlap)
- Easy to control room sizes and density

Cons:
- Can feel "grid-like" without post-processing
- Corridor placement can be predictable
"""

class BSPDungeon:
    def __init__(self, seed: int):
        self.rng = SplitMix64(seed)
        self.rooms = []

    def generate(self, width: int, height: int,
                min_room_size: int = 6,
                max_depth: int = 4) -> tuple:
        """
        Generate dungeon using BSP.
        Returns (grid, rooms) where grid[y][x] is 0=floor, 1=wall.
        """
        self.rooms = []

        # Start with root node covering entire space
        root = BSPNode(1, 1, width - 2, height - 2)

        # Recursively split
        self._split(root, min_room_size, max_depth, 0)

        # Create rooms in leaf nodes
        self._create_rooms(root, min_room_size)

        # Initialize grid as all walls
        grid = [[1] * width for _ in range(height)]

        # Carve rooms
        for room in self.rooms:
            for y in range(room.y, room.y + room.h):
                for x in range(room.x, room.x + room.w):
                    grid[y][x] = 0

        # Connect rooms (connect sibling nodes)
        self._connect(root, grid)

        return grid, self.rooms

    def _split(self, node, min_size: int, max_depth: int, depth: int):
        """Recursively split a node."""
        if depth >= max_depth:
            return

        # Stop if too small
        if node.width < min_size * 2 and node.height < min_size * 2:
            return

        # Choose split direction
        if node.width > node.height * 1.5:
            split_horizontal = False  # Split vertically (make narrower)
        elif node.height > node.width * 1.5:
            split_horizontal = True   # Split horizontally (make shorter)
        else:
            split_horizontal = self.rng.next_float() > 0.5

        if split_horizontal:
            if node.height < min_size * 2:
                return

            # Random split point
            split = self.rng.next_int(min_size, node.height - min_size)

            node.left = BSPNode(node.x, node.y, node.width, split)
            node.right = BSPNode(node.x, node.y + split, node.width,
                                 node.height - split)
        else:
            if node.width < min_size * 2:
                return

            split = self.rng.next_int(min_size, node.width - min_size)

            node.left = BSPNode(node.x, node.y, split, node.height)
            node.right = BSPNode(node.x + split, node.y,
                                 node.width - split, node.height)

        # Recurse
        self._split(node.left, min_size, max_depth, depth + 1)
        self._split(node.right, min_size, max_depth, depth + 1)

    def _create_rooms(self, node, min_size: int):
        """Create rooms in leaf nodes."""
        if node.left is None and node.right is None:
            # Leaf node - create room
            room_width = self.rng.next_int(min_size, node.width - 2)
            room_height = self.rng.next_int(min_size, node.height - 2)
            room_x = node.x + self.rng.next_int(1, node.width - room_width - 1)
            room_y = node.y + self.rng.next_int(1, node.height - room_height - 1)

            room = Room(room_x, room_y, room_width, room_height)
            node.room = room
            self.rooms.append(room)
        else:
            if node.left:
                self._create_rooms(node.left, min_size)
            if node.right:
                self._create_rooms(node.right, min_size)

    def _connect(self, node, grid: list):
        """Connect sibling rooms with corridors."""
        if node.left is None or node.right is None:
            return

        # Recurse first
        self._connect(node.left, grid)
        self._connect(node.right, grid)

        # Get a room from each child (any room will do)
        room1 = self._get_room(node.left)
        room2 = self._get_room(node.right)

        if room1 and room2:
            self._carve_corridor(grid, room1.center, room2.center)

    def _get_room(self, node) -> Room:
        """Get any room from a node's subtree."""
        if node.room:
            return node.room
        if node.left:
            room = self._get_room(node.left)
            if room:
                return room
        if node.right:
            return self._get_room(node.right)
        return None

    def _carve_corridor(self, grid: list, start: tuple, end: tuple):
        """Carve L-shaped corridor between two points."""
        x1, y1 = start
        x2, y2 = end

        # Random choice: horizontal first or vertical first
        if self.rng.next_float() > 0.5:
            # Horizontal then vertical
            for x in range(min(x1, x2), max(x1, x2) + 1):
                grid[y1][x] = 0
            for y in range(min(y1, y2), max(y1, y2) + 1):
                grid[y][x2] = 0
        else:
            # Vertical then horizontal
            for y in range(min(y1, y2), max(y1, y2) + 1):
                grid[y][x1] = 0
            for x in range(min(x1, x2), max(x1, x2) + 1):
                grid[y2][x] = 0

class BSPNode:
    def __init__(self, x: int, y: int, width: int, height: int):
        self.x = x
        self.y = y
        self.width = width
        self.height = height
        self.left = None
        self.right = None
        self.room = None

class Room:
    def __init__(self, x: int, y: int, w: int, h: int):
        self.x = x
        self.y = y
        self.w = w
        self.h = h
        self.center = (x + w // 2, y + h // 2)

Chunked Infinite World Generation

Generate content on-demand for infinite worlds

Open world games, Minecraft-style generation, large terrains

# CHUNKED INFINITE WORLD GENERATION

"""
Infinite worlds require on-demand generation:
- Can't generate everything upfront (infinite!)
- Must be fast enough during gameplay
- Same chunk must always generate identically

Key insight: Use coordinate hashing, not sequential random.
This lets any chunk be generated independently.
"""

class InfiniteWorld:
    CHUNK_SIZE = 32

    def __init__(self, world_seed: int):
        self.world_seed = world_seed
        self.loaded_chunks = {}  # (cx, cy) -> Chunk
        self.noise = SeededNoise(world_seed)

    def get_tile(self, world_x: int, world_y: int) -> Tile:
        """Get tile at any world coordinate."""
        chunk_x = world_x // self.CHUNK_SIZE
        chunk_y = world_y // self.CHUNK_SIZE

        chunk = self.get_or_generate_chunk(chunk_x, chunk_y)

        local_x = world_x % self.CHUNK_SIZE
        local_y = world_y % self.CHUNK_SIZE

        return chunk.tiles[local_y][local_x]

    def get_or_generate_chunk(self, cx: int, cy: int) -> Chunk:
        """Load chunk from cache or generate it."""
        key = (cx, cy)

        if key in self.loaded_chunks:
            return self.loaded_chunks[key]

        # Generate chunk
        chunk = self._generate_chunk(cx, cy)
        self.loaded_chunks[key] = chunk

        return chunk

    def _generate_chunk(self, cx: int, cy: int) -> Chunk:
        """
        Generate a single chunk.
        CRITICAL: Must be deterministic based only on (cx, cy, world_seed).
        """
        # Get chunk-specific seed (deterministic hash)
        chunk_seed = coord_hash(cx, cy, self.world_seed)
        chunk_rng = SplitMix64(chunk_seed)

        chunk = Chunk(cx, cy)

        for ly in range(self.CHUNK_SIZE):
            for lx in range(self.CHUNK_SIZE):
                world_x = cx * self.CHUNK_SIZE + lx
                world_y = cy * self.CHUNK_SIZE + ly

                # Terrain height
                height = self.noise.fbm(
                    world_x * 0.01,
                    world_y * 0.01,
                    octaves=6
                )

                # Moisture for biomes
                moisture = self.noise.fbm(
                    world_x * 0.01 + 1000,
                    world_y * 0.01 + 1000,
                    octaves=4
                )

                # Determine biome
                biome = self._get_biome(height, moisture)

                chunk.tiles[ly][lx] = Tile(biome, height)

        # Add features (trees, rocks, etc.)
        self._add_features(chunk, chunk_rng)

        return chunk

    def _get_biome(self, height: float, moisture: float) -> str:
        """
        Biome selection based on height and moisture.
        Based on Whittaker biome diagram.
        """
        if height < -0.2:
            return 'deep_water'
        if height < 0.0:
            return 'water'
        if height < 0.05:
            return 'beach'
        if height > 0.7:
            return 'snow'
        if height > 0.5:
            return 'mountain' if moisture < 0.3 else 'alpine'

        # Normal land biomes
        if moisture < 0.2:
            return 'desert'
        if moisture < 0.4:
            return 'grassland'
        if moisture < 0.7:
            return 'forest'
        return 'rainforest'

    def _add_features(self, chunk: Chunk, rng: SplitMix64):
        """Add trees, rocks, etc. to chunk."""
        for ly in range(self.CHUNK_SIZE):
            for lx in range(self.CHUNK_SIZE):
                tile = chunk.tiles[ly][lx]

                if tile.biome == 'forest':
                    if rng.next_float() < 0.15:  # 15% tree chance
                        tile.feature = 'tree'
                elif tile.biome == 'desert':
                    if rng.next_float() < 0.02:  # 2% cactus chance
                        tile.feature = 'cactus'

    def unload_distant_chunks(self, center_cx: int, center_cy: int,
                              radius: int = 8):
        """Unload chunks far from player to save memory."""
        to_remove = []

        for (cx, cy) in self.loaded_chunks:
            dist = max(abs(cx - center_cx), abs(cy - center_cy))
            if dist > radius:
                to_remove.append((cx, cy))

        for key in to_remove:
            del self.loaded_chunks[key]

    def preload_chunks(self, center_cx: int, center_cy: int,
                      radius: int = 3):
        """Pre-generate chunks around player for smooth movement."""
        for dy in range(-radius, radius + 1):
            for dx in range(-radius, radius + 1):
                self.get_or_generate_chunk(center_cx + dx, center_cy + dy)

Anti-Patterns

Using Math.random() for Generation

Why: Non-seedable random prevents reproducibility

Generate and Hope

Why: Not validating generated content is playable

Pure Randomness

Why: Making everything random without design constraints

Floating-Point Coordinates at World Scale

Why: Using floats for large world coordinates

Synchronous Generation Blocking Main Thread

Why: Generating large content on main thread freezes game

Ignoring Edge Cases in Noise

Why: Not handling noise artifacts and edge cases

One-Size-Fits-All Generation

Why: Same generation parameters for all content types

Validation Checklist

• [ERROR] Unseeded Math.random() Usage

  • Math.random() detected in procedural generation code. Use a seedable PRNG instead:

• SplitMix64/Xoshiro for high quality

• Mulberry32 for simple use cases

• Custom LCG if you need to match legacy systems

• [WARNING] Seed Storage/Logging

  • Ensure seeds are:

1. Logged on generation (console.log, analytics)
2. Stored with save data
3. Displayed to players for sharing

• [WARNING] Deterministic Operation Order
  • Potential non-determinism detected. Ensure:

1. Sort arrays before iteration with random
2. Use arrays instead of Sets/Maps when order matters
3. Avoid Promise.all when results affect random sequence

• [ERROR] Generated Content Validation
  • Generated content should be validated for:

1. Connectivity (all areas reachable)
2. Completability (can reach exit from spawn)
3. Required elements present (keys, items)
4. No softlock conditions Have a fallback for when validation fails.

• [WARNING] Fallback Content Exists
  • No fallback content detected. Add:

1. Hand-crafted backup levels
2. Known-good seed database
3. Simplified generation mode

• [WARNING] Flood Fill Connectivity Check

  • No connectivity check found. Generated maps may have isolated areas. Implement flood fill from spawn to verify all areas are reachable.

• [WARNING] Async/Background Generation

  • Large generation loop may block main thread. Consider:

1. Web Workers for heavy computation
2. requestIdleCallback for time-slicing
3. Chunked generation across frames
4. Show loading indicator during generation

• [WARNING] Chunk-Based Infinite World
  • Large world detected without chunking. Implement:

1. Coordinate to chunk mapping
2. Chunk loading/unloading by distance
3. Chunk caching with LRU eviction
4. Pre-generation of nearby chunks

• [INFO] Noise Function Caching
  • Consider caching noise values for repeated lookups:

1. Memoize by coordinate hash
2. Pre-compute heightmaps
3. Use LOD for distant samples

• [INFO] Domain Warping for Natural Terrain

  • Consider adding domain warping to break up noise grid artifacts: warpedNoise(x, y) = noise(x + noise(x,y), y + noise(x+c,y+c))

• [WARNING] WFC Backtracking Support

  • WFC detected without visible backtracking. Implement:

1. History stack for backtracking
2. Max backtrack limit
3. Restart on contradiction
4. Fallback pattern for repeated failures

• [WARNING] L-System Growth Limits
  • L-system detected without visible limits. Add:

1. Maximum iteration count
2. Maximum string length
3. Early termination on overflow

• [INFO] Markov Chain Training Size

  • Ensure Markov chain has sufficient training data:

• Order 1: 20+ examples

• Order 2: 50+ examples

• Order 3: 200+ examples

• Higher orders need exponentially more

• [WARNING] Large Coordinate Handling

  • Large coordinates detected. Ensure:

1. Rendering uses camera-relative coords
2. Chunk coordinates are integers
3. Local positions within chunks
4. Origin recentering for far positions

• [INFO] Float Accumulation Errors

  • Float accumulation may cause platform divergence. Calculate from integers: BAD: pos += 0.001 GOOD: pos = step * stepSize

• [INFO] Content Variety System

  • Consider adding variety mechanisms:

1. Weighted rarity tiers (common/uncommon/rare)
2. Bad luck protection (increasing rare chance)
3. Guaranteed unique elements per level
4. Level "moods" or themes

• [INFO] Biome Transition Smoothing
  • Biome system detected. Consider smooth transitions:

1. Sample biomes at low frequency
2. Blend properties in transition zones
3. Define valid transition pairs
4. Avoid impossible adjacencies (snow next to desert)

• [INFO] Player-Visible Seed

  • Consider displaying seed to players for sharing. Human-friendly format: "dragon-castle-42" > "847293847"

• [INFO] Generation Quality Metrics

  • Consider tracking generation metrics:

• First-attempt success rate

• Average retry count

• Fallback usage rate

• Failed seed patterns

• [INFO] Generation Debug Visualization

  • Consider adding debug visualization:

1. Noise value heatmaps
2. Room/corridor overlays
3. Validation step display
4. Parameter sliders (dat.GUI)