Génération procédurale pour jeux indés : 5 algorithmes à implémenter ce week-end

Chaque partie est différente. La carte n’est jamais la même deux fois. Les joueurs passent des centaines d’heures sur un jeu qui contient une fraction du contenu fait main.

C’est la promesse de la génération procédurale. Et la bonne nouvelle, c’est que les algorithmes derrière des jeux comme Spelunky, Dead Cells et The Binding of Isaac sont étonnamment accessibles. Pas besoin d’un doctorat en maths ni d’une équipe de 50 personnes. Il vous faut une grille, un générateur de nombres aléatoires et quelques règles bien choisies.

Ce guide couvre cinq techniques qui font tourner la plupart des jeux indés procéduraux. Tous les exemples utilisent du pseudocode indépendant de tout moteur. Choisissez votre moteur, traduisez la logique et commencez à générer.

1. Fonctions de bruit : la base des mondes naturels

Le bruit de Perlin et son successeur le bruit Simplex génèrent des valeurs aléatoires lisses et continues sur une grille. Contrairement au hasard pur (qui produit du bruit statique), le bruit de Perlin crée des motifs cohérents avec des transitions douces. Pensez collines ondulantes, pas pics déchiquetés.

Comment ça marche : Vous échantillonnez une fonction de bruit aux coordonnées de la grille et obtenez une valeur entre -1 et 1. La magie opère quand vous superposez plusieurs échantillons à différentes échelles. C’est ce qu’on appelle la superposition d’octaves.

// Bruit en octaves pour la hauteur du terrain
function terrainHeight(x, y):
    height  = noise(x * 0.01, y * 0.01) * 50   // grandes collines
    height += noise(x * 0.05, y * 0.05) * 10   // bosses moyennes
    height += noise(x * 0.1,  y * 0.1)  * 2    // détails fins
    return height

Le bruit basse fréquence donne les continents et chaînes de montagnes. La haute fréquence ajoute les aspérités rocheuses et petites variations. Ensemble, ils produisent un terrain naturel à tous les niveaux de zoom.

Où ça excelle : Génération de terrain, distribution des biomes, placement de ressources, cartes de densité de grottes, systèmes météo. Minecraft utilise du bruit de Perlin multi-octave pour son monde entier. Terraria superpose des fonctions de bruit pour créer des biomes souterrains distincts. Caves of Qud combine Perlin, Simplex et bruit fractal pour son vaste monde ouvert.

Astuce : Utilisez le bruit comme couche de décision, pas seulement comme carte de hauteur. Échantillonnez du bruit pour décider “cette tuile doit être forêt ou désert ?” selon des seuils. Deux cartes de bruit (une pour la température, une pour l’humidité) vous donnent un système de biomes complet avec presque aucun code.

2. Partitionnement binaire de l’espace : des donjons fiables

Le BSP (Binary Space Partitioning) divise récursivement un rectangle en rectangles plus petits, place des salles dans les feuilles, puis les relie par des couloirs. C’est le cheval de bataille de la génération de donjons traditionnelle.

Comment ça marche :

function generateBSP(area, depth):
    if depth == 0 or area is too small:
        place a random room inside the area
        return

    split area into two halves (random horizontal or vertical)
    generateBSP(leftHalf, depth - 1)
    generateBSP(rightHalf, depth - 1)
    connect a room from each half with a corridor

La division récursive garantit que les salles ne se chevauchent jamais. Remonter l’arbre pour connecter les nœuds frères garantit que chaque salle est accessible. Vous obtenez un donjon entièrement connecté sans chevauchement, à chaque fois.

Où ça excelle : Tout jeu avec des salles distinctes et des couloirs. L’algorithme est un incontournable des roguelikes et dungeon crawlers. NetHack et Dungeon Crawl: Stone Soup utilisent tous deux la génération BSP.

Astuce : Les donjons BSP bruts font très “boîtes”. Corrigez cela en randomisant les tailles de salle dans chaque partition, en ajoutant des salles de forme irrégulière en post-traitement, ou en combinant le BSP avec les automates cellulaires (technique n°3) pour des sections de grottes organiques entre les salles structurées.

3. Automates cellulaires : des grottes organiques en 20 lignes

C’est l’algorithme le plus simple de cette liste et l’un des plus impressionnants visuellement. Basés sur le même principe que le Jeu de la Vie de Conway, les automates cellulaires transforment du bruit aléatoire en systèmes de grottes lisses et organiques.

Comment ça marche :

function generateCave(width, height):
    // Étape 1 : Remplissage aléatoire (45% de murs)
    for each cell in grid:
        cell = WALL if random() < 0.45 else FLOOR

    // Étape 2 : Lissage avec la règle 4-5 (répéter 4 à 6 fois)
    repeat 5 times:
        for each cell in grid:
            wallNeighbors = count neighbors that are WALL (8 directions)
            if cell is WALL and wallNeighbors >= 4:
                cell stays WALL
            else if cell is FLOOR and wallNeighbors >= 5:
                cell becomes WALL
            else:
                cell becomes FLOOR

