Dll algorythme de recherche de chemin en a star, a*, fasm

Soyez le premier à donner votre avis sur cette source.

Vue 5 893 fois - Téléchargée 1 330 fois

Description

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.

Conclusion :


Si vous avez un conseil d'optimisation ou autre faites moi signe ;)

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
20
"rep movs" sont des instructions du temps jadis qu'il convient de remplacer par une boucle perso correctement écrite. Du code perso ne forcera pas obligatoirement les PUSH POP de ESI et EDI, on emploiera les registres libres à ce moment. Depuis le Pentium (c'est pas hier...), une boucle avec des instructions bien parallélisées battra un "rep movs" à tout coup.

Ce qui anéantit gravement les perfs au moins autant, c'est l'APPEL (et donc le FAR JMP suivi du retour) vers la dll externe (kernel32 ici).
Messages postés
3
Date d'inscription
jeudi 19 juin 2008
Statut
Membre
Dernière intervention
30 avril 2009

Si tu debug RtlMoveMemory tu vois très vite qu'elle est basée sur une instruction "rep movs" qui est difficilement plus optimisable.
Pour les push/pop de ecx et edx, je vais corriger ça.
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
20
des appels RtlMoveMemory dans du code ASM, ouh la....
Tu nous parlais vitesse, bein c'est pas avec des appels sur dll externe que tu y gagneras, surtout pour un truc si simple à coder en local. Un compilo C correct remplace l'appel par le code inline, il va te battre à tout coup.

idem des ralentissements en entrée et sortie de quasi chaque fonction.
EAX, ACX et EDX sont à considérer comme écrasés après un appel de fonction, inutile de les PUSHer POPer.

L'ASM ne donne aucune garantie de perfs, on sait seulement qu'on "peut" en obtenir avec de très gros efforts d'optimisation suite à une longue pratique.

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.