Génération procédurale – Part 2

Cet article fait suite à celui ci.

On trouve évidement différents algos, pour générer un certain type de structure. Aujourd’hui intéressons nous aux cavernes : c’est le plus simple, à mon avis.

Commençons par définir deux fonctions usuelles : créer une map et l’afficher ; ainsi qu’une classe tile() :

MAP_HEIGHT = 30 
MAP_WIDTH = 30

class Tile:
  def __init__(self, blocked=False):
    self.blocked = blocked
    
def makeMap(width, height, blocked=False):
  #fill map with tiles
  newMap = [[Tile(blocked)
    for x in range(height)]
      for y in range(width)]    
  return newMap

def printMap(aMap):
  for y in aMap:
    for tile in y:
      if tile.blocked:
         print("#", end="")
      else:
         print(".", end="")
      print(" ", end="")
    print()

myMap = makeMap(MAP_WIDTH, MAP_HEIGHT)
printMap(myMap)

 

Drunk walker

Celui ci a une fonctionnement qui me touche particulièrement : il se déplace aléatoirement comme un type bourré. Il est simple à mettre en place et donne des résultats sympas, avec un coût de calcul faible. Les plus pénibles le nommeront « algorithme brownien à diffusion limitée », mais je préfère le nommer « marcheur bourré ».

0 – Créer une map remplies de cases pleines.

1 – Au milieu de la map, placer quelques cases vides, définies de manière aléatoire.

2 – Dans une de ces case, placer un objet que nous nommerons « marcheur bourré ».

3 – Déplacer, de manière aléatoire, le marcheur bourré jusqu’à ce qu’il rencontre une case pleine.

4 – Rendre cette case vide. Répéter 3.

On définira une limite pour 3 (par exemple : 40% des cases sont vides). On obtiendra une map avec une zone centrale vide, d’aspect irrégulier, dont chaque case est accessible.

En Python, ça donne ceci :

