Wave Function Collapse sur mobile

Depuis longtemps, je voulais essayer cette nouvelle technique de construction de niveaux, mais je n'avais pas l'occasion d'y consacrer du temps. Et voilà que mon patron arrive et me dit « écoute, on va devoir faire toute une série de nouveaux niveaux pour ce nouveau mini-jeu de course, tu as un tour de magie à me donner ? ». Il ne m'en fallait pas plus pour m'enfermer pendant une semaine dans mon bureau et me plonger dans le sujet.

Le Wave Function Collapse est une technique qui permet de construire automatiquement de grands mondes en assemblant des blocs. Pour simplifier, nous disons au programme que ce bloc peut être placé à côté de ce bloc, mais PAS à côté de cet autre bloc ! Celui-ci doit être associé à un autre, et nous continuons ainsi jusqu'à ce que toute la scène soit remplie.

J'avais des exemples de mise en œuvre dans Unity, mais je n'ai jamais trouvé que des exemples en 2D. Et nous avions besoin de 3D... J'ai donc trouvé cette solution :

Cela RESSEMBLE à de la 3D, mais ce n'était en fait que de la 2D, mais avec des meshes. L'algorithme n'avait pas à gérer l'axe Y, il devait seulement s'assurer que les blocs pouvaient être placés les uns à côté des autres, mais pas au-dessus ou au-dessous des autres. Et c'est là que les choses se compliquent. Pour arriver à ce résultat, il m'a suffi d'assembler dans Blender mes blocs comme si je faisais un tileset en 2D :

J'ai écrit un programme qui parcourt en boucle toutes les mailles de ce fichier, et enregistre leurs possibles voisins. Ensuite, la génération de niveaux fonctionne de la même manière :

• Il démarre sur une cellule aléatoire avec un bloc aléatoire

• Il vérifie pour ce bloc nouvellement placé quels voisins possibles peuvent être placés à côté sans enfreindre les règles.

• Et le code continue jusqu'à ce que toute la carte soit remplie de blocs.

Mais ensuite, j'ai essayé d'ajouter de la complexité : un second jeu de tuiles que je voulais combiner avec le premier...

Je n'irai pas trop loin dans les mathématiques, mais disons que si nous avons un peu de complexité graphique, cela devient exponentiellement difficile en termes de code. Le problème ici est que je n'avais pas assez de blocs pour remplir toutes les possibilités. Et plus le nombre de tuiles possibles augmente, plus la charge sur nos pauvres smartphones est importante, il fallait donc trouver d'autres astuces.

La première chose à laquelle j'ai pensé a été d'ajouter du bruit après coup. Et je dois dire que c'est plutôt réussi ! Cela a permis de casser l'uniformité de la carte rendue.

Ensuite, j'ai réalisé que j'étais censé faire un runner, donc je me suis concentré sur la création du chemin que mon personnage va suivre. C'était assez facile : j'ai sélectionné des cellules voisines sur ma carte et je les ai marquées comme chemin, puis un autre script a été chargé d'instancier les blocs de chemin avant que l'algorithme WFC n'entre en jeu. Je voulais aussi que le chemin puisse se traverser lui-même et j'ai donc eu besoin de ponts.

Voici donc à quoi ressemblait l'ensemble du jeu de tuiles 3D à la fin :

Et voici le résultat auquel j'ai abouti :

J'ai décidé d'avoir le nombre minimal de blocs pour rendre le rendu crédible, et j'ai forcé le placement de ces gros morceaux de feuillage dans les cellules qui n'ont pas pu trouver de cellule appropriée. Pour le projet que nous avions en tête, et pour les appareils ciblés, cette solution a très bien fonctionné !