GALERIE    EN COURS    SCENES    MACROS    GUIDE    A PROPOS


Labyrinthe - Première partie



Introduction

Je ne suis bien sûr pas le premier à vouloir générer des labyrinthes avec POYRay, d'ailleurs, Robert McGregor nous a fait partager ses superbes essais récement dans le newsgroup povray.binaries.images

Une simple recherche sur Google donne directement un article dans Wikipédia : Modélisation mathématique d'un labyrinthe. Après une rapide lecture de l'article, l'algorithme dit de "Fusion aléatoire de chemins" m'a bien plu. La suite est donc basée sur cette méthode. Merci de vous reporter à cet article pour toutes les informations sur ces algorithmes.



Fort de cette lecture, nous allons donc mettre en pratique cet algorithme avec POVRay.


Modélisation

cellules 3x3 J'ai choisi de représenter chaque cellule du labyrinthe par un ensemble de 3x3 carrés comme le montre l'image ci contre.

Les carrés bleu représentent les murs horizontaux, les carrés brun, les murs verticaux et les carrés gris le sol.

Trois variables sont déclarées :
#declare xDim = 7;
#declare zDim = 11;
#declare boxSize = 5;
et représentent le nombre de cellules dans la direction x, z ainsi que la taille de chaque carré constituant une cellule. Au total, le labryrinthe aura xDim * zDim * 9 éléments (un peu plus en fait, mais nous verrons cela plus loin).

Chaque cellule occupera donc un carré dont le coté est égal à 3 x boxSize. Quatre tableaux sont utilisés :
#declare TheMaze = array[XDim][ZDim]
#declare Indices = array[XDim*ZDim]
#declare VWalls = array[XDim+1][ZDim+1]
#declare HWalls = array[XDim+1][ZDim+1]
TheMaze represente les lignes et les colones du labyrinthe.
tableau lignes et colonnes

Indices représente les mêmes cellules mais misent bout à bout... on passe d'un tableau de deux dimensions à une seule.tableau une seule ligne

VWalls et HWalls représentent les murs horizontaux et verticaux. Ces deux tableaux contient des valeurs booléennes indiquant la présence ou l'absence des murs.

Notre labyrinthe modélisé ressemble donc à ça :

labryrinthe modelise



Quelques macros utiles

// --------------------------------------------------------------------------
// Convert (Raw,Col) to Indice.
// --------------------------------------------------------------------------
#macro lc2indice (thisRow, thisCol)
  zDim*thisRow+thisCol
#end

// --------------------------------------------------------------------------
// Convert Indice to (Row,Col)
// --------------------------------------------------------------------------
#macro indice2lc (thisIndice)
  #local row = int(thisIndice/zDim);
  #local col = thisIndice-(zDim*row);
  array[2]{row,col};
#end

// --------------------------------------------------------------------------
// Get random direction : Right or Bottom
// --------------------------------------------------------------------------
#macro GetRandomWay()
  (rand(alea)>0.50 ? RIGHT : BOTTOM)
#end


Initialisation du labyrinthe

C'est la première macro utilisée. Elle est appelée avec deux paramètres : le nombre de cellule dans chaque direction. Les deux tableaux TheMaze et Indices sont remplis avec l'indice de chaque cellule. Les tableaux VWalls et HWalls sont initialisés avec la valeur true, symbolisant la présence d'un mur et tout les murs sont présents au début ! C'est aussi dans cette macro que deux variables sont déclarées : RIGHT et BOTTOM. Elles serviront à déterminer de manière aléatoire, la direction à explorer dans le labyrinthe.
// --------------------------------------------------------------------------
//  Initialize the maze. Fill somes arrays.
// --------------------------------------------------------------------------
#macro InitTheMaze(XDim, ZDim)
 // --- Define two constants
 #declare RIGHT=0;
 #declare BOTTOM=1;

 // --- Define some arrays
 #declare TheMaze = array[XDim][ZDim]
 #declare Indices = array[XDim*ZDim]
 #declare VWalls = array[XDim+1][ZDim+1]
 #declare HWalls = array[XDim+1][ZDim+1]

 // --- Fill Cells and Indices arrays
 #local r = 0;
 #while( r < XDim )
  #local c = 0;
  #while ( c < ZDim )
   #local indice = lc2indice(r,c);
   #declare TheMaze[r][c]=indice;
   #declare Indices[indice]=indice;
   #set c=c+1;
  #end
  #set r=r+1;
 #end
 
 // --- Fill Vertical walls array
 #local r = 0;
 #while( r < XDim+1 )
  #local c = 0;
  #while ( c < ZDim+1 )
   #declare VWalls[r][c]=true;
   #set c=c+1;
  #end
  #set r=r+1;
 #end

 // --- Fill Horizontal walls array
 #local r = 0;
 #while( r < XDim+1 )
  #local c = 0;
  #while ( c < ZDim+1 )
   #declare HWalls[r][c]=true;
   #set c = c + 1;
  #end
  #set r = r + 1;
 #end
#end


Construction du labyrinthe

