Gaming Maze

Les points de développement dont parle cet article ont eu lieu fin octobre 2010.

La grille était désormais construite et dotée d’un bon système de coordonnées. Un premier personnage sommaire, « Bonhomme » avait fait son apparition dessus et pouvait être placé facilement sur n’importe quel hexagone.

La prochaine tâche était de permettre au personnage de se déplacer…

En effet, dans notre jeu, l’utilisateur contrôlera différents personnages et il pourra cliquer sur les cases où il souhaitera les faire se déplacer.

Il est très facile de faire bouger le personnage d’une case vers une case directement adjacente. Il suffit de faire une petite animation dans laquelle il se déplace sur une ligne imaginaire tracée entre le centre de son hexagone et le centre de l’hexagone de destination.

On pourrait, de la même façon, envisager d’animer le déplacement du personnage jusqu’à une case très éloignée en le faisant bouger à nouveau sur une ligne imaginaire allant de centre à centre. Mais cela ne conviendrait pas pour notre jeu, car il est au tour par tour, et les personnages auront à chaque tour une capacité de mouvement limitée en nombre de cases (points de mouvement). Il nous faut donc pouvoir savoir précisément combien de cases un personnage va traverser.

D’autre part, cette méthode ne permettrait pas de gérer efficacement les obstacles et leur contournement.

Comme nous n’allons pas, de toute évidence, demander au joueur de déplacer ses personnages en cliquant case par case, car cela ferait un jeu plutôt fastidieux (!), il va nous falloir trouver un moyen de calculer toutes les cases intermédiaires entre la case de départ et la case de destination.

Pour un déplacement en ligne droite, le problème ne se pose pas. Je reprends l’image de la note de développement précédente :

Si par exemple Bonhomme est sur la case (10, 7) et doit bouger jusqu’en (14, 7), le programme saura qu’il devra d’abord amener Bonhomme en (11, 7), puis en (12, 7), puis en (13, 7), puis enfin en (14, 7). Il suffit de rajouter 1 en abscisse à chaque fois jusqu’à atteindre 14. Le programme connaîtra ainsi l’intégralité des cases intermédiaires entre (10, 7) et (14, 7) et il lui sera facile de représenter le mouvement de Bonhomme jusqu’à sa destination.

Et si l’utilisateur souhaite déplacer Bonhomme sur une case qui n’est pas en ligne droite comme (14, 5) par exemple, il suffira d’aller en (14, 7) comme plus haut, puis de passer par des cases qui ont 1 de moins en ordonnée, donc (14, 6) puis enfin (14, 5).

Il faut juste que le programme sache utiliser correctement les cases de la diagonale (cases jaunes sur l’image) lorsque c’est nécessaire pour toujours pouvoir proposer le chemin le plus court. Car dans un jeu où les points de mouvement sont limités, on ne peut pas vraiment se permettre de proposer au joueur un trajet non optimal, comme celui ci-dessous par exemple !

Ce trajet utilise 9 points de mouvement, là où 5 suffiraient.

Mais que faire si un obstacle, si des murs se dressent entre Bonhomme et sa destination ? Comment le programme va-t-il savoir quelles cases emprunter pour contourner ? Comment va-t-il faire pour savoir si la destination peut seulement être atteinte ?

Aussi intéressant que puisse être l’exercice de réinventer la roue, il semblait plus raisonnable de réutiliser un algorithme largement utilisé pour calculer les chemins (algorithmes dit de pathfinding) : l’algorithme A* (« A star »).

Je ne vais pas me lancer ici dans une description précise du fonctionnement de l’algorithme. Je vous renvoie à sa page Wikipédia. Pour ceux que cela intéresse, il y a aussi cette page qui décrit l’algorithme de façon détaillée en s’efforçant d’être pédagogique.

Je vais juste tenter de schématiser. On commence par considérer tous les hexagones adjacents à l’hexagone de départ (appelons-le Hexagone zéro) et qui ne sont pas des murs (qu’on peut utiliser pour le trajet donc).

Comme dit dans la note précédente, leurs coordonnées sont très faciles à récupérer.

Ensuite, on va donner un poids à chacun des hexagones considérés.

Ce poids est une sorte d’estimation de la pertinence de passer par cet hexagone pour atteindre la destination. Plus le poids est élevé, moins il semble pertinent de passer par cet hexagone.

Je dis « semble », car encore une fois, ce poids n’est qu’une estimation. Si on pouvait calculer directement la pertinence exacte de chaque hexagone pour le trajet, cela voudrait dire qu’on pourrait calculer directement le trajet sans recourir à l’algorithme.

Mais comment est réalisée cette estimation ? Elle dépend de deux paramètres.

Premier paramètre : le coût du voyage depuis l’hexagone de départ jusqu’à l’hexagone examiné. Mettons que cela coûte 10 de passer d’un hexagone à un hexagone adjacent. Tous les hexagones adjacents à l’hexagone de départ auront donc un coût de 10, ce qui n’avance pas à grand chose… Mais c’est là qu’on pourrait prendre en compte, si on voulait, d’autres paramètres comme la nature du terrain. On pourrait dire par exemple que traverser un hexagone de boue ou de ronces vaudrait 20, ce qui le rendrait moins intéressant à considérer de ce point de vue.

