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:
“The Gettysburg speech is at once the shortest and the most famous oration in American history. Put beside it, all the whoopings of the Websters, Sumners and Everetts seem gaudy and silly. It is eloquence brought to a pellucid and almost gem-like perfection—the highest emotion reduced to a few poetical phrases.”
—H.L. (Henry Lewis)
“Examples are cited by soldiers, of men who have seen the cannon pointed, and the fire given to it, and who have stepped aside from he path of the ball. The terrors of the storm are chiefly confined to the parlour and the cabin.”
—Ralph Waldo Emerson (1803–1882)