Votre avis : Recherche du plus court chemin

[mmarc2007]

Bonjour,

Je cherchais à faire un algo pour trouver le plus court chemin entre deux points tout en évitant des obstacles. (obstacles représentés par des segments de droite)

Après quelques recherches, j'ai trouvé Dijkstra et AStar.
J'ai tout de suite éloigné le premier trop complexe pour mon besoin.
J'ai aussi écarté AStar qui scan de façon récursive tous les "nœuds" proche et que j'ai trouvé trop "lourd" étant donné que l'on sait très bien où sont les obstacles.

Donc j'ai mis au point ce petit algo qui travaille avec des segments de droite, ce que je voulais savoir c'est :
1) Ai-je réinventé la roue ? Je pense que oui...
2) S'il vous semble correcte ?

On déclare deux tableaux de segment T_temporaire et T_final qui peuvent contenir des segments de droite.

Donc soit A le point de départ et B l'arrivée.
On place [AB] dans segment T_temporaire

tant que le bon chemin n'est pas trouvé et que segment T_temporaire n'est pas vide:

Pour chacun des segments de segment T_temporaire que l'on nome [AB]
--> Si [AB] traverse un segment d'obstacle :
-----> on nome [CD] l'obstacle le plus proche de A et on place [AC] [AD] [BC] et [BD] dans le segment T_temporaire
--> si non on place [AB] dans T_final

Voila c'est tout simple et ça permet de contourner tous les obstacles. Le premier résultat trouvé ne sera pas forcément le plus court mais celui avec le moins de "segments". Il est toujours possible d'évaluer les chemins en calculant les différentes longueurs de segment.

Merci de me donner votre avis
-----

[Dlzlogic]

Bonjour,
Ce type de problème est assez récurrent.
Je pense qu'il faut bien distinguer la recherche d'un chemin en empruntant des routes, et la recherche d'un chemin en évitant des obstacles. Manifestement c'est le second problème qui vous intéresse.
tel que décrit, effectivement, cela parait assez simple. Imaginez par exemple qu'un obstacle est constitué d'une ligne fermée, c'est à dire une ligne brisée. Etes-vous sûr de trouver le moyen le plus court de contourner l'obstacle?
Contrairement à la recherche de chemin en prenant des routes, je ne connais pas d'algorithme particulier. J'ai eu l'occasion de réfléchir à ce type de problème à propos du parcourt d'animaux.

[polo974]

il faudrait définir une largeur minimale du chemin, sinon, il va passer "entre" 2 segments ayant un point commun...

pour le reste de l'algo, je n'ai pas été plus loin.

[Dlzlogic]

Bonjour,
Cette technique qui consiste à fixez une largeur minimale de chemin, non nulle peut être intéressante, mais elle revient à calculer le bord gauche et le bord droit du chemin.
Le préfère la technique où les obstacles sont des zones à contourner.
Il est assez facile de constater que le trajet direct rencontre un obstacle, un peu plus difficile de trouver le moyen de le contourner. D'autant que on peut estimer que l'objet qui cherche son chemin voit plus loin que le bout de son nez et apercevra l'obstacle avant de se cogner dessus.

Il y a aussi une autre façon d'aborder le problème. A partir du point A, en regardant vers le point B, s'il n'y a pas d'obstacle, tout va bien. S'il y a un obstacle on recherche à droite et à gauche de l'obstacle, la limite la plus proche, c'est à dire celle qui dévie le moins de la direction d'origine.

Si au contraire, le chemin est celui parcouru pas une taupe, étant donné qu'elle n'a aucune visibilité, le caractère aléatoire devra être pris en compte.

En fait, ce problème est un peu plus compliqué qu'il n'y parait, puis qu'il y a plusieurs façons d'envisager les choses. Donc les hypothèses ne sont pas assez précises pour faire un algorithme passe-partout.

[A voir en vidéo sur Futura]

[polo974]

Houlaaaa,
je n'ai pas été aussi loin, je disais juste que l'algo proposé permet de passer par un point final d'un segment, donc de se faufiler entre 2 segments ayant un point commun.

le passe muraille informatique (qui se glisse entre les briques)...

[mmarc2007]

Merci pour les remarques!

Effectivement si deux segment ont des points finaux confondu, l'algo peut passer à travers!

Ce que j'ai fais pour remédier à ça, c'est que lorsque je cherche à éviter un obstacle genre [CD], j’agrandis volontairement le segment de chaque coté. En plus ça laisse une marge de contournement!

J'ai fais un test en java, je mettrai les sources à disposition.

[mmarc2007]

Salut,

Si ça peut intéresser un jour quelqu'un j'ai mis les sources ici :
https://projets.connectme.fr/accueil/index.php?projet=8

Pour donner un exemple avec un labyrinthe :