Je crée mon jeu vidéo E11 : génération procédurale de carte (partie 2)

«Je crée mon jeu vidéo» est une série d'articles sur la création d'un jeu vidéo, depuis la feuille blanche jusqu'au résultat final. On y parlera de tout : de la technique, du contenu, de la joie de voir bouger des sprites, de la lassitude du développement solitaire, etc. Vous pourrez suivre cette série grâce au tag gamedev.

Dans l'épisode 10, on a fabriqué des cartes d'altitude avec diverses méthodes et divers opérateurs qui permettent de rendre la carte plus réaliste. Dans cette deuxième partie de ce double épisode consacré à la génération de carte pour un RPG, on va décorer notre carte.

Sommaire

• En retard
• Rappel de l'objectif
• Les étapes de construction
  • Génération des rivières
  • Génération des biomes
  • Générations des formes de collisions
• La carte prête à l'emploi
  • Le problème fondamental
  • Détermination du tileset
  • La carte finale dans Tiled
  • La carte finale dans le jeu
• La suite !
  • Les zones inaccessibles
  • Les décorations
  • D'autres pistes à explorer
• Conclusion

En retard

Avant toute chose, cet épisode a pris beaucoup plus de temps que prévu. La fatigue de la vie quotidienne est un élément qu'il ne faut jamais sous-estimer, surtout quand elle s'accumule. Elle réduit considérablement la capacité à avancer, malgré une motivation intacte. C'est ce qui m'est arrivé ces dernières semaines, ce qui a provoqué un énorme retard. Pourtant, les tâches étaient simples et claires, il y avait un peu de travail algorithmique, comme nous allons le voir, mais rien de vraiment insurmontable. Juste qu'une fois devant le clavier, je n'arrivais plus à taper les choses efficacement, tout mettait des heures alors que ça aurait dû mettre quelques minutes.

Les vacances actuelles seront sans doute profitables pour me remettre sur les rails. En tout cas, elles m'ont déjà permis de finir cet épisode, même s'il est assez loin de ce que j'avais imaginé au départ. Parce qu'il reste du travail sur ce sujet.

Rappel de l'objectif

L'idée de ce double épisode est d'être capable de générer des cartes pour un RPG. Plus précisément, on utilisera notre carte comme un fond, étant donné que le jeu utilise la vue de dessus. Ça veut donc dire que cette carte sera très présente sur l'écran et qu'il faut la préparer au mieux. Pourquoi la générer ? Il ne s'agit pas ici de générer toute la carte dans ses moindres détails, mais simplement de produire un canevas assez précis qui puisse être manipulé par la suite. Toute la question est dans cette précision.

Le premier épisode permettait de générer une carte d'altitude, ce qui est une première étape essentielle. Cette carte d'altitude avait de bonnes caractéristiques, par exemple en terme de déplacement possible des unités, ce qu'on avait matérialisé par le score de jouabilité. On avait donc à notre disposition une carte d'unité dont on va se resservir ici.

Pour cet épisode, on va voir trois aspects essentiels : la génération des rivières, la génération des biomes, la génération des formes de collision. Puis on discutera de ce qu'on peut apporter de plus.

Les étapes de construction

Génération des rivières

La génération des rivières est sans doute la partie la plus facile. Il s'agit d'ajouter à notre carte des rivières pour la rendre un peu plus réaliste. Et puis le franchissement de rivière peut devenir une activité importante quand on joue à un RPG.

L'algorithme utilisé ici est extrêmement simple, tout en donnant des résultats pas trop mauvais. L'idée est de partir d'un point en altitude (on peut fixer l'altitude minimale) puis de suivre la pente la plus forte jusqu'à arriver à la mer. Ça a l'air simple comme ça mais ça ne l'est pas. Parce qu'il se peut que l'eau se retrouve piégée dans un minimum local, et il faut donc savoir comment sortir de ce minimum local sans effondrer les performances de la génération.

