Jeux Indépendants Explications sur le Pathfinding. [Archives]

Voir la version complète : Jeux Indépendants Explications sur le Pathfinding.

LPTheKiller

05/09/2009, 20h20

Parmi toutes les difficultés qui se présentent lors de la réalisation d’un jeu, celle du pathfinding est sans doute loin d’être la plus simple à résoudre.

Profitant de la rubrique DevBlog prévue à cet effet, nous allons parler ici d’un type de pathfinding particulier que j’ai mis au point pour Ronin Blades (http://www.canardpc.com/news-38693-ronin_blades___mon_jeu_de_baston_de_samura__s.html ), un des jeux flash que je développe personnellement.

Qu’est-ce que le pathfinding ? C’est l’ensemble des algorithmes qui vont permettre à l’ordinateur de calculer le chemin que doit emprunter un personnage contrôlé par l’IA pour aller d’un point A à un point B tout en évitant les obstacles et en parcourant la distance la plus petite possible.

Si la plupart des jeux flash, parce qu’ils sont vus de côté ou parce que leur réalisation est primaire, n’ont pas besoin de pathfinding, ce n’était pas le cas de Ronin Blades, qui est vu de haut et présente des environnements contenant des bâtiments et autres obstacles qu’il faut contourner et derrière lesquels il est possible de se cacher.

J’aurais pu me renseigner quelque peu sur le sujet et tenter de copier ou même d’utiliser des algorithmes déjà existants, mais cela aurait été contraire à ma démarche traditionnelle, qui est de tout programmer moi-même.
Ainsi, j’ai dû faire grand usage de mon imagination et de mes connaissances en algo, que j’ai acquises au fil des années de manière autodidacte, et bien sûr en mathématiques.
Et alors qu’il me semble que bon nombre des pathfindings ordinaires se basent sur une grille de cases "ouvertes" ou "bloquées" représentant le terrain, j’ai opté pour une résolution vectorielle du problème, c’est-à-dire en utilisant des formes virtuelles et des équations mathématiques pour détecter les collisions, au lieu de bêtement "tester" les cases d’un grossier damier virtuel.
En l’occurrence, comme je voulais réaliser la chose en un temps raisonnable et ne pas m’embêter de manière exagérée, j’ai décidé que les formes représentant les obstacles seraient toutes des rectangles non inclinés à longueur et largeur variable, largement suffisants pour modéliser l’environnement de Ronin Blades.

Je vous propose ici de détailler comment fonctionne cet algorithme, et quelles en sont les limites.

Étape 1 :
Le principe de base est le suivant : Le plus court chemin reliant les points A et B étant la ligne droite, l’algo va d’abord s’occuper de tester si le chemin direct de A à B est dégagé. Si c’est le cas, évidemment, il ne se posera pas d’autre question et prendra cet itinéraire.
En revanche, si la résolution mathématique détecte une collision de la trajectoire avec un objet bloquant l’accès, il identifiera le côté de l’objet que la trajectoire touche en premier (le côté du haut, du bas, de droite ou de gauche), et il trouvera les deux coins adjacents à ce côté, que nous appelleront C et D.

http://pierre.parreaux.free.fr/Images/PathFinding/ABCD_PathFinding_Algo_N1.JPG

Étape 2 :
L’algorithme va alors se scinder en deux voies possibles : Passer par C ou passer par D.
Étudions le cas de la voie C.
L’algo va déterminer s’il est possible de se rendre en C directement et sans encombre. Si cela est possible, il va s’y rendre directement. Si, au contraire, il rencontre un nouvel obstacle, il créer un sous-processus qui réitérera l’étape 1 et les suivantes avec ce nouvel obstacle, en tentant de le contourner lui-aussi.
Le sous-processus, qui fonctionne de la même manière que le principal, se chargera de trouver le meilleur itinéraire pour se rendre au point C. Cet itinéraire s’ajoutera simplement à l’itinéraire principal, calculé dans le processus principal, et l’algorithme pourra continuer.

Étape 3 :
A partir du point C, nous allons simplement reprendre l’algorithme depuis l’étape 1 en remplaçant A par C : C'est-à-dire, regarder s’il est possible de se rendre en B depuis le point C, et si l’on rencontre une nouvelle face de l’objet contourné, l’algo va chercher à continuer le contournement en rejoignant un autre des coins de l’objet.

http://pierre.parreaux.free.fr/Images/PathFinding/ABCD_PathFinding_Algo_N2.JPG

http://pierre.parreaux.free.fr/Images/PathFinding/ABCD_PathFinding_Algo_N3.JPG

Étape 4 :
Une fois tous les itinéraires possible arrivant à leur but calculés (car sur tous ceux tentés, bon nombre n’aboutissent à rien), le programme se charge de calculer celui qui est le plus court.
(Si aucun chemin n’arrive au but, on choisira le chemin dont le point d’arrivée est le plus proche possible du point B.)

Voici une situation plus complexe schématisée :
http://pierre.parreaux.free.fr/Images/PathFinding/ABCD_PathFinding_Algo_N4.JPG

Des screens du jeu en mode debug quand j'ai programmé mon algo :
http://pierre.parreaux.free.fr/Images/PathFinding/RB_Pathfinding.JPG

L’algorithme, assez complexe, se basant sur des appels récursifs de fonctions dans elles-mêmes, et donc sur la création de boucles d’appels fonctionnels, il est nécessaire d’empêcher ces boucles d’être infinies en implémentant diverses vérifications : Par exemple, empêcher l’algorithme de passer deux fois par le même point.

Malgré tout, l’algorithme décrit est limité et ne répond pas à toutes les situations, car je me suis ici contenté de n’en expliquer que les principes fondamentaux.
Par exemple, il est impossible (en n’essayant de rejoindre que les deux coins adjacents au côté touché), de trouver une solution pour sortir d’un cul-de-sac.

Je suis en train de compléter le code afin qu’on puisse sortir d’un cul-de-sac, mais cela n’est pas encore terminé, et même si je sais globalement comment faire, cela risque de prendre un peu de temps (surtout parce que j’ai d’autres projets en cours).

http://pierre.parreaux.free.fr/Images/PathFinding/ScreenShot005.jpg

Voilà, j’espère que ceci a éclairé vos esprits avides de connaissance et que vous avez globalement compris. J’ignore si j’ai été assez clair, mais j’espère que vous prendrez dorénavant mieux conscience de la difficulté que représentent le genre de problèmes que pose la programmation d’un jeu, et en particulier celle de l’intelligence artificielle.

http://pierre.parreaux.free.fr/Images/PathFinding/ScreenShot004.jpg

Voir la news (1 image, 0 vidéo ) (http://www.canardpc.com/news-39155-explications_sur_le_pathfinding_.html)

sukiyaki

05/09/2009, 20h38

Génial, ça éclairci pas mal de questions :)
Merci pour les explications !

Aghora

05/09/2009, 20h54

Par contre les schémas ne sont pas très clairs, il manque une légende et un commentaire.

le_guide_michelin

05/09/2009, 20h57

C'était passionnant à lire, et très instructif. Tout ce travail force le respect.
Mais t'es un grand malade :O
Tout ce travail. Moi pour en faire le quart, je réclame un salaire. Alors se déchirer le crane pour un jeu gratuit ça me dépasse.
Moi aussi j'ai eu ma période bénévole, à l'époque où j'étais actif dans la communauté mandriva, Amiga (et ouai, y'a des nostalgiques qui travaillent, et développent encore dessus) handicap international.
Mais le système m'a bouffé. Le loyer, les factures, une femme, les emmerdes.... La vie quoi.

