I. Introduction▲
Dans un jeu vidéo, générer aléatoirement des terrains est une manière de renouveler l'expérience du joueur à chaque partie. Cela peut également servir à simplifier la tâche au concepteur de niveaux, surtout si les niveaux sont nombreux, en fournissant une base de travail qui pourra être retouchée et enrichie pendant la phase de développement d'un jeu.
C'est un domaine très actif avec un champ d'études et d'expérimentations qui ne cesse de s'élargir, au point qu'à l'heure actuelle il est possible de générer procéduralement des planètes entières avec un haut niveau de détails (cf. Outerra, cette vidéo).
Le premier objectif, beaucoup plus modeste, que se fixera cette présentation sera de générer aléatoirement le relief d'un terrain rectangulaire de dimensions finies, puis de le restituer en image bitmap 2D et en scène 3D. Avant d'arriver à ce résultat, plusieurs notions seront abordées, et c'est la raison pour laquelle je laisserai dans un premier temps de côté tout ce qui est accessoire comme les rivières, les lacs ou encore la végétation qui pourront être envisagés dans une présentation ultérieure.
Le langage utilisé pour illustrer le propos sera TypeScript, un sur-ensemble de JavaScript avec typage et héritage. Une présentation de ce langage est disponible ici.
II. Heightmap▲
II-A. Principes▲
La représentation du relief d'un terrain passe souvent par une carte des altitudes, plus communément appelée par son terme anglo-saxon, heightmap. C'est ce terme anglo-saxon qui sera utilisé dans cette présentation, car très répandu dans le jargon. L'idée d'une heightmap est d'associer une valeur correspondant à l'altitude à chaque point d'une carte en 2D. Ce modèle simple est très pratique, mais possède quelques limitations que nous ignorerons ici. Par exemple une heightmap ne permet pas de modéliser des grottes ou des tunnels. Pour que les heightmaps soient facilement manipulables, les altitudes d'une heightmap sont souvent codées en utilisant la couleur (une intensité de gris).
Sur la heightmap ci-dessus, les zones les plus claires (blanches) correspondent aux hautes altitudes, tandis que les zones les plus sombres (noires) correspondent aux basses altitudes.
Le codage d'une heightmap peut donc être une image bitmap où l'altitude d'un point est stockée en triple exemplaire chaque composante RGB du pixel du point correspondant. Cela implique qu'en pratique une heightmap ainsi codée a des valeurs d'altitude comprises entre 0 et 255, sur 8 bits. Par exemple, si en un point <x, y> tel que x et y sont respectivement l'abscisse et l'ordonnée, l'altitude vaut 73, alors le pixel correspondant en <x, y> aura ses composantes RGB qui vaudront <73, 73, 73> et une valeur alpha (transparence) constante de 255.
Il existe des codages de heightmaps en 16, 24 et même 32 bits, qui autorisent donc une plage de valeurs pour l'altitude nettement plus importante, mais qui ne sont pas vraiment standardisés.
À noter que contrairement à la convention usuelle dans le domaine de la 3D, on utilisera dans un premier temps le symbole y comme une coordonnée du plan horizontal et non comme une coordonnée de la hauteur. Ceci afin de se conformer aux notations des représentations graphiques dans le domaine de la 2D, ce qui est le cas d'une image bitmap classique. Ce n'est que lorsque nous aborderons la représentation effective en 3D que le symbole y désignera effectivement la coordonnée de la hauteur.
II-B. Affichage en 2D▲
Avant d'aborder les différents algorithmes possibles pour générer aléatoirement un terrain, voyons déjà comment afficher une heightmap sur un navigateur en HTML5.
Pour l'affichage, nous ne considérerons que le cas d'une heightmap sur 8 bits et nous utiliserons le repère habituel en informatique, à savoir l'origine de l'abscisse et de l'ordonnée en haut à gauche.
On supposera que la heightmap est un tableau à deux dimensions et dont chaque valeur est un nombre entier compris entre 0 et 255 correspondant à l'altitude en ce point. La première coordonnée du tableau sera l'abscisse x (la composante horizontale de l'écran) et la seconde coordonnée sera l'ordonnée y (la composante verticale de l'écran). Ainsi, si le tableau est nommé map, map[5][2] doit renvoyer l'altitude du point de coordonnées (5 ; 2).
Pour afficher la heightmap, il s'agit globalement de parcourir l'ensemble des cases du tableau et d'affecter à chaque pixel, et à chaque composante RGB la valeur adéquate.
function drawHeightmap(map: number[][], container: HTMLElement) {
var dimX = map.length;
var dimY = map[0].length;
var canvas = document.createElement("canvas");
canvas.width = dimX;
canvas.height = dimY;
var ctx = canvas.getContext("2d");
var img = ctx.createImageData(canvas.width, canvas.height);
var imgData = img.data; // optimisation
var i = 0; // indice imgData
for (var y = 0; y < dimY; y++) {
for (var x = 0; x < dimX; x++) {
var height = Math.round(map[x][y]);
imgData[i++] = height;
imgData[i++] = height;
imgData[i++] = height;
imgData[i++] = 255; // alpha opaque
} // for x
} // for y
ctx.putImageData(img, 0, 0);
container.innerHTML = "";
container.appendChild(canvas);
} // drawHeightmapLa fonction drawHeightmap prend deux paramètres : map et container. Le paramètre map qui comme son nom l'indique est la carte, doit évidemment être défini avant l'appel à la fonction. C'est d'ailleurs ce que nous verrons prochainement avec un algorithme générant aléatoirement un ensemble de valeurs cohérentes sous la forme d'un tableau de nombres à deux dimensions. Pour tester dans un premier temps l'affichage, nous pouvons affecter une valeur aléatoire comprise entre 0 (noir) et 255 (blanc).
var myMap = Array(128);
for (var x = 0; x < 128; x++) {
myMap[x] = Array(128);
for (var y = 0; y < 128; y++) {
myMap[x][y] = Math.round(255 * Math.random());
} // for y
} // for xLe paramètre container doit quant à lui contenir la référence à un objet du DOM existant dans la page HTML, comme une balise <div> déjà existante, qui servira de conteneur à l'image de la heightmap. Pour obtenir cette référence à une balise <div> ayant un identifiant, il suffit de faire appel à la méthode document.getElementById. Par exemple, si l'identifiant est view tel qu'on ait <div id="view">, on pourrait initialiser une variable myContainer ainsi :
var myContainer = document.getElementById("view");À l'aide de myMap et de myContainer, nous pouvons ainsi appeler la fonction drawHeightmap une fois la page HTML chargée :
drawHeightmap(myMap, myContainer);En reprenant les exemples précédents, ceci doit afficher un carré rempli d'un brouillard de points à l'endroit de la balise <div id="view"> définie dans le corps du fichier HTML.
Vous pouvez voir le code de cet exemple en action ici.
Bien évidemment, bien que valable du point de vue du format, une telle heightmap totalement aléatoire n'est pas exploitable dans la pratique, le relief généré ne pouvant pas être vraisemblable. Pour cela nous allons examiner un des algorithmes permettant de générer des reliefs cohérents.
III. Algorithme Diamond Square▲
III-A. Principes▲
L'algorithme Diamond Square est un algorithme relativement répandu dans la génération procédurale de terrain, car il est simple à comprendre et plutôt rapide à l'exécution.
Tout d'abord, cet algorithme ne fonctionne que sur des grilles carrées de longueur kitxmlcodeinlinelatexdvp2^{n}+1finkitxmlcodeinlinelatexdvp. Il se déroule principalement en deux étapes qui s'alternent. L'une est appelée l'étape du carré (square) et l'autre est appelée l'étape du losange (diamond). L'idée centrale est qu'à chacune de ces étapes, on calcule la hauteur du centre en fonction de la moyenne des quatre extrémités, soit du carré, soit du losange selon l'étape dans laquelle se trouve l'algorithme.
La hauteur du centre se base sur la moyenne des extrémités, mais est modifiée d'un décalage aléatoire, positif ou négatif, afin de donner un aspect irrégulier au terrain final.
Plutôt que de longues et interminables explications, l'animation ci-dessous permet d'illustrer simplement et intuitivement le déroulement de l'algorithme.
Pour ceux qui souhaitent rentrer dans le détail du fonctionnement de l'algorithme, il existe un très bon article en français rédigé par Hiko Seijuro.
III-B. Implémentation▲
Il existe deux grandes variantes de l'algorithme Diamond Square. La plus répandue étant la version récursive que l'on trouve facilement sur Internet. Dans cet article, nous présenterons la version itérative trouvée dans une discussion sur le site d'échange Stack Overflow, moins connue, mais pourtant légèrement plus rapide.
Il s'agit donc de définir une fonction prenant en paramètre principal la taille de la heightmap (pour être plus précis, la longueur d'un côté) et d'autres paramètres auxiliaires comme celui indiquant si la carte peut être répétable (wrap) et celui influençant la dureté du relief (roughness).
L'algorithme commence par des initialisations, et en particulier l'initialisation de la hauteur des quatre coins qui peuvent être fixes ou bien aléatoires comme c'est le cas dans cette implémentation.
Puis, on entre dans une grande boucle qui permet de balayer les différentes cases de la carte en utilisant le principe du déplacement du point central (midpoint displacement) sur une surface de plus en plus réduite à mesure de l'avancement de l'itération principale.
C'est dans cette itération principale que sont réalisées les deux étapes caractéristiques de l'algorithme Diamond Square, l'étape du carré et l'étape du losange, où la subtilité réside essentiellement dans le mode de calcul des coordonnées des coins qui permettent in fine d'attribuer une hauteur semi-aléatoire pour le centre.
Voici l'intégralité de l'algorithme Diamond Square en TypeScript :
Il est bien évidemment possible de faire appel à d'autres algorithmes que le Diamond Square (par exemple Perlin Noise, Value Noise, DLA, Particle Deposition, etc.) sachant que l'essentiel étant que l'algorithme doit produire en bout de course un résultat compatible avec notre implémentation générale, en l'occurrence ici un tableau de nombres entiers en deux dimensions.
Le résultat de la méthode Diamond Square peut donner une heightmap telle que celle-ci :
Vous pouvez voir ici le code du Diamond Square en action reprenant l'implémentation générale.
IV. Rendu en 3D▲
À partir d'une heightmap, il n'est pas forcément évident de se rendre compte concrètement du résultat. Pour cela, une possibilité serait d'enregistrer l'image (via un clic droit sur l'image dans votre navigateur par exemple) et de l'importer dans un outil spécialisé pour un rendu en 3D. Les outils pouvant importer une heightmap sont nombreux. Citons par exemple Terragen ou Geogen parmi les outils spécialisés disponibles gratuitement (sous certaines conditions), ou encore des moteurs de jeu comme Unity ou Unreal Engine même si ces derniers utilisent des formats bruts (raw) en 16 bits.
Il est cependant tout à fait possible de générer une petite scène interactive en 3D directement dans son navigateur grâce à des bibliothèques JavaScript se basant sur WebGL. Il existe différentes bibliothèques simplifiant l'emploi de WebGL comme babylon.js. Ici, nous utiliserons three.js qui bénéficie d'une bonne popularité.
Le rendu de la heightmap avec three.js suit les étapes classiques de n'importe quel rendu 3D. La scène est constituée d'une caméra et du terrain sous la forme d'un maillage de points dans l'espace et sur lequel nous appliquons une texture monochrome afin de rendre l'exemple le plus simple possible. Et nous associons le contrôleur (les entrées clavier) à la caméra afin de simuler un déplacement à la première personne. On notera que le contrôleur est défini dans une classe à part pour des besoins de clarté.
Malgré sa longueur, ce script est relativement simple et linéaire sur un mode plutôt déclaratif. Une démonstration en ligne de ce script est disponible ici. Dans cette démonstration, la navigation horizontale se fait via les touches W-A-S-D pour les claviers QWERTY (ou Z-Q-S-D pour les claviers AZERTY), la navigation verticale via les touches R et F, et l'orientation de la caméra via les flèches du clavier.
Ce rendu 3D nous permet de nous rendre compte d'un défaut important et bien connu de l'algorithme Diamond Square. Il a tendance à générer des pics disgracieux au sommet des montagnes. Pour y remédier, nous pouvons adoucir le relief.
V. Lissage▲
Il existe d'innombrables algorithmes, ou filtres dans le jargon du traitement de l'image, pour rendre une image plus lisse ou smooth en anglais. Dans cette présentation nous nous limiterons simplement à décrire l'un des plus simples d'entre eux : l'algorithme dit Box Blur.
Sans rentrer dans la théorie, le principe de cet algorithme est de remplacer la hauteur d'un point de notre heightmap par la moyenne des hauteurs de son voisinage, en incluant la hauteur du point concerné, et d'appliquer ce principe à tous les points de la heightmap.
Il faut voir le Box Blur comme une moyenne mobile en deux dimensions.
Avec le Box Blur, l'utilisateur peut jouer principalement sur deux paramètres. Le premier peut consister à faire varier la notion de voisinage. Cela peut être uniquement les points immédiatement adjacents au point concerné, ou bien incluant des points plus éloignés, sachant qu'en termes d'implémentation le voisinage sera très souvent modélisé par des matrices carrées. Plus le voisinage sera étendu, et plus le lissage sera fort à cause du poids relatif du centre qui tendra à diminuer.
Le second paramètre que peut faire varier l'utilisateur de cet algorithme est la notion de moyenne. Cela peut être une simple moyenne arithmétique ou bien une moyenne pondérée, avec des poids distincts selon les cases de la matrice de voisinage. On pourrait vouloir par exemple que le point concerné, au centre, ait un poids supérieur au poids de ses voisins dans le calcul de la moyenne, ce qui aura pour effet de rendre le lissage moins uniforme. Pour cette présentation, nous nous limiterons à une simple moyenne arithmétique où chaque point de la matrice de voisinage a le même poids.
Voici ce que pourrait donner une implémentation en TypeScript de l'algorithme Box Blur :
function boxBlur(map:number[][], radius: number): number[][] {
var dimX = map.length;
var dimY = map[0].length;
var result: number[][] = [];
var line: number[];
var val: number;
for (var i = 0; i < dimX; i++) {
line = [];
for (var j = 0; j < dimY; j++) {
val = 0;
for (var iy = j - radius; iy < j + radius + 1; iy++) {
for (var ix = i - radius; ix < i + radius + 1; ix++) {
var x = Math.min(dimX - 1, Math.max(0, ix));
var y = Math.min(dimY - 1, Math.max(0, iy));
val += map[x][y];
} // for ix
} // for iy
line.push(val / ((radius + radius + 1) * (radius + radius + 1)));
} // for j
result.push(line);
} // for i
return result;
} // boxBlurSi, juste après la génération de la heightmap via la méthode du Diamond Square vu plus haut, nous appelons cette fonction de lissage, voici ce que nous pourrions obtenir comme rendu 3D :
On notera ici l'apparition de « textures ». Il s'agit simplement d'une petite amélioration parmi celles disponibles dans cette démonstration en ligne.
L'intérêt majeur de l'algorithme Box Blur est qu'on peut l'utiliser pour approximer un filtre de Gauss (ou Gaussian Blur) un autre algorithme de lissage plus sophistiqué, mais plus coûteux en calculs. Il faut pour cela réaliser plusieurs passages du Box Blur pour simuler un filtre de Gauss, mais cela reste néanmoins plus rapide.
VI. Conclusion▲
À travers cette présentation des heightmaps, nous avons abordé l'affichage d'une image dans le navigateur, nous avons vu un algorithme, le Diamond Square, permettant de générer des hauteurs donnant un aspect plus réaliste que de simples valeurs aléatoires, même si cet algorithme comporte quelques défauts qui sont décelables via un simple rendu en 3D que nous avons également abordé. Et pour corriger ces défauts, nous avons utilisé un algorithme simple de lissage qui est le Box Blur.
VI-A. Remerciements▲
Je remercie LittleWhite pour la relecture technique ainsi que Claude Leloup pour la relecture orthographique de cet article.
Les commentaires et les suggestions d'améliorations sont les bienvenus, alors, après votre lecture, n'hésitez pas. Commentez.