Skip to content

Solve mazes from images with OpenCV and Numpy using the Dijkstra's algorithm

License

Notifications You must be signed in to change notification settings

jtris/maze-solver

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

77 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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:

screenshot screenshot

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

screenshot screenshot

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

good shape examplebad shape example

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

good number of openings (2)bad number of openingsbad number of openings

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.

maze400_2.png

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