Bonjour,

Je recherche actuellement des informations sur le pathfinding et sur les différentes méthodes employées.

J'ai déjà recueilli de nombreuses informations, mais je dois reconnaître que je suis un peu perdu. ^^

J'ai trouvé des renseignements sur certains algorithmes classiques de pathfinding tels que l'algorithme A* ou l'algorithme de Dijkstra.

Je suppose que chaque jeu utilise son propre système de pathfinding, qui sont autant de variations d'algorithmes plus généraux, mais j'aurais aimé savoir s'il existait de grandes méthodes "générales" répandues.

Il peut s'agir de méthodes atypiques ou très récentes, tout m'intéresse.

Je présume également que le pathfinding varie grandement en fonction du genre de jeu (course, simulation de foot, jeux de stratégies, FPS, etc ...).

Existent-ils des algorithmes connus, spécifiques à certains genres de jeux ?

J'ai également trouvé des vidéos à propos de Aiseek ou Kynapse qui permettent de gérer un pathfinding très abouti.
S'agit-il de "moteurs" dédiés au pathfinding ?

J'ai entendu parler d'une possible "accélération matérielle" dédiée à l'IA et plus particulièrement au Pathfinding.
Y a-t-il un rapport avec les moteurs évoqués précédemment ou ces deux notions sont-elles indépendantes ?

De simples noms de méthodes ou d'algorithmes répandus m'aideraient beaucoup dans ma recherche.

Si vous avez des adresses de sites traitant du sujet de manière assez générale et exhaustive, cela m'intéresserait grandement (pour l'instant, j'ai trouvé beaucoup d'informations techniques ou spécifiques à un algorithme).

Merci d'avance pour vos réponses !

P.S. : Je précise que je suis plutôt novice en la matière. ;)

«Je suppose que chaque jeu utilise son propre système de pathfinding, qui sont autant de variations d'algorithmes plus généraux, mais j'aurais aimé savoir s'il existait de grandes méthodes "générales" répandues. »

«J'ai trouvé des renseignements sur certains algorithmes classiques de pathfinding tels que l'algorithme A* ou l'algorithme de Dijkstra.»

De mémoire de mes cours d'IA l'algorithme A* est un algorithme heuristic totalement généraliste. Je ne peux pas trop t'en dire plus pour ma part je pense que tu as trouvé à peu près tout ce que tu cherchais maintenant yapuka.

Merci pour vos réponses.

En fait, je dois réaliser un exposé sur le sujet, c'est pourquoi j'essaie d'être le plus exhaustif possible (sans trop entrer dans le détail).

Je pensais illustrer différentes méthodes.

Pour l'instant, j'ai principalement trouvé l'algorithme A* et l'algorithme de Dijkstra.

Je voulais savoir s'il existait d'autres méthodes connues ou alors des techniques spécifiques à certains genres (RTS, jeux de course, ...).

Pour l'instant, je trouve beaucoup d’informations assez pointues. ^^

Le pathfinding, c'est la recherche du meilleur chemin dans un graphe. C'est un problème lié au problème plus général de planification, qui vise à produire des plans (séquences d'actions) en vue de la résolution d'un problème.
Djikstra et A* sont des méthodes canoniques de recherche de chemin.
Une sophistication possible est la planification dynamique, c'est à dire la prise en compte de l'évolution du problème dans le temps pour en rechercher la "meilleure solution". Une autre sophistication est la recherche multi-critères d'un meilleur chemin.
Dans le cadre des jeux video, ces deux sophistications ne sont pas forcément intéressantes (on fait souvent de grosses approximations dans les jeux vidéo parce que la performance des calculs compte plus que la fiabilité des resultats).

La spécificité des différentes applications du pathfinding ne vient pas en réalité de l'algorithme mais du domaine d'application, c'est à dire le graphe sur lequel tu vas chercher un meilleur chemin.

En clair : comment modéliser l'espace afin de trouver une bonne solution en un temps acceptable ? Comment paramétrer cet espace?

D'autres questions peuvent se poser : est-il vraiment utile de calculer un chemin d'un point A à un point B pour chaque unité du groupe dans un RTS, ou est-ce qu'il ne serait pas plus performant de calculer un seul chemin pour tous.

L'algorithme reste le même, mais la manière de l'appliquer change en fonction du problème annexe que l'on veut résoudre (recherche de performance, réalisme ou simplement définir correctement la qualité d'un noeud ou arc du graphe).

J'ai récemment étudié un algorithme de "pathfinding" dans un espace continu. Le principe était le suivant :

