LAlex devblog v6 - Traduction : article sur le pathfinding A* - Commentaires

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

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.

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 ...

Traduction : article sur le pathfinding A* - Maxime

Maxime — Fri, 10 Jun 2005 04:07:35 +0000

Tres bien la traduction, sauf que dans le recapitulatif, tu devrais rajouter en dessous de la ligne "Si on ne peut pas la traverser, on l'ignore." "Si la case est dans la "liste fermee", on l'ignore."

Car ce point important n'est pas present dans le recapitulatif.
Voila,
a part ca, c'est parfait !

Traduction : article sur le pathfinding A* - Imarkahann

Imarkahann — Tue, 08 Mar 2005 19:18:36 +0000

Merci et bravo, en premier pour cette traduction vraiment bien réalisée.

Et pour la remarque Ekameleon, j'ai souvenir oui des focntions natives traduites ... Je me suis retrouvé devant un crossdomain.xml avec des balise qui comportait des accents et des mots français ... et qui se nommai interDomaine.xml ou une chose du genre.... On se dit que els tracducteur ne devait pas trop se préocuper des futurs codeurs, ou ne pas connaitre el language.

Pour Mic : J'ai fais des copies de l'article sur un document Word pour pouvoir l'imprimer et le lire sur papier. Il est ici : [url:3e81452fb0]http://ftpimarkahann.free.fr/pathfinding/[/url]

Bonne continuation à tous !

Traduction : article sur le pathfinding A* - Cyrl

Cyrl — Thu, 13 Jan 2005 16:31:27 +0000

Bonjour, cet article est tres interressant.
Je suis le webmaster de Hoshimi.CodeS-SourceS.fr

J'aimerais savoir si je pourrais integrer cet article ainsi que d'autres du site sur mon site ?

Repondez moi à hoshimi [At] CodeS-SourceS.com

Merci

Traduction : article sur le pathfinding A* - Mic

Mic — Fri, 29 Oct 2004 10:09:35 +0000

Dommage qu'on ne puisse imprimer l'article...

Traduction : article sur le pathfinding A* - Mash

Mash — Wed, 08 Sep 2004 18:55:20 +0000

Hum, en fait non puisque dès qu'il trouve un chemin cé suposé être le meilleur donc il peut arrêter la recherche tout de suite.

Traduction : article sur le pathfinding A* - sauron

sauron — Mon, 23 Aug 2004 03:22:50 +0000

Wai en fait ... en lisant l'article y a un truc qui m'a titiller, et j'ai cru trouver la reponse mais comme ce n'est pas explicitement ecris, je ne suis pas sur.

En fait, meme quand on a trouver un chemin possible jusqu'au point d'arrivé, si on a encore des "cases" dans notre liste ouverte, on doit les parcourir, exact ?

Traduction : article sur le pathfinding A* - sauron

sauron — Mon, 23 Aug 2004 03:17:07 +0000

Salut,

Apres de tres longue heure de recherche, et de desespoir je dois l'avouer, je suis
tomber sur ton article, le premier vraiment clair et qui s'adresse au noob comme moi.
Merci beaucoup, ca m'a vraiment ete utile !

Traduction : article sur le pathfinding A* - darwin

darwin — Tue, 25 May 2004 19:51:34 +0000

hum .. .vlaa je fais un bomberman et j'utilise donc le A star tout ? non car un probleme persiste encore et toujorus a l'envahissuer !
Effectivement quand il ne trouve pas de chemin tu dis que la list eouverte est vide ??? pourtant moi quand il ne trouv epas le chemin ma case ouverte n'est pas vide .... hum ?

Traduction : article sur le pathfinding A* - ekameleon

ekameleon — Tue, 25 May 2004 17:12:39 +0000

Hello
d'un autre côté... tu gardes tout de même du mérite Car ici on a affare à une très bonne traduction
Quand une traduction est mauvaise, cela n'aide pas à comprendre même si le contenu original est intéressant, On peut prendre en contre exemple les traductions du dictionnaire actionscript avec les traducteurs qui ont tellement voulu bien faire leur boulot qu'ils ont traduit les noms de méthode native de flash .. du coup les bouts de code d'exemple ne marchent plus ... et c'est pas génial pour comprendre ce que l'on fait quand on débute... d'où le grand intérêt de bien traduire, c'est du boulot...
bye

Traduction : article sur le pathfinding A* - LAlex

LAlex — Tue, 25 May 2004 12:40:52 +0000

Tout le mérite revient à Patrick Lester, auteur original ! Je ne suis que le traducteur !