MAZE SOLVING WITH DEAD END FILLING USING IMAGE PROCESSING FOLLOWED BY A

Ruby Shrestha
2017
BSc.CSIT
Semester 7
Downloads 2

Path finding and agent movement are considered to be the core of AI Movement System. Automatic Maze Solver is based on the concept of such core AI Movement System components. Automatic Maze Solver aims to obtain maze path(s) from a maze image uploaded by the user, which can be any viewable natural maze or prior produced or pressed maze. In this project, the maze image uploaded by the user is digitized by the system and preprocessed for proper maze interpretation. Median filtering, Niblack thresholding and Zhang-Suen thinning are used during the preprocessing phase. The preprocessed maze is then acted upon by mixed module implementation for solving it. Mixed module implementation in the context of the project includes Dead End Filling with Image Processing, to find all possible paths in the maze, followed by Graph Theory based approach, A*, to find the shortest path. The implementation has been tested and confirmed to work with Rectangular, Circular and Hexagonal mazes; however, since the implementation approach is generic, it works fine with other maze shapes as well provided they have only two openings (start and end) at the edge of the maze. The overall system performance has been tested using 10 different mazes and the maximum total time obtained was 34.151 seconds.

Path Finding
Maze
Automatic Maze Solver
Image Processing
Graph Theory

Similar Projects