LAlex devblog v6 - Articles - Commentaires

Traduction : article sur le pathfinding A* - SuperDupont

SuperDupont — Sat, 08 Dec 2007 00:18:26 +0100

Article super, traduction nickel, j'ai codé l'algo - qui fonctionne - en deux heures
Plus qu'a l'optimisé et la je crois qu'il va me falloir plus de deux heures....
Quelqu'un a des trucs ????

Traduction : article sur le pathfinding A* - Daemonight

Daemonight — Wed, 13 Jun 2007 09:51:22 +0200

bloody -> pour répondre à ta question, oui, tu peux faire l'étape c avant l'étape a et b.... puisque que de toute façon tu fait ces 3 étapes en boucle !
Finalement, faire "a-b-c-a-b-c-a-b-c" ou "c-a-b-c-a-b-c-a-b-c", la seule chose qui change c'est par quoi tu commences.
Dans l'absolu, pour pouvoir faire l'étape "a", il faut forcément que la liste ouverte soit mise à jour, donc...
_Que l'étape "c" ai été réalisée (on y est !)
_ou... que l'on soit au début de l'algorythme et que la seule case dans la liste ouverte soit par conséquent le point de départ. Dans ce cas on commence par l'étape "a".

Tout est donc une question de relativité. L'important est bien faire les étapes dans l'ordre, et comme c'est une boucle, peu importe l'endroit d'où tu commences ^^

Bon matlab (j'en ai fait un peu dans mes études, je trouvais ça horrible...)

++
Daemonight, pour vous servir

Flash MX 2004 : d'ActionsScript 1 à ActionScript 2 - NiKo

NiKo — Mon, 21 May 2007 12:52:02 +0200

Petit intérêt des interfaces supplémentaires, pouvoir tester l'implémentation sur un objet instancié :

var h:Coureur= new Coureur();
if (h instanceof Humain) {
trace('Ce coureur est bien humain');
}

Sinon bon billet (oui, je laggue à mort.)

Traduction : article sur le pathfinding A* - bloody

bloody — Fri, 18 May 2007 22:06:37 +0200

je dois implementer A* avec matlab
sachant que le point de depart est toujours le meme et que je peux donc le mettre avant la boucle dans la liste ouverte
je me demandais si par raison de commodite, on peut faire l etape a et b apres la c.
Cela change le fonctionement de l algo?

Traduction : article sur le pathfinding A* - Duke

Duke — Tue, 06 Mar 2007 00:13:05 +0100

Je comprend vraiment pas ce qui se passe avec cet algo lorsque l'on tombe sur un cul de sac, j'essaye de schématiser vite fait un exemple:
.o. . . . . .M . x . .
. .M.M.M.M.M. . .
. . . . . . . . . . . . .
les M sont en fait des murs, au début donc, si o est le point de départ et x l'arrivée, il va directement arriver vers la droite, en ayant ajoutée toute les cases jusqu'a celle immédiatement a gauche du mur qu'il va rencontrer, à la liste fermée. Une fois qu'il sera là, il va examiner les cases adjacente, n'en trouver qu'une seule, donc se déplacer a gauche, ensuite il trouvera 2 cases adjacentes, et celle la plus interessante sera celle immédiatement à droite, il va donc retourner vers le mur.
J'ai essayé de poser sur papier et je comprend vraiment pas...
Si quelqu'un peut me donner une bonne explication je lui en serait très reconnaissant.
Merci

Traduction : article sur le pathfinding A* - Daemonight

Daemonight — Mon, 05 Feb 2007 20:57:58 +0100

sorry : errata :
Il n'y a donc plus aucune case du cul de sac dans la liste "fermé" => Il n'y a donc plus aucune case du cul de sac dans la liste OUVERTE (bien sûr lol)

Traduction : article sur le pathfinding A* - Daemonight

Daemonight — Mon, 05 Feb 2007 20:56:29 +0100

Pour répondre à ta question Duke :
Comme tu le dis Duke, effectivement, le programme va foncer à droite dans le cul de sac. Arrivé au bout, que ce passe-t-il ? tous les noeuds du cul de sac sont dans la liste fermé. Il n'y a donc plus aucune case du cul de sac dans la liste fermé.
Donc, en toute logique, la case dont le coût "F" est le plus "faible" est maintenant celle situé en dessous de ton "o" soit en dessous de la case départ. L'algorithme va donc repartir de là, et le tour est joué.
C'est typiquement dans un cas comme celui-ci que l'Astar (A*) trouve ses limites. Il trouvera la solution, mais il perdra du temps du fait qu'il est "aimanté" par l'arrivé dans le calcul du H en mode "Manhatan"
Imagine :
.............................................
..MMMMMMMMMMMMMMMM ...
..O...................................M ...
MMM...M...M...M...M...M... M ...
MMM...M...M...M...M...M... M ...
MMM...M...M...M...M...M... M ...
MMM...M...M...M...M...M... M ...
MMMMMMMMMMMMMMMMM X

Tu vois un peu la galère ? Avant de trouver le chemin qui passe par au desus, l'algo va faire tous les culs de sac un par un. Vive la perte de temps. Alors que visuellement, celà saute au yeux.
C'est précisement pour celà que le titre de l'article est Pathfinding A* : Pour débutant. C'est parfait pour comprendre le principe d'un pathfinder, mais tu l'aura compris, toute la subtilité d'un algo efficace réside dans le calcul du H.
Voila ^^

Bon code

et merci à toi LAlex !

Traduction : article sur le pathfinding A* - Zamer

Zamer — Sat, 27 Jan 2007 19:52:03 +0100

Salut, c'est vraiment dommage que cette traduction ait conservé les nombreuses fautes du document originel.

Flash MX 2004 : d'ActionsScript 1 à ActionScript 2 - zouzoute

zouzoute — Sat, 12 Aug 2006 23:31:17 +0200

merci pour ces explications claires!

Traduction : article sur le pathfinding A* - Neji

Neji — Mon, 24 Apr 2006 15:17:59 +0000

bon bin fait chier... après avoir constaté que le link sur la trad fr avait disparu,(depuis l'article original de P Lester sur gamedev.net j 'avais commencé à traduire jusqu' à la moitié avant que je ne m' aperçoive que le lien fonctionnait de nouveau...
=> j'ai travaillé pour rien !!!
enfin j'y ai pris du plaisir quand même

Bonne trad Lalex, j' aurais difficilement pu faire mieux.

Traduction : article sur le pathfinding A* - AlBrad0

AlBrad0 — Thu, 30 Mar 2006 23:43:10 +0000

Trés bon article, trés claire et surtout en français ce qui est rare sur le pathfinding
Merci ...

Flash MX 2004 : d'ActionsScript 1 à ActionScript 2 - david

david — Wed, 29 Mar 2006 13:02:52 +0000

bonjour et merci pour ce récapitulatif

Simplement j'ai une question à te poser concernant l'ajout de méthode en AS2.
Avant toute chose je suis novice en POO. :o))
Tu dis qu'il faut faire de l'héritage pour ajouter une méthode. Peux tu m'expliquer comment faire si je veux rajouter une méthode a une movieclip. Jusqu'à maintenant je faisait MovieClip.prototype.methode or je ne vois pas comment faire autrement sans passer par un fichier de class qui serait un héritage de movieClip
Merci
J'imagine que cette qustion doit faire sourire mais nous avons tous débuter un jour ;o))
A++ et boone continuation

Flash MX 2004 : d'ActionsScript 1 à ActionScript 2 - FireStorm

FireStorm — Mon, 02 Jan 2006 10:22:45 +0000

merci pour cet article bien écrit...

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