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

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

É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 :

Des screens du jeu en mode debug quand j'ai programmé mon algo :

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

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.