Maze Solving

---

---

A maze is a programming puzzle involving a collection of paths. What we seek to do here is construct an algorithm that will traverse a path starting from a specified location and ending to a destination location.

A Maze is typically given as an N*N array, eg. maze[N][N]. Imagine you're a rat trapped in the maze and you have to traverse the blocks to go from the Start to the Destination block. Reaching the destination blocks allows you to escape the maze and go free! The rat only possesses elementary movement abilities, either left/right or up/down. It's a 2d world for the rat and it suits us nicely.

In this example, we want to be able to construct a maze dynamically based on however many amount of rows and columns it consists of; for this reason we opted to use a vector of vectors - 2d vector called "maze".

You can provide whatever maze you want as input to this program. Use a file, place it somewhere inside the project and run the program by specifying the name of the maze as input. You can do this in Visual Studio, by Project Properties -> Debugging -> Command arguments -> write “maze.txt” (without the quotes).

To create your own mazes to supply as inputs to the program keep on reading to learn the proper format that this program requires. You will use the same ASCII characters. There's no restriction to the size of the maze, but obviously the larger it is, the slower the program to solve it.

• # indicates obstacles (the rat can't cross those)
• . : empty space (the rat can roam free)
• S : starting position
• G : ending (Goal) position
• = : path followed by the algorithm

So giving the maze “maze1.txt” below as input:

S#####
......
#.#.#.
#.#.#.
...#.G
##...#

Would output this:

S#####
======
#.#.#=
#.#.#=
...#.G
##...#

Algorithm

I went for the Breadth First Search algorithm to traverse the maze, which requires a Queue data structure. BFS is not an optimal (best choice) but it is a sensible choice. BFS will always find the shortest path to the destination, if one exists.

I provide my own implementation for a quickly put-together handicapped C-like queue (but you can change that to std::queue if you want).

1. construct a 2d array (vector) to store the maze
2. initialize the Queue
3. read the maze from the file character-per-character and place them to the 2d vector/array. At the same time when you get to the S block place it to the queue (enqueueit).
4. close the file when done reading
5. LOOP: while the Queue is not empty, peek its head square and name itcurrent 
6. start removing /dequeueing  Node s from the Queue repeatedly, placing them in traceablePathvector, till you find the S node - we want to begin our path traversal from the starting (S)!
7. if current square is the destination square ie. G then we're done. If so mark the correct path. This will be our reconstructed path, going from the Goal 'G' square backwards to the first 'S' square found in traceablePath.
8. Otherwise, investigate the 4 possible places (neighboring squares) to go ie. left, right, up & down. If those haven't already been visited, then enqueue them to the Queue as a Node, to be checked for later.
9. go to step 5

Be sure to check the link down below by Robert I. Pitts timeless article on the topic; it's succinct and he nails it. Here's some of my personal hand-written notes on BFS and path finding:

Although the compiler is C++ you should know that this is code adapted from C - a university course assignment - so take note that this code should not be used as an exemplary way to program in C++.

For completion sake, I have also provided the same program written in pure C. It is located inside the c folder and there's a makefile to build it cross platform (provided you have make - for windows get MINGW). Just go to the directory, open up a command prompt and type make.

I used Windows and Visual Studio to build the project.

Github

Github repository link.

Acknowledgements

Recursion: Solving a Maze link by Robert I. Pitts