La solution la plus efficace est d'utiliser une file de priorité. Pour chaque case ajoutée à la rivière, on ajoute toutes les cases adjacentes à la file avec comme priorité l'altitude la plus faible. Ainsi, on a toujours en tête de file la case qui permet de descendre le plus. Ainsi, quand on se retrouve dans un minimum local, cet algorithme va permettre de faire monter l'eau petit à petit jusqu'à trouver un endroit par où descendre un peu plus. On crée ainsi des lacs naturels.

Ensuite, on itère un certain nombre de fois pour avoir plusieurs rivières. Si on repart à chaque fois de la carte initiale, certaines rivières vont parcourir les mêmes cases, créant ainsi des affluents.

Voilà ce que ça peut donner avec vingt rivières. On voit en particulier le lac qui s'est créé au nord-est et comment la rivière longe la colline. Et on observe aussi qu'avec six rivières, on arrive à former un fleuve avec ses affluents à l'ouest.

Génération des biomes

Un biome est, d'après Wikipédia, «un ensemble d'écosystèmes caractéristique d'une aire biogéographique et nommé à partir de la végétation et des espèces animales qui y prédominent et y sont adaptées». Un biome est caractérisé par un climat, lui-même étant associé à des températures et des précipitations. Pour savoir quel biome correspond à quelle fourchette de températures et de précipitations, on utilise généralement le diagramme Whittaker.

Sur notre carte, nous n'avons ni températures, ni précipitations. Mais nous avons des altitudes et des rivières ! On va considérer que plus on monte en altitude, plus il fait froid. En vrai, la température baisse entre 0.6 et 1.0°C tous les 100m, donc l'approximation n'est pas si insensée. Il reste donc à calculer l'humidité, et là, on va considérer que plus on est loin d'un point d'eau (rivière ou mer), moins on est humide. Pour cela, on fait un parcours en largeur de toutes les cases, en commençant aux points d'eau et on décrémente l'humidité petit à petit.

On obtient une carte d'humidité : plus c'est clair, plus c'est humide. Et inversement, les zones sombres indiquent des zones très sèches.

Ensuite, en fonction de l'altitude et de l'humidité, on doit déterminer un biome. On s'inspire pour cela du diagramme de Whittaker qu'on adapte. J'ai utilisé la même adaptation que celle du tutoriel d'Amit Patel. On peut le visualiser de la manière suivante.

En abscisse, on a l'humidité (plus on va à droite, plus c'est humide), et en ordonnée, on a l'altitude (plus on va en haut et… plus on monte logique). Chaque couleur représente un biome différent. Depuis les forêts tropicales jusqu'au sommets enneigés, en passant par les steppes, tout y est à peu près.

Reste ensuite à appliquer les biomes en fonction de la carte d'altitude et de la carte d'humidité qu'on vient de calculer. Et tadam !

Ou, si on veut une version avec du relief :

On se rend compte que la zone quasi-désertique au sud-est correspond à une dépression où il n'y a pas de rivière. On voit également les montagnes qui se dégagent avec les zones neigeuses.

Générations des formes de collisions

Un des objectifs de cette génération de carte est de pouvoir générer automatiquement les formes de collisions. Parce que les faire à la main peut être assez long et fastidieux. Dans l'épisode précédent, on avait vu comment on générait une carte d'unité, c'est-à-dire un ensemble de cases accessibles à une unité dont on précise à la fois la taille (en nombre de cases) et la capacité à franchir les pentes.

La carte d'unité est donc une carte binaire. Il reste à déterminer les polygônes qui forment les contours infranchissables, c'est-à-dire la limite des zones blanches et noires. Je dois avouer que c'est un des algorithmes qui m'a demandé le plus de réflexion et dont je suis assez fier. Voici comment j'ai procédé.

