Des idées pour algo de pathfinding ?

Version imprimable

21/10/2008, 18h45
Mat.M

Des idées pour algo de pathfinding ?

Hello ,
le sujet a été abordé maintes fois mais pour ce que je veux faire c'est un peu complexe

Voilà le projet de jeu de tactique/stratégie sur lequel je travaille en C++ ( les graphismes ne sont pas définitifs -ils sont de ma création ).
Pour la progression sous la végétation les objets graphiques peuvent être triés dans la file de rendu éventuellement, j'ai mis cela en place ça fonctionne bien.
Le gros problème c'est évidemment trouver son chemin et gérer plusieurs unités :mrgreen:

http://www.megaone.com/mmarty/divers/pb_pathfind.jpg

( j'espère que l'image s'affiche bien )

Sur un clic souris, j'aimerais que les soldats évidemment trouvent leur chemin en contournant les obstacles mais si possible de manière fine par exemple en longeant les murs .

Dijkstra ? A* ?

Les soldats en se déplaçant sont évidemment animés.
J'ai pensé découper avec des cases et appliquer un algo de recherche en A*.
Avez-vous d'autres idées ?
( merci encore à khayyam90 )

Toutes les idées sont bienvenues 8-)
21/10/2008, 19h07
Alp

Salut Mat :)

Tout d'abord, :bravo: ç'a une très bonne tête je te souhaite bon courage pour la suite.

Ensuite, découper en cases et appliquer un A* est une solution possible effectivement. Une alternative c'est un algorithme de graphe, où le graphe serait fait de sorte que 2 noeuds ( = cases) sont liés <=> elles sont voisines sur ton terrain. Evidemment, tu ne prendrais que les cases sur lesquelles ils peuvent passer (par exemple pas les chalets :aie:).

Il y a énormément de documentation sur ces techniques. Tu pourrais nous dire ce que tu as déjà lu (à part le tuto de khayyam) ?
21/10/2008, 21h08
bafman

tu connait déjà le projet TACTIC sur lequel j'ai bossé, et comme j'ai fait l'ensemble de la partie pathfinding, je peut en parler des heures ;)

en gros, sur ce projet, ce qu'on a fait, c'est mettre en place un pathfinding hiérarchique. dans ce projet, le terrain est représente par une matrice de cases carré. les cases peuvent être passable ou pas et ont un type (route, herbe, foret...), jusque la, que du classique.
au début du projet, on a fait un simple A* sur la matrice, qui donnait des résultats correctes, mais ne supportait pas les cartes trop grandes ou les trop grand nombres d'unités.
du coup, ce que j'ai fait, c'est de créer un graphe de plus haut niveau. Ce graphe avait plusieurs contraintes qui sont intéressantes à étudier :
- il ne devait contenir que des formes convexes pour faciliter les calculs
- les nœuds du graphe devaient avoir la formes la plus proche possible d'un cercle (pour assurer que tout point à la limites du nœud est a peut près à la même distance du centre que les autres).
du coup, je me suis naturellement tourné vers des nœuds en forme de carré (c'est convexe et c'est ce qu'il y a de plus circulaire quand on a que des cases carré :mouarf:). chaque nœud du graphe ne continent que des cases de même sémantique (des cases du même type, passable, et avec un delta d'altitude faible pour prendre en compte le dénivelé dans le calcul du chemin)

du coup, on se retrouve avec un graphe de carré adjacents sur lequel on peut effectuer un pathfinding (il ne faut pas oublier de maintenir un lien case <-> nœud du graphe bidirectionel car généralement, on veut aller d'une case à un autre et non pas d'un nœud du graphe à un autre)

l'intérêt de ce graphe, c'est qu'on peut calculer un chemin approché bien plus rapidement que sur la matrice, qui va nous donner un couloir dans cette matrice dans lequel effectuer le pathfinding final.
Un autre effet de ce graphe, c'est qu'on peut conserver le résultat quand on fait des recherche de chemin pour des groupes d'unité proches.

Pour utiliser ce chemin, j'ai mis en place un système de masque qui permet de rendre temporairement une case non passable. Comme toutes les cases de la cartes sont rendu non passables sauf celles du couloir, on réduit très fortement le nombre de cases a visiter ;).
Dans un premier temps, le masque utilisé était binaire, mais ça posait des problèmes quand on a des nœuds de taille importante mais avec un petite jonction (par exemple, quand 2 carré ne se touchent que par une case) car du coup, ça contraignait trop le couloir qui était obligé de passé par la case de jonction alors que ce n'était pas forcement la meilleure solution.
Pour résoudre ce problème, on a utiliser un masque flottant qui ajoutait un surcout au cases. en fait, les cases contenu dans le chemin calculé par le graphe n'avait pas de surcout, les cases contenu dans les nœuds adjacents avait un surcout léger, les cases transitivement adjacentes un surcout fort et les autre avait un surcout "infini" qui nous assurait de ne pas les visiter.

sinon, pour l'algo a choisir, c'est bien évidement A* qui va te permettre, via une gestion de l'heuristique complexe, d'obtenir des comportement interessant tout simplement en changeant le cout des cases au runtime.