Tu as un agent qui souhaite se déplacer vers un point défini, on appellera vecteur directeur le vecteur entre ta position et ta destination. Dans ton univers tu as différents obstacles qui se dressent sur sa route. L'agent va donc repérer les points des obstacles qui sont les plus proches de sa propre position, puis il va déterminer pour chacun de ses points un vecteur de glissement (vecteur orthogonal au vecteur normal à ton obstacle dans le sens de ton objectif). La norme du vecteur de glissement est décroissante avec la distance à ta position. Ensuite, on calcule la somme de ton vecteur directeur et de tes vecteurs de glissement et ça te donne la direction à suivre. Et à chaque pas, tu reprends ces calculs. Bien implémenté, cet algorithme peut s'exécuter très rapidement. Cet algorithme a aussi pour avantage de plutôt bien s'adapter à un environnement en mouvement, avec A* si tu as des obstacles qui se déplacent sur ta trajectoire, tu es obligé de refaire les calculs.

Seulement cet algorithme est loin d'être parfait, d'une part il ne donne pas le plus court chemin, d'autre part il y a évidemment des cas où il ne parvient pas à aboutir à la destination (notamment s'il y a des obstacles concaves, ça demande de réaliser quelques adaptations).
Donc si ton espace est un labyrinthe, A* sera nettement supérieur dans tous les cas tandis que l'algo que je viens de présenter, sans adaptation, ne parviendra jamais à trouver la solution.

Kaoron, merci beaucoup pour toutes ces précisions.

Je pense savoir dans quelle direction orienter mes recherches à présent.

Plutôt que de rechercher des algorithmes précis, je vais essayer de trouver quelles sont les contraintes de pathfinding spécifiques aux différents genres de jeux.

Si vous avez des idées de sites sur lesquels je pourrais trouver ce type d'information, n'hésitez pas.

Je vais donc commencer par présenter les algorithmes A+ et Djikstra.
Ensuite, je parlerai des contraintes spécifiques à chaque genre (et des solutions trouvées si je les trouve ^^).

Puis j'évoquerai les différents moteurs de pathfinding existants.

Selon vous, je n'oublie rien qui entrerait dans ce thème ?

Aldebran, merci pour votre réponse.

Je crois que je n'ai pas tout à fait compris votre exemple.

j'ai essayé de réaliser un schéma à partir de ce que j'ai compris, pourriez-vous m'indiquer où j'ai fait erreur s'il vous plait ?

Schéma : http://www.hostingpics.net/viewer.php?id=765342pathfindingschma.jpg

Ok, là ça va être typiquement un cas où ça ne va pas marcher. L'algorithme présenté ne fonctionne bien qu'avec des obstacles strictement convexes (si il y a des obstacles concaves, il faut bricoler par derrière).

J'ai fait un schéma expliquant l'algo :
http://hpics.li/b2e4525

Tu fais la somme des vecteurs verts et de k*AB (où k est une constante à paramétrer) et ça te donne une direction à suivre, et en plus le mouvement résultant sera à peu près réaliste. Et imagine que les boules se déplacent, on voit que le mouvement sera adapté très rapidement. Aussi il n'y a pas de contraintes de connaissance de l'environnement : si ton agent ne perçois qu'une portion de l'environnement et qu'il connait sa position relative à son objectif, il peut quand même trouver un chemin.

Par contre avec un obstacle concave, on s'aperçoit tout de suite qu'on va rester coincé dans la concavité :
http://hpics.li/d55557c

L'idée dans ce cas c'est de sortir de cette zone. Mais c'est déjà loin d'être évident de repérer qu'on est face à un obstacle concave, donc si c'est possible cette donnée sera stockée directement dans le fichier de ta map.

Dans les RTS il est frequent de calculer un plus court chemin mais que les unites ne le suivent pas forcement a la lettre pour evider que les unites se deplacent en file indienne. Au lieu de ca, une des unite suit le chemin et les autres suivent la premiere unite en conservant une distance constante.

Merci, je crois que je commence à comprendre.

J'ai trois petites questions par rapport au nouveau schéma :

- Plus le facteur k est proche de 0 (entre 0 et 1) et plus le contournement est "anticipé"/rapide si je comprends bien ?
- Que se passe-t-il si l'obstacle convexe se trouve exactement dans l'alignement de la trajectoire entre A et B, la norme du vecteur de glissement est nulle non ?
- Pourquoi est-il nécessaire d'additionner tous les vecteurs de glissement des objets à proximité de l'agent ? Ne suffit-il pas de considérer le vecteur de glissement de l’obstacle uniquement (celui qui se trouve directement sur la trajectoire AB) ?
Car en additionnant tous les vecteurs, cela peut engendrer un conflit non ?
J'ai repris votre exemple pour illustrer mon interrogation : http://www.hostingpics.net/viewer.php?id=824507Pathfinding02.jpg

