LAlex devblog v6 - Articles - Commentaires

Traduction : article sur le pathfinding A* - Deimon's Blood

Deimon's Blood — Tue, 03 Nov 2009 06:00:24 +0100

Excellente traduction, elle m'a été d'une grande utilité bien que j'ai adapté à ma façon ^^, mais vraiment, géniale, c'est vraiment très utile !

Traduction : article sur le pathfinding A* - mimi

mimi — Mon, 08 Dec 2008 18:07:08 +0100

MERCI BIEN CH2RIE POUR CETT ARTICLE.vraiment tu m'aide bcp

Traduction : article sur le pathfinding A* - mimi

mimi — Tue, 02 Dec 2008 17:25:37 +0100

MERCI BIEN CH2RIE POUR CETT ARTICLE.vraiment tu m'aide bcp

Traduction : article sur le pathfinding A* - Manuel

Manuel — Thu, 31 Jul 2008 15:07:58 +0200

Bonjour, j'ai implémenté A* en m'aidant de ce tutorial.
Et j'ai publié certains résultat sur
http://doc.xino.ch/?page_id=64
J'y expose certaines optimisations et leurs conséquences.

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