An Improved Algorithm for Searching Maze Based on Depth-First Search
Ying‐Hsuan Chen, Chang-Ming Wu · 2020
In this paper, we propose an algorithm based on depth-first search to search for unknown mazes and construct the maps. In order to obtain a complete map of the maze, we use stacks to store the coordinates and directions of the agents that have not been searched, and we must leave the stack empty to end the search. In order to speed up the search, we improve the depth-first search method, using two agents to search in the maze at the same time, and exchange the searched maze information when the two agents met. After searching, we can find the shortest path between any two points in the searched maze.