Générateur aléatoire de labyrinthe

Méthode de fusion aléatoire.

Voir version :

Pas de dépendances

Télécharger :

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct Laby
{
    int** tab;
    int taille;
} Laby;

void Preparer(Laby* l)
{
    int i,j,cpt;
    l->tab = malloc(l->taille*sizeof(int*));
    for(i=0;i<l->taille;i++)
        l->tab[i] = malloc(l->taille*sizeof(int));
    for(cpt=1,i=0;i<l->taille;i++)
        for(j=0;j<l->taille;j++)
            if (i%2==1 && j%2==1)
                l->tab[i][j] = cpt++;
            else
                l->tab[i][j] = 0;
}

void Afficher(Laby* l)
{
    int i,j;
    for(i=0;i<l->taille;i++)
    {
        for(j=0;j<l->taille;j++)
            printf("%c",(l->tab[i][j]==0)?'*':'.');
        printf("\n");
    }
}

void Liberer(Laby* l)
{
    int i;
    for(i=0;i<l->taille;i++)
        free(l->tab[i]);
    free(l->tab);
}

void Remplacer(Laby* l,int anc,int nouv)
{
    int i,j;
    for(i=0;i<l->taille;i++)
        for(j=0;j<l->taille;j++)
            if (l->tab[i][j]==anc)
                l->tab[i][j] = nouv;
}

void Generer(Laby* l)
{
    int vec[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    int nbzones = ((l->taille-1)/2)*((l->taille-1)/2);
    while(nbzones>1)
    {
        int i,x,y,zone1;
        zone1 = 0;
        x = rand()%(l->taille-2)+1;
        y = rand()%(l->taille-2)+1;
        if (l->tab[x][y]!=0)
            continue; // pas un mur
        for(i=0;i<4;i++)
        {
            int valzone = l->tab[x+vec[i][0]][y+vec[i][1]];
            if (valzone>0)
            {
                if (zone1==0 || zone1 == valzone)
                    zone1 = valzone;
                else
                { // fusion
                    l->tab[x][y] = zone1;
                    Remplacer(l,valzone,zone1);
                    nbzones--;
                    break;
                }
            }        
        }
    }
}

int main()
{
    Laby l;
    srand((unsigned int)time(NULL));
    printf("taille ? Impaire et au moins 3: ");
    scanf("%d",&(l.taille));
    if (l.taille<3 || l.taille%2==0)
        return -1;  // relis la question.
    Preparer(&l);
    Generer(&l);
    Afficher(&l);
    Liberer(&l);
    return 0;
}





Commentaires

	Voici un petit programme pour générer des labyrinthes carrés. (ils pourraient être rectangles, mais ici, je les définis carrés.

	La taille du coté doit être impaire et au moins 3.
	En effet, l'idée est de partir de ce genre de cas :

	*****
	*.*.*
	*****
	*.*.*
	*****

	ou :

	*******
	*.*.*.*
	*******
	*.*.*.*
	*******
	*.*.*.*
	*******

	etc...

	Comme vous voyez, je pars d'un gruyère régulier : les . sont les trous, les * sont les murs.

	La fonction préparer alloue et initialise ce que je viens de dessiner ci dessus en fonction de la taille du coté rentrée.

	En mémoire, je garde un tableau ou les 0 seront les murs, et les nombres >0 seront du vide.
	C'est seulement lors de l'affichage que je mettrai les * (pour 0) et . (pour du vide), comme on le voit dans la fonction Afficher.

	Le labyrinthe préparé contient un nombre de zones non connexes. Par exemple, pour le laby de coté 5, j'ai 4 zones de départ.
	Sur le laby de coté 7, j'en ai 9.

	Sur un laby de coté n, j'en ai ((taille-1)/2)^2 : formule que l'on voit au début pour nbzones.

	Chaque zone isolée de départ a un numéro : 1,2,3,.....

	L'idée va être simple : on va casser des murs pour fusionner des zones, jusqu'à ce qu'il n'en reste qu'une. Alors le labyrinthe sera connexe.

	Voius vouyez dans la fonction Generer que tant que le nombre de zones ne vaut pas 0, alors je fais la chose suivante :

	Je choisis une case au hasard (rand), mais pas sur les bords : je ne casse jamais les bords.

	Si la case choisie est un mur, et si le casser permet de faire joindre 2 zones distinctes, on le fait. On fusionne.
	
	Pour fusionner, c'est très simple : on a donc deux valeurs de zones à fusionner, par exemple la 1 et la 4.

	On remplace donc le mur à casser (un 0 donc) par 1.
	Puis ensuite, avec un double for, on remplace tous les 4 par des 1 ... Et on fait nbzone--

	Voila, une fois tout cela terminé, le labyrinthe est connexe.
	

Laissez un commentaire / post a comment