PathFinding A*

Résolu
cs_gomoz Messages postés 134 Date d'inscription mardi 22 avril 2003 Statut Membre Dernière intervention 23 décembre 2009 - 11 janv. 2005 à 21:59
cs_gomoz Messages postés 134 Date d'inscription mardi 22 avril 2003 Statut Membre Dernière intervention 23 décembre 2009 - 5 févr. 2005 à 16:18
Bonjour, je dois programmer un PathFinding mais j'ai vraiment du mal :(.

Est-ce que vous pourriez m'aider à comprendre le fonctionnement de A* ?
Voici ce que j'ai piger :
- on a le cout de déplacement pour aller sur un autre noeud (une route, une chemin boueux)
- on a le trajet réstant (on le calcule comment ?)
==> on aditionne les 2.
Seulement comment fait on pour le reste ? (une fois que l'on a déterminer un parcours) ?
Et dans ce cas cela ce passe comment ?
a00001100
000001100
001111100
00000000b
(une fois que a est dans la partie concave ?)

merci d'avance,
[mailto:gomoz@free.fr Gomoz]

PS: génial l'interface pour les messages !

15 réponses

cs_Bidou Messages postés 5487 Date d'inscription dimanche 4 août 2002 Statut Membre Dernière intervention 20 juin 2013 60
12 janv. 2005 à 11:02
3
cs_Bidou Messages postés 5487 Date d'inscription dimanche 4 août 2002 Statut Membre Dernière intervention 20 juin 2013 60
12 janv. 2005 à 07:48
Héhé, laisses-moi deviner? T'es inscrit au projet Hoshimi!
Y'a une tapée de documentation sur le net à propos de A*, c'est super bien expliqué, et sur le site du projet Hoshimi (dans les forums) tu trouveras vraiment tout ce dont tu as besoin !

Bonne chance....

[Pub] http://www.csharpfr.com/auteurdetail.aspx?ID=13319 [\Pub]
C# forever
0
cs_gomoz Messages postés 134 Date d'inscription mardi 22 avril 2003 Statut Membre Dernière intervention 23 décembre 2009
12 janv. 2005 à 08:14
effectivement ;)
pour la doc, tu parles du forum visual gaming en français ? Car l'aide que j'ai trouvé c'est souvent à partir de VB. sinon j'ai posé des questions sur un tread et c'est long les réponses (faut dire aussi qu'il y a rien qui nous préviens qu'une réponse à été posté).

sinon voici le tread où j'ai poster http://fr.thespoke.net/MessageBoard/MessageBoard_ViewThread.aspx?postid=131 car j'ai un problème : GetVoisin() est défini dans le SDK ? Et aussi on calcul comment le trajet restant ? (G si j'ai bieen compris).

[mailto:gomoz@free.fr Gomoz]
0
cs_Bidou Messages postés 5487 Date d'inscription dimanche 4 août 2002 Statut Membre Dernière intervention 20 juin 2013 60
12 janv. 2005 à 10:49
Ben sur le forum anglais y'a plus d'info quand même...
Mais tapes seulement A* dans Google, tu verras que y'a une tapée d'exemple et d'introduction sur le sujet qui expliquent assez bien comment ça marche.

[Pub] http://www.csharpfr.com/auteurdetail.aspx?ID=13319 [\Pub]
C# forever
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
cs_gomoz Messages postés 134 Date d'inscription mardi 22 avril 2003 Statut Membre Dernière intervention 23 décembre 2009
12 janv. 2005 à 11:20
Merci beaucoup pour ces liens, très pratique ... mais en anglais (je vais m'acrocher et les lires quand même, mais pas facile :.( ).

Sinon pour A* dans google. On fait comment ? (pour "*")

Et aussi, en deux mots : le trajet réstant, c'est à vol d'oiseau que l'on doit le calculer ?

a00001100
000001100
001111100
00000000
b

(Ici, sans tenir compte du poids de la case, "a" a quel score ? 11 ou quoi ?)

[mailto:gomoz@free.fr Gomoz]


En tout cas merci bien pour ces liens ;)
0
cs_gomoz Messages postés 134 Date d'inscription mardi 22 avril 2003 Statut Membre Dernière intervention 23 décembre 2009
12 janv. 2005 à 11:31
c'est bon, en fait c'est avec l'heuristic que l'on calcule le chemin. (pourquoi "heuristic" ???) Donc je devrais m'en tirer avec google pour le reste ... à moins que tu ais une bonne methode pour l'heuristic ;)

