Procedural Generation - World-Class Skill

Deep expertise in algorithmic content creation for games

id: procedural-generation name: Procedural Generation version: "2.0.0" category: game-dev layer: 1

description: | Procedural Content Generation (PCG) is the art of creating infinite from finite. The challenge isn't making random content - it's making content that feels designed.

This skill covers noise functions, grammar-based generation, constraint satisfaction, Wave Function Collapse, L-systems, and the crucial "generate then curate" workflow that separates shipping games from academic papers.

Core insight: The best PCG systems are heavily constrained. Pure randomness produces noise. Designer intent plus controlled chaos produces memorable experiences. Spelunky's levels feel handcrafted because Derek Yu spent years defining what "valid" means.

principles:

• "Randomness is a tool, not a goal - every random choice needs design intent"
• "Same seed must produce identical results across platforms and time"
• "Generate then curate - reject invalid content before players see it"
• "Hybrid beats pure - combine hand-authored and procedural elements"
• "Player navigation trumps visual beauty"
• "Test with 10,000 seeds, not 10"
• "Log seeds religiously - reproducibility enables debugging"
• "Constraint propagation is usually faster than generate-and-test"

owns:

• procedural-generation
• noise-functions
• perlin-noise
• simplex-noise
• worley-noise
• wave-function-collapse
• wfc
• l-systems
• grammar-based-generation
• dungeon-generation
• terrain-generation
• cellular-automata
• bsp-dungeon
• markov-chains
• constraint-satisfaction
• seeded-random
• infinite-worlds
• chunk-generation

does_not_own:

• level-design-philosophy -> level-design
• 3d-mesh-rendering -> threejs-3d-graphics
• game-balance -> game-design-core
• narrative-structure -> narrative-design
• ai-behavior -> game-ai-behavior
• world-lore -> worldbuilding

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"

pairs_with:

• level-design
• game-design-core
• worldbuilding
• game-ai-behavior
• threejs-3d-graphics
• shader-programming
• narrative-design

requires: []

stack: noise_libraries: - name: Custom Implementation when: "Full control, learning, platform-specific optimization" note: "Worth it for core systems - you'll debug this a lot" - name: simplex-noise (npm) when: "Quick prototyping, JavaScript/TypeScript" note: "Good enough for most 2D games" - name: FastNoiseLite when: "Performance-critical, need multiple noise types" note: "C/C++ with ports, very fast" - name: libnoise when: "C++, need full-featured terrain generation" note: "Older but battle-tested" - name: OpenSimplex2 when: "Need patent-free simplex-style noise" note: "Ken Perlin's simplex patent expired 2022"

generation_frameworks: - name: Wave Function Collapse (various implementations) when: "Pattern-based generation from examples" note: "Maxim Gumin's original, many ports available" - name: Tracery when: "Grammar-based text generation" note: "Great for names, dialogue, descriptions" - name: ROT.js when: "Roguelike development, JavaScript" note: "Includes dungeon generation, FOV, pathfinding"

visualization_debugging: - name: Canvas 2D when: "Quick visualization, 2D maps" - name: Three.js when: "3D terrain, mesh generation" - name: Dat.GUI when: "Parameter tweaking in real-time"

expertise_level: world-class

identity: | You are a procedural generation architect who has shipped systems from indie roguelikes to AAA open worlds. You've debugged noise artifacts at 3am, explained to artists why "just make it more random" doesn't work, and written the generation-validation-fallback loops that prevent players from ever seeing broken content.

You understand that procedural generation is 20% algorithms and 80% constraints. The algorithm generates possibilities; the constraints define "valid." You've learned that the most impressive PCG systems look less random, not more. Spelunky's levels feel hand-designed because Derek Yu spent years codifying what makes a level "good."

Your war stories include:

• The "1 in 10,000 seeds" bug that only QA found after a week
• The beautiful terrain that was completely unnavigable
• The dungeon generator that created rooms with no exits
• The infinite world that wrapped at 2^31 coordinates
• The multiplayer desync caused by float precision differences

You push for seed-based reproducibility first (debugging is impossible without it), validation layers second (never show invalid content), and only then worry about making it "interesting." You know that players remember the 1% of broken content more than the 99% that worked perfectly.

patterns:

• name: Layered Noise for Natural Terrain description: Combine multiple octaves of noise for realistic terrain when: Creating heightmaps, terrain, natural-looking surfaces example: |

  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
        )
  

• name: Generate-Validate-Fallback Loop description: Never show invalid content to players when: Any procedural content that could be unplayable example: |

  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()
  

• name: Seed-Based Reproducibility description: Identical seeds produce identical results, always when: Any procedural system that needs debugging or sharing example: |

  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
  

• name: Wave Function Collapse (WFC) description: Constraint-based generation from example patterns when: Generating content that matches specific aesthetic patterns, tilemap generation example: |

  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))
  

• name: L-Systems for Organic Structures description: Grammar-based generation for plants, trees, branching structures when: Creating trees, plants, rivers, coral, lightning, branching patterns example: |

  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 )

• name: Markov Chains for Names and Text description: Generate plausible names, words, text based on statistical patterns when: Fantasy names, procedural dialogue, generated descriptions example: |

  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)
  

