probleme de connexité dans un labyrinthe

Bonsoir,

j'ai creer un petit programme qui est censé généré aléatoirement un labyrinthe avec au moins un chemin possible, mais j'ai un probleme à ce niveau là, car cela ne marche pas tous le temps.

J'ai appliqué l'algorithme décrit sur ce pdf :
http://www.ai.univ-paris8.fr/~amsi/S...ts/cours07.pdf

Voici mon code :
http://membres.lycos.fr/bdzarena/laby_or.c

Merci pour votre eclaircissement

Description du problème svp au lieu de simplement "ca marche pas." :king:

mon programme génére bien un labyrinthe mais qui n'est pas totalement connexe il reste des murs à casser, alors que ça ne devrait pas être le cas.

Relis ton algorithme, il est mal implémenté ;)

De plus, il serait bien de tester le retour des malloc afin de voir si la mémoire à bien été allouée.

Il faut aussi penser à inclure l'entête time.h pour que le rand fonctionne correctement.

Ensuite, si tu ne vois pas d'où viens ton erreur, je te conseilles fortement à indenter proprement ton code et à suivre une certaine "convention" dans ta manière de coder, tu y verras plus clair et découvrira par toi-même les endroits où tu as fais les erreurs d'implémentation.

++

Pour l'implementation de l'algorithme je pense voir à quoi tu fais reference, comme quoi normalement je dois propager une valeur sur toutes les cases autour d'un point de depart ayant une valeur Z, sur papier j'ai testé l'algorithme et j'ai vu qu'il n'y avait jamais cette valeur Z autour du point de depart, c'est pour ça que j'ai allégé le code en propagant que sur une case.

J'avais quand même fait la version identique à l'algo mais même probleme :

http://membres.lycos.fr/bdzarena/laby.c

j'en ai profité pour include le time.h que j'avais completement oublié, et de tester les retours des malloc.

Un algorithme, ça ne se négocie pas !

Ensuite, ton indentation est horrible et me donne même pas envie de regarder plus profondément ton code...

De plus, tu mets des return dans une fonction ne renvoyant normalement rien (void).

Mets déjà ton code au carré et tu y verras plus clair.

je ne comprend pas, mon code est indenté automatiquement avec emacs, en quoi n'est elle pas bonne?

Je trouve ce genre de code plutôt illisible...

Code:

---

1 2 3 4 5 6 7 8 9 10

int **allouer_tab(int n,int m) {   int **tab; int i; tab=(int**)malloc((2*m+1)*sizeof(int*)); if(tab==NULL) fprintf(stderr,"erreur d'allocation mémoire"); for(i=0;i<(2*m+1);i++) tab[i]=(int*)malloc((2*n+1)*sizeof(int)); if(tab[i]==NULL) fprintf(stderr,"erreur d'allocation mémoire"); return tab; }

---

Plus lisible :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

int **allouer_tab(int n, int m) {   int **tab= NULL; int i; tab= malloc((2*m+1) * sizeof(int*)); if(tab==NULL) { fprintf(stderr,"erreur d'allocation mémoire"); } for(i= 0; i < (2*m + 1); i++) { tab[i]= malloc((2*n + 1) * sizeof(int)); if(tab[i] == NULL) { fprintf(stderr,"erreur d'allocation mémoire"); } }   return tab; }

---

Mais bon, après c'est question de préférence... (j'ai corrigé quelques fautes au passage...)

Tu remarqueras que le fait de n'avoir pas mis d'accolade t'as joué un préjudice car lorsque tu fais (dans ton cas) :

Code:

---

1 2 3 4

if(tab[i] == NULL) { fprintf(stderr,"erreur d'allocation mémoire"); }

---

tu n'étais plus dans la boucle for, mais après, autrement dit, ce test est incorrect.

Puis, c'est bien beau de dire qu'il y erreur d'allocation mémoire, mais encore faut-il désallouer ce qui a déjà pu l'être, voire quitter le programme proprement et ne pas le laisser continuer comme tu le fais.

