Solving a Maze
From STAB Resources
Contents |
Solving a Maze using Image Processing
Can you solve this maze?
Simple, isn't it? Now can you solve this one?
Mazes can very elegantly be solved using image processing.
Check out this video It illustrates how easy it is to solve a maze in Adobe Photoshop, which is nothing but a graphical image processing tool.
How to solve any maze in 3 easy steps
The Algorithm
- Select one part of the maze. Convince yourself that the solution lies at its boundary
- Now expand the selection by few pixels
- Next, contract it and keep the border
- Voila! You have your solution!
Sounds easy?
Sample Code in OpenCV
#include <iostream> #include <opencv/cv.h> #include <opencv/highgui.h> using namespace std; using namespace cv; int main() { Mat maze; maze=imread("simple_maze.png",0); Mat solved_maze, dilated, eroded; eroded=maze.clone(); dilated=maze.clone(); imshow("maze",maze); vector<vector<Point> > parts; vector<Vec4i> hierarchy; findContours(maze,parts,hierarchy,CV_RETR_LIST,CV_CHAIN_APPROX_NONE); cout<<parts.size()<<endl; solved_maze=maze.clone(); Mat dst = Mat::zeros(maze.rows,maze.cols,CV_8UC3); dst=maze.clone(); //Scalar color(255,0,0); //drawContours( dst, parts, 0, color, CV_FILLED, 8, hierarchy ); imshow("dst",dst); erode(maze,eroded,Mat()); imshow("eroded",eroded); dilate(eroded,dilated,Mat()); imshow("dilated",dilated); waitKey(); return 0; }
