mazeSolver

In their paper "A Maze Solver for Android", Rohan Paranjpe and Armon Saied devised a method to automate solving mazes with nothing but a picture of said maze. My partner and I decided that this would be cool to implement ourselves, and did so accordingly. Many of the things we found in the paper were absolutely crucial to the success of the project, such as using a median and Otsu's filter to preprocess the image, and using the Zhang-Suen algorithm to generate a 1-pixel wide path. However, we innovated on some of their methods, like generating a graph out of the thinned path so that future iterations of the project can handle a more robust problem space (like multiple entrances or exits). Our entire algorithm runs in a little less than a minute on average for a 720x1080 image. The run time of this algorithm is comparable to the time it would take the intended audience of these mazes, elementary school children, to solve. Improvements to the run time of this algorithm can be made by improving our implementation of the Zhang-Suen algorithm, as this is currently the most computationally expensive step.

Built With

• html
• javascript
• node.js
• opencv
• python