A*

Salut !

Je suis en train de créé un programme pour trouver le chemin le plus court entre deux point dans un labyrinthe.

J’ai donc fait des recherche et est constaté que l’algorithme A* est celui qui me fallait, très précis sans demandé trop de temps pour trouver le chemin le plus cour.

J’ai codé cette algorithme avec 16 déplacements possibles.

Malheureusement, lorsque le cadrage deviens un peu grand, le temps de résolution devient trop long ?

Bon but étant ensuite d’intégré ce programme dans un moteur graphique pour créé un jeux de stratégie en temps réel.

Comment puis je faire pour optimisé cette algorithme ?

Merci

Vérifie déjà que tu l'as implémenté avec les bonnes structures de données et que tu n'as pas d'erreur grossière dans ton code, ou encore que tu utilises une distance pas trop compliquée.

Si c'est pour utiliser dans du temps réel, tu peux répartir tes calculs sur plusieurs frames ou utiliser des threads par exemple.

Ensuite si réellement c'est la taille des données à traiter qui est trop élevée, tu peux fragmenter ta carte en sous-zones, précalculer les plus courts chemins entre les zones, et n'utiliser A* qu'à l'intérieur de chaque zone.

Il y a encore pas mal d'optimisations plus ou moins compliquées à ce sujet, il me semble que ce lien n'était pas mauvais (à vérifier) :

http://theory.stanford.edu/~amitp/GameProgramming/index.html

Ok, je te remercie pour t'a réponse je vais vérifier tout ça.