Le pathfinding c’est quoi t’est-ce donc t’il ?
Le “pathfinding”, ou “recherche de chemin”, en bon françois, décrit une série d’algorithmes permettant à un object O de se déplacer d’un point P à un point P’ dans un environnement E, c’est, en gros, l’algorithme A qui permet à un tank mammouth M de se déplacer de sa position courante PC vers les petits machins verts qui courent en rigolant PMVQCER dans la direction D de votre base B. (ndc1 : ouf)
Mais attention, il ne faut pas le confondre avec l’algo qui se charge de la prise de décision, ce qui est un tout autre problème ! le pathfinding n’est utilisé qu’à partir du moment où (ndc2: DTC proof ) l’on sait où l’on est et où l’on va, il se contrebat du pourquoi, du comment et de la réponse ultime (42, soit dit en passant) (ndc : mon dieu, ils sont partout)(nda : oui)
Le nombre d’algo potentiels pour résoudre ce genre de problèmes est énorme, de plus la complexité du problème lui même en fait un sujet d’études très couru des chercheurs en blouse blanche et en IA, (pour les forts en math : c’est de la théorie des graphs bourrue, et c’est un problème n§ complexe… super… ).
Histoire de ne pas partir dans le grand vide, je vais tout baser sur l’idée d’un jeu se passant sur un landscape, comme ça, ça sera plus simple, j’expliquerai aussi plus tard comment on pourrait adapter la chose sur un fps, ou même sur “Barbie Chaval” (ndc2:A cheval non ?)(nda:non) (y en a qu’aiment… en tout cas ça vend… ).
Comme base on utilisera la map suivante :
Le vert c’est la position de départ, en bleu la destination, et en noir les obstacles.
On va jeter un bref coup d’oeil a 3 solutions : la 1, la 2 et la 3. La 1 étant à la limite de l’idiotie, et la 3 a la limite du génie… il est bien évident qu’il existe bien d’autre solutions et variations sur le theme.(ndc2 : VARIANTES non ? )(ndr : oui aussi)
Solution 1, dite «Le bourrin ».
Solution réellement applique dans le mémorable “Trucks” édité par Microfolies en 199queque chose. (enfin en tout cas moi je me le rappel, et je pense que TBF doit s’en souvenir (parce que TBF se souvient de tout)).
Le principe est simple, voir simpliste, il s’agit de se dire que si le joueur ne regarde pas dans sa direction, tout ce qu’une unité a à faire, c’est se déplacer directement vers la destination, en prenant bien soin d’ignorer les obstacles, et si jamais le joueur la surprend, elle prend un air dégagé et attaque le joueur… celui ci n’ayant que le temps de se dire “mais comment il e…”. (ndc2 : Le fameux “mais qu’est-ce que…” dans Splinter Cell )
C’est tricher, mais ça marche plutôt pas mal :
Solution 2, dite “Je suis plus con que j’en ai l’air”.
La solution 2 repose sur du hasard, l’unité va toujours tenter de se déplacer vers sa destination, si elle ne peut pas, elle va alors choisir une autre direction possible, mais au hasard.
Des fois ça marche, des fois ça marche pas, c’est le problème avec le hasard… il peut (souvent) arriver que la direction tirée au hasard éloigne l’unité, ou lui fait prendre un détour.
Quand ça marche bien, ça peut donner ceci :
sinon, ça donne plus souvent cela :
Solution 3, dite “A la cosaque”
(aussi appelée, chez les chercheurs en IA et en blouses blanches “A*” ou “AStar” (comme dans A->A *->Star))
Là ça devient un poil plus musclé…
Le principe de base est de se dire que pour chaque case, on peut calculer un score, et que plus ce score est bas, plus la case a la de chance d’être sur le meilleur chemin.
Toute la difficulté vient de la façon de calculer ce fameux score (par ex. : un bien fameux score 6-3 3-6 6-0 6-0 ).
Pour calculer ce score, on va utiliser deux choses : un coût et un heuristique.
Dans des versions simples le coût n’est que le nombre de cases parcourues depuis la case de départ. Pour corser les choses, on peut ajouter d’autres trucs dans ce coût, comme le type de terrain (genre béton = +0, herbe = +1, boue = +10, v’voyez l’esprit quoi).
L’heuristique, c’est une règle bidon (c’est à dire qui marche mais sans véritable raison) qu’on fixe et qui permet de juger de l’importance d’une position par rapport au chemin à rechercher. La plupart des algos d’A* utilisent soit la distance entre la case courante et la destination :
Racine carré de ((PC.x-PO.x)^2 + (PC.y-PO.y)^2),
soit, plus rapide à calculer, le manhattan, qui est une approximation grosso modo valable (bidon je vous avais dit… qui se calcule :
(PC.x-PO.x) + (PC.y-PO.y)
Une fois qu’on a définit ces deux valeurs, on parcours la carte en partant du point de départ, on calcule le score de toutes les destinations possibles, puis on recommence sur toutes les destinations, en commencant par celles qui ont le plus petit score…
Vous avez compris ?
Non ?
Moi non plus….
Donc j’ai fait des petits dessins.
étape 1
Coût :
Heuristique :
Score total :
Déplacement possible à partir de la position de départ :
Conclusion de l’opération : nos deux nouvelles cases potentielles ont toutes les deux un score de 6… donc on va tester ces deux là…
en route pour l’étape 2 :
étape 2
Coût :
Heuristique :
Score total :
Déplacement possible à partir de la position de départ :
Là encore, toutes les nouvelles cases ont le même score 6 toujours, donc on persiste.
Et zou : étapes 3
étape 3
Coût :
Heuristique :
Score total :
Déplacement possible à partir de la position de départ :
Et là, affolant, un truc se passe : une case a un score de 5 alors que les deux autres plafonnent à 6… c’est sans doute dans cette direction qu’il faut aller…
Let’s rock’n step 4
étape 4
Coût :
Heuristique :
Score total :
Déplacement possible à partir de la position de départ :
et là encore le miracle se produit ! une case ressort de la masse avec un score inférieur aux autres !
Allons voir a l’étapes 5, si, enfin cette recherche pourrait arriver à quelque chose (parce que là les chtits dessins : J’EN PEUX PLUS).
étape 5
Coût :
Heuristique :
Score total :
Déplacement possible à partir de la position de départ :
Glory glory allelyuah ! on a trouvé la destination ! et ça c’est bien.
Maintenant tout ce qu’il reste à faire : c’est de remonter le chemin depuis la case de destination, jusqu’à la case de départ, chose facilité par le fait qu’on a toujours fait super gaffe à partir d’une position vers plusieurs, mais jamais le contraire (super clair, hein ?), en bref : quand on est sur une case on ne peut revenir en arrière que vers une et une seule case.
Et hop la solution est là :
voilà, l’A* a une fois de plus prouvé sa force !
Enfin presque, le problème principal de l’A* (et de la plupart des algos de pathfinding, d’ailleurs) c’est que le coût CPU n’est pas constant, certains chemins vont être super rapide à calculer, d’autres plus lents, et il faut aussi prendre en compte que les obstacles bougent dans la Vrai Vie (vous avez déjà vu un tank attendre au feu rouge, vous ?) (ndc1 : oui, à GTA VC)(nda : genre je l’attendais pas, celle la) obligeant parfois à recalculer le chemin en cours depuis le début !
Et après, il y a plein de détails d’implémentation et d’optimisation, que vous pouvez faire varier pour adapter l’algo à votre jeu.
Super, et comment j’adapte tes putains de cases à un beau FPS (ou à Barbie Chaval (ndc2 : QUOI ???)(nda : Pffff…))…
Bah c’est très bête : finalement, quand on la regarde de près, la map de case, on pourrait dire que c’est un réseau de cellules interconnectées comme ça :
et qu’est-ce qui nous oblige à les organiser comme ça, les cellules du réseau ?
bah rien…
et c’est obligé d’être que des angles fixes comme ça ?
bah non plus…
donc on pourrait déformer le graphe, pour suivre les contours de Q3-DM3 ?
bah ouais, et le plus grave dans tout ça ? hey bah c’est que ça marche ! (ndc1 : encore heureux putain)(nda : ça fait plaisir : y en au moins 1 que ça interesse… )
Quand un Level-Designer prépare un niveau, en plus des portes, armes, pickup et autres boutons divers et variés, il va aussi (souvent aidé par des outils qui vont ““découvrir”” le décors automatiquement) poser son réseau de path finding, comme ça les bots auront l’air moins cons !!
Et voilà !!!
(bon j’avoue j’ai pas fait l’éclairage, mais ça m’a pris plus longtemps que prévu, cette petite chose….)
Le bon lien qui va bien pour l’ia : www.gameia.com
Le bon lien qui va bien pour le devellopement de jeux en general : www.gamasutra.com
Et merci à tous les gens qui ont écrits des articles sur le pathfinding que j’ai pu piller comme un sale !
Et merci à tous les 3 gens qui ont corrigé : messieurs Lije, End[ER], et Moktar (nda : on peut dire “contrebat” comme dans “je m’en bat…”).
Et merci a End[ER] pour l’hebergement (sans accents).
Et le lien de Barbie Chaval, car, aparement, les gens ne connaissent pas : Barbie Chaval
Et enfin, tout de même, merci a moi même, parce que bon la, quand même, j’assure…
[EDIT]
c’t’imbecile d’editeur il prend tout les . ) et les transform en .) …
[EDIT]
micro correction pour faire plaisir a End[ER]
Ce message a été édité par c0unt0 le 04/07/2003
Ce message a été édité par c0unt0 le 04/07/2003
Un autre !