LAlex devblog v6 - Erratum article sur le pathfinding A star - Commentaires

Erratum article sur le pathfinding A star - dav

dav — Mon, 31 Oct 2005 11:28:38 +0000

Salut trés interessant tout ca mais j'ai difficulté à comprendre comment le cout d'une case est attribué. D'après les tuto que j'ai lu 10 pour les cases adjacentes et 14 pour les diagonales mais lorsque j'utilise ta classe sans les diagonales il resout le chemin mais le chemin est trés long et trés complexe et lorsque j'utilise les diagonales il ne resout pas le chemin ou en tout cas il y a des trous.

Erratum article sur le pathfinding A star - xion

xion — Sun, 21 Aug 2005 22:48:13 +0000

tu as raison, je n'avais pas pris en compte le fait que le tri fait revenir en arrière la recherche dès que cela devient moins intéressant (arghk, j'ai fait comment pour passer à côté ? )...

à noter pour approfondir A* un lien des plus intéressants, mais je suppose que tu l'as déjà dans ta liste sur A* : http://theory.stanford.edu/~amitp/GameProgramming/

Erratum article sur le pathfinding A star - LAlex

LAlex — Fri, 19 Aug 2005 00:05:18 +0000

xion > Je vais regarder de ce côté plus en profondeur alors... J'avais de toutes façons l'intention de le faire évoluer pour qu'il gère les cases hexagonales, ce sera l'occasion de refaire tous mes tests... Je développe actuellement une mini-plateforme de test pour du pathfinding justement

Par contre, tu te trompes sur la situation que tu donnes : en effet, plus le chemin va se rallonger, plus l'estimation de la "valeur" de la case (valeur H) sera importante. Il va donc tester éventuellement de rebrousser chemin s'il se trouve qu'une des cases qui rebroussent chemin devient plus interessante... C'est d'ailleurs là qu'intervient le tri de la liste ouverte...

L'algo A* est a priori le plus fiable qui existe concernant le fait de trouver le chemin le plus court (enfin UN des chemins les plus courts, i peut y en avoir plusieurs). Son inconvénient se situe au niveau des ressources processeur utilisées, qui peuvent devenir assez importantes... :o

Erratum article sur le pathfinding A star - xion

xion — Thu, 18 Aug 2005 21:34:35 +0000

Bon, bas j'ai l'impression que ce n'est pas un problème de mon implémentation, donc si jamais tu as des bugs ou autres chemins bizarres, tu pourras toujours chercher sur cette piste

En tout cas je remarque, et c'est normal en fait, que ce genre de pathfinder trouve LE CHEMIN le plus évident à première vue... cependant, il ne trouve pas LE PLUS COURT CHEMIN.
Il est normal de dire cela tout simplement parce que s'il la boucle passe dans un chemin fermé, mais assez long, tout en allant jusqu'à la sortie alors qu'il suffisait de rebrousser chemin (aller en direction oppopsée à celle où se trouve la case de fin) pour trouver une ligne droite sur un bord ou autre, et bien on trouvera bien un chemin qui marche, mais le pathfinder ne trouvera pas le MEILLEUR. Cependant, pour être certain de trouver le meilleur, on est obligé de tester tous les chemins possibles, donc ta gestion via A* est bien meilleure pour le processeur et trouvera toujours un chemin, malgré que ce ne sera pas forcément le meilleur...

Erratum article sur le pathfinding A star - xion

xion — Tue, 16 Aug 2005 18:57:28 +0000

Salut, merci de ta réponse ;).

Quand tu dis que l'arbre binaire est toujours trié... il l'est à chaque fois, mais pour une des deux branches principales... or dans certains cas, il peut y avoir une branche qui n'est finalement pas mise à jour.. (je suppose que c'était le cas dans mon exemple, car ça n'était pas un problème de non-optimisation, mais une erreur de chemin, qui amenait à des valeurs illogiques et qui sont fausses au niveau du chemin)

Cependant, n'étant pas sur mon ordi et n'ayant pas mon code de base, je ne puis dire si c'était plutôt une erreur de traitement pendant la gestion du tri de l'arbre... donc en attente
De plus j'essaierait d'utiliser ta version as2 pour voir si c'est une erreur ou bien un défaut de mon implémentation java...

Erratum article sur le pathfinding A star - LAlex

LAlex — Tue, 16 Aug 2005 10:06:51 +0000

