Maze Solving Algorithms

From STAB Resources

Jump to: navigation, search


A maze is a set of lines and open spaces and solving the maze means finding a path consisting of only open spaces from a specified starting point to a specified end point. Maze solving has been extensively studied as a part of computer science. Maze solving is a part of many robotics events like Micromouse, our very own Nexus etc.

Maze1.gif

Contents

The Algorithms

Two of the most popular algorithms for solving a maze are

Depth First search is reasonably straightforward and intuitive. Breadth First Search on the other hand is somewhat involved. Each one is described below. A maze is often encoded as a 2-D array of 1's and 0's where the 1's represent an open space and the 0's represent a block. So the problem of solving now becomes the problem of finding a sequence of 1's from the start to the end such that from a particular place we can move only to one of the four surrounding positions (if they represent an open space).

Depth First Search

This is a straightforward algorithm. Given a start point we start moving along any path from it towards our goal and if we hit a dead-end (a point from where no paths other than the one by which we reached that point exist) we backtrack our path by one step and take an alternate path after backtracking. The algorithm is described in steps below.

Pseudocode

1  procedure DFS(G,v):
2      label v as explored
3      for all edges e in G.incidentEdges(v) do
4          if edge e is unexplored then
5              w ← G.opposite(v,e)
6              if vertex w is unexplored then
7                  label e as a discovery edge
8                  recursively call DFS(G,w)
9          else 
10             label e as a back edge


This way we will exhaust all possible paths. But this algorithm is time inefficient and might end up doing too much backtracking.


Breadth First Search

This algorithm thinks like a computer should and better uses the power of a computer to compute. It uses much more space than the previous algorithm but is much faster. Above all it finds the shortest possible path to solve the maze which makes it the most popular algorithm in use. It's description requires the definition of a 'queue' as a datastructure

Here's the description of the algorithm. The basic idea is that instead of exploring a single path till we hit a dead end, starting from the start point explore every possible path at once by branching out to all possible paths from an empty space. First we create an empty queue and 'enqueue' the starting position into it. Then we recursively dequeue elements from the queue, and for every element removed from the queue we mark it as traversed and search for all the possible surrounding positions which have not been traversed yet and enqueue these positions at the back of the queue. Every time we remove an element from the queue we check if we have reached the goal. This will termonate when we reach the goal and since at every stage a single step is being added to all possible paths the final path we obtain will be the shortest path.


Pseudocode

1  procedure BFS(Graph,source):
2      create a queue Q
3      enqueue source onto Q
4      mark source
5      while Q is not empty:
6          dequeue an item from Q into v and mark v
7          for each edge e incident on v in Graph:
8              let w be the other end of e
9              if w is not marked:
10                  enqueue w onto Q
Personal tools
Namespaces
Variants
Actions
Navigation
Clubs
Toolbox