Discussion :

[Ragoudcep]

Bonsoir,

Je m’intéresse à l’algorithme A star pour faire du pathfinding, et il y a un détail qui me chagrine.

Je comprend que l'on va passer de nœud en nœud et scanner tous leurs voisins pour calculer leurs qualités.
Je comprend aussi que l'on se positionnera toujours sur les voisins du nœud ayant la meilleurs qualité.
Je comprend AUSSI que l'on ajoute les nœuds dans la closelist s'ils sont prometteurs, et dans l'openlist si on les a déjà scanné et qu'on connait leur qualité.

Mais je ne comprend PAS que l'on recalcule leur qualité s'il l'on retombe dessus !


Si e cite la phrase du tuto trouvé sur développez :

• On regarde tous ses noeuds voisins
• si un nœud voisin est déjà dans la liste ouverte, on met à jour la liste ouverte si le noeud dans la liste ouverte a une moins bonne qualité (et on n'oublie pas de mettre à jour son parent)

Du coup je me dit que j'ai certainement mal compris l'algorithme... La qualité étant "la somme des distance du départ vers le point et du point vers l'arrivé", je ne vois pas comment celle ci pourrait changer

Pourquoi faudrait-il la recalculer ?

http://khayyam.developpez.com/articles/algo/astar/

[pseudocode]

Pourquoi faudrait-il la recalculer ?

Parce que le noeud courant sera un meilleur chemin vers l'arrivée si on se situe sur le noeud voisin.

Si on a estimé à un moment que le noeud voisin (v) était à une distance de 15 de l'arrivée.
et si on estime que le noeud courant (u) est à une distance de 8 de l'arrivée.
alors, on peut ré-estimer que le noeud voisin (v) est maintenant à une distance de 9 (8+1) de l'arrivée.