Pour chacune des cases accessibles (les cases blanches), j'ai ajouté quatre arcs orientés qui représentent le contour de cette case à un premier ensemble E1. Toutes les cases sont orientés dans le même sens, ici le sens des aiguilles d'une montre. Ensuite, il faut enlever des arcs pour ne garder que ceux des contours des zones blanches. L'idée est ici d'enlever les arcs (A,B) tels que l'arc (B,A) fait également partie de l'ensemble E1. En effet, si on trouve ces deux arcs, c'est qu'ils ont été ajoutés par deux cases adjacentes et donc, ils font partie de l'intérieur de la zone. Nous obtenons alors un ensemble E2 qui contient tous les contours mais en petits morceaux. Dernière étape, il faut donc reconstituer les contours ! Pour ça, tant que E2 n'est pas vide, on prend un arc, puis on cherche le ou les arcs qui ont comme origine l'extrêmité de cet arc.

Je dis «le ou les» parce qu'il se peut qu'il y en ait deux, dans le cas où deux cases sont reliées uniquement par un sommet, comme on peut le voir sur la figure ci-dessus. Il faut alors faire un choix non-aléatoire : un choix aléatoire pourrait nous faire tourner en rond assez longtemps. Pour maximiser la taille du contour, on choisit de toujours tourner à gauche. Comme on parcourt le contour dans le sens des aiguilles d'une montre, on inclut dans chaque zone les cases qui sont reliées uniquement par un sommet et donc on minimise le nombre de contours. On itère tout ça et on obtient nos contours.

Cet algorithme est assez efficace si on prend garde à utiliser les bonnes structures de données et les bons algorithmes. S'il y a n1 cases accessibles, c'est-à-dire 4*n1 arcs dans l'ensemble E1, la construction de E2 peut se faire en O(n1 log n1), grâce à un tri préalable des arcs, puis à une recherche dichotomique pour essayer de trouver l'arc inverse pour chaque arc. Ensuite, s'il y a n2 éléments dans E2, on peut reconstruire les contours en O(n2 log n2) de la même manière, c'est-à-dire en triant les arcs et en faisant une recherche dichotomique pour trouver le ou les prochains arcs. Au final, on n'est jamais quadratique, ce qui est une performance tout à fait honorable à mon sens.

Cette fois, on a tout ce qu'il nous faut en terme de données.

La carte prête à l'emploi

Il faut désormais générer la carte prête à l'emploi, c'est-à-dire au format TMX de Tiled, et plus précisément avec les conventions retenues pour le jeu lui-même.

Le problème fondamental

Tiled est un très bon logiciel et il permet de faire plein de choses. Il a notamment une brosse qui permet de créer des «terrains» de manière très facile, une fois qu'on a indiqué sur le tileset quel morceau de tuile était associé à quel terrain. La brosse est capable de générer des gros morceaux de carte de manière à ce que les cases adjacentes de la carte aient des terrains identiques. Tout ceci est bien expliqué dans un tutoriel pour créer les terrains et utiliser la brosse.

Pour pouvoir bénéficier de cette fonctionnalité le jour où on passera à l'édition manuelle de la carte, il nous faut deux choses. Premièrement, déterminer les terrains. Ça, c'est la partie facile, parce qu'on peut identifier les biomes aux terrains et donc, on a autant de terrains que de biomes. Deuxièmement, il faut avoir un tileset adapté à cette brosse. Et ça, c'est la partie difficile. Parce qu'on voit bien dans le tutoriel que ce qui marche bien, c'est quand la limite entre deux terrains est sur la tuile, puisque c'est ça qui va permettre à l'outil de pouvoir générer des zones complètes.

Or, notre carte, pour l'instant, ce sont uniquement des cases monochromes. Au départ, j'avais pensé à modifier la carte pour étendre certaines zones d'une demi-case. Ça permettait notamment d'élargir les rivières facilement. Le problème, c'est qu'on arrive très vite à des cas particuliers impossibles à démêler. On doit prendre en compte au moins les huit cases adjacentes (directement ou par un coin) et donc, si on prend en compte qu'on peut avoir autant de biomes que de cases, ça fait un nombre de cas beaucoup trop importants. La solution est toute bête, il suffit de décaler notre grille d'une demi-case suivant les deux axes ! Et pour faire simple, on sacrifie une rangée sur le bord. Ainsi, toutes les limites de biomes sont maintenant au milieu des cases.

