Necrown - Devlog #13 [Game Dev] : Algorithme Diamond-Square et génération procédurale de mondes
Splix Il y a 11 mois Premium Pro6

Salut les gamecodeurs !!!

Aujourd’hui nous allons commencer à véritablement travailler sur le jeu. J’ai créé des classes destinées à gérer les tuiles (merci à notre système orienté objet développé dans un précédent devlog qui permet l’héritage). Ces classes sont locales, au final les tuiles n’existeront qu’en un exemplaire, et la tilemap du jeu ne contiendra que des numéros, correspondant aux identifiants des tuiles, le tout pour des questions de performances. Maintenant il nous faut générer des mondes, et nous allons utiliser pour cela un algorithme de génération procédurale appelé Diamond-Square (ou en français L’algorithme Diamant-Carré).

Cet algorithme utilise un tableau de taille 2n + 1. On commence par initialiser le tableau avec des valeurs aléatoires (au moins le quatre coins), ensuite l’algorithme va générer le reste des valeurs. Le Diamond-Square est divisé en deux phases qui se répètent jusqu’à ce que la map soit entièrement générée (vous l’aurez deviné 😉 ): La phase du diamant et la phase du carré…

Lors de la phase du diamant, on fait la moyenne de quatre coins d’un carré (possédants déjà une valeur), à laquelle on ajoute une petite variation proportionnelle au côté du carré (pour garder une cohérence dans le résultat), et cela définit la valeur du centre du carré, formant ainsi des losanges. La phase du carré fonctionne de la même façon, sauf que l’on va utiliser les quatre points des losanges créés précédemment, formant ainsi des carrés. Et on répète l’opération, avec des carrés et des losanges de plus en plus petit, jusqu’à ce que la map soit entièrement générée…

Cet algorithme est en général utilisé pour produire ce que l’on appelle une heightmap, une « carte d’élévation » simulant un relief, mais comme il s’agit de bruit cohérent, on peut l’utiliser pour simuler n’importe quoi (on pourrait par exemple créer une carte de température ou de taux d’humidité…). Voici mon implémentation de l’algorithme (les fonction getSample et setSample permettent juste de récupérer ou de modifier une valeur dans la map, et featureSize correspond à l’intervalle entre les valeurs lors de l’initialisation du tableau, c’est à dire le pas de départ de l’algorithme):

function diamondSquare:generate()
  local stepSize = self.featureSize
  repeat
    local halfStep = stepSize / 2
    
    -- Phase du diamant
    for x = 1, world.wt, stepSize do
      for y = 1, world.ht, stepSize do
        local a = self:getSample(x, y)
        local b = self:getSample(x + stepSize, y)
        local c = self:getSample(x, y + stepSize)
        local d = self:getSample(x + stepSize, y + stepSize)
        
        local v = ((a + b + c + d) / 4) + self.rand:random() * (stepSize / self.featureSize) * self.smooth
        self:setSample(x + halfStep, y + halfStep, v)
      end
    end
    
    -- Phase du carré
    for x = 1, world.wt, stepSize do
      for y = 1, world.ht, stepSize do
        local a = self:getSample(x, y)
        local b = self:getSample(x + stepSize, y)
        local c = self:getSample(x, y + stepSize)
        local d = self:getSample(x + halfStep, y + halfStep)
        local e = self:getSample(x + halfStep, y - halfStep)
        local f = self:getSample(x - halfStep, y + halfStep)
          
        local v1 = ((a + b + d + e) / 4) + self.rand:random() * (stepSize / self.featureSize) * self.smooth
        self:setSample(x + halfStep, y, v1)

        local v2 = ((a + c + d + f) / 4) + self.rand:random() * (stepSize / self.featureSize) * self.smooth
        self:setSample(x, y + halfStep, v2)
      end
    end
    
    stepSize = stepSize / 2
  until stepSize <= 1
end

Nous avons ce qu’il nous faut pour générer nos monde, nous n’avons besoin de rien d’autre pour le moment. Donnez une valeur au niveau de la mer et nous avons des continents et des îles qui se dessinent, ou croisez les résultats de deux maps et vous obtiendrez des formes surprenantes, comme lorsque l’on place les éléments stone ou clearGrass:

local map = {}
map.tiles = {}
map.entities = {}

for xt = 1, world.wt do
  for yt = 1, world.ht do
    local h = heightmap:getSample(xt, yt)
    local m1 = mountain_1:getSample(xt, yt)
    local m2 = mountain_2:getSample(xt, yt)
    local c1 = clearGrass_1:getSample(xt, yt)
    local c2 = clearGrass_2:getSample(xt, yt)
    
    if h < 0.25 then
      map.tiles[xt + (yt - 1) * world.wt] = water.id
    else
      if h > 0.4 and (m1 < 0.1 or m2 > 0.9) then
        map.entities[xt + (yt - 1) * world.wt] = stone.id
      end
      if h > 0.3 and (c1 < 0.15 or c2 > 0.85) then
        map.tiles[xt + (yt - 1) * world.wt] = clearGrass.id
      else
        map.tiles[xt + (yt - 1) * world.wt] = grass.id
      end
    end
  end
end

On va également placer des arbres, et la technique que l’on utilisera ici est asses simple: On prend des points au hasard sur la map, puis on va prendre tout un tas de points autour de celui-ci (avec une densité aussi élevée qu’on en est proche), et si les conditions sont réunies, on placera un arbre… Voici au final le résultat de notre algorithme de génération procédurale de mondes:

Vous avez ici quatre maps générées avec notre algorithme et des seeds aléatoires. Nous avons une bonne base pour débuter le développement de notre jeu. Dans le prochain devlog, nous allons mettre au point un système de chunks. Ils seront pré-générés lors de la phase de génération du monde et rendront moins lourds les sauvegardes et les chargements, ce qui sera utile lorsque l’on sauvegardera avant de quitter le jeu ou lorsque l’on voudra créer un système de sauvegardes automatiques (sauvegarder toute la map, même si elle est loin d’être gigantesque, serait beaucoup trop long). Mais en attendant…

Bon code et à la prochaine!!!

Comments (6)

Merci duruti,
Mdr je ne suis encore jamais allé sur le discord, et pourtant je suis premium depuis 2016 XD. J’ai quelques problèmes de sociabilité et je ne suis pas très doué pour faire de la pub, mais je ferais un effort.
Merci du conseil 😉

Laisser un commentaire

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.