Je te conseille, comme Tasslehoff l'a proposé, d'utiliser l'algorithme A*. Il est très rapide et très simple d'utilisation.
Chaque noeud de l'algorithme doit garder en mémoire : La distance entre le point de départ et la position actuelle (disons G), la distance entre la position actuelle et le point d'arrivée (à vol d'oiseau, appelons ça H), la somme de ces deux variables (disons F), et enfin un pointeur vers le noeud parent.
L'algorithme est géré par deux listes, une liste dite ouverte, et une autre dite fermée. La liste fermée contiendra tous les noeuds qui ont déjà été "vérifiés". Au tout départ, la liste fermée doit donc être vierge, et la liste ouverte doit contenir le premier point (le point de départ).
À chaque tour de boucle, l'algorithme doit aller chercher le noeud (dans la liste ouverte) possédant le plus petit F. Ce noeud doit passer dans la liste fermée, et on va ajouter 4 (ou 8 si tu veux inclure les diagonales) noeuds autour de cette position si c'est possible (donc si il n'y a aucun obstacle). On vérifie également qu'il n'y a pas un noeud dans la liste fermée sur cette position. Si tout est bon, alors on vérifie si il n'y a pas un noeud dans la liste ouverte à cette position, si il n'y en a pas : On l'ajoute, sinon, on modifie l'existant (c'est-à-dire on recalcule le G, et le F du coup, et surtout on modifie le noeud parent).
Ensuite, dès qu'il y a un noeud "fermé" à la position d'arrivée, cela veut dire que l'algorithme est fini. Il ne te reste plus qu'à repartir de ce noeud et à aller de parent en parent pour retrouver le chemin.
Voilà, j'espère avoir été assez clair. L'avantage de cet algorithme c'est qu'il est relativement rapide, donc parfait pour les intelligences artificielles. Après, il ne choisira pas forcément le chemin le plus rapide à chaque fois (mais la plupart du temps si), mais arrivera toujours à destination.
Si tu cherches un algorithme encore plus complexe, alors dans ce cas je te conseille d'aller jeter un coup d'oeil sur l'algorithme Djikstra (comme l'a cité Grim).
J'avais réalisé cet algorithme sur RPG Maker 2003, il faut que je réupload le projet.
|