d'abord, si tu utilises ALLOW_DIAG, ne serait-ce pas plus logique d'utiliser if(!ALLOW_DIAG) pour la première condition étant donné que si on n'utilise pas les diagonales, on n'a pas la complication dont tu t'occupes après (dans le else) ?

de plus, le calcul des diagonales me paraît faut :
var nbDiag = Math.abs(x1-x0-y1+y0);Tu as tout à fait raison. Incroyable d'être passé la-dessus sans le voir. Merci!

nbDiag * 14 ne marcherait pas ? ou alors une constante genre DEFAULT_DIAG_COST qui vaudrait 14 par exempleEn effet, c'est largement optimisable, mais plutôt en utilisant un ratio. Il n'est pas normal que l'on ai à modifier deux variables pour un chagement du coût par défaut. La solution serait d'utiliser une variable statique DIAG_RATIO. Si on veut être mathématiquement exact, ce serait DIAG_RATIO=Math.sqrt(2), et si on veut éviter trop de virgules, on peut mettre DIAG_RATIO =1.4...

Ensuite, concernant le tri des arbres binaires, le ''<=" sert à éviter des boucles supplémentaires... En effet, ce tri fonctionne par permutations, et en fait, étant donné que le tableau est déjà trié et qu'on se contente de rajouter une nouvelle valeur, on peut considérer indifféremment qu'on va permuter deux valeurs égales ou non. J'ai choisi la deuxième option...
Je n'ai pas analysé en détail le cas pratique que tu donnes, mais a priori, a partir du moment ou le tableau est trié, ca devrait fonctionné. Peut-être que cela peut provoquer un chute des performances dans certains cas, mais ca devrait les améliorer dans d'autres cas... On ne peut pas tout avoir !

En gros, voici la méthode heuristique rectifiée grace a tes remarques :private static var DIAG_RATIO:Number = Math.sqrt(2); //..... private static function heuristic(mp:Array, x0, y0, x1, y1):Number { if (!ALLOW_DIAG) { return (Math.abs(x1-x0)+Math.abs(y1-y0))*DEFAULT_COST; } else { var dX:Number = Math.abs(x1-x0); var dY:Number = Math.abs(y1-y0); return Math.round(Math.min(dX, dY)*DIAG_RATIO*DEFAULT_COST)+Math.abs(dX-dY)*DEFAULT_COST; } }

Je vais republier la classe rectifiée. Merci encore de tes infos.

Erratum article sur le pathfinding A star - xion

xion — Mon, 15 Aug 2005 19:10:44 +0000

resalut... je ne sais pas si c'est propre à ma méthode réimplémentation, mais bon, je le poste quand même...

j'ai réimplémenté la base de ton pathfinder, en l'orientant plus objet et en changeant certains point structurel, cependant cela en java...
et au final, j'ai réussi à faire marcher ça correctement, mais juste avant de trouver la fin, je suis resté bloqué sur un point qui était pourtant compréhensible...