Second paramètre pris en compte : la distance en nombre d’hexagones entre l’hexagone examiné et l’hexagone de destination. Il y a une formule très simple qui donne le nombre d’hexagones entre deux hexagones en fonction de leurs coordonnées : nous allons donc pouvoir l’utiliser.

Le problème est que la distance donnée par la formule ne prend pas en compte les murs : c’est à cause de ce paramètre que le « poids » n’est qu’une estimation.

Maintenant qu’un poids a été attribué à chaque hexagone adjacent, on peut isoler en quelque sorte le « meilleur candidat au poste de premier hexagone du trajet » : celui qui a le poids le plus faible (ou l’un de ceux qui ont le poids le plus faible en cas d’égalité). Appelons-le Hexagone 1. On note dans un coin qu’on est arrivé sur cet hexagone en passant par l’hexagone de départ (Hexagone zéro) pour garder une trace de notre chemin, un peu comme Hansel et Gretel sèment des petits cailloux blancs pour marquer le chemin jusqu’à chez eux.

Quant aux autres hexagones adjacents qui ont été jugés moins intéressants, on les range dans une sorte de boîte imaginaire des hexagones qui pourraient servir plus tard.

Ensuite, on examine Hexagone 1 à son tour. On regarde :
- tous les hexagones qui lui sont adjacents,
- qui ne sont pas dans la boîte (autrement on aurait pu s’y rendre directement depuis Hexagone zéro sans passer par Hexagone 1),
- qui n’ont pas déjà été pris pour base (Hexagone zéro est donc exclus),
- et qui, bien sûr, ne sont pas des murs.

On calcule leur poids. Pour le paramètre coût du voyage, on calcule de la même façon mais on ajoute le coût du voyage d’Hexagone 1 parce qu’on veut considérer le coût total du trajet depuis l’hexagone de départ jusqu’à l’hexagone considéré.

En jaune clair, les hexagones de la boîte

En jaune, les nouveaux hexagones « pesés »

On sélectionne à nouveau celui qui a le poids le plus intéressant, on range les autres dans la boîte des hexagones qui pourraient servir… Et ainsi de suite jusqu’à ce qu’on atteigne l’hexagone de destination. Une fois qu’on l’a atteint, on peut reconstituer le trajet grâce aux petits cailloux blancs qu’on a semés. Plein d’hexagones de la boîte auront pu ne jamais avoir été pris pour base, mais ce n’est pas grave si nous avons atteint notre but.

Parfois on tombe sur des culs-de-sac : on a toujours pas atteint l’hexagone de destination et tous les hexagones adjacents à notre position sont dans la boîte ou sont des murs.
Dans ce cas, on doit revenir sur nos pas, pour, dans une bifurcation donnée, choisir par exemple le « second meilleur candidat au poste d’hexagone X du trajet » comme base. Pour cela, on utilise les hexagones rangés dans la boîte des hexagones qui pourraient servir.

Parfois, on découvre des chemins plus efficaces vers des hexagones donnés. On doit donc changer nos notes, nos cailloux. Ces deux derniers points sont expliqués de façon bien plus précise dans les liens que j’ai donnés plus tôt.

Et parfois, on a vidé la boîte sans atteindre la destination. Dans ce cas, c’est que le trajet entre l’hexagone de départ et de destination n’existe tout simplement pas.

***

L’algorithme fonctionne quelle que soit la forme des tuiles de la grille : hexagonales, carrées, triangulaires… Tout ce qu’on a besoin de lui fournir pour pouvoir l’utiliser sur la grille qu’on veut, c’est une formule qui lui permettre de déduire les coordonnées de toutes les tuiles adjacentes à une tuile donnée, et une formule lui permettant de calculer la distance en nombre de tuiles entre deux tuiles. Ces deux formules sont, de façon évidente, différentes selon la configuration de grille choisie.

Avec ces données, et celles du coût de voyage des différentes types de tuiles (s’il y en a), l’algorithme a tout ce qu’il lui faut pour fonctionner.

***

Plus la configuration de la carte est complexe, avec de nombreux murs, plus la boîte des hexagones à examiner est amenée à contenir d’hexagones. Voici une illustration sur une carte à cases triangulaires. Tous les triangles colorés sont ou ont été dans la boîte des triangles qui pourraient servir. Dans le cas d’un trajet simple, il y en a très peu :

Dans le cas d’un trajet plus compliqué, il y en a beaucoup. Parfois, cela couvre presque toute la carte.

Vous pouvez trouver l’application que j’ai screenée sur cette page et essayer vous-même de placer des murs et bouger les points de départ et de destination du trajet.

***

Une fois le fonctionnement de l’algorithme compris, il suffit de le traduire en Actionscript. J’ai récupéré une vieille version de mon code pour vous faire une petite application illustrant le pathfinding. L’affichage des déplacements n’étant pas optimisé dans ce fichier d’exemple, le personnage est susceptible d’avoir des déplacements non fluides dans certaines situations.

Vous pouvez survoler une case pour afficher le trajet du personnage jusqu’à cette case, cliquer pour le faire se déplacer. Cliquez sur « placer des murs » pour dessiner ou effacer des murs sur la carte.