par exemple, dans TACTIC, pour faire longer la foret au unités lorsqu'elle était en mode furtif, on réduisait simplement le cout des cases en bord de foret, le A* faisait le reste. Pareil pour les colline, on augmentait le cout des case quand la case d'où l'unité venait était plus basse que la case d'où elle venait, ainsi, les unités avait naturellement tendance à essayer de contourner les collines...

bref, le principal lorsqu'on fait un A*, c'est de se laisser suffisamment de degré de liberté dans la modification de l'heuristique pour pouvoir obtenir des truc sympa.

d'ailleurs, un petit apport à l'heuristique qui est pas mal consiste à ajouter au cout d'une case le produit scalaire entre les vecteur normalisé (case courante, case suivante) et (case courante, destination finale). C'est un truc qui va permettre de discriminer les case de cout identique en choisissant celle qui est sur le chemin le plus droit vers l'objectif (car sinon, on se retrouve souvent avec des chemin qui zigzag en fonction de l'implémentation), et en plus, ça fait un lissage pour pas cher ;)

si tu veut t'amuser, sur TACTIC, du appuie sur ², ça ouvre la console, et ensuite tu tape help pour avoir l'aide sur les commandes accessibles. il y en a qui permettent d'afficher le graphe, de faire de recherche de chemin de tests et autres ;)

bon, j'espère que ce que j'ai écris n'est pas trop incohérent, car je n'ai pas le courage de me relire :aie:
21/10/2008, 22h14
Mat.M

Citation:

Envoyé par Alp

Salut Mat :)

Tout d'abord, :bravo: ç'a une très bonne tête je te souhaite bon courage pour la suite.

Merci mais je me demande si je n'ai pas vu trop ambitieux :oops:
D'un autre coté c'est frustant j'ai des graphismes qui sont ,je pense , relativement satisfaisants.

Citation:

Ensuite, découper en cases et appliquer un A* est une solution possible effectivement. Une alternative c'est un algorithme de graphe, où le graphe serait fait de sorte que 2 noeuds ( = cases) sont liés <=> elles sont voisines sur ton terrain. Evidemment, tu ne prendrais que les cases sur lesquelles ils peuvent passer (par exemple pas les chalets :aie:).

Oui je suis en train d'étudier cela je suis en train d'adapter le tuto de khayyam.
Bien qu'il soit excellemment fait je ne sais pas si je l'utiliserai il faut que j'étudie bien le problème. ;)

Citation:

Il y a énormément de documentation sur ces techniques. Tu pourrais nous dire ce que tu as déjà lu (à part le tuto de khayyam) ?

Pour dire la vérité je possède "Programming Game AI by Example" de Matt Buckland de chez Wordware mais c'est un chouaia compliqué il faut que j'investisse du temps pour tout décortiquer.
Sinon j'ai aussi Advanced Direct X programming de Peter Walsh qui traite également du problème

Merci pour la réponse

Citation:

Envoyé par bafman

tu connait déjà le projet TACTIC sur lequel j'ai bossé, et comme j'ai fait l'ensemble de la partie pathfinding, je peut en parler des heures ;)

Oui je l'ai regardé mais je vais re étudier le code.
Il me faut quelque chose de simple à exploiter c'est pour cela que le tuto de Khayyam est bien fait c'est rapidement exploitable

Citation:

en gros, sur ce projet, ce qu'on a fait, c'est mettre en place un pathfinding hiérarchique. dans ce projet, le terrain est représente par une matrice de cases carré. les cases peuvent être passable ou pas et ont un type (route, herbe, foret...), jusque la, que du classique.

Oui je vais commencer par cette voie là

Citation:

du coup, ce que j'ai fait, c'est de créer un graphe de plus haut niveau. Ce graphe avait plusieurs contraintes qui sont intéressantes à étudier :

je vais commencer par simple et après j'essaierai d'optimiser mais je retiens les idées

Citation:

d'ailleurs, un petit apport à l'heuristique qui est pas mal consiste à ajouter au cout d'une case le produit scalaire entre les vecteur normalisé (case courante, case suivante) et (case courante, destination finale). C'est un truc qui va permettre de discriminer les case de cout identique en choisissant celle qui est sur le chemin le plus droit vers l'objectif (car sinon, on se retrouve souvent avec des chemin qui zigzag en fonction de l'implémentation), et en plus, ça fait un lissage pour pas cher ;)

C'est un peu compliqué mais je vais regarder cela
Merci encore pour les idées ;)

Encore besoin d'aide :oops:
La carte du jeu est constituée de cases de 64*64 pixels et elle fait 128*128.
Bon j'ai pu implémenter un algorithme avec des noeuds, listes ouvertes et fermées.
Le pathfinding fonctionne bien et la recherche de chemin satisfaisante
Le gros problème : les déplacement sont moches, le perso se déplace de 64 en 64 ce qui fait très moche et saccadé.
Sur le click souris dans ma classe de personnage j'initialise une liste de waypoints retournés par le pathfinder.
Puis toutes les x ms avec la méthode Update la position courante est restituée de la liste.
J'ai pensé à une interpolation de points entre la position précédente et la nouvelle position avec Bresenham.
Une autre idée ?
Merci encore :D