Recherche chemin labyrinthe en C
ameni.enis
Messages postés
22
Date d'inscription
Statut
Membre
Dernière intervention
-
parcours Messages postés 15 Statut Membre -
parcours Messages postés 15 Statut Membre -
Bonjour,
Svp si qqun peut m'aider à résoudre ce problème
j'ai un labyrinthe défini à partir d'une matrice avec 1 pour les murs et 0 sinon
je veux trouver un chemin entre deux points
comment je procéde pour le programmer en C
Merci d'avance
Svp si qqun peut m'aider à résoudre ce problème
j'ai un labyrinthe défini à partir d'une matrice avec 1 pour les murs et 0 sinon
je veux trouver un chemin entre deux points
comment je procéde pour le programmer en C
Merci d'avance
Configuration: Linux Firefox 3.0.6
3 réponses
-
-
En fait je pense qu'une pile (ou deux) serait plus adapté, et si tu ne connais pas les piles, c'est le moment de t'y mettre ;)
Tu pars de ton point de départ, tu places les cases adjacentes (celles à 0) dans la pile puis tu vides la pile en faisant la même recherche sur les cases que tu viens de dépiler (en s'assurant de ne pas tourner en rond) jusqu'à ce que tu tombes sur ta case d'arrivée...
Il te faudra cependant pouvoir "remonter" le chemin parcouru (associe chaque case empilée à sa case adjacente "père") et alors tu auras un chemin pour aller de ta case de départ à ta case d'arrivée, et si c'est bien fait normalement cette méthode doit te donner le plus court chemin...-
PS. c'est un peu le même algorithme que celui que j'avais décrit en détail ici
-
-
-
De toute façon l'algorithme de Dijkstra n'est pas fait pour ce genre de problème, à moins que tu ne veuilles connaitre tous les chemins de tous les possibilités (départ-arrivée)
Ce que tu essayes de faire demande des connaissances un peu plus poussées, et c'était l'occasion de voir le fonctionnement des piles...
Pour une autre solution j'espère que tu comprends au moins la récursivité, parce que sinon il va falloir qu'on te l'explique...
La solution que je proposais était optimale (on pouvait pas trouver de chemin plus court) mais si tu veux juste trouver un chemin quelconque du moment qu'il rejoint l'arrivée, alors tu peux décider de suivre l'algorithme suivant :
Tu pars d'une case (la première fois c'est ta case d'arrivée)
Si c'est ta case d'arrivée t'as gagné
Si c'est un mur t'as perdu
Sinon tu essaye avec la case du haut (qui essayera elle même en haut/gauche/bas/droite)
Sinon tu essaye avec la case de gauche (qui essayera elle même en haut/gauche/bas/droite)
Sinon tu essaye avec la case du bas (qui essayera elle même en haut/gauche/bas/droite)
Sinon tu essaye avec la case de droite (qui essayera elle même en haut/gauche/bas/droite)
Sinon ta case d'arrivée ne peut pas être atteinte
(en fait l'ordre haut/gauche/bas/droite importe peu)
C'est l'algo le plus simple que je connaisse pour ton problème (pas le plus efficace) et en plus quand la récursivité se terminera avec tous tes cas positifs tu pourras faire l'affichage (en ordre inverse) de tes cases intermédiaires -
-
-
Tu peux faire un chemin aléatoire.
Tu met les murs à -1 plutôt que 1.
Ensuite, quand tu es dans une case, tu incrémente sa valeur de 1. Tu as alors 4 directions possible au plus (haut bas gauche droite), parmis ces 4 cases possibles, supposons qu'il y ait 3 zéros (des cases encore non visités) et 1 case à 1 (déjà visité) tu prends alors le groupe de plus petite valeur (les 0) et tu en choisi une au hasard.
Tu peux repasser plusieurs fois au même endroit, mais il faut incrémenté alors à chaque fois la case.
En retenant chaque mouvement, tu pourra alors reconstitué le chemin.
