Maze Solving with Anomaly Tolerant Dead End Filling and A*: Implementation and Analysis

Keywords: Path Finding, Automatic Maze Solving, Image Processing, Dead End Filling, Anomaly Tolerant, A*
Ruby Shrestha - Department of Computer Science, Deerwalk Institute of Technology, Kathmandu, Nepal
Published Date: 2019-04-03

Maze solving, based on the concept of path finding and AI agent movement, has numerous solving techniques and approaches. This paper aims to propose, implement and empirically assess a unique mixed model approach to solve maze image uploaded by the user, and intends to show that the approach is feasible and effective. The mixed model implementation involves anomaly tolerant dead end filling using image processing followed A*. Along with the primary aim of empirically assessing mixed maze solving approach, this paper also aims to introduce distortion/anomaly tolerant version of dead end filling algorithm and show its usage in maze solving. The maze image uploaded by the user is first digitized and preprocessed, and is then solved using mixed model implementation. The overall system performance is tested using 10 different maze images of varied sizes, shape and number of dead ends. With a size of 733 x 700 pixels and 179 dead ends, a maximum total time of 34.151 seconds is obtained. Moreover, the correlations of image properties with proposed model components are also evaluated. It is observed that the approach works with various maze shapes provided they have only two openings, at the edge, and are infected by only salt and pepper noise, if any; hence, the proposed model for maze solving is generic and practical with some limitations.

View PDF Download