Vincentdaniele
commented
4 years ago Bonsoir,
Merci beaucoup pour ces indications très bien expliquées. Je vais continuer à chercher pour régler le problème du retour à (1,1) et je reverrai l'implémentation de l'A*. Je vous suis sincèrement reconnaissant pour votre implication dans mon problème cela va énormément m'aider.
Bonne soirée, Vincent
Le lun. 18 mai 2020 à 22:17, Pierre Vigier notifications@github.com a écrit :
Bonsoir (je me permets de parler en français, j'imagine que ça ne pose pas de souci),
Après, avoir regardé un petit peu le code, j'ai trouvé une source de non-déterminisme dans la classe Astar qui expliquerait que vous obteniez des résultats différents à chaque exécution.
Dans le bout de code ci-dessous, le minimum n'est pas forcément unique. En règle général, ça ne pose pas de problème, ce serait le dernier élément de l'ensemble qui atteint le minimum qui serait sélectionné. Or ici, comme les éléments sont stockés dans un std::set<Node*> l'ordre de parcours des éléments n'est pas déterministe (ils sont ordonnés par leur adresse en mémoire qui n'est elle-même pas déterministe).
La solution la plus simple est d'utiliser une relation d'ordre qui va rendre le minimum unique. Je propose celle-ci :
if (node->getScore() < current->getScore() || (node->getScore() == current->getScore() && (node->coordinates.x < current->coordinates.x || (node->coordinates.x == current->coordinates.x && node->coordinates.y < current->coordinates.y)))) { current = node; }S'il y a égalité pour le score, on compare les coordonnées. Ça m'a l'air de régler le problème de non-déterminisme.
Après, j'ai l'impression qu'il y a un autre problème, lorsque l'arrivée est atteinte (10, 10), et qu'il cherche à revenir au départ, l'A échoue : il sort de la boucle non pas parce que l'arrivée est atteinte mais parce que openSet est vide. Il faudrait dessiner la carte pour vérifier si (10, 10) est bien atteignable depuis (1, 1). L'implémentation de A me parait un peu douteuse aussi : vous explorez plusieurs fois le même nœud.
J'espère que ces quelques indications vous aideront.
Bonne continuation, Pierre
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/Vincentdaniele/Pathfinding/issues/1, or unsubscribe https://github.com/notifications/unsubscribe-auth/ANMOOM27TN2RDCYVX3OH543RSGJXPANCNFSM4NEMQ5LQ .
pvigier
Bonsoir (je me permets de parler en français, j'imagine que ça ne pose pas de souci),
Après, avoir regardé un petit peu le code, j'ai trouvé une source de non-déterminisme dans la classe Astar qui expliquerait que vous obteniez des résultats différents à chaque exécution.
Dans le bout de code ci-dessous, le minimum n'est pas forcément unique. En règle général, ça ne pose pas de problème, ce serait le dernier élément de l'ensemble qui atteint le minimum qui serait sélectionné. Or ici, comme les éléments sont stockés dans un
std::set<Node*>l'ordre de parcours des éléments n'est pas déterministe (ils sont ordonnés par leur adresse en mémoire qui n'est elle-même pas déterministe).https://github.com/Vincentdaniele/Pathfinding/blob/0cac7e34b8a060bbde8c31ff08a4c67f2c2cff27/SFML_Pathfinding/src/AStar.cpp#L73-L85
La solution la plus simple est d'utiliser une relation d'ordre qui va rendre le minimum unique. Je propose celle-ci :
S'il y a égalité pour le score, on compare les coordonnées. Ça m'a l'air de régler le problème de non-déterminisme.
Après, j'ai l'impression qu'il y a un autre problème, lorsque l'arrivée est atteinte (10, 10), et qu'il cherche à revenir au départ, l'A échoue : il sort de la boucle non pas parce que l'arrivée est atteinte mais parce que
openSetest vide. Il faudrait dessiner la carte pour vérifier si (10, 10) est bien atteignable depuis (1, 1). L'implémentation de A me parait un peu douteuse aussi : vous explorez plusieurs fois le même nœud.J'espère que ces quelques indications vous aideront.
Bonne continuation, Pierre