Simulating a Maze Generation & Search

The course Programming with Structures was mainly about using algorithms and structures. For the maze generation the stack structure was used. The maze can be seen as a grid of cells, with a border between all cells. From the start cell an unvisited neighbour is selected randomly. The neighbour cell is added to the stack. The wall between the cell and its neighbour will be deleted and the neighbour cell becomes the current cell. This continues until a cell doesn’t have any unvisited neighbours anymore. At that point the top cell of the stack is deleted and the previous cell becomes the top cell of the stack. For this cell is checked if there are any unvisited neighbours, if so, again a random neighbour is selected etc. At the end all the cells are visited and the maze is generated.

For the search basically the same algorithm is used, the depth first search. It randomly selects a unvisited and accessible neighbour and add this cell to the stack. If there is no unvisited and accessible neighbour any more and the exit cells is not reached yet, the top cell is deleted from the stack and the previous cell becomes top. For this cell is again checked if there are any unvisited neighbours, a random neighbour is selected and added to the stack. Add the end the path of cells will be in the stack and drawn on the screen.