Pathfinding dans un plan

Dans le cadre d’un nouveau projet, je me suis récemment retrouvé confronté à un problème de recherche de chemin. Pour résumer, j’avais une surface plane, de taille non fixée, sur laquelle se trouve différents obstacles, et le problème consistait à trouver un chemin reliant deux point de ce plan, en évitant bien évidemment les obstacles.
Le chemin ne devant pas forcement être optimal, mais plutôt rapide à trouver, je me suis donc penché sur l’algorithme A*, qui correspondait exactement à mes besoins. Reste alors à définir un graphe correspondant au plan et à ses obstacles sur lequel je pourrais appliquer l’algorithme.

La première idée est d’utiliser une grille, où chaque nœud pourrait correspondre par exemple à un pixel du plan. Cette méthode a l’avantage d’être assez précise, mais malheureusement trop gourmande en temps et en mémoire si la zone de travail devient trop grande.
L’utilisation d’une grille étant performant sur des petites zones, il pourrait être intéressante d’essayer de simplifier le graphe, en prenant par exemple un maillage plus grand qu’un simple pixel. Mais une fois encore, un problème se pose, non plus de performance, mais de cohérence dans le chemin. En effet, le chemin va donc passer par les nœuds de la grille, et ne sera donc pas forcement une ligne droite lorsqu’il s’agira de relier deux nœuds, même s’il n’y a pas d’obstacle.

L'utilisation d'une grille provoque un effet d'escalier.

Évidemment, la meilleure solution consisterait à obtenir un graphe collant parfaitement aux obstacles. Le problème restant de trouver comment l’obtenir. En fait, ce n’est pas aussi compliqué que ça peut en avoir l’air, car au final, on a seulement besoin de connaître les sommets des obstacles (à condition que ceux-ci soient des polygones, le cas des figures courbes est plus complexe et je n’en parlerai pas).
Le travail va donc se décomposer en plusieurs étapes:

• Création de la carte des obstacles.
• Création des sommets du graphe.
• Création des arrêtes du graphe.

Création de la carte des obstacles

Il n’y a pas énormément de choses à dire sur cette étape, elle dépend avant tout des besoins du programme. Dans mon exemple, je me contenterais d’utiliser des obstacles rectangulaires car ils sont plus simple à gérer, et que je n’ai pas eu l’occasion de travailler avec d’autre formes. A noter toutefois que rien n’empêche la superposition de plusieurs rectangles.

Les zones d'obstacles

Création des sommets du graphe

Deux sous-étapes sont nécessaires ici, la première consistant à ajouter les futurs nœuds, et la seconde à supprimer ceux qui ne sont pas valides et/ou inutiles.
Dans le cas d’un rectangle, il suffit de prendre les sommets déjà existant. J’ai, dans mon cas, eu besoin d’ajouter une marge autour de mes obstacles, de manière a ce que, lors de l’affichage final, les unités ne se superposent pas aux obstacles.
La marche à suivre est donc simple:

• Ajout des nœuds.

• Détection et suppression des nœuds invalides, c’est à dire qui se retrouvent à l’intérieur d’un rectangle.

Ce qui nous donne:

Les nœuds du graphe

Il y a d’autres tests possibles concernant la validité d’un nœud, comme la non-superposition avec un autre nœud, ainsi que le non-alignement de trois nœuds, cas dans lequel le nœud médian sera sûrement inutile (sauf si un obstacle les sépare).

De plus, une petite note technique, ici j’ai crée les nœuds puis je les ai testé, avant de les supprimer si ils n’étaient pas valides. Il est évident que pour faire les choses correctement, il est plus logique de ne créer le nœud que si la position à laquelle on veut le mettre est une position valide, c’est-à-dire faire le test avant de le créer. Dans le cas où ce n’est pas possible (on ne sait jamais), l’ordre création/test/suppression est une bonne alternative, moins gourmande en mémoire.

Création des arrêtes du graphe

La méthode est exactement la même que pour la création des nœuds, on commence par créer toutes les arrêtes possibles avant de détecter et supprimer celles qui ne sont pas valides:

• Ajout des arrêtes.
• Détection et suppression des arrêtes invalides. Il s’agit des arrêtes qui passent à travers un obstacle, ou qui sont incluses dans une autre arrête (bien que cette possibilité ne puisse arriver si les nœuds inutiles ont été supprimés).

On obtient alors:

Les arrêtes du graphe

Les mêmes remarques que pour la création des nœuds s’appliquent ici, à savoir que créer toutes les arrêtes pourrait être très gourmand en mémoire, surtout si la carte comporte de nombreux obstacles.
Certains auront surement remarqué que, depuis le début, je n’ai pas inclus les points de départ et d’arrivée dans le graphe. Il y a une bonne raison à cela: contrairement aux sommet des rectangles, ces nœuds là ne sont pas fixes, et les arrêtes correspondantes devront être recalculés à chaque déplacement, il est donc possible de pré-calculer les nœuds et arrêtes du graphe, et d’y ajouter à la demande les nœuds de départ et d’arrivée.

Résultat

Une fois le départ et l’arrivée inclus dans le graphe, il suffit d’appliquer n’importe quel algorithme de recherche de chemin pour obtenir le résultat recherché:

Résultat final

Pour les curieux, toutes les images, sauf la première et la dernière, ont été générée via un script php, disponible ici.
Ce script ne permet que de générer le graphe, et n’implémente pas la recherche de chemin.
Ayant codé ce script rapidement pour tester cette méthode, et n’ayant pas prévu à l’origine de le distribuer, la syntaxe est un peu brouillon et peu, voire pas du tout, commentée. Toutefois, son utilisation est suffisamment simple pour s’y retrouver.