Procédural Generation — Créer des niveaux infinis avec des algorithmes

La génération procédurale transforme un jeu linéaire en expérience infinie. Découvrez les algorithmes qui font tourner vos roguelikes préférés.

1. Perlin Noise — Terrains naturels

Le bruit de Perlin génère des valeurs continues idéales pour les terrains.

# Pseudo-code
def generate_terrain(width, height, scale):
    terrain = []
    for y in range(height):
        row = []
        for x in range(width):
            # noise() retourne une valeur entre -1 et 1
            value = noise(x / scale, y / scale)
            
            if value < -0.3:
                row.append('DEEP_WATER')
            elif value < 0:
                row.append('WATER')
            elif value < 0.2:
                row.append('BEACH')
            elif value < 0.6:
                row.append('GRASS')
            else:
                row.append('MOUNTAIN')
        terrain.append(row)
    return terrain

Dans Godot 4

extends Node2D

var noise = FastNoiseLite.new()

func _ready():
    noise.noise_type = FastNoiseLite.TYPE_PERLIN
    noise.frequency = 0.05
    noise.seed = randi()
    
    generate_world()

func generate_world():
    for x in range(100):
        for y in range(100):
            var value = noise.get_noise_2d(x, y)
            place_tile(x, y, value_to_tile(value))

2. BSP (Binary Space Partitioning) — Donjons

L'algorithme BSP divise récursivement l'espace pour créer des salles connectées.

class BSPNode:
    def __init__(self, x, y, width, height):
        self.rect = Rect(x, y, width, height)
        self.left = None
        self.right = None
        self.room = None
    
    def split(self, min_size=6):
        if self.left or self.right:
            # Déjà divisé, continuer récursivement
            self.left.split(min_size)
            self.right.split(min_size)
            return
        
        # Choisir direction de division
        split_horizontal = random.random() > 0.5
        
        if split_horizontal:
            if self.rect.height < min_size * 2:
                return  # Trop petit
            split_at = random.randint(min_size, self.rect.height - min_size)
            self.left = BSPNode(self.rect.x, self.rect.y, 
                                self.rect.width, split_at)
            self.right = BSPNode(self.rect.x, self.rect.y + split_at,
                                 self.rect.width, self.rect.height - split_at)
        # ... split vertical similaire

3. Cellular Automata — Grottes

L'automate cellulaire simule l'évolution naturelle pour créer des grottes organiques.

def generate_cave(width, height, fill_prob=0.45, iterations=5):
    # Initialisation aléatoire
    grid = [[1 if random() < fill_prob else 0 
             for _ in range(width)] 
            for _ in range(height)]
    
    # Itérations de lissage
    for _ in range(iterations):
        new_grid = []
        for y in range(height):
            row = []
            for x in range(width):
                neighbors = count_wall_neighbors(grid, x, y)
                # Règle classique : 5 voisins = mur
                row.append(1 if neighbors >= 5 else 0)
            new_grid.append(row)
        grid = new_grid
    
    return grid

def count_wall_neighbors(grid, x, y):
    count = 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
            if 0 <= nx < len(grid[0]) and 0 <= ny < len(grid):
                count += grid[ny][nx]
            else:
                count += 1  # Bords = murs
    return count

4. Wave Function Collapse — Tiles cohérentes

WFC garantit que les tiles adjacentes sont toujours compatibles.

Règles de compatibilité :
[MER] peut être adjacent à : [MER, PLAGE]
[PLAGE] peut être adjacent à : [MER, HERBE, PLAGE]
[HERBE] peut être adjacent à : [PLAGE, HERBE, FORÊT]
[FORÊT] peut être adjacent à : [HERBE, FORÊT, MONTAGNE]

Algorithme :
1. Chaque cellule peut être n'importe quelle tile (superposition)
2. Choisir la cellule avec le moins d'options possibles
3. Choisir aléatoirement une option pour cette cellule
4. Propager les contraintes aux cellules adjacentes
5. Répéter jusqu'à ce que tout soit résolu

Combinaison des algorithmes

Les meilleurs jeux combinent plusieurs approches :

Overworld (Perlin Noise)
    ↓ selon biome
Entrée de donjon (BSP pour les salles)
    ↓ entre les salles
Grottes (Cellular Automata)
    ↓ décoration
Tiles intérieures (Wave Function Collapse)

Conseils pratiques

1. Seed reproductible — Toujours permettre de regénérer le même niveau
2. Vérification de connexité — Assurez-vous que toutes les zones sont accessibles
3. Placement de contenu — Générez la structure puis placez les objets selon des règles
4. Debug visuel — Affichez la génération en temps réel pendant le développement

# Seed reproductible dans Godot
var rng = RandomNumberGenerator.new()
rng.seed = hash("neotoad_level_42")