La trajectoire rouge correspond à l'addition des vecteurs de glissement et du vecteur AB.

Godrik, merci pour cette précision.

Je suppose qu'il existe des ajustements dans l'algorithme lorsque l'unité de référence contourne un obstacle en le frôlant. Car admettons qu'une unité aie une distance constante par rapport à l'unité de référence, elle pourrait potentiellement se retrouver à passer à travers un angle que la première aurait juste frôlé ?
(Peut-être que dans ce cas de figure, l'unité suivra exactement mais temporairement le chemin de la référence pour éviter la collision).

En tout cas, merci pour vos réponses !

oui, j'imagine.

"- Plus le facteur k est proche de 0 (entre 0 et 1) et plus le contournement est "anticipé"/rapide si je comprends bien ? "

Oui on peut dire ça.

"- Que se passe-t-il si l'obstacle convexe se trouve exactement dans l'alignement de la trajectoire entre A et B, la norme du vecteur de glissement est nulle non ? "

D'après ton schéma, j'ai l'impression que tu calcules la norme du vecteur de glissement de manière à ce qu'il rejoigne la droite (AB). A vrai dire, la norme du vecteur de glissement dépend uniquement de la distance par rapport au point A et est généralement du type ||g|| = k/d² où k est une constante et où d est la distance entre le point A et le point de l'obstacle le plus proche du point A.
Autrement dit, le vecteur de glissement va être très important si tu es proche de l'obstacle, et très faible si l'obstacle est éloigné.

"- Pourquoi est-il nécessaire d'additionner tous les vecteurs de glissement des objets à proximité de l'agent ? Ne suffit-il pas de considérer le vecteur de glissement de l’obstacle uniquement (celui qui se trouve directement sur la trajectoire AB) ? "

Tu n'es pas obligé de calculer les vecteurs de glissement pour tous les obstacles (notamment pour ceux qui sont trop loin ou derrière toi), mais si tu ne tiens compte que d'un seul obstacle je pense qu'il y a un risque de foncer dans un autre obstacle en cas de déplacement trop rapide.

"Car en additionnant tous les vecteurs, cela peut engendrer un conflit non ?
J'ai repris votre exemple pour illustrer mon interrogation : http://www.hostingpics.net/viewer.php?id=824507Pathfinding02.jpg

La trajectoire rouge correspond à l'addition des vecteurs de glissement et du vecteur AB. "

A vrai dire, sur ce schéma les normes des vecteurs de glissement ne sont pas cohérentes. Normalement la norme du second vecteur doit être quasiment aussi grande que celle du premier. Puis au fur et à mesure que tu vas te rapprocher de l'obstacle en bas, la norme du vecteur de glissement va augmenter, ce qui va permettre à ton agent de décrire une courbe assez réaliste.

A part ça, l'algo que j'ai présenté est très imparfait. J'imagine qu'il existe des variantes de cet algorithme nettement plus travaillées et plus performantes. Ce genre d'algo étant très intéressant dans le cas où on ne connait pas complètement l'environnement ni la façon dont il va évoluer, j'imagine qu'il doit y avoir pas mal de recherche là-dessus.

En effet, c'est une confusion de ma part.
Je comprends mieux maintenant.

||k/d²|| : je dois dire que je ne l'aurais pas déduite intuitivement. ^^

Je suppose que le choix est arbitraire, tant qu'il correspond à l'effet souhaité : augmenter la norme du vecteur de glissement plus rapidement que de façon linéaire pour avoir une trajectoire courbe et plus "réaliste" ?

Merci beaucoup pour toutes ces explications et pour votre patience !

"||k/d²|| : je dois dire que je ne l'aurais pas déduite intuitivement. ^^ "

C'est vrai que j'aurais du le préciser dès le début, ça aurait été plus clair

"Je suppose que le choix est arbitraire, tant qu'il correspond à l'effet souhaité : augmenter la norme du vecteur de glissement plus rapidement que de façon linéaire pour avoir une trajectoire courbe et plus "réaliste" ? "

Tout à fait. Tu peux choisir une autre norme mais je ne pense pas que ça rendra pareil. A vrai dire cet algorithme que je t'ai présenté n'est pas franchement mathématique comme l'est l'algorithme de Dijsktra, il y a plein de paramètres différents qu'on peut ajuster un peu au feeling selon le problème auquel on est confronté.

D'accord, je vois le genre.

Mais c'est un système intéressant je trouve.

En tout cas, merci beaucoup pour toutes ces précisions.