A* vs Dijkstra pour un jeu de tactique

Bonjour,

Je lis partout que A* est préférable aux autres algorithmes de pathfinding pour la plupart des jeux.

Dans un contexte de jeu de tactique (déplacement par case) où l'on peut déplacer son personnage de plusieurs case, où chaque case à son propre coût de mouvement et où l'on veut pouvoir afficher le chemin pour aller sur une case lorsque celle-ci est survolée : Dijkstra n'est-il pas préférable ?

Je vais essayer d'éclaircir ma question : le fait de calculer le chemin avec A* à chaque survol d'une case n'est-il pas plus gourmand que de calculer tous les chemins d'un coup et se contenter de le retrouver au survol ?

Je sais que ça dépend de la taille de carte mais théoriquement : pour toute taille de carte ?

Désoler si je ne suis pas clair,

Pierre

:salut:

Citation:

---

Envoyé par thatPiero

Je lis partout que A* est préférable aux autres algorithmes de pathfinding pour la plupart des jeux.

---

Ce constat part du fait que Dijkstra calcule beaucoup trop de choses que strictement nécessaire : l'algorithme cherche à prouver qu'il a obtenu le chemin optimal, alors que, dans les graphes présents dans les jeux, la structure est telle que l'algorithme prend beaucoup de temps pour prouver qu'une solution rapidement trouvée est optimale. De plus, un jeu n'a pas toujours besoin d'un chemin optimal : un très bon chemin est suffisant (c'est-à-dire à peine un peu plus long que l'optimal, mais pas tellement).

Ici, au contraire, tu peux passer ton temps à calculer plus de choses que strictement nécessaire, puisque tu les utiliseras. À la condition que… lancer ton Dijkstra une fois ne soit pas plus lent que lancer un A* !
(D'ailleurs, Dijkstra ne calcule pas tous les plus courts chemins, mais seulement une bonne flopée, selon ce qui est nécessaire : si tu les veux vraiment tous, soit tu relances Dijstra pour les nouvelles destinations en réutilisant les résultats précédents, soit tu utilises Bellman-Ford.)

ok merci d'avoir pris le temps de répondre