Notre nouvelle carte est alors composée de tuiles, elles-mêmes découpés en quatre parties qui ont les couleurs de quatre cases de la carte originale. Évidemment, on va trouver toute sorte de tuiles et il va bien falloir déterminer le tileset.

Détermination du tileset

Comme notre carte est générée, il faut également générer le tileset qui sera utilisée pour la carte. Pour ça, il faut déterminer l'ensemble de tuiles qui a été utilisé. Au départ, on place déjà dans le tileset les tuiles pleines qui seront les référents pour chacun des terrains et qui les identifie dans Tiled.

Ensuite, on parcourt toute notre carte et pour chaque tuile nouvelle, on l'ajoute à notre ensemble de tuiles. Puis, une fois qu'on a fini, il ne reste plus qu'à générer l'image avec toutes les tuiles, comme les attends le format TMX. Ici, en l'occurrence, les tuiles font 32x32 à l'affichage mais à cause d'un pseudo-bug, les tuiles font en fait 34x34. Le bug provoquait des petits défauts d'affichage, on voyait notamment la couleur de la tuile voisine à la limite des tuiles, ce qui était assez désagréable. Je crois avoir lu que ce bug vient d'une erreur d'arrondi dans les nombres flottants, voilà pourquoi je parle de pseudo-bug. La solution que j'avais trouvée à l'époque, c'était d'agrandir mes tuiles d'un pixels, ce qui permet de masquer ces petits défauts.

Touche finale, plutôt que d'avoir des limites de biomes uniquement horizontales et verticales, on peut modifier un peu les tuiles de manière à avoir des biseaux. Et ce n'est pas si simple. Il y a notamment le cas merdique où la tuile a deux couleurs mais disposées en diagonales. Dans ce cas, il faut donner la priorité à une des deux couleurs pour les joindre. C'est essentiel quand une de ces deux couleurs représente une rivière, on veut que la rivière soit continue. Je passe les détails qui tiennent parfois de la magie sur comment déterminer si on dessine un biseau ou pas, et je passe aussi sur la taille de ce biseau pour que les diagonales joignent parfaitement sans qu'on ne puisse voir les limites des tuiles.

Au final, on obtient ça :

Évidemment, une fois ce tileset généré, rien n'empêche un artiste de l'améliorer comme bon lui semble. Mais cette version de base peut tout à fait convenir, dans un premier temps, pour le développement du jeu.

La carte finale dans Tiled

Ce moment où on ouvre la carte générée dans Tiled la toute première fois est un moment assez intense. On se demande si on a tout fait correctement, si ça va marcher, si ça ne va pas être trop gros pour Tiled. Et puis tadam, ça s'affiche et c'est merveilleux. Voici quelques captures d'écran pour montrer le résultat dans Tiled.

Sur cette première capture, on voit les contours qu'on a calculés précédemment. On retrouve les formes qu'on avait dans la carte d'unité (ce qui est plutôt une bonne nouvelle). On peut également voir le tileset en bas à droite, avec les limites des tuiles, qui a été ajouté par Tiled, ce qui permet de mieux les distinguer.

Sur cette seconde capture, on voit exactement le même endroit mais avec les biomes, c'est-à-dire ici l'ensemble des tuiles. En bas à droite, j'ai mis la vue où on peut voir tous les terrains.

Sur cette troisième capture, j'ai zoomé sur une des rivières au nord pour observer les limites biscornues entre les biomes qu'on obtient avec les biseaux. Ce n'est pas si mal que ça, non ?.

La carte finale dans le jeu

Évidemment, la carte marche également dans le jeu. Pour vous convaincre, voici une petite capture d'écran avec Kalista à la plage. L'endroit correspond à la troisième capture dans Tiled, au nord de l'île.

Pour les contours, vous devez me faire confiance, ça marche aussi. Presque trop bien d'ailleurs, et nous allons en parler maintenant.

La suite !

Les zones inaccessibles

