Maze-solving algorithm: Difference between revisions

Revision as of 04:32, 27 January 2019

Revision as of 13:37, 12 February 2019

Line 127:

== Shortest path algorithm ==

[[File:MAZE 40x20 DFS no deadends.png|thumb|A maze with many solutions and no dead-ends, where it may be useful to find the shortest path]]

When a maze has multiple solutions, the solver may want to find the shortest path from start to finish. There are several algorithms to find shortest paths, most of them coming from [[graph theory]]. One possiblesuch 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 (data structure)|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. The breadth-first search in its simplest form has its limitations, like finding the shortest path in weighted graphs.

==See also==