Maze Solver

Usage

python3 maze_solver.py [help | -help] <path> [-s <save_path>]

-help (optional): prints usage
<path>: path to an image of a maze
-s (optional): the result will be saved, if there's no <save_path> after it, save path will be the current working directory
<save_path> (optional): path to where the image will be saved

Showcase

• example image (maze300.png) and the resulting output:

• example image (maze500.png) and the resulting output:

Using your own mazes

• the mazes it can solve have to follow a certain set of "standards" I've accounted for:

1. it has to be either a square or a rectangle, doesn't work with round mazes or other unconventional maze shapes

2. it has to have an entrance and an exit, i.e. two places where the outer wall is discontinuous (has a hole)

About the maze examples in \mazes

• the number always rougly corresponds to the number of pixels per side if it was a square image
• for example maze300.png -> you can assume that the image size is 300x300 px
• maybe you've noticed that maze400_2.png doesn't fully obey the maze standards I mentioned before this, yet it still works. That's because when it gets cropped, we're only looking for the top left, bottom right, and then top right corner of the maze, so you might be able to successfully use some weird shapes.

How to run

1. Clone

   git clone https://github.com/triskj0/maze-solver.git
   
   cd maze-solver

2. Install required packages

   python3 -m pip install -r requirements.txt

3. Compile grid_dijkstras_algorithm.pyx into .pyd for better performance

   cd src
   
   python3 cython_setup.py build_ext --inplace

4. Run with an example maze

   python3 maze_solver.py ..\mazes\maze300.png

Does the program seem to overlook a wall?

• in case you get an incorrect result, consider whether the cause of this could be thin walls, the image gets scaled down so when the walls are too thin, the program doesn't see any after scaling

• try dilation

   python3 maze_wall_dilation.py <path> <number of iterations>

  path = path to the image that yields bad results
  number of iterations (optional) = how many times should we dilate, more iterations -> thicker walls, recommended amount: 1-3

• this will save the dilated image into your current working directory