def drunkenWalker(aMap, limit, emptyTilesAtStart, seed=None):

  #Initialiser le générateur de nombre aléatoire.
  #Par défaut seed=None, donc l'heure système sera utilisée
  #(ça ressemble beaucoup à un nombre aléatoire)
  #Mais il est utile de laisser la possibilité de définir un seed particulier.
  random.seed(seed)

  #Creuser quelques cases au centre de la map
  for emptyTile in range(0, emptyTilesAtStart):
    randX = random.randrange(( len(aMap)//2-emptyTilesAtStart//2 ),
       ( len(aMap)//2+emptyTilesAtStart//2 ))
    randY = random.randrange(( len(aMap[0])//2-emptyTilesAtStart//2 ),
       ( len(aMap[0])//2+emptyTilesAtStart//2 ))
    aMap[randX][randY].blocked=False
  
  #tmp
  i=0
  
  #le marcheur ivre commence sur la dernière case qu'on a creusée
  walker=(randX, randY)
  
  while True:
    
    unblocked = True
    while unblocked :

      #choisir au hasard une direction
      dx = random.randrange(-1,2)
      dy = random.randrange(-1,2)
      #on vérifie qu'on ne sort pas de la map (avec une marge de 1)
      if not ( walker[0]+dx < 1
          or (walker[0]+dx >= len(aMap)-1)
          or walker[1]+dy < 1
          or (walker[1]+dy >= len(aMap[0])-1)):
         #si on ne sort pas de la map, on se déplace comme prévu
        walker = (walker[0]+dx, walker[1]+dy)
        unblocked = not aMap[walker[0]][walker[1]].blocked
      else:
        #si on sort de la map, on fait demi tour
        walker = (walker[0]-dx, walker[1]-dy)

    #on creuse
    aMap[walker[0]][walker[1]].blocked=False
    
    #Compter le nombre de cases vides.
    #C'est assez moche, je pense qu'on pourrait trouver beaucoup plus élégant.
    emptyTiles = 0
    for row in aMap:
      for tile in row:
         if not tile.blocked:
            emptyTiles +=1

    #print("cases vides : %s / %s" % (emptyTiles, limit))
    #printMap(aMap)
    
    if emptyTiles >= limit:
      break
    


myMap = makeMap(MAP_WIDTH, MAP_HEIGHT, True)

#(pour une map de 20x20)
#on veut 200 cases vides à la fin, 5 au début, sans préciser de seed :
drunkenWalker(myMap, 200, 5)

printMap(myMap)
# # # # # # # # # # # # # # # # # # # # # # # # # 
# # # # # # # # # # # # . # # # # . . # # # # # # 
# # # # # # # # # # # . . # # # # . . # . # # # # 
# # # # # # # # # . . . . . . # . . . . . . # # # 
# # # # # # # . # . . . # . # . . . # # . . . # # 
# # # # # # # # . . . . . . . . . . . . # # . # # 
# # # # # # . . . . . . . . . . . . . . . # # . # 
# # # # # . # # . . . # . . . . . . . # # . # # # 
# # # . . # # # # # # . . . . . . . . . # # # # # 
# # # . . # # # # # # # # . . . # . . . # # # # # 
# # # . # # # # . . # # . . . . . . . . # # # # # 
# # . . # # # . . . . # . . . . . . . # # . # # # 
# . . # . # . . . . . . . . . . . . # . . . # # # 
# # . # . . . . . # . . . . . . . . . . # # . # # 
# . . . # . . # . . . . # . # # . . . # . . # # # 
# . . . . . # # . . . # # # # # # # . . # # # # # 
# # . . . . # # # . # # # # # # # # # # # # # # # 
# . . . . . # # # # # # # # # # # # # # # # # # # 
# . . . . . # # # # # # # # # # # # # # # # # # # 
# . . . . . # # # # # # # # # # # # # # # # # # # 
# # # . . . # # # # # # # # # # # # # # # # # # # 
# # # . # # # # # # # # # # # # # # # # # # # # # 
# # # # # # # # # # # # # # # # # # # # # # # # # 
# # # # # # # # # # # # # # # # # # # # # # # # # 
# # # # # # # # # # # # # # # # # # # # # # # # #

Game of life

On peut utiliser des automates cellulaires pour générer des structures intéressantes. Un automate cellulaire, est un programme qui remplit ou vide des cases selon des règles très simples, vaguement calquées sur la biologie : si une case à plus de x voisins, elle meurt ; si une case à moins de x voisins, elle se duplique. Ces règles simples peuvent donner lieu à des comportement complexes ; d’ailleurs, un automate cellulaire de Conway (celui de base quoi), est Turing-complet : ça veut dire que dans le principe, c’est un vrai ordinateur en soi.

D’ailleurs c’est très bien expliqué sur Wikipédia :

En informatique ou en logique, un système Turing-complet1 est un système formel ayant une puissance de calcul au moins équivalente à celle des machines de Turing. Dans un tel système, il est possible de programmer n’importe quelle machine de Turing, mais également tout ce que l’on peut programmer dans une machine de Turing. Si de plus ce système peut être codé par celui des machines de Turing, on dit qu’il est équivalent aux machines de Turing. wikidepia : Turing-complet

Tout est soudain beaucoup plus clair*. Enfin bref, on s’en fout, ce qui nous intéresse c’est qu’on peut faire des niveaux de jeu vidéo avec. Donc revenons au schmilblick.

La map a deux types de cases : vide, et pleine.

0 – Créer une map remplies de cases aléatoirement vides, ou pleines

1 – Appliquer l’automate cellulaire sur la map

2 – Répéter 1 jusqu’à un certain niveau de raffinement

Vous le voyez, l’avantage c’est que c’est simple. Plus le raffinement sera élevé, plus la map sera lisse (sans anfractuosités). Néanmoins on a un problème, il peut y avoir plusieurs sections de « vide » qui ne sont pas reliées : le joueur ne pourra donc pas y accéder. Selon le type de jeu, c’est soit un problème, soit un avantage (dans un jeu de « minage », c’est intéressant que certaines zones soient inaccessibles sans creuser un tunnel).

*Concretement, ça veut dire qu’en théorie on peut programmer un Game of Life dans un Game of Life. C’est une source inépuisable de mindfuck, renvoyant au choix au mythe de la caverne de Platon, aux Méditations métaphysiques de Descartes, ou au Matrix des Wachowski : c’est grosso modo le même message de toute façon.

 

Perlin Noise

Je ne vais pas détailler cette solution, pour deux raisons. D’abord, parce qu’elle donne des solutions similaires à la solutions précédentes (différents niveaux de complexité, fortes probabilités de cavités, etc). Ensuite, parce que les articles où Perlin explique ces algos sont momentanément inaccessibles  ; donc j’essayerais d’éditer plus tard.

Pour info, Ken Perlin écrit des algorithmes qui trouvent des applications dans la CG (génération de texture, en particulier), mais aussi dans l’animation de personnages. Si vous utilisez Blender ou un autre soft du même acabit, vous connaissez probablement le Perlin Noise : bin oui c’est lui. Le genre de mec qui n’a même pas de page sur Wikipedia, mais dont les cours sont disponibles. Voilà.

 

Rendre une map utilisable

On a vu que les maps générées par un Perlin Noise ou un Game of Life n’étaient pas directement utilisables. En effet, elles peuvent présenter des cavités : des zones auxquelles le joueur ne peut pas accéder.

On peut imaginer plusieurs approches.

  • S’en foutre. Ça parait idiot ou brutal, mais dans certains types de jeu, les zones inaccessibles font partie du gameplay. C’est le cas par exemple, d’un jeu où le joueur a la possibilité de creuser les murs.
  • éliminer les zones inaccessibles. C’est assez facile à faire avec un algo de « remplissage » : on part de la position de départ du joueur, et on remplit chaque case de la map que l’on peut atteindre. Lez cases non rempies seront éliminées (= marquées comme pleines). Par contre, on obtient souvent une map peu intéressante avec beaucoup de pleins.
  • creuser des tunnels, entre les zones inaccessibles, et  les zones accessibles. C’est de loin la solution la plus compliquée, mais elle permet d’obtenir une map très intéressante. Une solution, est de détecter les zones inaccessibles (avec un algo de remplissage) puis ce creuser pour chacune de ces zones, un tunnel qui va en ligne droite vers le centre de la map (= l’endroit où le player se trouve au début de la partie). Après coup, on pourra éventuellement appliquer un algo de lissage, par exemple un Game of Life (à tester).

Une réflexion au sujet de « Génération procédurale – Part 2 »

  1. Ping : Génération procédurale – Part 1 | thibsert

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *


Time limit is exhausted. Please reload CAPTCHA.