Discussion :

[NoIdea]

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++.

[Invité]

Quelle est la taille de ton graphe ?
A mon avis, le fait que tu as des obstacles dynamique rend ton pré-calcul inopérant. Si ton graphe n'est pas trop gros, un A* devrai être largement assé performant pour calculer ton chemin "a la volée".

Pour la taille de l'objet, je ne comprend ce que tu veux dire, il faudrait que tu en dise plus sur ton jeu...

[NoIdea]

On peut imaginer avoir 500 "points repères".

Si ton graphe n'est pas trop gros, un A* devrai être largement assez performant pour calculer ton chemin "a la volée".

C'est possible, mais dans le cas d'un A*, je n'ai plus réellement de "point repères". Il se peut donc que le graphe soit nettement plus gros.

A mon avis, le fait que tu as des obstacles dynamique rend ton pré-calcul inopérant.

J'avais imaginé dans par exemple la liaison A->PointRepere1 qui est sensée être en ligne droite sans les obstacle dynamique appliquer un A* pour gérer les obstacle dynamiques. De plus, ce système peut me permettre d'insérer de nouvelles propriété : on pourrait "pousser un autre personnage".

Pour la taille de l'objet, je ne comprend ce que tu veux dire

Un objet (ou personnage) est caractérisée par un polygone décrivant sa forme. Or, un passage peut être suffisamment large pour un personnage et trop étroit pour un autre.

L'autre problème d'un A*, c'est qu'il s'agit d'un algorithme qu'il me faudra refaire souvent (si le delta t est trop grand, il peut y avoir des collisions).

[Invité]

Dans ce cas, je te suggère de faire des mesures :
tu récupère un A* déjà codé sur internet, et tu l'applique sur ton graphe le plus grand possible. Tu verras comme ça s'il est assé performant pour ton problème.

En fait, ça va dépendre de ton problème :
- Si on considère ton plateau comme un ensemble de pixels (chacun est un sommet relié par des arcs à ses 4 voisins) :
* si ton plateau de jeu est composé de petits obstacles isolés, A* devrai être casiment instantané (complexité N).
* si tu as beaucoup d'obstacles de type "mur", qui obligent de faire un long détour pour contourner : A* risque de s'enfoncer dans une impasse et de perdre du temps à en sortir.

- Si on considère ton plateau comme un ensemble de sommets (les points repères), il faut bien réfléchir à la façon dont du créé ton graphe : tu peut relier tes sommets de proche en proche, par exemple par une triangulation de delaunay. Tu as des librairies qui font ça très bien. Avec ça, a mon avis un A* "à la volée" devrai suffire.

Par contre pour ton histoire de taille de tes objets, je n'ai pas trop d'idée. A mon avis le seul moyen de gérer ça c'est de donner une "capacité" à tes arcs correspondant à la largeur min du chemin emprunté. Par contre, comment calculer cette capacité... Aucune idée !

[NoIdea]

Si on considère ton plateau comme un ensemble de pixels (chacun est un sommet relié par des arcs à ses 4 voisins)

A priori, je ne gère en aucun cas les pixels, et mon personnage peut bouger dans plus de 4 directions.

si ton plateau de jeu est composé de petits obstacles isolés, A* devrai être casiment instantané (complexité N).

Ces obstacles seront présents mais pas uniquement.

si tu as beaucoup d'obstacles de type "mur", qui obligent de faire un long détour pour contourner : A* risque de s'enfoncer dans une impasse et de perdre du temps à en sortir.

C'est justement le problème.

Par contre pour ton histoire de taille de tes objets, je n'ai pas trop d'idée. A mon avis le seul moyen de gérer ça c'est de donner une "capacité" à tes arcs correspondant à la largeur min du chemin emprunté.

C'est parfait :
Chaque arc possède une longueur mini, calculée avant (suffit de calculer distance(obstacle, droite) ).

Merci.