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
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
A voir également:
- Pathfinding algorithm python
- Python attendre ✓ - Forum VB.NET
- Python arrondi supérieur ✓ - Forum C# / .NET
- Courbe de tendance python - Forum Python
- Arrondir à l'entier supérieur ✓ - Forum Visual Basic
- Arrondir au +5 supérieur ✓ - Forum C# / .NET
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
61
12 janv. 2005 à 11:02
12 janv. 2005 à 11:02
Quelques petites adresses qui devraient aider :
http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html
http://www.c2i.fr/code.asp?IDCode=1013&type=&IDCate=15&Cate
http://rajiv.macnn.com/tut/search.html
http://www.lalex.com/blog/archives/200309/49-traduction-article-sur-pathfinding.html
[Pub] http://www.csharpfr.com/auteurdetail.aspx?ID=13319 [\Pub]
C# forever
http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html
http://www.c2i.fr/code.asp?IDCode=1013&type=&IDCate=15&Cate
http://rajiv.macnn.com/tut/search.html
http://www.lalex.com/blog/archives/200309/49-traduction-article-sur-pathfinding.html
[Pub] http://www.csharpfr.com/auteurdetail.aspx?ID=13319 [\Pub]
C# forever
cs_Bidou
Messages postés
5487
Date d'inscription
dimanche 4 août 2002
Statut
Membre
Dernière intervention
20 juin 2013
61
12 janv. 2005 à 07:48
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
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
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
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]
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]
cs_Bidou
Messages postés
5487
Date d'inscription
dimanche 4 août 2002
Statut
Membre
Dernière intervention
20 juin 2013
61
12 janv. 2005 à 10:49
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
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
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
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 ;)
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 ;)
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
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]
[mailto:gomoz@free.fr Gomoz]
cs_Bidou
Messages postés
5487
Date d'inscription
dimanche 4 août 2002
Statut
Membre
Dernière intervention
20 juin 2013
61
12 janv. 2005 à 12:03
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
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
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
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]
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]
TheSaib
Messages postés
2367
Date d'inscription
mardi 17 avril 2001
Statut
Membre
Dernière intervention
26 décembre 2007
23
12 janv. 2005 à 18:20
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
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
TheSaib
Messages postés
2367
Date d'inscription
mardi 17 avril 2001
Statut
Membre
Dernière intervention
26 décembre 2007
23
12 janv. 2005 à 18:22
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
::|The S@ib|::
MVP C#.NET
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
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
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
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
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]
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]
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
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
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
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
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
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
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
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]
[mailto:gomoz@free.fr Gomoz]