Dans le jeu, les zones inaccessibles sont bien inaccessibles, aucun problème pour ça. Malheureusement, ces zones ne sont pas distinguées visuellement des autres zones. Ce qui fait qu'on a l'impression de heurter des murs invisibles en permanence. C'est très désagréable. Je suis à la recherche d'un artefact visuel permettant de distinguer ces zones.

J'ai fait quelques essais qui sont pour l'instant non-convaincants. Le premier essai consistait à mettre par dessus chaque tuile inaccessible une autre tuile, partiellement transparente qui assombrissait la tuile du dessous. Outre le fait que ça ne rendait pas très bien visuellement, on n'avait pas l'impression d'une zone infranchissable mais plutôt d'un biome différent. Bref, solution abandonnée. Au second essai, j'ai essayer de placer des objets qui montrerait que la zone est infranchissable, en l'occurrence des cailloux. J'ai donc fabriqué une tuile avec trois cailloux. L'impression visuelle était nettement meilleure, et on distinguait bien la zone infranchissable. Mais avec une tuile unique, on avait des zones très géométriques avec un même motif répété beaucoup trop de fois.

J'ai encore trois idées. La première, c'est de générer plusieurs tuiles de cailloux de manière à éviter cet aspect géométrique. Seulement, à force de voir des cailloux partout, ça risque d'être un peu rébarbatif à la longue. La seconde idée, c'est d'utiliser non pas des tuiles, mais des sprites complets, un peu comme mes arbres de l'épisode 06. On pourrait par exemple avoir des rochers. La difficulté ici consiste à recouvrir exactement la zone infranchissable avec ces sprites mais pas plus, ni moins. Une troisième idée est de se servir des informations de pentes (puisque ces zones correspondent à des endroits trop pentus pour notre unité) et de trouver des tuiles qui puissent rendre compte de la pente. Avec un rebord, par exemple.

Peut-être que la solution viendra d'un mélange de plusieurs idées.

Les décorations

Une autre manière de rendre la carte moins monotone est d'ajouter des décorations. Et là, je pense immédiatement à mes arbres. Pourquoi ne pas tout simplement créer des forêts complètes ? Générer des forêts aléatoirement n'est pas si difficile. Avec les biomes, je sais où elles sont situées, j'ai déjà des sprites d'arbres, yapluka. Ça permettrait d'avoir une première version de la carte pas trop pauvre.

Dans la même idée, on pourrait aussi ajouter des rochers, et pas seulement sur les zones infranchissables. Dans les zones montagneuses par exemple, ça ferait assez couleur locale. Reste à pouvoir générer des rochers aléatoirement. J'ai un peu avancé sur ce point, ça rend assez bien, dans le même style que les arbres en fait, donc ça pourrait marcher.

En termes d'éléments naturels, ça me paraît déjà une bonne base. Mais je suis sûr que les idées vont venir au fur et à mesure. N'hésitez pas à donner vos idées !

D'autres pistes à explorer

Parmi les autres pistes à explorer, il y également la génération de routes. Et là, il faut vraiment que je vous fasse découvrir quelque chose. J'ai eu l'occasion de discuter sur le canal IRC #akagoria avec un doctorant d'une équipe de recherche française qui étudie, entre autre, la génération procédurale de paysage, l'équipe GeoMod du LIRIS à Lyon. Ils ont notamment une plateforme de développement de mondes virtuels, malheureusement propriétaire. Mais on peut voir des vidéos de démonstration assez époustouflantes. Vraiment, je vous les conseille toutes, ça ne dure pas très longtemps et c'est bluffant.

Parmi tous les travaux de cette équipe, il y a notamment des travaux sur la génération de routes, ainsi que sur la génération de réseaux routiers hiérarchiques. On peut retrouver une partie de ces travaux dans la thèse d'Adrien Peytavie sur la génération procédurale de monde (en français). Ça donne une bonne base pour générer des routes, même si les algorithmes sont décrits très succinctement.

