Génération de labyrinthe

[Bobby Sixkilla]

Génération de labyrinthe

Auteur : rmstudiogames

Alors voilà comme je l'avais proposé, voici un algo tres simple pour créer un labyrinthe fermé, ce qui veut dire que l'on ne peut pas tourner en rond. Si l'on ne fait qu'avancer, on ne repassera jamais deux fois au même endroit.

Attention, le code n'est pas très propre, je vous file la version qui m'a servi de test. La version finale est codée pour NGage, donc ça ne recompilera jamais sur GBA ou n'importe quoi d'autre !

Par exemple, c'est "hardcode" pour un labyrinthe 11x12 cases, à changer bien sur avec des variables que l'on pourra initialiser au runtime. Egalement, pour le système de backtrack, l'implementation optimale devrait utiliser une stack, j'ai salement utilisé un tableau de la taille du nombre maximum de cases (beurk c'est moche, à proscrire). Je n'ai même pas utilisé de structures, j'ai des variables differentes pour les x et les y.

Il est conseillé de modifier l'algo de façon à le modeler pour ses besoins. Ainsi à chaque "step", choisissant une direction aléatoirement, je n'obtenais pas beaucoup de lignes droites, ca zigzaguait dans tous les sens. Pour mon jeu, lorsque je pars dans une direction, pour le prochain step j'affecte plus de probabilité à cette direction. On pourrait faire plein d'améliorations de ce style.

Bon assez parlé, voilà le code...

#include "stdlib.h"
#include "string.h"

static char	maze[132];	//	The array which stores the state of each maze cell.
static int	neighbourX[] = { 1, -1, 0, 0 };	//	An array which is used to determine coordinates of
static int	neighbourY[] = { 0, 0, 1, -1 };	//	an adjacent cell (up, down, left, right).

int GivePossibleNeighbours(int x, int y)
{
//	For a given cell, gives the total number of adjacent cells.
//	adjacent does not include diagonals.
if(((x == 0) || (x == 10)) && ((y == 0) || (y == 11)))
 return 2;
else if((x == 0) || (x == 10) ||(y == 0) || (y == 11))
 return 3;
else
 return 4;
}

bool CellIsFree(int x, int y)
{
//	A cell is considered as free if it is included in the maze
//	and has not been visited yet, so it still holds a '1' flag.
if((x >= 0) && (x < 11) &&(y >= 0) && (y < 12) && (maze[y*11+x] == '1'))
 return true;
else
 return false;
}

int GiveFreeNeighbours(int x, int y)
{
int	result;
int	scan;

result	= 0;
//	We inspect every adjacent cell and we increment the counter
//	when each of them is free.
for(scan = 0; scan < 4; scan++)
 if(CellIsFree(x+neighbourX[scan], y+neighbourY[scan]))
 	result++;

return result;
}

int main(int argc, char* argv[])
{
int	currentX;	//	The current cell visited during the algorithm.
int	currentY;
int	backTracksX[132];	//	The array of points where we store every cell
int	backTracksY[132];	//	which has been used as a progression in the maze.
int	numBackTrack;  //	Number of the cells filling the array.

//	All the maze if filled with blocks. Thus, all cells are not visited.
memset(maze, '1', 132);

//	By doing this, we consider the top left cell is being visited. This is the
//	starting point of the algorithm. It could be randomly chosen.
currentX  = 0;
currentY  = 0;
backTracksX[0]	= 0;
backTracksY[0]	= 0;
numBackTrack	= 0;

//	The main algorithm.
do
{
 int	possibleNeighbours, freeNeighbours;
 int	direction;
 int	test;

 //	We now clear the current cell
 maze[currentY*11+currentX]	= '0';

 //	We choose a random direction and increment the counter of tests.
 direction	= ((double)rand()/(double) RAND_MAX)*4;
 test  = 1;

 while(test <= 4)
 {
 	//	For a given direction, we get the number of possible and actual free neighbours.
 	//	If there is exactly one less free neighbour (because we come from a visited neighbour),
 	//	this means that this cell has no neighbours which has been visited before. We can safely
 	//	visit it, we will not "break" the maze.
 	possibleNeighbours	= GivePossibleNeighbours(currentX+neighbourX[direction], currentY+neighbourY[direction]);
 	freeNeighbours  = GiveFreeNeighbours(currentX+neighbourX[direction], currentY+neighbourY[direction]);
 	if((freeNeighbours == possibleNeighbours - 1) && CellIsFree(currentX+neighbourX[direction], currentY+neighbourY[direction]))
   	break;

 	//	Otherwise, we look for another close cell. If we have tested four times, it means all
 	//	neighbours have been visited.
 	test++;
 	direction++;
 	if(direction == 4)
   direction	= 0;
 }

 //	If we have found a free neighbour then we can jump to this cell.
 if(test <= 4)
 {
 	//	The current cell is added to the stack of visited cells (yes, this is an array),
 	//	before using the free neighbour as the current cell and restarting the algorithm.
 	numBackTrack++;
 	backTracksX[numBackTrack-1]	= currentX;
 	backTracksY[numBackTrack-1]	= currentY;
 	currentX	= currentX+neighbourX[direction];
 	currentY	= currentY+neighbourY[direction];
 }
 else
 {
 	//	Otherwise, this cell has no free neighbour, we have come to a dead end.
 	//	We leave this cell and use our stack (our array) to inspect the last visited
 	//	cell in case it can lead somewhere else.
 	numBackTrack--;
 	currentX	= backTracksX[numBackTrack-1];
 	currentY	= backTracksY[numBackTrack-1];
 }
}
while(numBackTrack);	//	Of course we can stop when there are no more visited cells available.

return 0;
}