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




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 :

• Une cellule n'est jamais choisie deux fois.
• Toutes les cellules sont choisies.
• Pour choisir N cellules, il faut N choix, pas un de plus.

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