A l'époque j'étais respecté, dans ces trois communautés. Maintenant elle m'interdit d'avoir plus d'un PC, et ne me laisse plus que le droit d'aller poster des conneries sur les forums :'(
Ne te laisses pas embrigader comme moi.Le feu sacré brule encore en toi. Fait tout pour le préserver.
TUES TA FEMME AVANT QU'ELLE NE L'ÉTEIGNE

Mambba

05/09/2009, 21h09

Oui, les schémas me laissent perplexes o_O" entre les C, les P, les points qu'on sait pas quesqueca veut dire
Bon je suis pas bête et j'ai quand même su remplacer B par P et C par les points qu'on voit sur les dessins, mais c'est pas pour autant que j'ai tout pigé les lignes ... @_@

Mais pas mal les explications ;)

Tout ça me rapelle mes braves personnages qui se payaient les murs dans Baldur's gate & co.

sepandemic

05/09/2009, 21h12

Je suis d'accord , le pathfinding est un véritable enfer a programmer et a créer .

Personne n'a idée de cette enfer avant de l'experimenter sois-meme.
Perso j'ai eu ce problème en essayant de développer un petit FPS sous directx .
Cependant il existe 2 possibilités ou "feintes" pour éviter de subir ce calvaire :

A ) la plus facile et rapide est de créer des "hiddent waypoints" ou bien points relais dans la map que L'IA va suivre , c'est le principe le plus repandu dans les jeux "dans half life 2 épisode 1 , en mode commentaire, dans l'hôpital les développeurs exposent ce problème et vous montrent en live dans le niveau les waypoints installés " .

B ) téléporter l'IA pres du joueur dans un angle invisible "detour d'un couloir par exemple" ou le monstre par exemple apparait ou disparait brutalement a coté du joueur, cette technique est utilisé dans les survival horror et les jeux d'actions "GTA" .

Pour le reste , il-y-a l'enfer ; l'algorithme !!!! Mais la il faut être chevronné en programmation pour le créer.
"exemple du jeux F.E.A.R qui utilise un des algorithme de pathfinding les plus élaborés jamais vu".

Quand a ton jeux je te conseil d'utiliser la technique "hiddent waypoints" pour gagner du temps.

Ton article m'a rappelé bien des souvenirs ! Merci !

edenwars

05/09/2009, 21h27

Il y'a des cours intéressant sur le site du zero aussi.

http://www.siteduzero.com/tutoriel-3-34333-le-pathfinding-avec-a.html
http://www.siteduzero.com/tutoriel-3-35706-le-pathfinding-avec-dijkstra.html

A voir

Rodwin

05/09/2009, 21h40

Pour l'expérimenter actuellement, je te confirme que la solution de la grille (avec les points de passages possibles et impossibles) est effectivement basique. Mais elle a le mérite d'être rapide : ton calcul du chemin le plus court n'est alors qu'un parcours des cases "possibles" entre deux points. S'il faut plus de boucles pour trouver le résultat, ceux-ci sont rapides à atteindre (utilisation d'index sur la grille), et à analyser. De plus, tu peux facilement gérer plusieurs niveaux de possible selon les mêmes cases : les cases visibles (cas de la visibilité limitée à une certaine distance), monter ou descendre d'un niveau (gestion basique de la 3D). Les possibilités sont nombreuses même si les ficelles du calcul sont tellement grosses qu'on dirait des cordes.

Jeremy

05/09/2009, 23h04

Je conseille tout de même tout ce qui est théorie des graphes : il y a déjà des gros bourrins qui ont bien galéré sur des algos pas trop dégueulasses. Bon après, il faut arriver à générer le bon graphe.

LPTheKiller

05/09/2009, 23h47

Par contre les schémas ne sont pas très clairs, il manque une légende et un commentaire.

Oui, les images sont nulles, en fait c'est parce que j'avais la flemme de faire plein de schémas, j'ai juste pris des screens des représentations qui me servaient à moi pour coder et que je suis seul à pouvoir comprendre.
Je ferai des beaux schémas en remplacement.

C'était passionnant à lire, et très instructif. Tout ce travail force le respect.
Mais t'es un grand malade :O
Tout ce travail. Moi pour en faire le quart, je réclame un salaire. Alors se déchirer le crane pour un jeu gratuit ça me dépasse.
Moi aussi j'ai eu ma période bénévole, à l'époque où j'étais actif dans la communauté mandriva, Amiga (et ouai, y'a des nostalgiques qui travaillent, et développent encore dessus) handicap international.
Mais le système m'a bouffé. Le loyer, les factures, une femme, les emmerdes.... La vie quoi.

