A* "au plus proche"?

[Argorate]

Bonjour,

je cherche une variante de l'algo de pathfinding A*, qui consisterait à rendre le chemin qui se rapproche le plus de la cible, lorsque la cible est inatteignable.

Une idée de comment modifier l'algo?

[niahoo]

Ben c'est le même je dirais. Quand l'algo se termine sur un échec tu prends le point le plus proche dans la closed list.

[Argorate]

Pas forcement. Si le chemin le plus court est la ligne droite mais qui est bloqué une case avant l'objectif par exemple. L'algo lui, va continuer a essayer d'autres combinaisons (par exemple faire un grand détour) et échoué quand même, mais tout ça pour dire que la dernière tentative de l'algo n'est pas forcement la plus courte en cas de "non chemin à l'objectif". Tu vois?

[Ter Rowan]

je maitrise pas l algo cependant ta réponse me donne une idée

normalement tu dois connaitre toutes les cases dans l'ordre fourni par A*

a partir de la, tu vérifies chacune des cases et tu choisis la meilleure d'après toi ?

[Xenos]

Et stocker le "meilleur chemin trouvé même s'il va pas jusqu'au bout" puis stopper A* quand la longueur du chemin en court de calcul devient trop grande?

Pour ce qui est du "meilleur chemin", à toi de voir si tu te bases sur le chemin qui amène au plus près de la cible, ou si tu préfères pondérer entre distance à la cible et nombre de directions possibles (aka, choisir le chemin qui va au plus près de la cible pourrait fourvoyer l'unité dans un corridor étroit dont elle sera de toute façon obligée de ressortir si elle veut aller vraiment sur la cible).

par exemple là:



Si je veux aller entre les maisons (vert) est-ce qu'il vaut mieux aller au fond de l'impasse qui est le point le plus proche trouvé au fil de A* (rouge) ou aller à l'entrée de l'impasse d'où partent plusieurs chemins qui vont assez près de la destination réelle (bleu)?

[Thêta Tau Tau]

Si tu sais que la cible est inatteignable.
Tu cherche la case atteignable la plus proche de la cible (l'algo dépendra du cas).
Tu fait ton A* entre la case de départ et cette case.

Si tu sais pas si la cible est atteignable ou non, t'as pas d'autre solution que laisser l'A* chercher des chemins tordus pour le savoir. Et après même chose, tu cherche la case la plus proche (et tu utilise l'A* déjà calculé pour le trajet).

[niahoo]

Pas forcement. Si le chemin le plus court est la ligne droite mais qui est bloqué une case avant l'objectif par exemple. L'algo lui, va continuer a essayer d'autres combinaisons (par exemple faire un grand détour) et échoué quand même, mais tout ça pour dire que la dernière tentative de l'algo n'est pas forcement la plus courte en cas de "non chemin à l'objectif". Tu vois?

Il me semble que ta case la plus proche aura quand même le meilleur score, car celui-ci est calculé à vol d'oiseau. Je ne suis pas sur. Mais pour chaque case de la closed list tu as plusieurs valeurs et il doit y en avoir une qui correspond à ce que je veux dire.

---

Voilà tu peux voir sur l'image ci dessous que les deux cases les plus proches de la case d'arrivée (rouge) ont leur chiffre en bas à droite de la case égal à 20. C'est le chiffre minimum sur tout le plateau.

---

Et stocker le "meilleur chemin trouvé même s'il va pas jusqu'au bout" puis stopper A* quand la longueur du chemin en court de calcul devient trop grande?

Effectivement, limiter la zone de calcul peut être intéressant. C'est parfois le rôle du brouillard de guerre.

Pour ce qui est du "meilleur chemin", à toi de voir si tu te bases sur le chemin qui amène au plus près de la cible, ou si tu préfères pondérer entre distance à la cible et nombre de directions possibles (aka, choisir le chemin qui va au plus près de la cible pourrait fourvoyer l'unité dans un corridor étroit dont elle sera de toute façon obligée de ressortir si elle veut aller vraiment sur la cible).

Là je suppose que c'est selon le gameplay. Si c'est un joueur qui clique, (et mettons qu'un chemin possible existe, inconnu du joueur (à cause du brouillard ou autre), alors il cliquera sur les zones non connues alentour pour trouver ce chemin. Si c'est le jeu qui gère tout alors on retrouve ce choix de laisser le personnage bloqué dans le corridor, ou bien imiter une action humaine en effectuant des cercles autour des murs bloquant la zone pour trouver un moyen d'avancer.

[Argorate]

Le truc c'est, reprend ton exemple niahoo, mais maintenant on rend la case directement à droite de la case rouge (objectif) atteignable (mais la case rouge elle même ne l'ai tjs pas), alors la "bonne" solution c'est d'aller à cette case qui aura pourtant un poids plus fort que celle à deux cases à gauche que l'objectif.

Si on arrête l'algo quand la valeur devient trop grosse par rapport au meilleur chemin trouvé jusque là, on peux donc passé à coté de la solution.

Pour ce qui est du choix, effectivement, je m'en fiche que ça fasse passer par l'Enfer, je veux que ça aille au plus proche, car c'est le choix du joueur^^


PS: tu as un lien pour ton simulateur là?

[niahoo]

Le truc c'est, reprend ton exemple niahoo, mais maintenant on rend la case directement à droite de la case rouge (objectif) atteignable (mais la case rouge elle même ne l'ai tjs pas), alors la "bonne" solution c'est d'aller à cette case qui aura pourtant un poids plus fort que celle à deux cases à gauche que l'objectif.

Ben non, sa valeur en bas à droite de la case sera de 10 (1 case de distance). C'est cette valeur là qui t'intéresse.

Si on arrête l'algo quand la valeur devient trop grosse par rapport au meilleur chemin trouvé jusque là, on peux donc passé à coté de la solution.

Son poids total sera de 134. Comme le disait Xenos, tu peux limiter cette valeur là. Mais si tu le fais effectivement ton algo ne trouvera pas la case. Hein, c'est normal ... Si tu veux aller à NewYork à pied mais que tu ne veux pas prendre de bateau ben j'ai pas de solution.

Pour ce qui est du choix, effectivement, je m'en fiche que ça fasse passer par l'Enfer, je veux que ça aille au plus proche, car c'est le choix du joueur^^


PS: tu as un lien pour ton simulateur là?

A* Pathfinding for Beginners