exemple de carte générée via le Wave Function Collapse Algorithm
Dungeon Generator est un projet personnel dont le but est d'implémenter le Wave Function Collapse Algorithm (WFC). Le WFC est un algorithme permettantt la création de cartes en 2D grâce à la définition d'un tileset ainsi que de règles définissant quelles tiles peuvent être à côte à côte.
exemple de carte générée via le Wave Function Collapse Algorithm
Pour expliquer le principe du WFC, nous commençons avec une carte vide où chaque case peut contenir n'importe quelle tile. Nous prenons ensuite une case au hasard, et définissons une tile. Le fait que cette tile soit maintenant défini va changer les probabilités autour de cette dernière. Ensuite, nous répétons l'opération de définition de tile parmis les cases avec le moins de possibilités, et ainsi de suite jusqu'à ce que la carte entière soit remplie.
au début il n'y a aucune tile défini
quand on défini une tile, celles aux alentours sont mis à jour. On recommence à l'étape précédente parmis les tiles avec le moins de possibilités.
autre exemple d'une update après définition
Une façon d'améliorer cette algorithme est d'ajouter un poids à chaque tile. Ainsi, on peut modifier les probabilités d'une tile d'apparaître, créant des cartes avec un même tileset mais avec des résultats très variées. Je ne l'ai personnellement pas implémenté, mais j'envisage de le faire à l'avenir.
une map avec principalement de l'eau
une map avec principalement des plaines
une map avec principalement des forêts
Afin de rendre mon programme plus simple d'utilisation, je me suis essayé à la création d'un User Interface avec Gtkmm, la version C++ de Gtk. J'ai réalisé quelque chose de très simple avec 3 boutons, servant respectivement à générer une map, choisir une fichier de configuration (les règles pour l'algorithme), et enfin pouvoir sauvegarder la map. Il est améliorable au niveau de l'esthétique, et certaines options sont rajoutables comme par exemple le choix de la taille de la carte (20x20 obligatoire).
UI du programme
Cet algorithme est très intéressant car assez flexible, permettant la création de monde en vue top down ou bien de profil, et rapidement implémentable d'en d'autres projets. Je pense pouvoir le réutiliser plus tard sans problème.
Pour comprendre l'algorithme et illustrer cette page, je me suis servi de cette vidéo ainsi que de cette article.
