Shortest Path Algorithm
When a maze has multiple solutions, the solver may want to find the shortest path from start to finish. One possible algorithm finds the shortest path by implementing a breadth-first search, while another, the A* algorithm, uses a heuristic technique. The breadth-first search algorithm uses a queue to visit cells in increasing distance order from the start until the finish is reached. Each visited cell needs to keep track of its distance from the start or which adjacent cell nearer to the start caused it to be added to the queue. When the finish location is found, follow the path of cells backwards to the start, which is the shortest path.
Read more about this topic: Maze Solving Algorithm
Famous quotes containing the words shortest and/or path:
“Cultivated labor drives out brute labor. An infinite number of shrewd men, in infinite years, have arrived at certain best and shortest ways of doing, and this accumulated skill in arts, cultures, harvestings, curings, manufactures, navigations, exchanges, constitutes the worth of our world to-day.”
—Ralph Waldo Emerson (1803–1882)
“I notice well that one stray step from the habitual path leads irresistibly into a new direction. Life moves forward, it never reverses its course.”
—Franz Grillparzer (1791–1872)