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.
Téléchargez le jeu et décompressez-le dans le dossier MS_ROOT/PSP/GAME de votre carte mémoire PSP.
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.zip dans le dossier MagicMaze, puis lancez le jeu avec MagicMaze.bat
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... 
... Puis une valeur X à la case contenant le trésor. Pourquoi X ?
"X marks the spot!" - Dr. Henry Walton Jones Junior
Il faut ensuite scanner dans l'ordre chaque case du tableau tant que l'on n’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.
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.
Et ainsi de suite jusqu'à obtenir l'un de ces deux cas :
Au final, le tableau se remplit avec plusieurs chemins, dans notre exemple, jusqu'au trésor :
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.
Rien du plus simple, il suffit de scanner une dernière fois entièrement le tableau :
Pour finir nous obtenons un joli chemin qu'il suffit de suivre avec le fil d'Ariane, mais à partir du personnage.
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 :
A priori, la case la plus proche devrait être la meilleure. Hors l'exemple suivant démontre le contraire :
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 :
Approche n°1
Testons si l'une de ces cases a une valeur numérique. À 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 !
