PathFinding A*

Résolu
Signaler
Messages postés
134
Date d'inscription
mardi 22 avril 2003
Statut
Membre
Dernière intervention
23 décembre 2009
-
Messages postés
134
Date d'inscription
mardi 22 avril 2003
Statut
Membre
Dernière intervention
23 décembre 2009
-
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 !
A voir également:

15 réponses

Messages postés
5487
Date d'inscription
dimanche 4 août 2002
Statut
Membre
Dernière intervention
20 juin 2013
58
Messages postés
5487
Date d'inscription
dimanche 4 août 2002
Statut
Membre
Dernière intervention
20 juin 2013
58
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
Messages postés
134
Date d'inscription
mardi 22 avril 2003
Statut
Membre
Dernière intervention
23 décembre 2009

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]
Messages postés
5487
Date d'inscription
dimanche 4 août 2002
Statut
Membre
Dernière intervention
20 juin 2013
58
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
Messages postés
134
Date d'inscription
mardi 22 avril 2003
Statut
Membre
Dernière intervention
23 décembre 2009

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 ;)
Messages postés
134
Date d'inscription
mardi 22 avril 2003
Statut
Membre
Dernière intervention
23 décembre 2009

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]
Messages postés
5487
Date d'inscription
dimanche 4 août 2002
Statut
Membre
Dernière intervention
20 juin 2013
58
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
Messages postés
134
Date d'inscription
mardi 22 avril 2003
Statut
Membre
Dernière intervention
23 décembre 2009

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]
Messages postés
2368
Date d'inscription
mardi 17 avril 2001
Statut
Modérateur
Dernière intervention
26 décembre 2007
22
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
Messages postés
2368
Date d'inscription
mardi 17 avril 2001
Statut
Modérateur
Dernière intervention
26 décembre 2007
22
"POur rechercher sur google tu peux taper A*" <= je voulais dire " A star algorithm "

::|The S@ib|::
MVP C#.NET
Messages postés
6814
Date d'inscription
dimanche 15 décembre 2002
Statut
Modérateur
Dernière intervention
13 octobre 2010
29
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
Messages postés
134
Date d'inscription
mardi 22 avril 2003
Statut
Membre
Dernière intervention
23 décembre 2009

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]
Messages postés
3
Date d'inscription
lundi 27 septembre 2004
Statut
Membre
Dernière intervention
3 février 2005

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
Messages postés
6814
Date d'inscription
dimanche 15 décembre 2002
Statut
Modérateur
Dernière intervention
13 octobre 2010
29
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
Messages postés
134
Date d'inscription
mardi 22 avril 2003
Statut
Membre
Dernière intervention
23 décembre 2009

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]