chemin le plus court

Bonjour tout le monde,

En fait, je suis en pleine creation d'un labyrinthe, et j'aimerai bien connaitre une technique pour trouver le chemin le plus court.

J'explique un peu comment est crée le labyrinthe :
C'est un tableau de structure de deux dimensions.

voici la structure :

Code:

---

1 2 3

typedef struct{ int d[4]; // une case pour une direction. }ts;

---

chaque case de "d" correspond à un degrée de liberté de la pièce. On met à "0" si le chemin n'est pas possible dans cette direction, sinon "1".

Si mon explication n'est pas très claire, je peux recommencer :o

Merci

Non, ce n'est pas clair.

Va voir du cote du forum Algorithmique, je pense que les gens seront plus aptes à t'aider là-bas.

C'est assez clair, c'est en effet une question d'algorithme.

Je vois une solution pour trouver le chemin le plus court entre deux cases:
Essayer tous les chemins possibles en comptant le nombre de cases et garder celui qui en a le moins.

Il faut représenter ton labyrinthe sous la forme d'un graphe, puis, par exemple, chercher le chemin le plus court entre les deux sommets qui sont tes cases avec un algorithme comme Dijkstra.

Je sais que chez Boost, il existe une fonction qui t'évitera de réécrire tout l'algo: http://www.boost.org/libs/graph/doc/...est_paths.html
A+

Merci de vos réponse. En fait, je fais un projet info pour l'école, et le problème, c'est que l'on a pas fait les graphes.

Mon tableau à deux dimension, est-ce un graphe ? Ou dois-je le convertir en graphe ?
Car dans une case, je peux avoir la direction droite autorisé, et dans la case à côté, la direction gauche interdite.
J'ai fais un petit dessin pour que se soit plus compréhensible.

ou sinon vous pouvez allez voir Mme Ru..o
:P

Citation:

---

Envoyé par fabetvince

Mon tableau à deux dimension, est-ce un graphe ? Ou dois-je le convertir en graphe ?

---

Ce qu'est un graphe est arbitraire. Un tableau peut tout à fait représenter un graphe. La question est après de voir si la gestion et l'utilisation de ton graphe sera facile. Mais de toute façon, ta question est plutôt une question algorithmique et il y a un forum pour ce genre de question.

Résumons:

- Oui ta structure de donnée peut fonctionner bien que ce sera plus difficile je pense
- Non, on ne peut pas t'aider ici, tu n'as pas encore l'algorithme
- Oui, on t'aidera avec le code lorsque tu auras un problème précis.

Jc

Est ce qu'en changeant mon tableau de structure( voir précédemment) de la façon suivante cela serai plus facil pour gérer les déplacement du perso dans le labyrinthe???

Je pense agrandir le tableau, en ne mettant plus 4 cases pour les directions. Chaque case du tableau contiendra une couleur(ex noir=mur, blanc=chemin), j'ai regardé beaucoup de structure pour faire un labyrinthe, et je ne sais pas comment m'y prendre.

Pourriez vous m'aider svp

Comprendre ce qu'est un graphe est très simple. A partir de là, implémenter Dijkstra n'est pas trop compliqué (tant qu'on ne cherche pas à optimiser à fond). Dis-nous quel est ton niveau qu'on sache comment te le présenter.

--
Jedaï

Quand on connait le plan du labyrinthe, on utilise en général cette méthode:
http://math.berkeley.edu/~sethian/Mo...erobotics.html
Ca consiste grosso modo à simuler la propagation d'une onde ou d'un liquide dans le labyrinth. C'est aussi comme ça que des fourmis retrouvent leur chemin dans un labyrinthe, grace aux féromones.
L'auteur a juste corsé le problème en se promenant avec une échelle dans le labyrinth.

Lorsqu'on cherche un plus court chemin en nombre d'arcs (ou de déplacements élémetaires dans le cas du labyrinthe), un parcours en largeur d'abord fait l'affaire: c'est plus simple et plus rapide que Dijkstra!

J'ai également eu à coder lors de mes études un labyrinthe, tu peux aussi faire un calcul du chemin le plus court pour trouver la sortie sans te soucier des obstacle et autre et mettre en place une heuristique (si je me souviens bien) pour trouver ensuite le chemin :

Tu calcules sans cesse le plus court chemin, mais tu enregistre des position antérieure dans le labyrinthe, et en cas de blocage hop tu reviens en arrière et prend une autre route. Ca porte un nom ce procédé mais je m'en rapelle plus back-quelque chose il me semble.

backtracking, mais c'est plus du profondeur que tu fais que du largeur. Dans le parcours en largeur, tu n'as pas vraiment de backtracking à faire. Mais ça ne marche que si les arcs ont le même poids.