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

The Algorithms

Two of the most popular algorithms for solving a maze are

  • Breadth-First search
  • Depth-First search.

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.

  • Set our current position as the start position.
  • Create a list of already visited positions and another one of inaccessible positions both of which are empty in the beginning.
  • From our current position find all the possible moves and take the one that takes us closest to the goal among the possible positions. Add the current position to the list of already visited positions. Add any 0's (blocks) detected into the list of inaccessible positions. Update the current position to the new position and check whether the goal has been reached or not.
  • If from a point we have no possible moves we move back one step. This involves setting the current position as an inaccessible position, popping the latest inserted element from the list of visited positions and setting this as the current element.

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

  • Queue : Think of it as any normal queue we come across in real life. We can do two main operations on it namely, 'enqueue' an element or 'dequeue' an element. The operation 'enqueue' inserts the element at the end of the queue whereas 'dequeue' removes the element at the top of the queue.

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