Magic Maze

Magic Maze est une interprétation du jeu de plateau Labyrinth de Ravensburger pour PSP. Je l'ai codé en LUA, un langage de script non compilé, donc n'importe qui peut jeter un coup d'œil au code source et le tripatouiller facilement.

De plus, je vais expliquer au fur et à mesure sur cette page les grands principes de l'intelligence artificielle du jeu. Je fais ça dans un but éducatif car j'aurais bien aimé trouver ce genre d'explications quand j'ai commencé à programmer. J'espère que ça pourra aider quelques personnes.

N'hésitez pas à me contacter si vous faites des découvertes intéressantes :)

TELECHARGEMENT & INSTALLATION

Téléchargez le jeu et décompressez-le dans le dossier MS_ROOT/PSP/GAME de votre carte mémoire PSP.

Magic Maze 0.2.6

Pour jouer sous sur PC, décompressez le jeu quelque part sur votre disque dur. Vous aurez en plus besoin de LUA Player. Téléchargez et décompressez le contenu de luaplayer.rar dans le dossier MagicMaze, puis lancez le jeu avec MagicMaze.bat

Lua Player 0.20

ALGORITHME DE PATHFINDING

Le principe de recherche du trésor dans le labyrinthe est assez simple: nous allons bêtement scanner tous les chemins possibles à partir de la case contenant le personnage !

Tout d'abord, donnons une valeur de distance d=0 à cette case... Magic Maze Pathfinding

... Puis une valeur X à la case contenant le trésor. Pourquoi X ?

X Marks the spot
"X Marks the spot!" - Dr. Henry Walton Jones Junior

Il faut ensuite scanner dans l'ordre chaque case du tableau tant que l'on a pas trouvé le trésor, ou que l'on ne peut plus avancer. Chaque fois que l'on tombe sur une case ayant pour valeur la distance courante, on analyse les cases contiguës haut, bas, gauche et droite. Si ces cases sont inoccupées et reliées à la case d'origine, on leur donne la valeur d+1. Dans notre cas, à partir de la case 0, nous pouvons avancer à gauche et en bas.

Magic Maze Pathfinding

Une fois toutes les cases scannées, et si nous avons trouvé des cases pouvant accueillir la valeur d+1, nous incrémentons la distance d de 1 et nous scannons à nouveau toutes les cases. Dans l'exemple, les cases contigües aux cases de valeur 1 prennent une valeur 2.

Magic Maze Pathfinding

Et ainsi de suite jusqu'à obtenir l'un de ces deux cas:

  • Une des cases devant prendre la valeur d+1 possède déjà la valeur X... Le trésor est trouvé !
    On donne la valeur d+1 à la case au trésor et on arrête de scanner.
  • On ne trouve plus de cases contiguës à qui donner la valeur d+1.
    Pas de trésor cette fois-ci... et on arrête de scanner.

Au final, le tableau se remplit avec plusieurs chemins, dans notre exemple, jusqu'au trésor:

Magic Maze Pathfinding

NETTOYAGE DU CHEMIN

Pour différencier le bon chemin, il nous faut les coordonnées d'arrivée (x,y) dans le tableau, ainsi que la valeur d de cette case. Ce peut être la case contenant le trésor ou une case proche. En remontant d jusqu'à 0, nous arrivons immanquablement à notre point de départ. C'est notre fil d'Ariane.

Dans notre exemple, la case contenant le trésor a une valeur d=5. Tout d'abord, ajoutons 100 à la valeur de la case trésor pour différencier le chemin. Puis nous allons tester les cases contiguës au trésor, mais sans scanner tout le tableau: testons les cases x-1, x+1, y-1 et y+1 jusqu'à trouver la valeur d-1. Ici la case du haut vaut 4. Ajoutons 100 à la valeur de cette case, puis nous déplaçons le centre de recherche avec y-- et continuons de scanner en croix pour trouver la valeur 3, et ainsi de suite jusqu'à arriver à 0.


Passons au nettoyage !

Rien du plus simple, il suffit de scanner une dernière fois entièrement le tableau:

  • On soustrait 100 aux valeurs > 100.
  • Ou on supprime les valeurs < 100 sauf la case 0.

Au final nous obtenons un joli chemin qu'il suffit de suivre avec le fil d'Ariane, mais à partir du personnage.

Magic Maze Pathfinding

♥ TECHNIQUE D'APPROCHE ♥

Si le trésor ne se trouvait sur aucuns chemins, il faut s'en rapprocher et définir une case qui sera notre case d'arrivée avant nettoyage. Calculons la distance entre chaque cases de chemins ayant une valeur numérique et le trésor. La distance se calcule simplement avec:

Distance euclidienne

A priori, la case la plus proche devrait être la meilleure. Hors l'exemple suivant démontre le contraire:

Magic Maze no path

Aucun personnage ne peut atteindre le trésor en un seul coulissement de couloir, ils vont donc seulement éviter de s'éloigner du trésor, du coup plus personne ne va bouger...

Ce cas arrive assez souvent quand une seule ou deux IA jouent entre elles.

Pour éviter ceci, nous allons définir des zones où il vaudra mieux s’arrêter plutôt que contre la case trésor. Une fois les chemins tracés, si la case trésor n'a pas été rencontrée, testons les cases alentours. Les cases n°1 et 2 permettent de ne pas être au plus proche du trésor et donc de pouvoir continuer à se déplacer:

Magic Maze no path

Approche n°1
Testons si l'une de ces cases a une valeur numérique. A partir des coordonnées du trésor, testons (x+1, y+1), (x-1, y+1), (x-1, y-1) et (x+1, y-1).

Approche n°2
Si aucune case n°1 n'a de valeur numérique, passons aux cases n°2. Toujours à partir du trésor, testons (x+2, y), (x, y+2), (x-2, y), (x, y-2).

Approche n°3
Toujours pas de valeur numérique?
Testons les cases contiguës au trésor avec (x+1, y), (x, y+1), (x-1, y) et (x, y-1).

Si aucune de ces cases n'ont de valeur numérique, nous pouvons finalement utiliser la technique de calcul de distance expliquée précédemment.

Ce moyen d'approche permet d'éviter que les personnages contrôlés par l'IA ne bougent plus, mais n'est pas sans faille. Bien sur, il faudra optimiser tout ceci en observant les probables connections de chemins et en évitant d'avantager les autres joueurs lors du coulissement de couloir...

Tout ceci sera pour une prochaine version du jeu !

Translate TRANSLATE Translate        Traducir TRADUCIR Traducir

Share Txori on Facebook Follow Txori on Twitter Add Txori to your RSS feed

Catégories

Archives

Tags

Derniers articles