Bonsoir,
Suite a de nombreuses demandes par MP j'ai décidé de faire un tuto sur le pathfinding. Ce tuto ne fournira pas de code cependant, je fourni une source d'un pathfinding A* sur une grille qui explique bien son fonctionnement. Demandez moi la source par MP.
Je vous redirige tout de suite sur ce lien, Lalex explique l'algorithme du pathfinding A*:
http://blog.lalex.com/post/2003/09/15/T ... hfinding-A
Pour pouvoir faire un pathfinding il nécessite:
- La lecture des d2p pour obtenir les données de la map (cellid marchable ou non) la dll de maxilia vous offre cette possibilitée
- Receptionner les données du 226 (récuperer notre cellid actuel)
On y va !
Comme vous le savez la map de dofus est regroupé en cases (Cellid) que l'on nomme par des nombres allant de 0 à 559 soit 560 cases.
- Il vous faudra tout d'abord savoir convertir une cellid en coordonnées sous la forme X ; Y comme les maps de dofus : [X;Y].
- Il vous faudra aussi a partir de deux coordonnées savoir calculer le nombre de cases les séparant
Regrouper ces deux fonctions en une class qui contiendra toute les cellids de la map. Vous nommerez cette liste "liste ouverte", elle regroupera toute les cellids de la map sur les quelles on peux marcher à l'aide des d2p.
Pour mon tutoriel vous n'aurez pas besoin de "liste fermée" regroupant les obstales. Cela ne nous sert à rien.
Maintenant on passe au choses sérieuses:
On supprime de la liste ouverte la cellid sur la quel on est.
On ajoute dans une nouvelle liste privée les 8 cells se trouvant autour de la cell sur la quelle on est.
On va calculer le cout F ce qui va nous permettre de savoir la quelle d'entre elle va nous permettre de trouver le chemin le plus rapide.
Le cout F = G + H
- G est une valeure correspondant au type de cell, il y a types types:
Diagonales, horizontal et verticale . Diagonales = 14 et horizontal et vertical = 10
- H est le nombre de cases séparant la cell actuelle et la cell d'arrivée
Donc on calcul le cout F pour chacune des cells de notre liste privée et on prend celle qui a le cout F le plus bas. Si deux cases ont le même cout F vous les départagez en comparant le cout G qui sera obligatoirement différent. Elle devient notre cell actuel. Et on va stoker tout notre chemin dans une nouvelle list public que l'on va appelle chemin. On l'ajoute donc à la liste et on recommence tout.
C'est a dire qu'on va reprend les 8 cells autour de nous, calculer le cout F, le comparer ect...
On arrete notre boucle lorsque la cell d'arrivée est ajoutée à la liste chemin.
Je récapitule :
Creer une liste ouverte et une classe qui contiendra les cellid marchable de la map, elle calculera a partir de la cellid ces coordonnées et calculera leur cout H.
Bouclez ces actions :
- Creer une liste qui contiendra les 8 cellids autour de la cell actuelle en vérifiant que ce ne sont pas des obstacles.
- Calculer leur cout F (F = G + H)
- Ajouter celle qui a le cout F le plus bas dans la liste chemin, la supprimer de la list ouverte. Elle devient la cell actuelle. Si deux cells ont le même cout F, comparez leur cout G.
On arrete la boucle quand la cell actuelle devient la cell d'arrivée.
Voilà, je vous rapelle que je fourni une source par MP.
J'ajouterais des screens plus tard.