3D Maze Solver
Author: Luke Larson
Professor: Dr. Zoe Wood
Course: CPE 471
Quarter: Spring 2013
Description
3D Maze Solver generates a 3D scene from an ASCII file containing specifications for a maze. Once the maze has been parsed and rendered, 3D Maze Solver will solve the maze in real-time. After successfully completing the maze, the solver will pause and play a success animation allowing the viewer to see the correct path through the maze. Techniques utilized: Phong shading, texturing, WASD + yaw + pitch camera movement, and a depth-first search algorithm to solve mazes.
- Mappings
- n/m - toggle wireframe
- q - quit
- a - move left
- d - move right
- w - move forward
- s - move back
- mouse - pitch and yaw
Example ASCII Maze
@@@@@@@@@@@@@@@@@@@@@
@.......@.......@..X@
@.@.@.@@@.@@@@@.@.@.@
@.@.@.@.......@...@.@
@.@.@@@.@@@@@@@@@.@.@
@.@.......@.....@.@.@
@@@@@@@@@@@.@@@.@.@.@
@...@...@...@...@.@.@
@.@.@.@.@.@@@@@.@@@.@
@.@...@...@...@.....@
@.@@@@@.@@@.@.@@@@@@@
@...@...@...@.......@
@.@.@@@@@.@@@@@@@@@.@
@.@.....@.@.....@.@.@
@.@@@@@.@.@@@.@.@.@.@
@.....@...@...@...@.@
@@@@@@@.@@@.@@@@@@@.@
@S@...@.....@.......@
@.@.@.@@@@@@@.@@@@@.@
@...@.........@.....@
@@@@@@@@@@@@@@@@@@@@@
- Character meanings
- @ - wall
- . - path
- S - start
- X - end
Screenshots
The example ASCII maze rendered and solved. Blue tiles are visited, yellow tiles are part of the solution, the green tile is the start position, and the red tile is the end position.
The solver is green when progressing and red when backtracking from a dead end.
Wireframe mode allows the solution path to be seen through walls.
Free camera movement allows spectators to view mazes from interesting angles.
Mazes can be up to 100x100 blocks. The larger mazes' solutions often form interesting patterns.
References
- Depth-first search: https://en.wikipedia.org/wiki/Depth-first_search