Author image

Maze Solving


Difficulty:
2/5


A maze is a programming puzzle involving a collection of paths. And the programmer must 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 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.

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 to the program continue reading to learn how my mazes are written. 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 will be 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

And now a little bit about the algorithm used to solve the maze. I use the Breadth First Search algorithm to traverse the maze, which requires a Queue data structure. BFS is not the optimal, or the 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. For more on BFS and path finding check out my personal notes of it:

breadth first search

I used Windows 8.1 x86_64, Visual Studio 2017 to build the project.

Although the compiler is C++ you should know that this is code adapted from C, so it is typically programmed using C standards - so 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 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.

Github

Github repository link.

Acknowledgements

Recursion: Solving a Maze link by Robert I. Pitts


0 likes