Je cherchais un algorithme qui me trouvait un chemin entre deux points avec des obstacles réutilisable, c'est à dire en DLL.
Comme c'était impossible à trouver j'ai décidé de le coder moi même :)
Le but était qu'il soit utilisable dans un jeu, j'ai donc opté pour l'assembleur pour avoir une vitesse d'exécution maximale.
Le source se décompose en deux parties, la partie gestion de la fenêtre (main.asm)
et la partie gestion de la dll (astar.asm)
La première partie n'est pas commentée car elle n'est pas importante.
La seconde est commentée car elle constitue le coeur du programme.
Le programme est compilé sous FASM (www.flatassembler.net).
L'algorithme est basé sur l'A* (voir www.siteduzero.com/tutoriel-3-34333-le-pathfinding -avec-a.html) mais j'ai ajouté une modification qui permet de choisir un chemin rapide à calculer ou un chemin plus cours.
La fonction principale du programme est "PathFinding"
elle prend les arguments suivants :
DebutX & DebutY : Coordonées du point de depard
FinX & FinY : Coordonées du point d'arrivée
PointeurTableau : Adresse du tableau ( le tableau ne sera utilisé qu'en lecture)
Largeur & Hauteur: Hauteur et largeur maximales du tableau
FonctionEvenement: Adresse de la fonction qui recevra les évènements
Details : Si > 0 alors on affiche les détails et on fait un sleep entre chaque calcul de case
VarStop : Adresse d'une variable qui sera vérifiée a chaque calcul de case, quand cette variable est à 1, la fonction s'arrête
Compteur : Adresse d'une variable que l'ont remplira du nombre de cases calculées
Constante : C'est le paramètre qui permet d'optimiser le calcul du chemin ou non, il est utilisé de la manière suivante :
Total = Poids + Distance * Constante
Où Poids est le poids parcouru, distance est la distance aproximative pour arriver jusqu'à l'arrivée, ce parametre permet donc de modifiier l'importance de la distance par rapport au poids.
Par exemple, avec la constante mise à 0 le chemin recherché sera celui qui aura le poids le plus faible donc le chemin le plus cours.
Le programme est optimisé pour la vitesse d'exécution, il prend donc un certain nombre de place en mémoire qui peux aller jusqu'à plusieurs Mo.
Les coordonnées étant enregistrés sur des words, la valeur maximale du repère est de 65535.