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 shortest answer is doing.”
—English proverb, collected in George Herbert, Jacula Prudentum (1651)
“A few hours’ mountain climbing turns a rogue and a saint into two roughly equal creatures. Weariness is the shortest path to equality and fraternity—and liberty is finally added by sleep.”
—Friedrich Nietzsche (1844–1900)