++

bon ben j'ai updaté le code, corrigé quelques trucs, ça à l'air mieux mais ça ne me fais toujours pas de chemin connexe dans tous les cas.

*désespéré*

code : http://membres.lycos.fr/bdzarena/laby.c

merci

Ton code est effectivement horrible.
Il y a l'indentation qui est importante certes, mais aussi l'aération (ligne sautée comme pour une dissertation), les commentaires, et surtout les conventions homogènes !!

Parfois tu sépares les mots de tes variables avec des majuscules, parfois avec underscore parfois tu colles tout !

Il n'y a aucun commentaire (enfin si, mais presque inutile)... comment espères tu retrouver des erreurs avec ça ?!

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

/* Fonction qui alloue la matrice de taille (2m+1)*(2n+1) */   int **allouer_tab(int n,int m) {   int **tab=NULL; int i; // blahblah for(i=0;i<(2*m+1);i++) { tab[i]=(int*)malloc((2*n+1) * sizeof(int)); if(tab[i]==NULL) { fprintf(stderr,"erreur d'allocation m�moire"); exit(EXIT_FAILURE); } } return tab; }   /* Fonction qui remplie la matrice */   void remplir_tab(int **tab,int n,int m) { // ICI   int d,x,y,i,j,k=0,NbCasesAZero=n*m+1; //blahblah

---

Est ce que tu trouves normale que ta fonction remplir_tab soit indentée ? (ligne avec le commentaire ICI)

Regardes le code de Buchs et le tien... tu ne vois pas que l'un est plus obscur que l'autre ?

Le temps que tu crois perdre en passant du temps à écrire un beau code lisible est, en règle général, récupéré à la puissance 10 lorsque tu corriges tes erreurs après coup.

bon j'ai suivi un peu vos conseils et j'ai updaté le code :

http://membres.lycos.fr/bdzarena/laby.c

Merci pour les conseils c'est vrai que c'est plus lisible comme ça j'indenterais toujours mon code comme ça dorénavant (manque les commentaires à rajouter, je sais).

En faite là mon programme marche sur des petits labyrinthes de taille 7/7 mais quand ça devient un peu plus grand, la connexité se perd.

C'est déjà un bon début et en effet, beaucoup plus lisible de la sorte.
Maintenant, pour les commentaires, c'est du même ordre, tu perds 10 minutes à les mettre mais gagne des heures par la suite si tu tiens à faire évoluer ton programme car tu n'a plus besoin de chercher qui fait quoi ;)

Quant à ton code, là ou j'ai des doutes, c'est sur cette partie :

Code:

---

1 2 3 4 5 6

do { x=(rand() % ((2*longueur+1)-2))+ 1; y=(rand() % ((2*largeur+1)-2))+ 1; } while((tab[x][y]!=-1) || (x%2==0 && y%2==0));

---

Surtout dans la condition du while, en effet l'algo préconise :

Citation:

---

L[x][y] = −1 et (x impair ou y impair7) ;

---

Or toi tu as mis || qui veut dire OU...

Ensuite, assures toi quand même que les nombres x et y générés sont bien >0 et inférieur à ton nombre de ligne (ou colonnes) de ton labyrinthe ;)

@++

oui justement à la base j'avais mis un ET et je ne sais pas pourquoi quand je debuggais le programme, les cases ne valant pas -1 n'etaient pas filtrés (ce qu'il ne faut pas) j'ai testé avec un OU et là bizarrement ces cases là sont bien filtrés.

Enfin bon je reviens tout juste de cours, je vais m'y repencher et je vous dirais si j'ai reussi à m'en sortir.

merci des precisions :)

Salut,

c'est peut etre pas important mais......
dans ton code tu as :

Code:

---

while(NbCasesAZero<(n*m)+1)

---

mais dans l'algo il y a :

Code:

---

Tant que NbCasesAZero < N ×M

---

Enfin, je dis ca, je dis rien