Surtout, les discussions que j'ai eues avec ce doctorant m'ont ouvert des pistes de réflexion intéressantes. Il regrettait (et je ne peux pas l'en blâmer) que la plupart du temps, la génération procédurale de paysage suit le même schéma : celui que j'ai présenté au cours de ces deux épisodes. Je partage son analyse. J'ai choisi cette voie par facilité, parce que je savais qu'elle donnerait des résultats suffisamment convaincants. Mais je pense comme lui qu'on peut faire mieux que le bruit de Perlin et le diagramme de Whittaker. Notons bien que ce couple est utilisé dans de nombreux jeux, dont le célèbre Minecraft.

Il défendait l'idée que c'était une erreur de faire de la génération de paysage à grain fin directement, comme je l'ai fait. Les algorithmes utilisés ne conviennent pas pour traiter à la fois les paysages globaux (des montagnes, des plaines) et les détails (un arbre, un cailloux). Il proposait plutôt de procéder en plusieurs étapes, tout d'abord déterminer un paysage global avec du bruit de Perlin ou autre, ce qui permet de déterminer des zones globales. Puis, dans chaque zone, d'utiliser à nouveau du bruit pour générer les détails. Pour donner un exemple concret, si on considère que chaque case de ma carte initiale représente non pas une tuile au final mais un grand carré de tuiles, on aurait alors la possibilité, pour chaque carré de tuiles d'ajuster les limites de biomes avec du bruit de manière à avoir des formes un peu moins rectilignes (même avec les biseaux). J'ai trouvé cette idée très intéressante même si le temps me manque pour l'expérimenter dans l'immédiat. Et dans son esprit, on pouvait même avoir plusieurs niveaux dans ce genre.

Le deuxième point qui mériterait sans doute un peu de travail, c'est d'oublier le diagramme de Whittaker. En effet, ce diagramme est très pratique mais il donne des paysages hautement irréalistes ! Qui a déjà vu un désert, une taïga, une forêt tropicale et des steppes sur une île aussi petite ? Bon, on est dans un jeu donc on peut faire un peu comme on veut, mais quand même. On pourrait aussi rester dans un climat tempéré, et donc limiter le nombre de biomes, et ça ne serait pas moins intéressant. On pourrait partir sur l'étagement et avoir toute une série de climat et de végétation très intéressante. Je crois que je vais approfondir ce point quand j'aurai un peu de temps parce qu'il me semble qu'il peut donner des résultats plus «réaliste» que le diagramme de Whittaker, si on peut parler de «réalisme» dans un jeu de cette nature.

Conclusion

Voilà donc où nous en sommes rendus : nous avons une carte de base qui demande encore quelques ajustements avant de pouvoir entrer dans la phase d'édition manuelle. Je n'ai pas encore tout pushé sur les dépôts git mais ça sera sans doute fait entre le moment où j'écris ces lignes et le moment où elles seront publiées. En particulier, j'ai mis tout ce que j'ai décrit ici dans un binaire à part dans le projet mapmaker de manière à séparer ce qui relève des algorithmes génériques (ceux de la partie 1) et des algorithmes spécifiques au jeu (ceux de la partie 2).

Pour la suite immédiate, je vais laisser cet aspect en plan et je vais m'intéresser aux inputs. Parce que ma réflexion sur les dialogues (prochain point dans ma feuille de route), ainsi que la bibliothèque jnuit de devnewton, m'ont amené à y réfléchir et de manière plus générale à réfléchir aux interactions entre mon personnage et mon univers. Sur les dialogues, les questions arrivent très vite : qui initie le dialogue ? Est-ce qu'il faut appuyer sur un bouton ? Comment détecter qu'on est bien à côté de quelqu'un qui veut dialoguer ? Comment gérer les dialogues interactifs ? L'exemple, donné dans un commentaire sur un épisode précédent, des dialogues du jeu Andor's Trail donne une piste.

Bref, encore de nombreux épisodes en perspective !

Aller plus loin

• Akagoria, la revanche de Kalista (373 clics)
• le tag gamedev (235 clics)