Magic Maze

Réalisé au printemps 2022 en binôme.

3ème Année de Licence.

UE : LIFAP6 - Algorithmique, Programmation et Complexité.

Langage de programmation : C++.

Magic Maze est un jeu de société de Kasper Lapp où les joueurs doivent orienter des aventuriers dans un supermarché pour réaliser des objectifs. Le robot développé pour remplacer les joueurs est en mesure de calculer à partir d'une situation de jeu les meilleurs coups à jouer.

Déroulement du projet

1. Génération des tuiles : chaque tuile est un graphe composé de plusieurs nœuds. Les nœuds représentent les différentes cases d'une tuile.
   Les cases peuvent avoir des types différents (case SORTIE, case OBJECTIF,...).
   Les cases peuvent être séparées par des murs.
2. Union-Find : afin de pouvoir sortir, le joueur doit briser des murs. L'algorithme Union-Find permet de gérer un ensemble de classes d'équivalences. Dans notre cas, deux cases sont équivalentes s'il existe un chemin de l'une à l'autre dans la tuile. Initialement, vu que tous les murs sont en place, il n'y a aucun chemin d'une case à une autre. Il y a donc une classe d'équivalence par case, ne contenant que la case. À chaque mur abattu, s'il n'existait pas de chemin entre les cases de part et d'autre mur, abattre le mur en crée un. Ainsi les deux cases sont désormais équivalentes, et leurs classes d'équivalences sont fusionnées : toutes les cases accessibles depuis la case d'un côté du mur deviennent accessible pour toutes les cases accessibles depuis la case de l'autre côté du mur, et vice versa.
3. Plus court chemin au sein d'une tuile : parcours en largeur du graphe afin de déterminer le plus court chemin.
4. Gestion du supermarché : le supermarché permet l'assemblage de différentes tuiles.