Bonjour à tous,
Pour coder un jeu, assez basique, il me fallait trouver un algorithme de plus cours chemin :

Pour l'instant, voici l'algorithme que j'avais prévu :

Au chargement de la map, je possède une liste de points considérés "points repères". Je pré-calcule tous les plus cours chemins entre tous couples de deux points (en ne considérant que les obstacles fixes).

En jeu, pour bouger de A vers B, je cherche le point repère le plus proche de A (P1) et le point repère le plus proche de B (P2).
Et mon trajet se résume à A->P1->trajet pré-calculé->P2->B

Voici mes questions :

Cet algorithme à le défaut de ne pas tenir compte de la taille de mes objets (vu que quand je pré-calcule mes chemins, je ne connais pas encore la taille de l'objet qui va bouger). Y a t-il une solution simple pour y remédier ?

Cet algorithme ne tient pas non plus compte des obstacles "dynamiques". Quand il existe un obstacle dynamique, j'improvise un A* ?
Par exemple, si entre A et P1, il y a un obstacle dynamique, j'applique un A*.

Il me faut tout pré-calculer au chargement de la map, or, si on veut que le chemin ne semble pas trop bizarre, il me faut un nombre important de points repères. Pour des soucis de performances, y a t-il un algorithme plus rapide que de faire n² dijkstra ? Je fonctionne sur un graphe orienté (pour permettre des passages dans un sens et non dans l'autre) représenté par des sommets d'adjacence.

Pensez vous que cet algorithme est viable ?

Merci.

Je code en c++.