A l'époque j'étais respecté, dans ces trois communautés. Maintenant elle m'interdit d'avoir plus d'un PC, et ne me laisse plus que le droit d'aller poster des conneries sur les forums :'(
Ne te laisses pas embrigader comme moi.Le feu sacré brule encore en toi. Fait tout pour le préserver.
TUES TA FEMME AVANT QU'ELLE NE L'ÉTEIGNE

:) Merci pour le conseil. Mais je me disais que quand j'aurais terminé le jeu (si je trouve le temps de le terminer) je pourrai le proposer aux gros sites de jeux Flash, qui payent pour leurs jeux.

Et puis sinon c'est surtout par passion et pour apprendre que je le fais. Parce qu'en faisant ça je deviens meilleur, et ça m'aidera plus tard.

En fait pour l'histoire je tire grosso-modo la technique algorithmique d'un moteur de connaissance logique avec analyse structurelle (je sais les termes sont un peu pompeux ^^) que j'étais déjà en train de programmer, et qui m'en avait VRAIMENT fait voir de toutes les couleurs (jamais fait un algo aussi complexe).
J'ai donc repris et simplifié le fonctionnement global de l'analyse structurelle pour implémenter le pathfinding.

Pour l'expérimenter actuellement, je te confirme que la solution de la grille (avec les points de passages possibles et impossibles) est effectivement basique. Mais elle a le mérite d'être rapide : ton calcul du chemin le plus court n'est alors qu'un parcours des cases "possibles" entre deux points. S'il faut plus de boucles pour trouver le résultat, ceux-ci sont rapides à atteindre (utilisation d'index sur la grille), et à analyser. De plus, tu peux facilement gérer plusieurs niveaux de possible selon les mêmes cases : les cases visibles (cas de la visibilité limitée à une certaine distance), monter ou descendre d'un niveau (gestion basique de la 3D). Les possibilités sont nombreuses même si les ficelles du calcul sont tellement grosses qu'on dirait des cordes.

Je sais que ça aurait été beaucoup plus rapide, niveau perf', mais j'avais envie de m'éclater. Et puis mon système est plus souple : il permet de positionner où on veut les objets et les personnages et non seulement alignés sur une grille.

P1ng0uin

06/09/2009, 00h06

Je vois pas trop l'intérêt de programmer en récursif: niveau perf c'est lourd.

En restant sur ton idée initiale (chemin le plus court sinon contournement)...

Je partirai plutôt en itératif avec un tableau de amorces de chemin qui se remplit au fur et à mesure des étapes et des longueurs mises à jour à chaque étape. Dès que tu as un chemin qui aboutit, tu "tues" toutes les amorces de chemin qui présentent une longueur supérieure à ton chemin complet. Tu construit ta boucle de manière à ce que la longueur de tes amorces soit strictemeny croissante d'une itération à l'autre. A chaque boucle tu mets à jour la longueur la plus courte pour chemin ayant abouti et tu dégages tout ce qui est supérieur. Comme ça tu n'as pas besoin de calculer tous les chemins jusqu'au bout.

Sinon on est en 2009, le path finding c'est un sujet battu et re-battu, faut pas vouloir réinventer la roue à chaque fois.

Rodwin

06/09/2009, 00h06

Oui, mais pour construire tes vecteurs, tu places bien les points à relier sur une grille, ou me trompe-je ?

Seboss

06/09/2009, 00h25

Sinon on est en 2009, le path finding c'est un sujet battu et re-battu, faut pas vouloir réinventer la roue à chaque fois.
Dans un contexte dans lequel on travaille en délai et coût restreint, je suis d'accord. Mais quand la démarche est auto-didactique, pourquoi pas ?
Merci pour cet article, je n'aurais pas été fâché de voir un peu de pseudo-code par contre :)

LPTheKiller

06/09/2009, 00h31

Voilà j'ai mis des nouveaux schémas.

Je vois pas trop l'intérêt de programmer en récursif: niveau perf c'est lourd.

En restant sur ton idée initiale (chemin le plus court sinon contournement)...

Je partirai plutôt en itératif avec un tableau de amorces de chemin qui se remplit au fur et à mesure des étapes et des longueurs mises à jour à chaque étape. Dès que tu as un chemin qui aboutit, tu "tues" toutes les amorces de chemin qui présentent une longueur supérieure à ton chemin complet. Tu construit ta boucle de manière à ce que la longueur de tes amorces soit strictemeny croissante d'une itération à l'autre. A chaque boucle tu mets à jour la longueur la plus courte pour chemin ayant abouti et tu dégages tout ce qui est supérieur. Comme ça tu n'as pas besoin de calculer tous les chemins jusqu'au bout.

Sinon on est en 2009, le path finding c'est un sujet battu et re-battu, faut pas vouloir réinventer la roue à chaque fois.

Comme je l'ai dit j'avais pas envie de m'emmerder, donc j'ai fait au plus simple et intuitif. J'ai pensé à ta méthode avec un tableau qui se remplirait mais c'était plus dur à débuguer, car tous les chemins sont calculés en même temps petit à petit. Mais c'est sans doute pas mal pour les perfs. Remarques que rien ne m'empêche dans ma technique de tuer les amorces trop longues au fur et à mesure, ni de commencer par les chemins potentiellement les plus court.

Réinventer la roue n'a pas l'air très utile, mais c'est très formateur. Qu'y a-t-il de mieux pour s'initier à la recherche ? Surtout que si on y arrive vraiment pas, on peut toujours aller s'aider des solutions qui ont déjà été trouvées.

Oui, mais pour construire tes vecteurs, tu places bien les points à relier sur une grille, ou me trompe-je ?

