A Review of Various Maze Solving Algorithms Based on Graph Theory |
Author(s): |
| Navin Kumar , Sri Sai College of Engineering & Technology, Manawala, Amritsar; Sandeep Kaur, Sri Sai College of Engineering & Technology, Manawala, Amritsar |
Keywords: |
| Maze Solving, Graph Search Algorithms, Artificial Intelligence, Image Processing |
Abstract |
|
Solving a maze using computers is a complex though enticing task as one needs to come up with an algorithm that is effective in terms of time withal space for finding the shortest path. There is an ample number of graph algorithms to solve this problem, each one surpasses the other in performance aspects. This paper reviews different graph algorithms for maze solving along with their performance. The image of the maze is first processed by using GD library[1] functions in PHP[2], eventually, converting it into a graph data structure. A particular graph search algorithm is subsequently applied to find the shortest path between the start and the end node which is then mapped back to the image highlighting the solution. An "8X8" maze is used here for studying the performance of all graph based algorithms. |
Other Details |
|
Paper ID: IJSRDV6I120362 Published in: Volume : 6, Issue : 12 Publication Date: 01/03/2019 Page(s): 431-434 |
Article Preview |
|
|
|
|
