Algorithme Astar
| Darktib |
Posté le 24 Nov 2007 à 22:07
|
|
 Messages : 4017 GCPoints : 347288 |
Bonjour tout le monde Je vais vous décrire l'algorithme A* (Astar) très utilisé dans les jeux vidéo pour le pathfinding (recherche du plus court chemin entre deux points) mais pas vous l'expliquer en détail, vu qu'il y a moult tutos dessus sur le net. Premièrement, si vous parlez un peu anglais, vous avez déjà compris le nom ;) .En effet Astar veut en fait dire A*,ce qui peut s'interpréter comme une recherche en étoile d'un chemin.  Késako? C'est quoi une recherche en étoile?Prenons une case dans un tableau, et nommons-la A. L'algorithme va rechercher le coût de chaque case adjacente, d'où le "étoile" Des que l'algo a trouvé la case de but, il s'arrête et prend les cases ayant le cout le plus faible comme point de parcours.On peut nommer ces case waytiles : en effet la distance entre deux waytiles est de 1 (dans le tableau des obstacles) d'où le -tile et comme c'est un chemin que l'on veut on utilise way.Tout simple. J'ai pas tout saisi. C'est quoi le cout des cases? et le tableau d'obstacles?Un tableau d'obstacles est un tableau de 0 et de 1. 0=pas d'obstacle, et 1=obstacle. Lorsque que l'on demande a l'algo de rechercher le chemin entre deux coordonnées, il traduit ça en coordonnées dans le tableau et recherche.C'est beaucoup plus simple. Quant au moyen de recherche,il consiste en cout de cases.Par exemple aller horizontalement de gauche a droite coute 1 et en diagonale coute 1.414 (heuristiques).En additionnant les cout on obtient le cout d'un chemin. Et après?Et après je ne vais pas vous faire tout le cours. En effet d'autres expliquent ça mieux que moi. Patrick Lester, notamment. Bonne nouvelle : je vous donne les liens ;) Article en anglais de Patrick Lester Mauvaise nouvelle: l'article traduit a été supprimé :( et il faudra que vous fassiez des recherches... Y a t-il d'autres algorithmes?Oui.Et pas qu'un peut! Il y a Djikstra, Viterbi, Ford-Bellman, et beaucoup d'autres... Pour plus d'infos : ->google  J'espère que cela vous a été utile. Et je termine sur une (éventuelle) bonne nouvelle : si l'article en français est introuvable, je le traduirai dans ce post... @+ ~Darktib
Dernière édition le 22 Août 2008 à 11:13
|
|
| Huntil |
Posté le 24 Nov 2007 à 23:27
|
|
 Messages : 1012 GCPoints : 289843 |
Moi je suis prenneur de toutes infos, surtout lorsqu'il s'agit d'IA (pas de catégorie IA dans les tutos ?!) . L'anglais ne me pose pas de problème, en revanche je suis une vraie quiche en math :P
Copyright © 2007 - 2010 Huntil
"Il faut toujours un drame" |
|
| Mod |
Posté le 25 Nov 2007 à 10:29
|
|
 Messages : 4954 GCPoints : 2100823 |
Mmmh, Djikstra, algorithme utilisé pour plein de trucs, que vous utilisez sans même le savoir quand vous êtes sur Internet... Utile pour trouver le meilleur chemin entre routeurs ^^. Si tu veux, postes ce tutoriel dans le menu "vos articles" à gauche. Je l'ajouterai à la liste du site ;). |
|
| Darktib |
Posté le 25 Nov 2007 à 17:24
|
|
|
Messages : 4017 GCPoints : 347288 |
Peut etre...Dans ce cas il faudrait que j'etoffe ca un peu... | |
| noob4ever |
Posté le 25 Nov 2007 à 19:50
|
|
 Messages : 295 GCPoints : 48742 |
algorithme
What did C:/DARTHVADER said to C:/DARTHVADER/LUKESKYWALKER ?
I'm your folder |
|
| Darktib |
Posté le 25 Nov 2007 à 19:55
|
|
|
Messages : 4017 GCPoints : 347288 |
M**** je sais on m'a deja fait remarquer que ce mot etait vicieux ;) mais bon c'est pas trop grave je pense? |
|
| gouessej |
Posté le 22 Août 2008 à 07:52
|
|
 Messages : 337 GCPoints : 64624 |
S'il te plaît, ça pique les yeux, fais un effort, j'ai remarqué quelques fautes d'orthographe. Que vaut Dijkstra par rapport à A*?
Dernière édition le 22 Août 2008 à 07:53
|
|
| Mod |
Posté le 22 Août 2008 à 11:25
|
|
|
Messages : 4954 GCPoints : 2100823 |
Dijkstra est plus fiable que A*, mais plus lent, le premier effectuant une recherche exhaustive parmi tous les chemins viables là où le second prend le premier chemin qui atteint sa cible, et qui donc n'est pas forcément le meilleur. Privilégier résultat ou performances, telle est la question. |
|
| SEB |
Posté le 22 Août 2008 à 13:39
|
|
 Messages : 554 GCPoints : 103313 |
Citation :
La je ne suis pas certain de tout ce que tu as dit XD... Dijkstra est plus fiable?? sur quel critère? Plus lent.. on est d'accord... en moyenne. Un A* avec une heuristique de 1 est un Dijkstra. Donc A* a forcément le meilleur chemin si l'heuristique est bonne. Plus l'heuristique approxime bien la valeur réelle plus A* est rapide. A* peut renvoyer un chemin qui n'est pas le meilleur uniquement si l'heuristique Surestime la valeur réelle. Et dans ce cas il peut etre Pire que Dijkstra. En clair en pathfinding globalement A* est meilleur car on possède au moins l'heuristique de la distance euclidienne. Mais pour un problème ou on ne connait pas d'heuristique Dijkstra est à étudier également. Enfin Il y aurais encore beaucoup de choses a dire sur A* ^^ mais c'est déjà un bon début. @++ Seb
NextGine : 3D games engine
Nombre de lignes actuel : 77683 |
|
| Darktib |
Posté le 22 Août 2008 à 20:01
|
|
|
Messages : 4017 GCPoints : 347288 |
En général Djisktra est plus fiable... c'est a dire que bien programmé il trouve le chemin le plus court... mais est un peu plus lent qu'Astar. Enfin, apres ca dépend énormement de la zone a rechercher. Pour les heuristiques et couts il faut arrondir a mort pour éviter des perfs pourris. ex: aller horizontalement ou verticalement = 1; aller en diagonale = 1.4 - je parle là pour une matrice non creuse. Mais le plus interessant est de changer ces cout et de changer les regles de selection de cases pour personnaliser la recherche... Apres il y a aussi un systeme d'octree a détailler, bien que complexe, les matrices creuses, enfin, tout ce qui peut passer par la tete ; et je ne pourrait evidemment pas tout écrire. Sinon pour les fautes d'orthographes... a part les accents je ne pense pas en avoir fait beaucoup... 
|
|
| Mod |
Posté le 22 Août 2008 à 20:15
|
|
|
Messages : 4954 GCPoints : 2100823 |
@ SEB : par fiable, j'entends que Dijkstra donne un résultat de meilleure qualité, justement par cette recherche exhaustive du meilleure chemin possible. A* aura tendance à retourner l'un des meilleurs chemins, mais pas nécessairement le meilleur. Qui plus est, si l'on tient compte de l'algorithme brut, A* inclus le paramètre de distance là où Dijkstra ne prend en compte qu'un coût, plus facilement modulable qu'une distance, qui reste absolue. @ Darktib : j'ai corrigé quelques fautes ce matin ;). Edit : C'était des algorythmes et des lettres manquantes, surtout. Le premier piquait effectivement les yeux :p.
Dernière édition le 22 Août 2008 à 20:53
|
|
| Darktib |
Posté le 22 Août 2008 à 20:29
|
|
|
Messages : 4017 GCPoints : 347288 |
Ah merci. C'était quel genre de fautes? |
|
| Arcanis |
Posté le 23 Août 2008 à 13:49
|
|
 Messages : 35 GCPoints : 14109 |
Faux! L'article en français n'a pas été détruit! C'est juste que l'auteur à changé la disposition du site, et que les liens ne sont donc plus fiables. Adresse du tutoriel en français: http://blog.lalex.com/post/2003/09/15/Traduction-%3A-article-sur-le-pathfinding-A Voili voilou ... j'étais aussi tombé sur ce tuto lors de mes recherches et je me demandais où étais passé sa traduction. Une heure avant de penser à utiliser la barre "Rechercher" sur le site au lieu de Mr. Google 
Le PHP fait des jeux vidéos (enfin ... quand même pas de la 3D en temps réel ...).
Le PHP fait des sites internet. Le PHP ne fait pas votre café. |
|
| Darktib |
Posté le 23 Août 2008 à 18:33
|
|
|
Messages : 4017 GCPoints : 347288 |
Ah tiens, je ne l'avais pas vu... En fait le tuto ci-dessus n'est plus tres a jour niveau références, d'autant plus qu'une traduction sur le site du zero existe aussi... et pareil un peu partout^^ |
|
Voir le profil
Envoyer un message privé
Voir le site