About Escape the Maze

The sheer joy of solving mazes has enthralled us all at some point or the other. Given a maze with often more than one choice to make from each cell, you need to find a path to reach the destination from a fixed source. In this mini project, an attempt is made to emulate a very basic version of this beautiful mind game.

The user is asked for dimensions of the maze, the source, or the starting point, the destination, and the method of solving of the maze. Once the user inputs the dimensions of the maze, the maze is autogenerated by creating a complete matrix, and removing walls using the DFS method to ensure that every cell is reachable.

Also, the user is provided with three potential ways of solving the maze - the traditional DFS, the intuitive direction based DFS, and Djikstras approach. While the traditional DFS and Djikstra's approach needs no explanation, the intuitive DFS is based on direction sense and human intuition.

The path travelled is relative to the destination - for example, if the destination is seen to be on the top left of the pointer's current location, the the next move will be in either the top direction or the left direction, depending on which wall is open.

A little more

Escape the Maze a project that Meghana, Kumar and I worked on over the duration of our Algorithms course in college. While words like Floyd's and Warshall's and Johnson's and Djikstra's were being thrown at us, we were still most comfortable with only the easier methods of breadth first search and depth first search.

Meanwhile, we were told that Djikstra's was an efficient algorithm - but only after this project did we understand how much more efficient it actually was. For example, depth first search took about 25 seconds to find the destination on average, in a 35 x 35 maze. Guess how long Djikstra's took. Three seconds. Yeah.