Je postais la dernière fois un article sur un algorithme maison de pathfinding, en y expliquant son fonctionnement et ses limites.

Il m’avait été reproché de vouloir réinventer la roue, ce qui n’était pas faux. Disons juste que je prenais plus cela comme une simple distraction, plutôt que comme un objectif à remplir dans des délais impartis et aux résultats nécessairement optimaux, demandant moult recherches et documentations.

Dans tous les cas, les commentaires étaient très intéressants et ont nourri mon petit esprit avide de nouvelle sensation. C’est pourquoi j’ai décidé de réécrire mon algorithme de pathfinding de manière à le rendre beaucoup plus performant et complet, en y incorporant le Dijkstra, algo classique en matière de pathfinding.

Je n’expliquerai pas aujourd’hui le nouveau fonctionnement de mon algorithme, mais je peux ici en énoncer les grandes lignes :

Le Dijkstra permet une optimisation du choix de la meilleure voix : Il est plus rapide et ingénieux que de bêtement mesurer un par un tous les chemins et de trouver le plus petit.

Mais il restait encore à les trouver les chemins ! Ce qui est primordial, et que le Dijkstra ne permet pas de faire (à ma connaissance).

J’ai donc récupéré l’idée globale de mon ancien pathfinding et je l’ai améliorée en m’aidant des idées mises en évidence dans les commentaires, pour créer une sorte de « wayPointing automatique » :

Là où dans beaucoup de jeu, les WayPoints (ces points de passage disposés par les designers dans les niveaux des jeux pour permettre à l’IA de s’y retrouver - ce qui est assimilable à de « la triche ») sont d’habitude placés placés manuellement, mon algo détecte les endroits clés qui nécessitent le placement d’un WayPoint, de manière à créer les balises dont nous aurons besoin par la suite pour former les chemins, que le Dijkstra analysera enfin.

Pour ce qui est des collisions avec les blocs, l’algo est resté le même et se base sur des résolutions mathématiques d’intersections.

Mais trêve de papotage, voilà une démo très concluante de ce nouvel algo que je viens de passer toute mon après midi et ma soirée à programmer :

Déplacez les drapeaux pour changer les points de départ/arrivée. Si vous voulez vérifier que le way-pointing est bien automatique, vous pouvez même déplacer les blocs. Mais attention à ne pas faire de passages trop étroits, car l’algo gère la largeur et prévoit si le personnage pourra passer ou non.

Quand le chemin est trop dur à trouver, ou qu’il est impossible à trouver, l’algo est programmé pour « abandonner la partie » : quand il atteint un certain seuil de complexité. C’est le « Max Cycles » auquel correspond le bouton dans la démo. Vous pourrez voir que s’il est mis très bas, l’algo ne retrouvera plus que les chemins les plus simples et sera totalement incapable de sortir du labyrinthe.

Il sera possible, simplement en améliorant l’algo de détection des collisions et en changeant légèrement l’auto-way-pointing (et sans toucher au pathfinding proprement dit), de pouvoir incliner les blocs au lieu de les laisser tous droits, ce qui ouvre beaucoup de perspectives !

Au niveau des perf’ :

Dans cette démo, quand vous déplacez les drapeaux, le pathfinding est recalculé en temps réel, 50 fois par seconde (avec le vieux langage du Flash, qui n’est qu’un semi-script peu rapide, en plus). Ainsi il se peut que lors des calculs effectués, les FPS diminuent.

Mais il faut bien savoir que dans le jeu final, il y aura beaucoup moins d’appels au pathfinding, qui ne seront que ponctuels, et se feront sur des niveaux beaucoup moins complexes !

Voilà, amusez-vous bien et dites-moi si vous repérez des anomalies.