Portfolio site for Robert J. Heywood

Projects - C++ Maze

Project Details

Completion Date: May, 2008
Language: C++, DirectX

This project was created as coursework for university. The project was split into three parts and programming was done in C++.

First Part: Create a perfect maze and output it to a CSV file.

Second Part: Solve the maze generated in part one.

Third Part: Render the maze from part one in 3D and implement its solution as a first-person, virtual reality, walk-through.

The project was so interesting it seemed a shame not to combine all 3 elements. So the finished project now creates and solves perfect mazes of any size, and provides a virtual reality walk-through of the solution.

I started task one by developing a framework upon which all the tasks could be built. The framework is object-oriented and multi-platform. The framework ensured consistent code structure throughout the project and allowed the three separate parts to be combined at the end.

The generator prompts the user to sellect one of the following algorithms; Depth First Search, Prims, Kruscal and RJH. DFS, Prims and Kruscal are industry standard graph traversal algorithms randomised to generate mazes. RJH is an algorithm developed by me which works by growing walls from the edges of the maze.

The solver prompts the user to select either of the the following two algorithms; Depth First Search or A* (pronounced A star). These algorithms are suitable for path finding applications and were used to solve the maze.

The VR walk through is written in C++ and rendered in Direct 3D using my scheduling engine to dictate the frequency at which program modules should run. Each program module is self contained and can if required be reused in different projects quite easily. The size of the maze is limited only by avalible memory. By scheduling modules at different frequencies, the walk through is pseudo multi-tasking. This feature in addition to horizon clipping was used to keep the walk through responsive.