Discussion :

[bleast8]

Bonjour,

j'utilise l'algorithme A-star pour trouver des chemins sur une map 2D case par case comportant des obstacles (un grand nombre de murs semblables à un labyrinthe).
Dans tous les cas, un chemin est trouvé d'un point A à un point B, en passant par des cases connues de l'unité se déplaçant.

rappel: pour choisir un pas dans la construction de l'itinéraire, A-star favorise la prochaine case par son coût (distance depart -> point + point -> arrivée).

Dans certains cas, A-star part dans une direction qui semble au premier abord avantageuse qui finalement ne permet pas d'atteindre l'arrivée. L'algorithme peut ensuite revenir sur ses pas et finir par trouver le bon chemin qui ne partait pas tout de suite vers l'arrivée.

Problème: Il arrive qu'un chemin commence en se dirigeant au plus pres de l'arrivée et y finit par y aboutir après un long parcours. Cependant il peut exister un chemin beaucoup plus court qui necessitait cependant de partir dans le sens opposé à l'arrivée (dans un premier temps).

A-star ne détecte pas cette solution (sauf erreur de ma part ..).

Comment y remédier ? sans avoir à étudier tous les chemins possibles de la carte (algo de dijkstra) ?

Une aide ou une idée seraient les bienvenues ...
Merci

[FrancisSourd]

Dès lors que l'estimation de la distance entre ton point courant et le point d'arrivée est une estimation minorante (borne inférieure) de la distance réelle, A* trouve forcément le plus court chemin.

Dans Dijkstra justement, on estime cette distance "point courant - point d'arrivée" par 0, qui est assurément une borne inférieure de la distance réelle.

[bleast8]

Un petit exemple du problème :



Sachant que l'unité ne peut se déplacer en diagonales, on ne favorise donc pas ces dernières.

Dans ce cas, a-star trouvera un chemin par le haut et ce chemin sera plus long que celui du bas.

départ (vert) -> 5 -> 7 -> 9 -> 9 ->11 -> 9 -> 7 -> 7 -> 7 -> 7 -> Arrivée (rouge)

au lieu de :

départ -> 7 -> 7 -> 7 -> 7 -> 5 -> 5 ->Arrivée

[FrancisSourd]

Je ne comprends pas bien ce que sont les chiffres dans les cases. Est-ce une évaluation de la distance à la case rouge?

En tout cas, dans l'implantation de A* (version exacte), tu considères comme dans Dijkstra plusieurs chemins possibles. A partir du moment où le chemin qui part vers le haut devient trop long, A* favorisera la construction du chemin vers le bas.

[bleast8]

les valeurs des cases sont les distances (vert->case + case->arrivée)

Je ne vois pas à quel moment A-star évalue 2 chemins différents s'ils sont tous deux bons mais de longueur différente.

la construction par Astar se fait case par case, avec éventuellement des simplifications si l'on finit par choisir une case qui était dispo bien avant. Mais au final un seul chemin est retenu, je me trompe ? Pour choisir entre 2 chemins corrects mais de longueur différente, il faut les avoir calculé tous les 2 et ensuite comparer leur taille. A-star fait çà ?

[FrancisSourd]

les valeurs des cases sont les distances (vert->case + case->arrivée)

Attention également, la distance "vert->case" correspond à une distance réelle du chemin partiel déjà construit (dans l'arborescence). Cette distance change donc au cours de l'exécution de l'algorithme. Je ne peux donc pas de faire une exécution détaillée de A* sur ton exemple.

Néanmoins, voici une idée du fonctionnement: En partant du noeud vert, A* va vers le noeud de plus petite évaluation (ie A* crée l'arc vert-5). Puis il pourra trouver l'arc 5-7. Mais comme il reste des voisins du noeud vert avec une évaluation 7, A* va ensuite considérer l'arc vert-7 (avec le 7 en dessous du vert) plutôt que d'aller vers une évaluation "9". Puis il considérera les évaluations 7-7 possibles et trouvera ainsi le chemin du bas.

A* construit une arborescence depuis le noeud vert plutôt qu'un chemin unique (et évalue les chemins partiels en cours de construction).

[bleast8]

Merci de ta réponse. Elle confirme ce que l'on a finit par déduire pour obtenir le plus court chemin. Nous n'avions pas inclu la notion d'arborescence et c'est ce qui faisait défaut à notre approche. On va essayer d'implémenter çà!
Merci encore