Ta méthode de tri de l'open :
private static function sortOpenListFrom(lst,ind):Void { if (BINARY_HEAPS) { var curInd:Number = ind; // On trie d'un enfant vers son parent // Si l'indice est 1, on arrete car on est en // haut de l'arbre while (curInd > 1) { var parInd = Math.floor(curInd/2); // Si le parent a un cout inferieur, on arrete le tri if (lst[curInd].totCost >= lst[parInd].totCost) { break; } var tmp:Object = lst[parInd]; lst[parInd] = lst[curInd]; lst[curInd] = tmp; curInd = parInd; } } } Je ne sais pas si ça marche en as2, étant donné que je n'ai testé que mon implémentation java, mais en java ça foire... La relation d'erreur est faite entre : if (lst[curInd].totCost >= lst[parInd].totCost) { break; } et var heur:Number = PathFinder.heuristic(mp,curX,curY,x1,y1); var newPt:Object = { x:curX, y:curY, pathCost:curPathCost, togoCost:heur, totCost:curPathCost+heur, parent:curPnt }; cloneMap[curX][curY] = newPt; PathFinder.open(openList, newPt); Je m'explique : Imaginons que j'ai une surface sans bloqueur. Je suis à (2,2) et je vais à (10,0). Chez moi ça a bloqué à partir de (5,0)... pourquoi : -à 4.1 : F(5,0) = 88 (d'après mon implémentation, mais cela ne change rien), disons F(5,0) = VALUE; or F(5,1) = 88 aussi (VALUE) mais c'est normal étant donné la manière de tourner des boucles, c'est à 5.0 que ça passe -à 5.0 : F(6,0) = 88 (VALUE), ce qui est juste, c'est en fait le seul point acceptable à ce moment or F(5.1) qui normalement devrait valoir une valeur plus grande étant donné que la valeur de retour de l'heuristique est relative à chaque case.. bas c'est pas le cas étant donné que la boucle n'a pas encore passé à 5.1 et donc il vaut toujours 88 (VALUE), sa valeur précédente... Dans le tri, on va avoir 6.0 qui remonte, et son parent 5.1 ne le laissera pas passé, alors qu'il le ferait s'il était à jour... c'est dû à ton if (lst[curInd].totCost >= lst[parInd].totCost) { break; } Donc il suffit d'écrire : if (lst[curInd].totCost > lst[parInd].totCost) { break; }
et hop, tous les cases sont totalement triées... et il n'y a plus de problèmes du tout
Je ne sais pas si j'ai fait une modification lors de mon implémentation java qui n'a pas la même structure je l'avoue, mais étant donné que dans mon implémentation java cela a causé des problèmes, je le notifie ici

Si j'ai oublié quelque chose qui justifierai ton signe et son égalité, dites-le-moi

Erratum article sur le pathfinding A star - xion

xion — Sun, 14 Aug 2005 13:55:32 +0000

resorry, la dernière phrase, c'est plutôt Pourquoi se compliquer avec ...
nbDiag * 14 ne marcherait pas ? ou alors une constante genre DEFAULT_DIAG_COST qui vaudrait 14 par exemple

Erratum article sur le pathfinding A star - xion

xion — Sun, 14 Aug 2005 13:52:12 +0000

arghk, sorry pour toutes les fautes de frappe (c'était pas intentionnel :))
autre question comme ça, quand tu crées les valeurs, juste après,la valeur des diagonales multipliée par un nombre...
ayant lu les articles en anglais, et surtout ta traduction, les diagonales utilisaient une simple valeur 14 à la place de 10...
pour se compliquer avec : nbDiag*Math.sqrt(2*DEFAULT_COST)) ?

Erratum article sur le pathfinding A star - xion

xion — Sun, 14 Aug 2005 13:47:50 +0000

Salut, j'ai un peu disséquer, et en tomber sur ta méthode heuristique... bas au premier abord, quelque chose clochait, et au deuxième, bas il y en a deux de choses qui clochent :(.

C'est pas si grave, mais bon, dans la méthode :
// Heuristique Manhatan private static function heuristic(mp:Array, x0, y0, x1, y1):Number { if (ALLOW_DIAG) { return (Math.abs(x1-x0)+Math.abs(y1-y0))*DEFAULT_COST; } else { // Nombre de diagonale var nbDiag = Math.abs(x1-x0-y1+y0); // Nombre de lignes droites var nbLine = Math.max(Math.abs(x1-x0),Math.abs(y1-y0))-nbDiag; return Math.round(nbDiag*Math.sqrt(2*DEFAULT_COST))+nbLine*DEFAULT_COST; } } d'abord, si tu utilises ALLOW_DIAG, ne serait-ce pas plus logique d'utiliser if(!ALLOW_DIAG) pour la première condition étant donné que si on n'utilise pas les diagonales, on n'a pas la complication dont tu t'occupes après (dans le else) ? de plus, le calcul des diagonales me paraît faut : var nbDiag = Math.abs(x1-x0-y1+y0); j'utiliserai plutôt : var nbDiag = Math.min(Math.abs(x1 - x0), Math.abs(y1 - y0)); // étant donné que c'est le minimum par rapport au déplacement en x ou y cependant, ton système marche à certain coup... donc ça n'a pas dû t'étonner : var x1:Number, x0:Number, y1:Number, y0:Number; x1 = 0; y1 = 1; x0 = 1; y0 = 3; var nbDiag:Number = Math.abs(x1-x0-y1+y0); trace(nbDiag); nbDiag = Math.min(Math.abs(x0 - x1), Math.abs(y0 - y1)); trace(nbDiag); sortie : 1 et 1, oki mais changeons les valeurs par : x1 = 0; y1 = 1; x0 = 1; y0 = 2;
sortie : 0 pour ton code, 1 pour l'utilisation du min et 0, c'est pas très possible dans le monde des distances entre deux points différents

ah moins que j'ai loupé quelque chose ?