Implémentation du pathfinding en Flash
Par -Alexandre LEGOUT aka LAlex- le lundi, août 25 2003, 11:46 - Projets - Lien permanent
J'ai essayé d'implémenter l'algorithme de pathfinding A* dans Flash, à l'aide du lien donné dans un post précédent.
Pour optimiser un peu, au lieu de créer des "listes" pour les 'open list' et 'close list', j'ai créé des tableaux à deux dimensions de même taille que la carte, ainsi accessibles directement par les coordonnées correspondantes au point de la carte que l'on utilise.Par contre, je n'ai pas implémenté le contour des murs, ce qui fait qu'on peut passer en diagonale de la case [ 2 ] à la [ 3 ], et de la [ 3 ] à la [ 4 ]. Vous voyez ici le visuel qui en résulte.
Mais le problème n'est pas la : j'ai fait en sorte que les déplacements en diagonale soient plus couteux que ceux en ligne droite (multipliés par 1.4), et j'ai intégré une notion de cout selon la nature du terrain (les cases vertes ont un coût de 10, et la case jaune un coût de 15). Vous constatez donc que le chemin emprunté n'est pas le bon ... mais pourquoi ?
En fait, l'algorithme A* fait une recherche dans les cases autour de la case en cours, et garde celle qui a le cout "total" le plus petit ("cout total" = "cout de parcour" + "cout restant à parcourir" : voir le lien avec l'algo). Or, dans ce cas précis, la case [ 2 ] et la case [ 2' ] ont le même coût, et le choix dépend donc de la comparaison faite lors du choix du minimum : soit un utilise '<' (strictement inférieur), soit on utilise '<=' (inférieur ou égal). Bref, dans les deux cas, il faut en choisir une, sans savoir s'il s'agit de la bonne ou pas.
Donc, je pense qu'il faut garder dans l'algorithme toutes les cases qui ont un coût minimum pour effectuer la recherche, et donc éliminer moins de cases, ce qui va évidemment se ressentir dans les performances ... :'(
Commentaires
il existe un algo qui calcul touts les plus court chemin (pcc) d'une carte.
l'algo est bien sur plus couteux qu'un simple plus court chemin (complexite de l'odre de N²)
Reste le probleme de la mise à jour (la carte qui evolue)
Sinon pour ce qui est de ton chemin, tu dois calculé tout les plus court chemin et te rappeler que du plus court mais c'est peut etre couteux..
En tout cas c'est du beau travail ce blog..
Je pense que le mieux est plutôt de calculer les plus courts chemins progressivement en parallèle (comme le veut l'algo A*), et des qu'un chemin devient plus long que l'autre, on l'élimine non ?
A+
en fait ce doit pas etre si couteux que ca...
pour le pathfinding tu connais le depart et l'arrivée.. non ?
si c'est le cas je vais essayer de retrouver le maniere de coder le graph en question..
ps: quand tu dis en parallele.. c'est plutot dans le sens en tache de fond ou au fur a mesur que le chemin avance...?
ps: est ce que l'on peux mettre des liens dans les comentaires .
a bientot.
si tu as vu les liens donnés auparavant sur ce même blog, il y en a qui concernent l'algo A*, référence en matière de pathfinding, dont le principe est :
- partir de la case de départ
- on teste les case autour et on attribue a chacun un "cout de déplacement depuis le départ", un "cout restant a parcourir", on additionne les deux
- on garde la case qui a la somme la plus petite, et on refais la même chose à partir de cette case.
Je suggérais donc de garder toutes les cases ayant lasomme la plus petite au lieu d'en garder une seule ... Si à un moment, pour un même nombre d'étapes, une des deux chemins a un cout plus important, on arrete de travailler dessus ...
Oui, tu peux mettre des URL dans les commentaires, elles seront automatiquement transformées en lien ...
Va voir sur le site d'andre michelle il a le meilleur pathfinder qui soit. Avec un system d'agent. Je ne me suis pas penché dessus, mais ça a l'air diabolique.
Fil des commentaires de ce billet