C'est cette macro qui est le constructeur.
// --------------------------------------------------------------------------
//  For the choosen cell, try to remove wall at right or at bottom. 
// --------------------------------------------------------------------------
#macro BuildTheMaze()
 #local index = 0;
 #while( index < (xDim*zDim) )
  #if(verbose) #debug concat("\nLoop ",str(index,2,0),", ") #end
  #local RandomCell = GetRandomCell()
  #local ThisRow = RandomCell[0];
  #local ThisCol = RandomCell[1];
  #if(verbose)
    #debug concat("Random Cell : [",str(ThisRow,0,0),",",str(ThisCol,0,0),"]")
  #end
  #local ThisCell = TheMaze[ThisRow][ThisCol];
  ExploreDirs(ThisRow,ThisCol)
  #if(verbose) DisplayASCIIMaze() #end
  #set index = index + 1;
 #end
#end
La boucle while parcourt toutes les cellules. Chaque cellule est choisie de manière aléatoire par le macro GetRandomCell(). Une fois la cellule choisie, la macro ExploreDirs() est appelée pour essayer de supprimer un mur.

La variable verbose (booléen) déclarée en début du programme permet de suivre l'évolution de la construction du labyrinthe.

Ci-dessous, la macro GetRandomCell().
#macro GetRandomCell()
 #local IndiceSize = dimension_size(Indices,1);
 #if( IndiceSize = 1 )
  #local RandomCell = Indices[0];
 #else
  #local RandomIndice = int(IndiceSize*rand(alea));
  #local RandomCell = Indices[RandomIndice];
  #local NewSize=IndiceSize-1;
  #local tempArray=array[NewSize]
  #local i=0;
  #while( i < RandomIndice )
   #declare tempArray[i]=Indices[i];
   #set i = i + 1;
  #end
  #set i = i + 1;
  #while( i < IndiceSize )
   #declare tempArray[i-1]=Indices[i];
   #set i = i + 1;
  #end
  #undef Indices
  #declare Indices = array[NewSize]
  #local i = 0;
  #while( i < NewSize )
   #declare Indices[i] = tempArray[i];
   #set i = i + 1;
  #end
 #undef tempArray
 #end

 indice2lc(RandomCell)
#end


Cette macro choisie aléatoirement une cellule et retourne ses coordonnées. Cette routine utilise les tableaux dynamiques. Au début, il y a N = xDim*zDim cellules. La valeur de chaque cellule est son indice : zéro pour la première, (N-1) pour la dernière. A chaque fois qu'une cellule est choisie, elle est supprimée du tableau. Cette méthode permet donc de choisir aléatoirement une cellule de manière optimisée : Grace à la macro indice2lc(), les coordonnées de la cellule choisie sont retournées sous forme de tableau. Une fois en possession des coordonnées de la cellule choisie, la macro ExploreDirs() va essayer de supprimer un mur.
#macro ExploreDirs(thisRow,thisCol)
 #local ThisCell = TheMaze[ThisRow][ThisCol];
 #local ThisWay = GetRandomWay();
 #if( verbose )
   #debug concat(" Direction : ")
  #en
 #switch( ThisWay )
  #case( RIGHT )
   #if(verbose) #debug "RIGHT" #end
   #if( ThisCol+1 < zDim )
    #local oldVal = TheMaze[ThisRow][ThisCol+1];
    ChangeMazeCells(oldVal, ThisCell)
    #declare VWalls[ThisRow][ThisCol+1] = false;
   #else
    #if( ThisRow+1 < xDim )
     #local oldVal = TheMaze[ThisRow+1][ThisCol];
     ChangeMazeCells(oldVal, ThisCell)
     #declare HWalls[ThisRow+1][ThisCol] = false;
    #else
     #error "OUT OF RANGE ERROR !"
    #end
   #end
  #break
  
  #case( BOTTOM )
   #if(verbose) #debug "BOTTOM" #end
   #if( ThisRow+1 < xDim )
    #local oldVal = TheMaze[ThisRow+1][ThisCol];
    ChangeMazeCells(oldVal, ThisCell)
    #declare HWalls[ThisRow+1][ThisCol] = false;
   #else
    #if( ThisCol+1 < zDim )
     #local oldVal = TheMaze[ThisRow][ThisCol+1];
     ChangeMazeCells(oldVal, ThisCell)
     #declare VWalls[ThisRow][ThisCol+1] = false;
    #else
     #error "OUT OF RANGE ERROR"
    #end
   #end
  #break
 #end
#end
La direction est choisie aléatoirement. La macro GetRandomWay() retourne deux directions : RIGHT ou BOTTOM. Si la suppresion du mur est possible, on récupère la valeur de la cellule et l'on propage cette nouvelle valeur à toutes les cellule déja connectées. En fait celle qui ont la même valeur que la cellule soit à droite, soit en dessous. Par exemple, si la valeur de la cellule est '5' et la direction RIGHT. La valeur de la cellule a droite est '10'. Il faut remplacer toutes les anciennes valeurs '10' par '5'. On voit très bien ces changements dans l'animation sur la page Wikipédia déjà citée plus haut.

C'est ce que fait la macro ChangeMazeCells():
#macro ChangeMazeCells(oldVal, newVal)
 #local r = 0;
 #while ( r < xDim )
  #local c = 0;
  #while( c < zDim )
   #if (TheMaze[r][c] = oldVal)
    #declare TheMaze[r][c] = newVal;
   #end
   #set c=c+1;
  #end
  #set r=r+1;
 #end
#end