Discussion :

[genova]

Bonsoir,

j'ai un labyrinthe a taille variable (rectangle, ovale, etc ...) avec un point de depart 1 et un point (ou plusieurs) point d'arrive 2. Le but est de se rendre le plus rapidement possible au point 2 (sachant qu'il y a des murs).

Voici un exemple de MAP :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
*****2****
* *   ****
*   **** *
* *** *  *
*  *     2
*  ** *  *
*     * **
***  **  *
1     ****
**********

Avez vous une idee d'algorithme pour parvenir a ce resultat (le language utilise est le C), sacha nt que je ne suis pas super doue en algorithme.

Je vous remercie bonne soiree.

[Laurent Gomila]

Salut

Essaye une petite recherche sur A* (A-star). Tu trouveras des posts et de la doc en abondance.

[Mac LAK]

Ou implémenter l'algo dit "de la main droite"... Ce n'est pas le plus rapide, mais tu SAIS que tu vas trouver une sortie dans ce type de labyrinthe. En faisant plusieurs tentatives, tu vas même pouvoir trouver toutes les sorties...

Principe : dans ce type de labyrinthe, à l'entrée, poser la main droite sur le mur à droite. Avancer sans JAMAIS lâcher le mur. On sort du labyrinthe à coup sûr.

Comment faire :
- Définir une "direction" de visée (N, S, E, O), et la position du "joueur".
- Vérifier s'il y a un mur à droite : oui, tenter d'avancer. Non, tourner de 90° vers la droite.
- Vérifier s'il y a un mur devant : oui, tourner vers la gauche de 90°. Non, avancer d'une case.

Pour trouver le plus court chemin, il te suffit alors de vérifier si tu es passé deux fois par un endroit ou pas : si oui, tu peux "couper" une branche de recherche (=c'était un cul-de-sac), et trouver peut-être pas le trajet optimal, mais un trajet proche de l'optimal en tout cas.

[genova]

Merci pour vos reponses, effectivement je viens de lire un article interessant sur l'algo A*, qui est pas super facile a comprendre mais qui semble le plus optimal.

Mac LAK >> Bonne idee, cet algo est simple mais super efficace en terme de finalite. Le seule probleme est que parfois la sortie est juste devant mais cet algo fera tout le tour de la piece avant dy arriver.

[Charlemagne]

Un bon algorithme (peut-être le meilleur) consiste à simuler la diffusion d'un liquide.

Le quide progresse d'une case à chaque fois, dans toutes les directions. On simule le temps de diffusion en incrémentant une variable.
J'ai commencé l'algorithme de ton exemple.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
*****2**** 
* *   **** 
*   **** * 
* *** *  * 
*  *     2 
*98**9*  * 
*87678* ** 
***56**  * 
123456**** 
**********

Quand 2 difusions du liquide se rencontre on choisit la plus rapide

[genova]

Un bon algorithme (peut-être le meilleur) consiste à simuler la diffusion d'un liquide.

Le quide progresse d'une case à chaque fois, dans toutes les directions. On simule le temps de diffusion en incrémentant une variable.
J'ai commencé l'algorithme de ton exemple.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
*****2**** 
* *   **** 
*   **** * 
* *** *  * 
*  *     2 
*98**9*  * 
*87678* ** 
***56**  * 
123456**** 
**********

Quand 2 difusions du liquide se rencontre on choisit la plus rapide

Exelente idee en effet, ca me parait bien plus simple que le A-star je vais me pencher dessus

[mathieu_t]

Salut !
Une méthode très utilisée pour calculer le plus court chemin (en traitement d'images) a aussi des applications très pratiques pour le genre de programme que tu fais:
Voici le site du maître en la matière, c'est lui qui a en quelque sorte inventé la méthode et c'est aujourd'hui très très utilisé :
http://math.berkeley.edu/~sethian/Mo...erobotics.html

C'est comme son nom l'indique très rapide et ça marche à tous les coups !

A+

[Mac LAK]

Mac LAK >> Bonne idee, cet algo est simple mais super efficace en terme de finalite. Le seule probleme est que parfois la sortie est juste devant mais cet algo fera tout le tour de la piece avant dy arriver.

Tu as raison, c'est pour ça que (dans ton cas du moins) il faut, après être sorti, "réentrer" dans le labyrinthe jusqu'à revenir à l'entrée initiale... En fonction du sens de parcours, tu peux trouver un chemin "plus court".

En d'autres termes, essaie l'algo "main droite", puis "main gauche" et vérifie lequel des deux est le plus court... ;-)

[Charlemagne]

Une méthode très utilisée pour calculer le plus court chemin (en traitement d'images) a aussi des applications très pratiques pour le genre de programme que tu fais:
Voici le site du maître en la matière, c'est lui qui a en quelque sorte inventé la méthode et c'est aujourd'hui très très utilisé :
http://math.berkeley.edu/~sethian/Movies/Movierobotics.html

C'est le même principe que mon liquide, ou onde sonore.
Il y une notion de vitesse de propagation, ça c'est tout simple.
Par contre, c'est plutôt marrant d'aller dans un labyrinth avec une échelle, ou un piano à queue!
L'avantage du principe, c'est qu'on trouve toutes les sorties (si y'en a plusieurs), et l'optimum à coup sûr.

Je me demande même si y'aurait pas moyen de trouver le meilleur chemin quasi instantanément entre 2 points quelconques A et B du labyrinth, après avoir fait le précalcul de la propagation de l'onde. A priori, dans le cas général, non. Mais ça serait une aide précieuse pour pas se perdre.

Je crois que la "main droite" est l'algorithme utilisé par Windows pour son économiseur d'écran qui fait mal à la tête. Il est simple, mais il passe et repasse dans les mêmes couloirs. De plus si la sortie est quelpart au centre du labyrinth (genre le jeux du labyrinth avec une bille), y'a aucune certitude de la trouver.

[Charlemagne]

Erratum

Il est simple, mais il passe et repasse dans les mêmes couloirs

J'avais pas vu, que tu coupes les branches

[Mac LAK]

Je crois que la "main droite" est l'algorithme utilisé par Windows pour son économiseur d'écran qui fait mal à la tête. Il est simple, mais il passe et repasse dans les mêmes couloirs. De plus si la sortie est quelpart au centre du labyrinth (genre le jeux du labyrinth avec une bille), y'a aucune certitude de la trouver.

La précondition pour que cet algo fonctionne, c'est que l'entrée et la sortie soient sur un "même mur", c'est à dire que le labyrinthe ne soit pas composé de deux (ou plus) labyrinthes "enchevêtrés". Typiquement, si tu dois sortir par un "îlot" isolé au centre du labyrinthe, il ne fonctionne pas... Il y a une variante basée sur le principe du fil d'Ariane, mais c'est infect à implémenter : ça ressemble à un algo FloodFill => dans ce cas, autant prendre la résolution façon "liquide" !

J'avais pas vu, que tu coupes les branches

Oui, sinon, c'est vraiment pas optimisé...
Le seul "inconvénient", c'est que si l'algo lui-même est extrêmement simple, l'algo de coupe des branches est un peu plus chaud car il requiert de "mémoriser" le chemin, et de calculer des 4-arbres. Alors qu'en version standard, l'algo ne requiert pas de mémoire du tout...

[Charlemagne]

Je comprends pas ton histoire des "4 arbres".

Que l'algo de base ne demande aucune mémoire, c'est plutôt un inconvénient dans le fond, parce que on marche les yeux bandés, et qu'il n'y a aucune vision globale.

Mais, pour couper les branches, ça devrait suffire de faire comme Hansel et Gretel, pour savoir si on est pas déjà passé par là. Les fourmis font ça aussi avec leurs phéromones, et je crois que des réseaux sont basés sur ce principe. Dans ce cas il n'y aurait besoin que d'une matrice de bool.

[Mac LAK]

Je comprends pas ton histoire des "4 arbres".

4-arbre parcequ'il y a 4 points cardinaux, tout simplement. J'aurais dû préciser.

Que l'algo de base ne demande aucune mémoire, c'est plutôt un inconvénient dans le fond, parce que on marche les yeux bandés, et qu'il n'y a aucune vision globale.

Vrai. Mais intéressant pour programmer un petit robot, par contre... ;-)

Dans ce cas il n'y aurait besoin que d'une matrice de bool.

Vrai aussi, sauf que ta matrice ne détermine pas le sens de parcours et consomme beaucoup de mémoire. De plus, ça requiert de connaître à l'avance la taille du labyrinthe... Les 4-arbres possèdent, sur chaque noeud, les "coordonnées" (par définition, l'entrée est en (0,0)), et on développe un des fils (N, S, E ou O) en fonction de la direction prise. Si l'on revient à un noeud déjà existant, on marque la branche comme "cul-de-sac" et on coupe. Les coordonnées se calculent de manière incrémentale, en fonction du déplacement (+1 ou -1 sur une seule coordonnée).

