Bonjour à tous, je me suis lancé dans un programme de résolution de labyrinthe en vu de l'intégrer dans un projet plus gros (un jeu de plateau si vous voulez tout savoir). Malheureusement, je me retrouve avec des boucles infinies, bref c'est assez embêtant.
J'utilise par ailleurs le principe des fonctions récursives pour parcourir toutes les cases de mon labyrinthe.
les variables xCibles et yCibles sont les coordonnées de la sortie de mon labyrinthe, et mon labyrithe s'appelle map, c'est une matrice à deux dimensions.
int Resolve (int i, int j, char map[HAUTEUR][LARGEUR], int xCible, int yCible)
{
if (map[i][j]!= CASE_VIDE)
{
printf("%c\n", map[i][j]);
return 0;
}
if ((i == xCible && j == yCible) || (Resolve(i + 1, j, map, xCible, yCible)) || (Resolve(i, j - 1, map, xCible, yCible)) || (Resolve(i, j + 1, map, xCible, yCible)) || (Resolve(i - 1, j, map, xCible, yCible)))
{
map[i][j] = CASE_SOLUTION;
return 1;
}
}
pourriez vous m'aider à comprendre ce qui ne va pas dans mon code svp ?
Quelle partie du message tu ne comprends pas. Est-ce possible que je puisse aller de gauche à droite et de droite à gauche sans m'arrêter? Pour le backtracking, je n'ai pas réfléchi à l'implémentation. Tu as 4 directions: gauche, haut, droite, bas. Mais tu viens de l'une d'entre elles. Il te reste 3 choix pour continuer. Si tu arrives dans une impasse, tu recules à la position précédente mais tu ne considères que les choix que tu n'as pas fait. Si tu peux te rendre à la sortie, tu devrais pouvoir trouver le chemin de cette façon. Sinon, tu devras reculer jusqu'avant l'entrée et il n'y a pas de solution pour ce labyrinthe.
Le Tout est souvent plus grand que la somme de ses parties.
Comme je te le disais tes appels récursifs sont inconditionnels … tu ne marques jamais l'endroit où tu es …
L'algo récursif doit être du genre :
si je suis sur un mur … je ne fais rien ;
si je suis sur une case vide de toute marque alors je marque la case courante comme faisant potentiellement partie de la solution ← à ne pas oublier !!!!! je fais les appels récursifs si au moins un finit en trouvant la sortie je ne fais rien sinon je démarque la case et je ne fais rien d'autre
si je suis sur la destination → bingo ! je dis que tout c'est bien passé
si je n'ai plus de choix alors je renvoie «pas bon»
La récursivité évite d'utiliser une pile qui sert normalement dans le backtracking. En fait, la pile est la récursivité avec les appels et leur retour. À chaque niveau, on fait le tour des solutions possibles ... jusqqu'à ce qu'on trouve la solution provenant des appels subséquents (on retourne c'est bon) ou qu'on a épuisé toutes les possibilités (on retourne pas bon) On marque ou démarque comme l'a indiqué White Crow. Les marques qui restent à la fin représente le chemin vers la sortie.
Le Tout est souvent plus grand que la somme de ses parties.
Bah normalement étant donné que l'on t'a aidé gratuitement, tu pourrais mettre également gratuitement ton code à disposition pour les futurs lecteurs …
De plus c'est toujours une bonne idée que de marquer le sujet comme résolu si tu considères qu'il l'est …
Résolution de labyrinthe en C
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.