The 4 masters of a dark citadel rush to be the first to collect the 4 keys.

Below on how to play

The Project

This is a Python project to develop an A* algorithm. That is, a pathfinding algorithm that tries to connect 2 points with the shortest path. In this case the pathfinding happens in a maze,  where obstacles change turn by turn, so there is an extra layer of complexity. 

Visual representation of the algorithm:

Which can be viewed as a graph as well:

How it works: when a CPU plays its turn (below all the steps of a turn), it runs some simulations, cloning the state of the game board and playing some logical moves. For each simulation, the A* algorithm (the one visualised in the pictures) is run to evaluate the results. If the player is connected to the goal, and is close to it, more points are awarded to the simulation. If the goal is unreachable, points are deducted. In addition, the states of other players are considered as well: all things being equal, simulations that make it harder for opponents to reach their goals are favored.

Finally, the Godot engine was used to create a visual interface, integrating and adapting the Python code to make it work visually.

How to Play

Goal: each player must enter all 4 grand tiles, the orange tiles that display the icon of their corresponding key:

A piece can move only if 2 tiles are fully connected, as shown below:

tile 1 and 2 are not connected. 2 and 3 are

A Player's Turn

1.  Throw the dice. 
2. Remove a tile from the board game, minding that only tiles that do not contain any player and the 4 grand tiles can't be removed. 
3. Using the empty space left by the removed tile, move rows or columns of tiles in any direction, up to the number shown on the dice.
4. Put the removed tile back into the board. Before doing that, you can rotate the tile
5. Move your piece by 1 space, if possible

____________________________________

Note: this game draws inspiration from the 2010 LEGO® Harry Potter® Board Game.  Fame mechanics are based on that edition’s rules, but differ a bit and have been adjusted for educational purposes only. No trademarks, graphics, or text from the original have been used.