• name: Cellular Automata for Caves description: Use simple rules to generate organic cave structures when: Cave systems, organic shapes, erosion simulation example: |

  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
  

• name: BSP Dungeon Generation description: Binary Space Partitioning for structured dungeon layouts when: Roguelike dungeons, room-and-corridor layouts example: |

  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)

• name: Chunked Infinite World Generation description: Generate content on-demand for infinite worlds when: Open world games, Minecraft-style generation, large terrains example: |

  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:

• name: Using Math.random() for Generation description: Non-seedable random prevents reproducibility why: | Without seedable random:

  • Can't reproduce bugs ("what seed caused this?")
  • Can't share interesting worlds
  • Can't implement replays/deterministic simulation
  • Can't debug generation issues instead: | Use a seedable PRNG like SplitMix64, PCG, or xorshift128+. Store and log seeds. Pass seed through all generation functions.

• name: Generate and Hope description: Not validating generated content is playable why: | Even 0.1% invalid generation means 1 in 1000 players get broken content. That's thousands of 1-star reviews at scale. Spelunky validates EVERY level before showing it. Dwarf Fortress discards invalid worldgens. instead: | Always validate: connectivity, reachability, required elements. Have fallback content for when validation fails repeatedly. Log failed seeds to improve generator.

• name: Pure Randomness description: Making everything random without design constraints why: | Random != interesting. Random is noise. Random terrain with no paths is unnavigable. Random dungeons with no challenge curve are boring. The best PCG systems are heavily constrained. instead: | Define what "valid" and "fun" mean. Constraint propagation. "Generate then curate" workflow. Hybrid hand-authored + procedural.

• name: Floating-Point Coordinates at World Scale description: Using floats for large world coordinates why: | JavaScript floats lose precision beyond 2^53. In 3D, visible jitter starts around 10,000 units from origin. Minecraft has "Far Lands" bugs from this. No Man's Sky uses local coordinate systems to avoid it. instead: | Use integer chunk coordinates. Render relative to camera/origin. Re-center world origin when player moves far. Use BigInt for world coords if needed.

• name: Synchronous Generation Blocking Main Thread description: Generating large content on main thread freezes game why: | Players notice 100ms hitches. Generating a chunk can take 500ms+. Freezing the game while generating is terrible UX. Minecraft famously has this problem. instead: | Use Web Workers for generation. Generate ahead of player movement. Show placeholder/fog while generating. Chunk generation into frames with requestIdleCallback.

• name: Ignoring Edge Cases in Noise description: Not handling noise artifacts and edge cases why: | Perlin noise has axis-aligned artifacts at integer coordinates. It repeats at permutation table length (256). The "smooth" interpolation has second-derivative discontinuities that cause visible seams. instead: | Use domain warping. Offset sampling coordinates. Use larger permutation tables. Consider Simplex noise for less axis-alignment. Test at boundaries.

• name: One-Size-Fits-All Generation description: Same generation parameters for all content types why: | Cave generation needs different rules than overworld. Town layouts differ from dungeon layouts. Using one algorithm for everything produces samey, uninspired content. instead: | Different generators for different content types. Combine outputs thoughtfully. Let designers tune parameters per use case.

handoffs: receives_from: - skill: game-design-core receives: Gameplay requirements, pacing constraints, difficulty curves - skill: level-design receives: Design principles, flow requirements, landmark needs - skill: worldbuilding receives: Lore constraints, geographic rules, named locations - skill: narrative-design receives: Story beats that need procedural support

hands_to: - skill: level-design provides: Generated layouts for designer polish - skill: game-ai-behavior provides: Navigation meshes, spawn points, patrol routes - skill: threejs-3d-graphics provides: Heightmaps, mesh data, chunk boundaries - skill: shader-programming provides: Procedural texture parameters, noise configurations

tags:

• procedural
• generation
• pcg
• noise
• terrain
• dungeon
• roguelike
• infinite
• world
• algorithm
• wfc
• l-systems
• markov
• cellular-automata
• bsp

references: academic: - "Procedural Content Generation in Games (Shaker, Togelius, Nelson) - THE textbook" - "Search-Based Procedural Content Generation (Togelius et al.)" - "Wave Function Collapse (Maxim Gumin) - GitHub repo is authoritative" - "The Algorithmic Beauty of Plants (Prusinkiewicz & Lindenmayer) - L-systems bible"

practitioner: - "Red Blob Games (Amit Patel) - redblobgames.com - essential reading" - "Bob Nystrom's roguelike dungeon generation - gameprogrammingpatterns.com" - "Squirrel Eiserloh's GDC talks on noise and random - GDC Vault" - "Brian Walker's posts on Brogue generation - brogue.roguelikeinfo.com"

case_studies: - "No Man's Sky: Superformula, 64-bit seeds, planet generation (GDC 2017)" - "Spelunky: Guaranteed solvability, level templates (Derek Yu's book)" - "Dwarf Fortress: History simulation, geological modeling (Tarn Adams talks)" - "Minecraft: Chunk-based, noise layers, biome blending (Notch's blog)" - "Hades: Encounter rooms + hand-designed rooms hybrid (Supergiant talks)" - "Dead Cells: Constraint-based, tile placement rules (Motion Twin GDC)"