Est-ce plus clair ?

[Charlemagne]

"beaucoup de mémoire", c'est relatif et ça dépend du problème.

Maintenant d'accord:
Les 2 algorithmes ont en fait des cahiers des charges différents (je caricature):
-La propagation d'un liquide: chercher l'optimum quand on a la carte du labyrinth
-La main droite/gauche, Ariane, Hansel&Gretel, Fourmis: faire au mieux quand on a pas la carte et que le labyrinth est potentiellement immense

[Mac LAK]

"beaucoup de mémoire", c'est relatif et ça dépend du problème.

Disons que ça a son importance dans un système robotique embarqué... Et aucune pour la "beauté de la chose"... ;-)
Cependant, le coup de la matrice de booléens me dérange pour le côté "primaire" : tu n'as pas le sens de parcours, tu peux donc avoir du mal de couper certaines branches.

(je caricature):

Pas tant que ça, justement...

le labyrinth est potentiellement immense

Que crois-tu que je fais, sur des jeux comme Morrowind et tous ces jeux de rôle/aventure, pour réussir à tout explorer dans un nouveau donjon un peu trop complexe ? ;-)

[Charlemagne]

Je réfléchis, je suis pas un pro des labyrinths, ni de Doom-like, mais ça pourrait marcher à priori la combinaison Hansel&Gretel + Main droite avec une matrice de booleens.