Après cinq itérations, le bruit aléatoire se résout en formes de grottes lisses et naturelles. De larges cavernes, des passages étroits et des parois organiques émergent de rien d’autre qu’un ratio de remplissage et une règle de comptage de voisins.

Le piège : Les automates cellulaires ne garantissent pas la connectivité. Vous pouvez vous retrouver avec des poches isolées. La solution est un passage de flood fill après la génération. Trouvez la plus grande région connectée et soit vous écartez le reste, soit vous creusez des tunnels entre les zones déconnectées.

Où ça excelle : Grottes naturelles, environnements souterrains, paysages extraterrestres, ruines érodées. Tout terrain qui doit sembler formé par la nature plutôt que dessiné par un architecte.

Astuce : Ajustez le ratio de remplissage initial pour contrôler la densité des grottes. 40% de murs produit de vastes cavernes ouvertes. 50% crée des tunnels étroits et claustrophobes. Plus d’itérations de lissage pour des formes arrondies, moins pour des contours plus rugueux.

4. Wave Function Collapse : des motifs cohérents à partir de tuiles

Le Wave Function Collapse (WFC) est la technique la plus récente de cette liste et celle qui génère le plus d’enthousiasme. Il produit des tilemaps complexes et localement cohérentes à partir d’un petit ensemble de tuiles et de règles d’adjacence. C’est comme résoudre un Sudoku.

Comment ça marche :

function generateWFC(grid, tileSet, rules):
    // Initialiser : chaque cellule peut être n'importe quelle tuile
    for each cell in grid:
        cell.possibilities = all tiles in tileSet

    while any cell is uncollapsed:
        // Trouver la cellule avec le moins d'options restantes
        cell = cell with lowest entropy (fewest possibilities)

        // La réduire à une seule tuile aléatoire valide
        cell.tile = random choice from cell.possibilities

        // Propager les contraintes aux voisins
        propagate(cell, rules)
        // Retirer des voisins les tuiles qui violent les règles d'adjacence

L’idée clé : le WFC travaille à rebours depuis les contraintes. Vous définissez quelles tuiles peuvent être voisines, et l’algorithme remplit un arrangement valide. Un petit jeu de tuiles avec des règles bien définies peut produire une sortie énorme et variée qui a toujours l’air “correcte.”

Townscaper d’Oskar Stalberg a mis le WFC sous les projecteurs en l’utilisant pour générer de charmantes petites villes à partir de clics de souris. Caves of Qud utilise le WFC spécifiquement pour les intérieurs de bâtiments (huttes, cryptes, repaires) tout en utilisant d’autres techniques pour le monde extérieur.

Où ça excelle : Décoration de tilemaps, génération de bâtiments, agencements de villes, toute situation où la cohérence locale compte plus que la structure globale. Le WFC excelle pour que les choses aient l’air placées à la main quand elles ne le sont pas.

Limitation : Le WFC ne garantit pas les propriétés globales comme “il y a un chemin de A à B.” Il assure que chaque tuile s’adapte à ses voisines, mais pas que l’agencement global fait sens pour le gameplay. Utilisez-le pour la décoration et l’esthétique, et combinez-le avec le BSP ou des méthodes par graphe pour la structure.

5. La marche de l’ivrogne : rapide et connectée

L’algorithme de génération de couloirs le plus simple. Un agent virtuel marche aléatoirement sur une grille, creusant des tuiles de sol sur son passage. Quand il a creusé assez d’espace, il s’arrête.

function drunkardWalk(grid, targetFloorPercent):
    position = random starting point
    floorCount = 0
    totalCells = grid.width * grid.height

    while floorCount / totalCells < targetFloorPercent:
        grid[position] = FLOOR
        floorCount += 1
        direction = random choice of [UP, DOWN, LEFT, RIGHT]
        position = position + direction
        clamp position to grid bounds

Le résultat est toujours entièrement connecté car le marcheur ne se téléporte jamais. Il produit des chemins sinueux et organiques qui fonctionnent bien comme systèmes de grottes ou réseaux de couloirs.

Astuce : Utilisez plusieurs marcheurs partant de points différents pour une couverture plus rapide et des formes plus intéressantes. Ou utilisez une marche biaisée (pondérée vers une direction cible) pour créer des tunnels allongés entre des positions de salles connues. La marche de l’ivrogne se combine bien avec le BSP : utilisez le BSP pour le placement des salles, puis envoyez des marcheurs entre les centres des salles pour creuser les couloirs de connexion.

Comment font les pros : trois études de cas

Spelunky : la garantie par templates

