Voilà, vu qu'il n'y a aucun forum pour la programation en C, je poste mon message ici, je previent que c'est pour les gens bien calés en fin je pense =)
En fait c'est un prog pour mon cousin qui séche un petit peu dessu =) :P
"Salut !
Je code un petit programme pour générer aléatoirement un labyrinthe.
Je procède en deux temps :
-> Je crée une matrice que je remplis avec des "0" (passages) et des "-1" (murs) aléatoirement.
-> Je "creuse" un passage aléatoire dans les murs, d'en haut à gauche à en bas à droite
pour ça, j'utilise une liste doublement chaînée qui contient :
-> le numéro de la case de mon passage creusé
-> les coordonnées de cette case dans la matrice
-> l'adresse mémoire de la précédente et de la suivante
-> le nombre de mouvements qui étaient autorisés à la création
je cherche un moyen d'insérer à la ligne 157 un bout de code qui fasse rebrousser chemin (à cause d'un cul de sac déjà détecté) jusqu'à une case où le nombre de mouvements possibles était d'au moins 2, et de forcer le chemin à ne pas repartir dans le même sens.
Merci d'avance!"
Voilà le code source :
[quote:ace8579b72]
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 15
#define P 45
/*strucure de liste doublement chaînée*/
struct LC
{
int x;
int y;
int num;
struct LC *next;
struct LC *prev;
int nbmvts;
};
typedef struct LC lc;
/*renvoie le nombre de mouvements qui peuvent être effectués depuis la case de coordonnées x, y*/
int nb_mvts(int grid[N][P], int x, int y, int dx[4], int dy[4])
{
int i, n;
n = 0;
for(i = 0 ; i < 4 ; i++)
{
if(x + 2 * dx[i] < P-1 && x + 2 * dx[i] > 0 && y + 2 * dy[i] < N-1 && y + 2 * dy[i] > 0)
if(grid[y + 2 * dy[i]][x + 2 * dx[i]] == 0)
n++;
}
printf("nb mvts (%d,%d) : %d\n",x, y, n-1);
return n;
}
/*affiche la grille*/
void disp(int grid[N][P])
{
int i, j;
printf("\n");
for(i = 0 ; i < N ; i++)
{
for(j = 0 ; j < P ; j++)
{
if(grid[i][j] == -1)
printf(".");
else
printf(" ");
}
printf("\n");
}
}
/*affiche la grille et le chemin creusé*/
void disp_p(int grid[N][P], lc *path, int mx[2], int my[2])
{
int i, j;
lc *cur;
j = 0;
for(cur = path ; cur->next == 0 ; cur = cur->next)
{
/*grid[cur->y][cur->x] = 1;*/
j++;
printf("mvt %d : (%d,%d) -> (%d,%d)\n", j, cur->x, cur->y, cur->next->x, cur->next->y);
}
printf("\n\t");
for(j = 0 ; j < P ; j++)
{
if(j < 10)
printf(" %d", j);
else
printf("%d", j);
}
printf("\n\n");
for(i = 0 ; i < N ; i++)
{
printf("%d\t", i);
for(j = 0 ; j < P ; j++)
{
if((i != my[0] || j != mx[0]) && (i != my[1] || j != my[1]))
{
if(grid[i][j] == -1)
printf("++");
if(grid[i][j] == 0)
printf(" ");
if(grid[i][j] > 0 && grid[i][j] < 10)
printf("0%d", grid[i][j]);
if(grid[i][j] > 9)
printf("%d", grid[i][j]);
}
else
printf("##");
}
printf("\n");
}
}
/*toutes les gestions de variables sont faites dans main*/
int main(int argc, char *argv[])
{
int grid[N][P], i, j, ch, dx[4] = {1,0,-1,0}, dy[4] = {0,-1,0,1}, poss[4]={1,1,1,1}, cpt, k, mx[2], my[2];
lc *path, *last, *el;
srand(time(0));
/*remplir la matrice de 0 (passages) et de -1 (murs)*/
for(i = 0 ; i < N ; i++)
for(j = 0 ; j < P ; j++)
grid[i][j] = (i==0 || j==0 || i==N-1 || j==P-1 || (i%2==0 && j%2==0)) ? -1 : 0;
for(i = 1 ; i < N-1 ; i++)
for(j = 1 ; j < P-1 ; j++)
if((i+j)%2 == 1 && rand()%2 == 0)
grid[i][j] = -1;
disp(grid);
/*initialisation du chemin creusé*/
path = (lc *) malloc(sizeof(lc));
path->num = 1;
path->nbmvts = 2;
path->x = 1;
path->y = 1;
grid[1][1] = 1;
path->next = 0;
last = path;
/*on boucle jusqu'à arriver en bas à droite (et on se débrouille pour y arriver)*/
while(last->x != P-2 || last->y != N-2)
{
el = (lc *) malloc(sizeof(lc));
last->next = el;
el->prev = last;
el->num = last->num + 1;
for(cpt = 0 ; cpt < 4 ; cpt++)
{
/*liste des mouvements possibles : a priori tous le sont*/
poss[cpt] = 1;
}
/*choix aleatoire d'un mouvement :
^
1
<2 0>
3
v
*/
ch = rand()%4;
/*conditions pour quel le mouvement choisi soit valide :
* ne pas sortir de la grille
* ne pas revenir vers le départ quand on est contre un mur (sinon on s'enferme)
* ne pas se croiser
* le nombre de mouvements possibles depuis la nouvelle case n'est pas égal à 0*/
while(last->x + 2 * dx[ch] < 1
||last->x + 2 * dx[ch] > P-2
||last->y + 2 * dy[ch] < 1
||last->y + 2 * dy[ch] > N-2
||( (last->x == 1 || last->x == P-2) && ch == 1)
||( (last->y == 1 || last->y == N-2) && ch == 2)
||grid[ last->y + 2 * dy[ch] ][ last->x + 2 * dx[ch] ] > 0
||nb_mvts(grid, last->x + 2 * dx[ch], last->y + 2 * dy[ch], dx, dy) <= 0)
{
/*ce mouvement n'est pas bon, on l'élimine*/
poss[ch] = 0;
printf("mouvement impossible : %d\n", ch);
/*Si tous les mouvements sont impossibles*/
if(poss[0] == 0 && poss[1] == 0 && poss[2] == 0 && poss[3] == 0)
/*mauvaise idée que j'avais eue avant :*/
/* {
printf("cul de sac : (%d, %d) -> (%d, %d)\n",last->x, last->y, last->prev->x, last->prev->y);
mx[0] = last->x;
my[0] = last->y;
mx[1] = last->prev->x;
my[1] = last->prev->y;
grid[last->y][last->x] = 0;
last = last->prev;
free(el);
el = (lc *) malloc(sizeof(lc));
last->next = el;
el->prev = last;
el->num = last->num + 1;
for(k = 0 ; k < 4 ; k++)
{
poss[k] = 1;
}
}*/
{
/*c'est là que j'ai besoin d'un gros coup de main =) */
}
srand(rand());
/*choisir un nouveau mouvement qui ne soit pas un déjà éliminé*/
while(poss[ch] == 0)
ch = rand()%4;
}
/*la nouvelle "dernière case" du chemin est "el".*/
el->x = last->x + 2 * dx[ch];
el->y = last->y + 2 * dy[ch];
el->nbmvts = nb_mvts(grid, el->x, el->y, dx, dy);
grid[last->y + dy[ch]][last->x + dx[ch]] = 0;
grid[el->y][el->x] = el->num;
last = el;
getchar();
disp_p(grid, path, mx, my);
}
return 0;
}
[/quote:ace8579b72]