Pour couper les branches, on suivrait Hansel&Gretel à la trace et lorsque l'on arriverait à un carrefour avec plusieurs pistes jonchées de cailloux, on suivrait le chemin de cailloux le plus à gauche.

J'avais dis matrice de booleens, mais on peut envisager une pile de coordonnées des carrefours avec la dernière orientation prise. Bref, c'est pas le probleme...
Mais j'aime bien l'image des cailloux...

[Mac LAK]

mais on peut envisager une pile de coordonnées des carrefours avec la dernière orientation prise.

Et d'après toi, ça va se coder comment, en mémoire, si ce n'est avec l'équivalent d'un 4-arbre ? ;-)

[Charlemagne]

C'est pas le problème la manière de coder, du moment que ça revient au même, on s'intéresse à l'algo non? Maintenant si le robot a pas plus de cases qu'un Shadok, alors d'accord il faut aviser, mais c'est qu'un problème d'implémentation. Je veux pas me focaliser la dessus.

Ma méthode pour couper les branches me paraît valable, et toute simple. non?

Il est où dark_genova? C'est qu'on cogite pour lui là...

[Charlemagne]

Le problème est peut-être plus compliqué si y'a des boucles dans le labyrinth, mais j'ai plus envie d'y réfléchir.

[Mac LAK]

Le problème est peut-être plus compliqué si y'a des boucles dans le labyrinth, mais j'ai plus envie d'y réfléchir.

Ben oui, c'est pour ça que je te parlais du sens du parcours, et de l'implémentation en arbre... Enfin, on verra bien.
Bon, on attends le p'tit père dark_genova pour poursuivre ?