[mailto:gomoz@free.fr Gomoz]
0
cs_Bidou Messages postés 5487 Date d'inscription dimanche 4 août 2002 Statut Membre Dernière intervention 20 juin 2013 60
12 janv. 2005 à 12:03
Ben en fait même si je me suis qualifié pour le 1er round (y'avait rien à faire... ha si, changer la valeur de deux variables) je sais pas si je vais me lancer pour le round2... donc en fait, j'ai pas (encore) fait de A* !
Ceci dit, dans un projet qui date d'environ 2 ans j'avais du créer un jeu, Bomberman (c'était en Java) et j'avais fait un petit A*. Et si mes souvenirs sont bons, l'heuristique est une fonction qui permet d'évaluer le chemin restant depuis la position dans laquelle tu trouves jusqu'à l'arrivée.
L'heuristique proposée par A*, sauf erreur, est de simplement calculé le nombre de case horizontale et verticale qui te sépares de l'arrivée, et d'en faire la somme (tout con). Cette méthode marche dans presque tout les cas (il paraîterait que dans certains rares cas, cet heuristique ne permet pas de trouver le chemin le plus court...).
Voilà en gros.

[Pub] http://www.csharpfr.com/auteurdetail.aspx?ID=13319 [\Pub]
C# forever
0
cs_gomoz Messages postés 134 Date d'inscription mardi 22 avril 2003 Statut Membre Dernière intervention 23 décembre 2009
12 janv. 2005 à 15:12
Oui c'est bien ce que j'ai commencé à voir, A* n'ai pas toujours au top, mais il y a peu de marge d'erreur. Sinon pour le round 1, en effet, pas besoin de A* mais après ils nous ont laissé penser que ils nous "obligeraient".
Merci bien pour cette aide, sinon domage qu'il n'y est pas d'exemple de A* en c# sur coude-source. Peu etre que quand j'aurai fini, je m'y mettrais ?

[mailto:gomoz@free.fr Gomoz]
0
TheSaib Messages postés 2368 Date d'inscription mardi 17 avril 2001 Statut Modérateur Dernière intervention 26 décembre 2007 23
12 janv. 2005 à 18:20
POur rechercher sur google tu peux taper A*
Mais tu devrais aussi regarder du côté de djikstra , D* mais aussi d'après des algorithmes génétiques, voire meme un simple tout droit suffirait dans certains cas :)

Bon courage

::|The S@ib|::
MVP C#.NET
0
TheSaib Messages postés 2368 Date d'inscription mardi 17 avril 2001 Statut Modérateur Dernière intervention 26 décembre 2007 23
12 janv. 2005 à 18:22
"POur rechercher sur google tu peux taper A*" <= je voulais dire " A star algorithm "

::|The S@ib|::
MVP C#.NET
0
jesusonline Messages postés 6814 Date d'inscription dimanche 15 décembre 2002 Statut Membre Dernière intervention 13 octobre 2010 29
13 janv. 2005 à 13:37
J'ai vu le message, je me suis dit pourquoi ne pas faire ma petite pub, j'espere que personne ne m'en voudra.



Donc si ca interesse du monde, j'ai fait un petit site :
http://hoshimi.codes-sources.fr le forum est en route il y a une
discution entre Akhenathon et Zogstrip sur le TSP, et des articles vont
arriver sur les algos etc...



D'ailleur je recherche des redacteurs ...

<!--StartFragment -->
<hr>

Cyril - Webmaster de Hoshimi.CodeS-SourceS.fr
0
cs_gomoz Messages postés 134 Date d'inscription mardi 22 avril 2003 Statut Membre Dernière intervention 23 décembre 2009
13 janv. 2005 à 16:03
oui, j'ai déjà vu ton site (très bonne idée !). Mais encore rien sur le pathfinding mais si ca viens ce sera super.

Sinon j'ai compris le principe pour construire un itinéraire mais pas pour l'ordonné. Je m'explique :

sur http://www.lalex.com/blog/archives/200309/49-traduction-article-sur-pathfinding.html il dise ca :
"Maintenant, comment déterminer le chemin lui-même ? Tout simplement en partant de la case d'arrivée, et en remontant le chemin en sens inverse d'une case à sa case parent, en suivant les flèches. Cela va vous ramener à votre chemin de départ, et voila votre chemin ! Cela devrait ressembler à l'illustration ci-contre. Se déplacer du point A ou point B consiste maintenant à vous déplacer du centre d'une case au centre de la prochaine case de votre chemin, jusqu'à ce que vous atteignez votre destination. Simple non ?!?"
euh .... en fait non pas simple. Pour trouver la case parent, je fais comment ? sur le papier, je vois bien : (les pti roud avec laa barre) mais pour le PC, je lui dis quoi ?

help again please

[mailto:gomoz@free.fr Gomoz]
0
gwylom Messages postés 3 Date d'inscription lundi 27 septembre 2004 Statut Membre Dernière intervention 3 février 2005
3 févr. 2005 à 20:46
C'est peut-être un peu tard pour répondre, mais je le fais quand même :o)



Pour retrouver le chemin, il te faut avoir mémorisé, pour chaque case
explorée, de quelle case tu venais (laquelle est la précédente, quoi)!

En gros tu peux faire un tableau de la taille du terrain, et quand tu
cherches les voisins d'un point, tu mets dans la case de ce tableau le
point d'où tu viens (ou juste la direction ex : 1 nord, 2 sud, 3 est, 4
ouest).



Quand tu as trouvé la destination, tu regardes la flêche de la dernière
case. ça t'indiques la case que tu avais trouvé juste avant. Tu
regardes alors la case trouvée juste avant.... jusqu'à la première case!

Tu as ton chemin (a l'envers quand même)!!

-----
L'ennemi est con, il croit que c'est nous l'ennemi alors que c'est lui
0
jesusonline Messages postés 6814 Date d'inscription dimanche 15 décembre 2002 Statut Membre Dernière intervention 13 octobre 2010 29
3 févr. 2005 à 21:56
Tient quelqu'un qui ne m'est pas inconnu ici



Akhenaton a fait un article la dessus, pour ceux que ca interesse :
http://hoshimi.codes-sources.fr/Default.aspx?TabID=40&newsType=ArticleView&articleId=55
j'ai aussi mis un document pdf de 45 pages sur le pathfinding, j'ai
encore pas finit de le lire (grippe oblige ) mais il est tres interessant



Bonne prog

<hr>

Cyril - http://Hoshimi.CodeS-SourceS.fr
0
cs_gomoz Messages postés 134 Date d'inscription mardi 22 avril 2003 Statut Membre Dernière intervention 23 décembre 2009
5 févr. 2005 à 16:18
en effet ce doit etre la seul solution, je ne voulais pas faire ca car j'avais peur pour la raidité de l'algo mais en fait ca ne joue pas beaucoup.Mais merci de la précision

[mailto:gomoz@free.fr Gomoz]
0