ismael-joffroy-chandoutis 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, r
…(truncated)