Génération d'îles volantes procédurales

Publié le 2025-08-01

Introduction

Bonjour bonjour. Aujourd’hui, nous allons parler de la génération procédurale, plus particulièrement des îles volantes. Il s’agit d’un problème ayant un très grand nombre de solutions qui ont toutes leurs avantages et leurs inconvénients. J’aimerais aborder celle que j’ai utilisée pour la création du jeu Nimbus Nibbler.

Pas d’inquiétude, bien que le système se base sur des méthodes classiques, vous trouverez surement quelque chose d’utile ici. Mon objectif était de créer un système facile à contrôler, utilisant des algorithmes simples et ayant un rendu organique.

Comment ça marche ?

Eh bien, dans les grandes lignes, le système fait apparaitre diverses îles volantes sur une grille, puis fait apparaitre des ponts suspendus pour les relier. Jusque-là, rien de bien spécial, on retrouve un grand nombre de générateurs qui font ça, particulièrement dans les rogue-like.

La méthode classique

Ces systèmes fonctionnent en général en deux grandes étapes :

1. Placer des cellules sur la grille de manière aléatoire
2. Générer les chemins qui les relient à l’aide d’un algorithme comme A*

Voilà à quoi cela peux ressembler :

Cependant, ces systèmes ont une mise en place complexe :

• Avoir le contrôle sur la génération demande des outils et/ou des algorithmes avancés.
• Créer une distribution organique et non répétitive peut s’avérer compliqué.
• L’effet de grille est souvent très visible.
• La génération des chemins nécessite des algorithmes de path finding comme A*
• Empêcher les chemins de se chevaucher demande une attention particulière.

La méthode simplifiée

Dans le cadre d’un petit projet, plutôt que de partir sur un système complexe qui sollicite beaucoup de travail pour enlever des edge cases. Est-ce qu’on pourrait passer outre certaines problématiques entièrement en utilisant un système beaucoup plus simple ?

Eh bien oui !

Si on considère que chaque île ne peut être connectée à une île adjacente, on réduit grandement les problématiques liées à la génération des chemins. On peut garantir de ne pas avoir d’iles avec des ponts qui se chevauchent. On ne risque pas d’avoir des ponts trop longs pour le gameplay. On peut réduire la taille de la grille et augmenter la densité des îles pour réduire le nombre de cases et donc le nombre de calculs et leurs complexités.

L’approche des textures procédurales

Je me suis inspiré des méthodes utilisées pour créer des textures procédurales, utiliser du bruit et des filtres. C’est également comme ça qu’on génère les terrains via des outils comme World Builder ou Gaia et même directement dans les jeux comme Minecraft.

J’ai donc considéré la grille de génération comme une image 2D contenant des pixels d’une valeur de 0.0 à 1.0 et dans laquelle j’ai appliqué des modifications pour définir l’apparition des îles. Cela m’a permis de prototyper le générateur visuellement dans un éditeur d’images Affinity Photo.

J’avais déjà une idée assez précise des spécifications que je voulais pour le générateur :

1. Avoir des îles dont l’apparition semble organique.
2. Avoir une plus grande densité d’îles au centre de l’aire de jeu.
3. Ne pas avoir de blocs très denses d’îles (par exemple 2x2) toutes connectées.
4. Avoir toujours une île au centre de la grille pour spawner le player controller.
5. Avoir un nombre d’îles orphelines assez réduit*.

Et comme par hasard, cette hiérarchie de besoins s’adapte facilement en une suite de layers dans une image et donc par extension d’étapes de générations.

Apparition organique

Le générateur commence par créer une grille/image de taille voulue et applique un filtre de bruit dessus. Pour cela, j’ai créé un petit utilitaire qui utilise la librairie mathématique d’Unity pour échantillonner du bruit de perlin, du bruit bleu ou du bruit cellulaire. Le choix du type de bruit est donné à l’utilisateur pour expérimenter.

Voici ce que cela donne dans le jeu.

À la fin de la génération, les cases ayant une valeur de plus de 0.5 feront apparaitre des îles.

Densité variable

Pour avoir une densité d’îles supérieures au centre de la grille. Je crée un gradient circulaire centré sur la grille qui est à une valeur de 1.0 au centre et une valeur de 0.0 à l’extérieur. Il suffit ensuite de multiplier le bruit par le gradient pour avoir une densité plus forte au centre du niveau.

En interne, le gradient est généré en utilisant une fonction de distribution gaussienne. On peut contrôler sa taille et si elle est douce ou abrupte pour contrôler la densité des îles.

Pas de zones trop denses

Le centre de la grille a une grande chance de faire apparaitre des îles. Pour éviter d’avoir des zones pleines, j’ai utilisé un masque qui fait des “trous” dans la grille. Le masque en lui-même est une forme hexagonale qui permet de réduire l’effet de grille en plus de régler les problèmes de densité.

Île au centre

image[centre][centre] = 1.0f; 👀

Bon, pas grand chose à dire là dessus…

Seuil d’apparition des îles

Maintenant que la texture d’apparition des îles a été créée et filtrée, il ne reste plus qu’à effectuer un seuillage. Toutes les cellules ayant une valeur supérieure ou égale à 0.5 vont faire apparaitre une île volante.

Réduire le nombre d’îles orphelines

Avec la méthode actuelle et la taille des grilles en jeu, je n’ai pas eux, de problème d’un grand nombre d’îles orphelines (qui ne sont pas raccordées au centre). J’ai testé avec des grilles très larges et dans ces situation le problème arrive plus souvent.