Non, en fait je prend les coordonnées des points A et B, et de tous les coins ses obstacles et je résous toutes les collisions mathématiquement (intersection de segments, c'est assez basique).
Et pour le calcul des coordonnées des coins, qui sont éloignés des vrais coins de l'obstacle, elle se fait en prenant en compte la largeur de l'ennemi.

---------- Post ajouté à 23h31 ----------

Merci pour cet article, je n'aurais pas été fâché de voir un peu de pseudo-code par contre :)

Ok si tu veux je posterai du code, mais demain.

szwip

06/09/2009, 00h32

L'idée de départ d'utiliser le vectoriel et de détecté les murs et les angles s'y rapportant est bonne : le chemin optimal passe forcément par les angles des rectangles. Par contre au niveau de l'algo tu est en train de réinventé des choses qui existent. C'est vrai que c'est formateur, mais ce n'est pas le plus efficace.

Pour ton problème tu devrais regarder du côté de l'algorithme "A*". Il est assez simple à mettre en oeuvre et t'évitera les tests de boucle infinie et de cul de sac, qui sont en quelque sorte naturellement gérés par l'algo ;)

yuushiro

06/09/2009, 01h32

Trés interéssante cette approche.
J'avais un peu plongé dans l'algo A* mais le seul gros soucis de cet algorithme c'est l'évaluation optimale d'un chemin. On peut sous-évaluer ou sur-évaluer mais ça nuit quand même grandement sur les performances. Parfois on se retrouve pratiquement à explorer autant la zone qu'avec un vieux coup de Djikstra.

Sinon, en faisait un peu de géométrie algo en info, j'ai pu percevoir d'autres manières pour faire du pathfinding. En fait en utilisant tout ce qui est triangulation de delaunay et diagramme de voronoi, etc.

On reviendrait a definir des surfaces praticables où non. Aprés c'est certain que de cette manière le chemin obtenu n'est peut-être pas le plus rapide.

Je me demande donc si en combinant A* sur cette carte minimale obtenue à partir de delaunay&voronoi on pourrait ainsi obtenir quelque chose qui donne un résultat assez bon avec des perfs pas trop moisies.

rOut

06/09/2009, 03h37

D'après ce que j'ai pu lire, A* ou Dijkstra sont clairement les agorithmes optimals à l'heure qu'il est, pour trouver le chemin le plus court dans un graphe pondéré. A* marchant mieux en général que Dijkstra, mais moins bien dans certains cas particuliers (cul de sac typiquement).

Il est donc à peu près inutile d'essayer de trouver un meilleur algorithme, effectivement, la théorie des graphes est un sujet battu et rebattu depuis des dizaines d'années, et les meilleurs mathématiciens se sont déjà arrachés les cheveux dessus.

Par contre, et c'est finalement la ou la démarche de LPTheKiller est intéressante, c'est au niveau de la création du graphe, sur lequel on va appliquer l'algorithme, que tout se fait. Dans Half Life par exemple, ils ont choisir de créer un graphe grossier avec des waypoints placés à la main, d'autres utilisent une grille régulière qui marchent bien pour des jeux à base de blocs de tailles identiques et carrés ou rectangulaires. Ici par contre, tu as essaies de créer un graphe dynamiquement, au fur et à mesure de la recherche, par rapport à l'environnement qui entoure les objets. Au final, le graphe sur lequel tu appliques Dijkstra inconsciemment, c'est celui formé par tes points A, B, C, D et par les distances qui les séparent. D'ailleurs, tu remarqueras qu'en créant ton graphe dynamiquement, tu fais des choix initialement qui peuvent s'avérer mauvais par la suite : Dans ton exemple un peu plus complexe avec les deux carrés, il choisit C comme premier coin, mais ensuite le détour effectué à cause du deuxième carré aurait rendu le choix de D plus intéressant en fin de compte.

Si ça t'intéresse, tu devrais regarder aussi du coté des théories du partitionnement de l'espace (Diagrammes de Voronoi (http://fr.wikipedia.org/wiki/Diagramme_de_Vorono%C3%AF) par exemple, enfin, c'est vaste comme sujet), parce que ca permet potentiellement de diviser ton univers en une grille, plus forcément carrée, prenant en compte les contraintes de l'environnement et les obstacles, de manière à obtenir ensuite un graphe suffisamment grossier pour que l'algorithme soit rapide et suffisamment précis tout de même pour pouvoir calculer n'importe quel itinéraire.

rOut

06/09/2009, 03h44

...
Bon bah voilà, il doit être tard parce que je n'avais même pas vu...

Enfin, juste pour dire que le partionnement de l'espace (Voronoi, Delaunay...) et un algo de type A* ne sont pas du tout concurrentiels mais plutôt complémentaires. Voronoy et Delaunay te permettant de créer un graphe assez optimisé, et A* te permettant de calculer le plus court chemin dessus.

Sk-flown

06/09/2009, 07h35

Sinon on est en 2009, le path finding c'est un sujet battu et re-battu, faut pas vouloir réinventer la roue à chaque fois.

Je ne suis pas d'accord.

Oui je sais c'est très constructif comme approche.

xheyther

06/09/2009, 08h11

yuushiro

06/09/2009, 10h37

@rOut : C'est tout à fait là où je voulais en venir.

Sinon pour les histoires de cul de sac concernant l'algo de LPTheKiller, il pourrait être judicieux aussi de faire une sorte de précalc pour définir des polygones convexes. De cette manière on peut éviter d'explorer les culs de sac, mais je ne sais pas si il veut vraiment éviter de les explorer.

titi3

06/09/2009, 10h50

P1ng0uin

06/09/2009, 11h19

J'ai pensé à ta méthode avec un tableau qui se remplirait mais c'était plus dur à débuguer, car tous les chemins sont calculés en même temps petit à petit.
Plus lourd à débugger, sûrement (à chaque étape on fait avancer tous les chemins), plus compliqué je ne pense pas, en général le récursif est abominable à débugguer.

Pour l'optimisation, la solution itérative reste meilleure. En récursif tu calcules toutes chemin les uns après les autres, donc si t'as pas de bol tu vas commencer par calculer les chemins les plus long. Dans la solution itérative, tu identifies en premier les chemins les plus rapides à calculer (moins d'étapes/points de contournement le + rapidement) ce qui permet de commencer à éliminer plus vite.

La solution récursive peut être plus rapide en terme de calcul suivant la map, notamment si le chemin le plus court est parmi les premiers, mais bon avoir du bol, la solution itérative est quand même a priori plus propre.

Sinon en général, le récursif c'est très beau intellectuellement mais en terme de perfs c'est le mal.

Dans le cas d'espèce, le djikstra est loin de tout résoudre puisqu'il faut quand même créer l'arbre ce qui, si on part du "tout géométrique" reste quand même un gros boulot.

Pour les culs de sac, je penserai à un système genre si l'angle est obtu, renvoyer au suivant.

Réinventer la roue n'a pas l'air très utile, mais c'est très formateur. Qu'y a-t-il de mieux pour s'initier à la recherche ? Surtout que si on y arrive vraiment pas, on peut toujours aller s'aider des solutions qui ont déjà été trouvées.
Disons que ça peut former le caractère, mais en général on se donne beaucoup de mal, et puis, sauf si on est un génie, on se rend compte qu'on a quand même plusieurs générations de retard sur les solutions éprouvées et que t'as passé du temps à bosser sur des systèmes soit dépassés, soit à coté de la plaque. Mais ça tanne le cuir.

Peut être plus intéressant de regarder les solutions complexes genre Djikstra et d'en extrapoler les principes à d'autres problèmes. D'essayer de s'approprier des outils plus sophistiqués.

L'algo c'est quand même de plus en plus un boulot de pointe réservé aux théoriciens, l'informatique "moderne" c'est quand même de plus de la normalisation /normalisation/intégration de briques algo/logicielles et que le recours aux algo "maison" est plus un facteur de complexité/erreur qu'autre chose.

PS: mes messages ont peut être l'air un peu définitifs, mais bon c'est juste pour le plaisir de la discussions, hein, tu fais ce que tu veux et y a pas de mal à expérimenter juste pour voir, been here done that.

xheyther

06/09/2009, 11h31

Passionnant, tu dois en utiliser des tranquillisants après avoir coder ce genre de choses ^_^

Par contre question: en général dans les STR (Company of Heroes), le pathfinding est assez lamentable (surtout pour les blindés dans le cas de CoH), selon toi c'est dû à la complexité de l'environnement ou codage avec des gants de boxe ou mauvais algorithme ou... ?
Je pense que c'est un choix délibérré : les programmeurs sont en général suffisamment intelligent pour implémenter un algorithme correct, surtout s'il s'agit juste de repomper un algo super connu.

Quand tu as des dizaines, voir des centaines ou des milliers de chemin à calculer et à recalculer à chaque itération de la boucle du jeu (l'environnement change à chaque fois : les autres unités peuvent constituer des obstacles), ben tu implémentes un algorithme mauvais mais peu complexe pour ne par consacrer trop de ressources uniquement à ce problème.

Peut être qu'un jour on verra des algo qui exploiteront les GPGPU vu que c'est quand même des truc facilement parallélisable.

ducon

06/09/2009, 11h41

Herrmann Goulag

06/09/2009, 11h44

Bon, j'ai suivi les instructions du guide-michelin, j'ai tué ma femme.
Que dois-je faire ensuite?

P1ng0uin

06/09/2009, 11h45

les programmeurs sont en général suffisamment intelligent pour implémenter un algorithme correct, surtout s'il s'agit juste de repomper un algo super connu.

Quand tu as des dizaines, voir des centaines ou des milliers de chemin à calculer et à recalculer à chaque itération de la boucle du jeu

Ouep en général, les situations sont souvent très complexes, les algos "parfaits" sont trop lourds à implémenter en temps réels, donc ils emploient des algos simplifiés ou employant des artifices (commes des waypoints pré-positionnés par les levels-designers...) pour un résultat qui sans être parfait donne un résultat satisfaisant dans des temps raisonnables. Ce sont ces bricolages qui sont réalisés avec plus ou moins de talent.

HellBoy

06/09/2009, 12h52

Il fallait dire :
Je suis pas d'accord, réinventer la roue, dans le cadre de l'apprentissage de la programmation et de la création d'un premier jeu, c'est instructif et rend meilleur un développeur.

L'important c'est pas de jamais réinventer la roue, c'est de le faire une fois pour voir comment ça marche, et ensuite d'utiliser des trucs plus élaborés (http://fr.wikipedia.org/wiki/Algorithme_A*) (ou même vraiment compliqués (http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra))qu'il aurait fallut loooongtemps à réinventer.

Ou encore plus complexe (utilisé par gpg pour Supreme commander 2) :

http://en.wikipedia.org/wiki/Fluid_mechanics (http://en.wikipedia.org/wiki/Fluid_mechanics)
http://en.wikipedia.org/wiki/Navier-Stokes_equations (http://en.wikipedia.org/wiki/Navier-Stokes_equations)

Admirez les déplacement ultra fluide des unités sans aucune collision :

http://www.youtube.com/watch?v=CMvsjn8KDS0

Krobill

06/09/2009, 12h55

Qu'y a-t-il de mieux pour s'initier à la recherche ? Surtout que si on y arrive vraiment pas, on peut toujours aller s'aider des solutions qui ont déjà été trouvées.

Je loue la démarche intellectuelle personnelle qui consiste à se dépatouiller tout seul comme un grand mais comme P1ng0uin, je reste sceptique sur son utilité réelle. En effet si on veut faire un parallèle avec la 'Recherche' comme dans 'recherche scientifique', il ne faut pas oublier que la Recherche, c'est avant tout un gros travail de documentation et de bibliographie. Tous les chercheurs dans un domaine tâchent d'assimiler ce qu'on fait leurs aînés plutôt que de le redémontrer. C'est le seul moyen d'espérer aller plus loin avant le terme de la courte vie qu'est la notre.
Sinon la démarche récursive est un vrai performance killer pour du Flash. Le moindre appel de fonction y coûte fort cher et au coude à coude avec l'instanciation c'est l'un des points auquel il faut en général faire le plus attention pour conserver de bonne perfs.
Mais voilà, tout ceci n'engage que moi, et je comprends tout même la volonté du 'j'essaie de tout faire moi même pour apprendre'.

rOut

06/09/2009, 13h18

Je pense que ces algorithmes sont un peu artificiels : ils font comme si le personnage connaissait l’univers comme sa poche, comme s’il savait que derrière l’énorme immeuble se trouve un gouffre à contourner… ils oublient que bien souvent, on optimise son parcours à partir des données perceptibles, pas à partir du monde entier (ton dentier ?)
En plus, dans le cas de poursuite du joueur, cela suppose que le personnage sait exactement où il est (comme dans Doom), comme s'il disposait de la vision de Superman.
J’aime assez l’idée de petites modifications aléatoires des chemins.
Je pensais justement hier à un algorithme différent qui se baserai sur la perception des personnages :p Mais bon, ça risque de donner des situations ou ils ne choisissent absolument pas le bon chemin, et même si c'est beaucoup plus réaliste, on va te dire ensuite "Ouais, ton pathfinding il est pourrave, ils arrivent même pas à trouver un chemin correct". Le but des jeux vidéso est de s'amuser, pas de faire un truc super réaliste.

Imagine les unités d'un STR qui essaient de traverser une forêt, lorsque tu cliques de l'autre coté, puis se paument dedans et n'en ressortent jamais. Ca te ferait sacrément rager en tant que joueur, et tu blamerais les dev qui codent avec leurs pieds. :p

Errata

06/09/2009, 13h21

Ou encore plus complexe (utilisé par gpg pour Supreme commander 2) :

http://en.wikipedia.org/wiki/Fluid_mechanics (http://en.wikipedia.org/wiki/Fluid_mechanics)
http://en.wikipedia.org/wiki/Navier-Stokes_equations (http://en.wikipedia.org/wiki/Navier-Stokes_equations)

Ils utilisent ca pour obtenir quelque chose de correcte quand tu déplace plein d'unités, mais pour définir le chemin, ca reste les méthodes habituelles , avec une carte et des zones "non utilisable".

xheyther

06/09/2009, 13h46

Je pense que c'est possible de faire du path finding avec navier-stockes. Si tu mets des conditions de débit positif et négatif respectivement au point de départ et d'arrivée de ton dépassement, les ligne de courant vont "naturellement" s'établir entre les deux, sur le chemin qui engendrera le moins de perte de charge (comme en vrai avec de l'eau dans ta baignoire).
J'ai pas d'argument qui prouve que ce sera le chemin optimum, mais je vois pas pourquoi ça serait pas le cas.
Je trouve ça plutôt élégant comme utilisation de N-S.

Reste le problème de la résolution, vu qu'on ne sait pas le faire de manière exacte, il faut discrétisé le terrain et tout mais dans le cas d'un jeu je pense que ça améliore les performances et qu'en plus on a pas besoin de beaucoup de précision. D'autant que dans un ordinateur tout est discrétisé :)

ducon

06/09/2009, 13h47

Imagine les unités d'un STR qui essaient de traverser une forêt, lorsque tu cliques de l'autre coté, puis se paument dedans et n'en ressortent jamais. Ca te ferait sacrément rager en tant que joueur, et tu blamerais les dev qui codent avec leurs pieds. :p

Ça devrait être réglable, ou le réserver à l’ennemi IA.

Tramb

06/09/2009, 14h02

On peut croire que le pathfinding est un problème simple si on ouvre un bouquin de théorie des graphes, justement.
Mais quand on rajoute le steering et le flocking, on obtient un "hard problem" bien ouvert :)

La solution mécaflu de gpg est créative pour gérer des flux de déplacements d'unité, je materai ça à l'occase, tiens.

Sk-flown

06/09/2009, 16h03

Tous les chercheurs dans un domaine tâchent d'assimiler ce qu'on fait leurs aînés plutôt que de le redémontrer. C'est le seul moyen d'espérer aller plus loin avant le terme de la courte vie qu'est la notre.

Et si la base nous emmène sur la mauvaise voie?

(en parlant de Pathfinding ça tombe bien)

Krobill

06/09/2009, 17h20

Remettre en question le travail des anciens est salvateur certes. Mais l'ignorer, sous pretexte de ne pas se polluer l'esprit, est juste... Arrogant. Einstein ne devait sûrement pas ignorer les bases de la physique classique quand il a pondu la théorie de la relativité ;)

_tibo_

06/09/2009, 17h21

Article très intéressant, merci ! Ça me donne envie de refaire un peu de code, tout ça...

LPTheKiller

06/09/2009, 18h01

Merci pour vos réponses, qui sont très intéressantes.

Au niveau de la réinvention de la roue, je tiens quand même à préciser que les scientifiques passent une bonne partie de leur temps à vérifier et à préciser les résultats des autres. Et donc à refabriquer cette roue, qu'ils ont vu dans la publication scientifique, chez eux.
(Voir à ce propos le Science & Vie qui parlait des arnaques scientifiques, beaucoup plus courantes qu'on peut le croire, où des chercheurs créent des données et résultats sous la pression du stress et des attentes de leurs supérieurs.)

Ensuite, il faut bien vous rendre compte que je n'ai sans doute pas encore le niveau pour me mettre à la pointe de la recherche, en synthétisant tous les travaux précédents, tout simplement parce que je sors à peine de Terminale et que j'entre seulement en école d'ingénieurs dans quelques jours.

Ceci n'était qu'une simple distraction de vacances, un jeu que j'avais envie de faire vite-fait et moi-même.

Je pense que ces algorithmes sont un peu artificiels : ils font comme si le personnage connaissait l’univers comme sa poche, comme s’il savait que derrière l’énorme immeuble se trouve un gouffre à contourner… ils oublient que bien souvent, on optimise son parcours à partir des données perceptibles, pas à partir du monde entier (ton dentier ?)
En plus, dans le cas de poursuite du joueur, cela suppose que le personnage sait exactement où il est (comme dans Doom), comme s'il disposait de la vision de Superman.
J’aime assez l’idée de petites modifications aléatoires des chemins.

En fait, il y a beaucoup de choses que je n'ai pas dites, pour alléger l'article. Mais sache que lorsque le joueur disparaît du champ de vision du computer, celui-ci tente uniquement de rejoindre sa dernière position connue. Il ne sait pas où va le joueur ensuite.
Mais s'il entend un bruit, provenant de l'autre côté d'un obstacle, il ira voir ce qu'il se passe dans les environs (il y a introduction d'une approximation, fonction inverse de l'intensité du bruit entendu).
Dans tous les cas il ne sait jamais la position du joueur avant de l'avoir vu.

Lorenzo77

06/09/2009, 18h44

LPTheKiller

06/09/2009, 18h48

Salut,

Il est bien moins gourmand de placer des waypoints au moment de la conception (comme sur les maps d'unreal), ca évite toute la phase de calcul lourd puisque l'IA dans ce cas ce limitera a passer par le moins de point possible entre A et B

Oui je sais ça a déjà été remarqué ;)
C'est une technique que je connaissais vaguement mais je ne m'étais jamais penché dessus, et il est vrai qu'elle conviendrait assez bien pour mon jeu, du moins sous réserve de quelques perfectionnements, que j'envisage bien.

titi3

06/09/2009, 22h26

Je pense que c'est un choix délibérré : les programmeurs sont en général suffisamment intelligent pour implémenter un algorithme correct, surtout s'il s'agit juste de repomper un algo super connu.

Quand tu as des dizaines, voir des centaines ou des milliers de chemin à calculer et à recalculer à chaque itération de la boucle du jeu (l'environnement change à chaque fois : les autres unités peuvent constituer des obstacles), ben tu implémentes un algorithme mauvais mais peu complexe pour ne par consacrer trop de ressources uniquement à ce problème.

Peut être qu'un jour on verra des algo qui exploiteront les GPGPU vu que c'est quand même des truc facilement parallélisable.

Ouep en général, les situations sont souvent très complexes, les algos "parfaits" sont trop lourds à implémenter en temps réels, donc ils emploient des algos simplifiés ou employant des artifices (commes des waypoints pré-positionnés par les levels-designers...) pour un résultat qui sans être parfait donne un résultat satisfaisant dans des temps raisonnables. Ce sont ces bricolages qui sont réalisés avec plus ou moins de talent.

Merci pour vos éclaircissements :cigare: En lisant l'article j'étais loin de m'imaginer la complexité du pathfinding pour un jeu simple, c'est dire pour les blockbusters même si les moyens sont différents :o

rOut

06/09/2009, 22h36

Peut être qu'un jour on verra des algo qui exploiteront les GPGPU vu que c'est quand même des truc facilement parallélisable.
A force d'utiliser le GPU pour tout faire (la physique, le pathfinding, etc), la pauvre carte graphique ne va même plus avoir le temps d'afficher les images :o

Ravine

06/09/2009, 23h38

J'ai lu un peu de tout dans ce thread au niveau intervention, et je rejoins les gens qui t'enjoignent a te documenter sur les travaux effectues sur les parcours de graphes. C'est un probleme "classique" d'algorithmique, qui a donne naissance au Djikstra et au A* (et a des cousins comme les BFS et DFS).

Vouloir reflechir par soi meme est louable, et comme dit precedemment, ignorer les decennies de recherche sur le sujet est au mieux idiot, au pire une enorme preuve d'orgueil. Mais rien de mieux pour guerir ca que de se rendre compte du temps perdu a imaginer une solution non optimale quand il existe des solutions meilleures, plus simples (ce qui devrait t'arriver tout le temps si tu t'echines a vouloir reinventer la roue).

2 petits liens au passage qui m'ont bien servi quand j'etais a plancher sur un exercice de pathfind/IA : un article de Gamasutra (http://www.gamasutra.com/features/19990212/sm_01.htm) sur le pathfind (assez court mais tres bien ecrit et clair); et la page du celebre Amit (http://theory.stanford.edu/~amitp/GameProgramming/), une espece de reference sur le sujet de l'internet, qui a le merite aussi bien d'aborder les algorithmes de parcours que les methodes de representation de l'espace et les problemes de partitionnement de celui ci.

Cela n'enleve rien au travail effectue, et j'avoue avoir beaucoup aime ton jeu. L'ambiance y est excellente, et on s'y croirait.

LPTheKiller

07/09/2009, 00h08

Ce n'est pas du temps perdu. Je le répète, ce n'était qu'à but ludique, et je n'avais pas la tête à aller fouiner dans la de la documentation pour essayer de reprendre des systèmes que je sais par ailleurs pertinemment être meilleurs.
Mon système ne m'a d'ailleurs pris que 4 ou 5 jours (réflexion + implémentation) sur le mois que m'a pris le jeu (à peu près). <= Ces temps sont des temps en période de vacances, c'est à dire que je me suis surtout détendu et j'ai fait autre chose que de la prog.

Merci pour les liens.

Seboss

07/09/2009, 10h19

A propos de réinventer la roue bien, pas bien, je pense que du moment qu'on comprend ce qu'on écrit, ça n'a finalement pas beaucoup d'importance.
Trouver la solution soi-même peut être intellectuellement très stimulant, mais je pense que globalement on gagne du temps et on apprend aussi beaucoup en réimplémentant une solution éprouvée.
Méfiez-vous juste du code que vous ne comprenez pas (http://www.pragprog.com/the-pragmatic-programmer/extracts/wizards).

fofo

07/09/2009, 21h32

(Pour info, c'est pas applicable pour du flash je pense)

T'as l'algo des fourmis, hyper simple mais qui nécessite un langage compilé (ie. Performant) :
Tu définies ta carte en matrices.

Tu codes une routine toute conne (mais qui doit être hyper performante genre en C voir assembleur) :
- Chercher la case adjacente aléatoirement en préférent les cases déjà marquées
- Marquer dans la matrice les cases sur lesquelles tu es passé.
- S'arrêter dés que t'arrive au point B (ou relancer la fourmi du point A)

Lancer les fourmis du point A (ie. Appeler un bon nombre de fois ta routine)

Qu'est ce qui va se passer :
- Initialement toute ta matrice est à 0, les premières fourmis vont partir au hasard.
- Les premières fourmis qui arrivent sont celles qui ont trouvées un chemin plus rapide que leur soeurs,
- Au prochain passage les fourmis auront tendances à préfèrer le chemin déjà marqué par les plus rapides.

Au bout d'un certain temps, tu tues toutes les fourmis (oui c'est sauvage), et tu suits le chemin le plus marqué pas forcément optimal mais plutôt rapide.

Les avantages sont multiples:
- Tu peux fixer un temps maximal pour trouver un chemin, (plus tu laises les fourmis se baladée, plus se sera précis, mais rapidement tu as une tendance plutôt bonne).
- Tu peux peux "pondérer" tes chemins (par ex. Dans l'eau ton gus marche moins vite, donc tu marques moins fort la case ou ta fourmi passe, en ville c'est limité en 50, sur le périph. 130...etc).
Inconvénients:
- Faut un langage performant sinon c'est trèèès long,
- Faut un peu bricoler pour trouver le bon nombre de fourmis, et l'algo pseudo aléatoire.

C'est ce genre d'algo (avec pas mal de mise en cache), qui permet à Mappy et autres google map de trouver des chemins instantanément à travers la France.

ça sert aussi dans les réseaux pour trouver quels routeurs utiliser.

C'est ce que font les fourmis dans la nature pour trouver et ramener de la bouffe :
- Toutes partent au hasard en laissant une trace de phéromone,
- Dés qu'une fourmi trouve de la bouffe, elle la ramène à la maison, en suivant le chemin qui sent le plus les phéromones.

T'as qu'a observer les fourmis elle se suivent très rapidement vers le plus court chemin pour la bouffe.

Edit un lien : http://fr.wikipedia.org/wiki/Algorithme_de_colonies_de_fourmis#Origine

rOut

07/09/2009, 21h45

LPTheKiller

07/09/2009, 22h44

Tiens c'est marrant çe truc :)

Je connaissais ce fonctionnement chez les fourmis mais je savais pas que ça avait été réutilisé en informatique...

Pour le Flash, tout dépend à quelle fréquence l'algo est appelé. Si c'est en continu à chaque frame c'est pas possible, mais si c'est une fois de temps en temps pourquoi pas, je pense que ça peut se faire, on pourrait d'ailleurs étaler les calculs sur plusieurs frames : ça ferait que le perso précise son chemin au fur et à mesure qu'il avance.

Dans un jeu comme le mien, je pense que ça pourrait être envisageable, car le pathfinding n'est pas invoqué en continu (même s'il y a poursuite d'objets dynamiques : C'est soit il le voit et il va tout droit dessus ; soit il le voit pas et il rejoint sa dernière position connue).
Mais la solution me paraît pas du tout optimale. Ca marcherait mieux pour des labyrinthes ou des trucs comme ça.

Je vais réécrire mon pathfinding en utilisant Dijkatruc, en y mélangeant mes algos détections d'obstacles, et en faisant du wayPointing automatique en reprenant mon idée des coins caractéristiques des blocs. Ca devrait super bien marcher.

Triz'

08/09/2009, 15h24

- Chercher la case adjacente aléatoirement en préférent les cases déjà marquées
- Marquer dans la matrice les cases sur lesquelles tu es passé.
- S'arrêter dés que t'arrive au point B (ou relancer la fourmi du point A)

(...)

- Initialement toute ta matrice est à 0, les premières fourmis vont partir au hasard.
- Les premières fourmis qui arrivent sont celles qui ont trouvées un chemin plus rapide que leur soeurs,
- Au prochain passage les fourmis auront tendances à préfèrer le chemin déjà marqué par les plus rapides.

Au bout d'un certain temps, tu tues toutes les fourmis (oui c'est sauvage), et tu suits le chemin le plus marqué pas forcément optimal mais plutôt rapide.
Faut lancer beaucoup de fourmis alors.

Si une majorité part du mauvais coté au début, le chemin le "plus marqué" fera systématiquement un détour.

Non ?

ducon

08/09/2009, 19h43

Ça fait beaucoup de calculs quand tu veux déplacer une seule unité à l’autre bout de la carte. ^_^

LPTheKiller

08/09/2009, 22h52

Faut lancer beaucoup de fourmis alors.

Si une majorité part du mauvais coté au début, le chemin le "plus marqué" fera systématiquement un détour.

Non ?

Je pense que si tu jauge bien les paramètres, tu peux faire en sorte que ça arrive le moins possible, et que la rapidité d'atteinte de l'objectif renforce assez la meilleure voie pour éclipser les premiers aléas.

szwip

09/09/2009, 00h21

Je m'étais déjà amusé avec l'algo des fourmis, mais c'est effectivement très lourd. Et si le nombre d'itération n'est pas infini, on n'est pas assuré d'être sur le chemin optimal. Du coup, on obtient souvent de bon chemin, mais à l'allure un peu erratique.

rOut

09/09/2009, 12h30

Avec une implémentation sur le GPU ça doit le faire, ça à l'air de bien se paralléliser.

SnakesMaster

10/09/2009, 00h54

Ca me rappelle l'époque où je voulais implémenter l'algo de djikstra juste avec ce que j'avais appris à faire en terminale ES spé maths, sans wikipedia ou autre aide... Ya pas à dire, dessiner ça rend les choses plus simples ! Et je suis pratiquement certain que tu prends le temps de faire de la pédagogie parce que ça t'aides toi à clarifier ton problème !

Quand on peut expliquer sans ambiguité sa problematique à un novice, on rend le probleme bien plus clair pour soi même ! B)