In QHJ #12 there was an article on Cellular Automata that discussed how CA could be used to quickly and easily solve mazes. On Usenet I’ve seen some postings that deal with other ways to solve mazes (the more “classical” approaches). I thought they would be of interest. – ED
Can anyone gave me suggestions as to algorithms for searching and finding the shortest path through a maze?
A maze can be thought of as a graph, where the starting point is the “start vertex” and the destination is the “end vertex.” Then by modeling the maze as a graph such that a vertex represents a “decision point” in the maze where more than one path can be followed, and where the edge represents the path between two such “decision points,” then the “shortest path” algorithm for a graph will find the shortest path in the maze.
_______________
|S X | S----------X-------X
|------ |----X| S = Start / /
|--X ---| __| | E = End / /
| | | X | X /
| | | --------| | X
| | ---- --- | | \
|__X_____X__|E| | \
X---------X-----E
We can create a “vertex” at all decision pints (“forks in the road”). There are marked “X” ni the graph above. The edges will exist if there’s a direct path between two X’s without crossing another X. We then have a graph, and when a “shortest path” algorithm returns the set of vertices (in order) which have been visited, we can “transform” the problem back to a maze and find the path selected. In the above example, there are clearly two paths that work; the “shortest” would depend on the length of the edges ( as represented by a “weight” for each edge. There are several “weighted graph shortest edge” algorithms, such as Dijkstra’s algorithm. Any decent book on algorithms will give you this algorithm ( and might even discuss a “maze-to-graph transformation” in more detail.
Tim Irvin J056600@LMSC5.IS.LMSC.LOCKHEED.COM
Breadth First Search. This requires marking maze cells as “distance K from entrance”, and appending the indices to these cells to a queue.
You can, for example, thread the queue through an array representation of the maze itself: if a cell holds (i,j,k), then it is distance k, and the next cell on the queue is cell (i,j).
BFS is basically this:
- mark and put in the queue neighbors of the entrance cell (distance k = 1).
- repeat this step until the queue is empty, or (*): mark the neighbors of the head of the queue (distance k+1) and append them to the queue, if they are not already marked; move the head-of-queue to successor.
(*) the first time the exit cell is marked, it’s distance to the entrance becomes known; a trace-back (k->..->0) can be done to produce an optimal path.
William Chang (wchang@csh1.org)