aMAZE
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.