Dans le cas où j’aurais eu besoin d’utiliser des grilles très larges. J’aurais eu plusieurs approches possibles pour régler ce problème, par exemple :

• Garder uniquement le groupement d’îles central à l’aide d’un algorithme de type flood fill
• Forcer l’apparition de nouvelles îles dans les zones vides qui peuvent reconnecter plusieurs groupes d’îles.
• Forcer la génération de ponts entre deux groupes d’îles.

Génération et placement de chaque île

C’est bon, le système a choisi quelles cases de la grille va faire apparaitre des îles. Il reste maintenant à gérer l’apparition de ces îles.

Les spawners de groupes d’îles ont une liste pondérée des types d’îles à faire apparaitre et tire au sort le type pour chaque case de la grille.

Îles semi-procédurales

Pour ajouter de la variété dans la génération, chaque île contient elle-même des spawners de décorations. Chaque spawner à une liste pondérée de prefabs qu’il peut faire apparaitre

Ici, un spawner contient trois décorations différentes. En appuyant sur le bouton, vous pouvez lancer et relancer un processus de génération.

Chaque décoration peut contenir d’autres spawners. Par exemple une colone peut faire apparaitre un toit, un toit peut faire apparaitre une tour, une tour peut faire apparaitre une hélice. Quand un spawner fait apparaitre une décoration il vas vérifier si elle contient d’autres spawners et les activer. Le système continue jusqu’à ce que touts les spawners aient été activés.

==widget slider avec un spawn récursif==

Ce système permet d’obtenir un grand nombre de variations par type d’îles tout en gardant un nombre limité de décorations de bases.

Déplacement des îles dans leurs cellules

Maintenant que l’on a un grand nombre d’îles différentes, la problématique de répétition est presque réglée. Néanmoins, il reste le problème du placement des îles. Comme chaque île est placée sur les cases d’une grille carrée, il est très simple de voir cette structure.

On retrouve cette problématique dans la création de textures répétitives. Le cerveau humain est très bon pour discerner les patterns répétitif, si on applique une texture en boucle, il est très facile de repérer la répétition. Et on peut utiliser une des solutions qui marche pour les textures : ajouter un décalage à chaque répétition.

Dans notre cas, en déplacent chaque île dans sa case de grille ainsi que verticalement, on peut faire disparaitre presque complètement la structure de la grille.

Voilà ce que cela donne en jeu :

Algorithme

En regardant cette technique de plus près, on peut se rendre compte qu’elle ressemble beaucoup à un algorithme utilisé pour créer des textures de bruit. Le bruit cellulaire ou voronoi noise. Cet algorithme choisit des points aléatoirement placés dans chaque cellule d’une grille et calcule pour chaque pixel la distance au point le plus proche.

Oui on peut faire de cellules de voronoi nativement en HTML et CSS. C’est fou ce qu’on peut faire avec des gradients et des blend modes.

Génération des ponts

On à maintenant plusieurs îles qui apparaissent dans le vide, il ne reste plus qu’à les connecter entre elles ! La première étape est de choisir quels ponts vont apparaitre.

Choix des ponts

Pour avoir un nombre de ponts correct par île, j’ai mis en place un choix en deux étapes :

1. En premier, chaque île vérifie si elle est voisine à une autre île dans les directions cardinales
2. Si ce n’est pas le cas, elle vérifie si elle est voisine d’autres îles dans les diagonales. Cela permet d’avoir un nombre de ponts pas trop élevé tout en réduisant grandement le nombre d’îles orphelines.

À noter qu’en réalité, les îles ne sont responsables de leur connections que pour la moitié des directions, par exemple, Nord, Nord-Est, Est et Sud-Est. Et cela, pour la détection d’îles et pour la génération des ponts. Les connexions dans les autres directions sont gérées par les îles voisines.

Génération des ponts

Système de points de connexions

Chaque île contient 8 points de connexions possibles prédéfinie. Ces points de connexion sont un prefab qui a deux modes :

• Mode barrière : Il fait apparaitre un obstacle pour ne pas tomber de l’île comme une barrière ou un mur.
• Mode connexion : Il fait apparaitre un point de passage pour le pont qui peut être orienté dans la direction du point de connexion de l’autre île.

==schéma cool==

Génération de chemins

Pour la génération des ponts suspendus, j’ai utilisé le package Splines d’Unity. Il permet de générer des courbes 2D ou 3D dans l’espace d’une scène et de faire apparaitre des objets le long de ces courbes.

Pour garder la génération des ponts la plus simple, j’ai effectué la majorité des calculs de courbe en 2D. Je projette d’abord les points de connexion des ponts sur un plan 2D. Je génère ensuite une courbe 2D qui ressemble à un pont suspendu. Puis j’oriente cette courbe dans la direction de l’autre île. Enfin, il faut faire apparaitre des modules de ponts le long de la courbe, ce qui est géré directement par le package.

Résultats

Voici un dernier widget pour faire le topo des étapes de création des îles.

Ce projet de génération procédural était pour moi un bon moyen d’expérimenter avec différentes méthodes d’effectuer de la génération procédurale. L’objectif était de réaliser rapidement un générateur d’îles volantes en utilisant des méthodes inspirées de la génération de textures.

Si jouer au jeu vous intéresse, vous pouvez retrouver Nimbus Nibler sur itch.io

Merci d’avoir lu jusqu’ici, j’espère que cet article a été intéressant à lire, s’il vous à plus n’hésitez pas à le partager ou me le faire savoir ce que vous en pensez !