Spelunky divise chaque niveau en une grille 4x4. D’abord, il trace un chemin critique garanti de l’entrée à la sortie par une marche aléatoire dans les cellules de la grille. Ensuite, chaque cellule est remplie avec un template de salle conçu à la main, sélectionné selon les côtés qui nécessitent des ouvertures. Les templates sont “mutés” avec des placements aléatoires de blocs et d’ennemis.

Le génie : chaque niveau est completable par construction. Le chemin critique est garanti avant tout placement de contenu. Les templates faits main assurent la qualité. La randomisation apporte la variété.

Dead Cells : l’assembleur hybride

Les designers de Dead Cells créent des templates de salles individuelles et définissent une structure en graphe pour chaque biome décrivant comment les salles se connectent. L’algorithme sélectionne et assemble les templates selon le graphe. La philosophie de Motion Twin : “impliquer l’algorithme de la manière la plus contrainte possible.” Le générateur gère la sélection et l’assemblage des salles. Les humains gèrent le design de chaque salle individuelle et chaque règle de connexion. Si vous voulez comprendre ce qui rend les jeux comme Dead Cells si percutants, cette approche hybride est la réponse.

Hades : le roguelike anti-procédural

Supergiant Games a délibérément rejeté la génération procédurale de salles pour Hades. Chaque salle est conçue et peinte à la main. La randomisation intervient au niveau de la sélection : quelles salles apparaissent, quels ennemis spawnent, quelles récompenses sont proposées.

Cela prouve quelque chose d’important. Vous n’avez pas besoin de génération algorithmique de salles pour faire un roguelike. Des salles faites main avec une sélection, des rencontres et des récompenses randomisées peuvent créer la même expérience “chaque run est différente” sans sacrifier la direction artistique ni la qualité du level design.

Les pièges qui tuent les projets procéduraux

Le problème des “1000 bols de porridge.” Votre système génère mille niveaux uniques qui sont techniquement différents mais semblent identiques. La solution : assurez-vous que votre génération crée des situations reconnaissablement différentes, pas juste des arrangements de tuiles différents. Si la stratégie du joueur ne change jamais entre les niveaux, votre variété est cosmétique.

Pas de log des seeds. Les bugs dans les systèmes procéduraux sont quasi impossibles à reproduire si vous ne pouvez pas recréer la sortie exacte. Utilisez toujours un générateur de nombres aléatoires basé sur une seed et loguez-la. Les joueurs peuvent partager des mondes intéressants. Vous pouvez reproduire et corriger les bugs.

Sauter la validation. Un niveau généré injouable est pire que pas de génération du tout. Après chaque passe de génération, lancez des vérifications automatiques. Y a-t-il un chemin du début à la fin ? Les ressources sont-elles accessibles ? La difficulté est-elle dans des bornes acceptables ? Rejetez et regénérez tout ce qui échoue.

Sur-ingénierie avant le playtesting. Aucun ajustement de paramètres ne remplace les enseignements tirés de 200 niveaux joués. Construisez la version la plus simple d’abord. Jouez-la. Puis décidez ce qui nécessite plus de sophistication. Si vous débutez en développement de jeux, notre guide pour débutants couvre les fondamentaux du cadrage et du lancement.

Par où commencer

Choisissez l’algorithme qui correspond à votre jeu :

• Dungeon crawler en vue du dessus ? BSP + couloirs par marche de l’ivrogne
• Explorateur de grottes ? Automates cellulaires avec connectivité par flood fill
• Monde ouvert / survie ? Terrain par bruit avec seuils de biomes
• Ville ou décoration par tuiles ? Wave Function Collapse
• Roguelike au design serré ? Salles faites main avec assemblage randomisé (l’approche Hades/Dead Cells)

Commencez simple. Un générateur de donjons BSP avec 20 templates de salles conçus à la main sera plus fun qu’un algorithme sophistiqué sans contenu conçu. L’objectif n’est pas que le joueur admire votre algorithme. L’objectif est que les niveaux générés donnent l’impression que quelqu’un les a conçus exprès.

Ressources pour aller plus loin

• Red Blob Games (redblobgames.com) propose les meilleurs tutoriels visuels et interactifs pour le bruit, le pathfinding et les algorithmes sur grille
• RogueBasin (roguebasin.com) est un wiki rempli de techniques de développement roguelike, incluant des walkthroughs BSP et automates cellulaires
• Boris the Brave (boristhebrave.com) publie des analyses techniques détaillées de comment Binding of Isaac et Enter the Gungeon génèrent leurs niveaux
• “End-to-End Procedural Generation in Caves of Qud” par Jason Grinblat (GDC 2019) est le meilleur talk sur la superposition de systèmes procéduraux dans un jeu cohérent

Votre premier niveau procédural ne sera pas beau. Le centième vous surprendra. Commencez avec un algorithme, faites-le générer du contenu jouable et itérez à partir de là.