Python maze game

aMAZE is a Python-based maze game my classmate Michael Steer and I designed for a school project. The objective of the game is to navigate out of a maze while competing against a computer opponent. The game has varying degrees of difficulty such as the maze size and "intelligence" of the computer.

My role in the project was to design the maze generation and AI algorithms.

The AI uses modified depth-first search (DFS) and A* search algorithms to traverse the maze.

A maze can be represented as an undirected graph where each intersection is a node and each path is an edge. The AI uses modified depth-first search (DFS) and A* search algorithms to traverse the maze (graph) and find a path from start to finish.  It also uses a standard breadth-first search to find the shortest path.  The AI's path is computed when loading the game. This is done by traversing the maze from the start point until it reaches an intersection. It then chooses which intersection to explore based on the selected difficulty. For higher difficulties, the AI chooses a path that brings it it closer to the finish (based on the manhattan distance), whereas lower difficulties will take it to a farther away from the finish. If the AI reaches a dead end, it retraces its steps until another path can be taken. This is repeated until the endpoint is reached.

AI Demonstration

Grid size: 16x16
Start: (0, 0) - top left
Finish: (15, 15) - bottom right

The AI's path decreases in length as it becomes "smarter".

Difficulty 0

Difficulty 60

Difficulty 100

Shortest path

For this particular maze, the AI set to difficulty 100 actually found the shortest path.

AI performance (path length) vs difficulty

Grid size: 32x32
Start: (0, 0) - top left
Finish: (31, 31) - bottom right

Each colour represents the AI performance over a unique, randomly-generated maze. The data point are the average path length from 1000 trials across the same maze.