How to find your way out of a maze

  0         1         2         3
  0123456789012345678901234567890123456
0 #################################E###
1 ###....#.....#......###...#...#...#.#
2 #...##...###...####.....#..##.#.##..#
3 #.#########.###....##.####.##.#.#..##
4 #.............##.######..#......#...#
5 #####.#####.#..........#.##########.#
6 #S..........###.#.#.##..............#
7 #####################################

• Maze is given as 2-dimensional array of characters.
• '.' = empty field
• '#' = wall
• 'S' = start position (6,1)
• 'E' = exit (0,30)

Goals

1. Is the exit reachable from the start? (Yes or No)
2. How many steps does it take to reach the exit on a shortest path?
3. Output a shortest path from the start to the exit.

Reachability of the exit field

Since the graph is already implicitly given by the character matrix of the maze, the only additional data structure we need is a color matrix:

int color[num_rows][num_columns];

• white = an undiscovered vertex (not yet in the queue)
• gray = a vertex currently in the queue
• black = a finished vertex (not in the queue anymore)

for row from 0 to num_rows-1 {
  for column from 0 to num_columns-1 {
    color[row][column] = white;
  }
}

q = new queue();
q.enqueue(start_row,start_column);
color[start_row][start_column] = gray;

while (q.head != q.tail) {
  v = q.dequeue();
  color[v.row][v.column] = black;
  for each (r,c) adjacent to (row,column) {
    if (maze[r][c]!='#' && color[r][c]==white) {
      q.enqueue(r,c);
      color[r][c] = gray;
    }
  }
}

switch (color[exit_row][exit_column]) {
  case white: 
    print("Exit is unreachable");
    break;
  case black: 
    print("Exit is reachable");
    break;
}

Computing Distances

int distance[num_rows][cum_columns];

• We set the distance of the start node to 0
• We initialize all other distances with "infinity".
• When we enqueue a node, we set its distance to the distance of its predecessor + 1.

for row from 0 to num_rows-1 {
  for column from 0 to num_columns-1 {
    color[row][column] = white;
    distance[row][column] = MAXINT;
  }
}
q = new queue();
q.enqueue(start_row,start_column);
color[start_row][start_column] = gray;
distance[start_row][start_column] = 0;
while (q.head != q.tail) {
  v = q.dequeue();
  color[v.row][v.column] = black;
  for each (r,c) adjacent to (row,column) {
    if (maze[r][c]!='#' && color[r][c]==white) {
      q.enqueue(r,c);
      color[r][c] = gray;
      distance[r][c] = distance[row][column] + 1;
    }
  }
}
switch (color[exit_row][exit_column]) {
  case white: 
    print("Exit is unreachable.");
    break;
  case black: 
    print("Exit is reachable in "+distance[exit_row][exit_column+" steps");
    break;
}

Computing the Shortest Path

vertex pred[num_rows][num_columns];

for row from 0 to num_rows-1 {
  for column from 0 to num_columns-1 {
    color[row][column] = white;
    distance[row][column] = MAXINT;
  }
}
q = new queue();
q.enqueue(start_row,start_column);
color[start_row][start_column] = gray;
distance[start_row][start_column] = 0;
pred[start_row][start_column] = null;
while (q.head != q.tail) {
  v = q.dequeue();
  color[v.row][v.column] = black;
  for each (r,c) adjacent to (row,column) {
    if (maze[r][c]!='#' && color[r][c]==white) {
      q.enqueue(r,c);
      color[r][c] = gray;
      distance[r][c] = distance[row][column] + 1;
      pred[r][c] = vertex(row,column);
    }
  }
}
switch (color[exit_row][exit_column]) {
  case white: 
    print("Exit is unreachable.");
    break;
  case black: 
    print("Exit is reachable in "+distance[exit_row][exit_column]+" steps: ");
    print_path_to(exit_row,exit_column);
    break;
}

print_path_to (r,c) {
  if (pred[r][c]!=null) {
    print_path_to(pred[r][c].row,pred[r][c].column);
  } 
  print("("+r+","+c+")");
}

What if edges have different lengths?

• In our problem, all edges have length 1.
• If edges have different lengths, use Dijkstra's algorithm.
• Breadth-first search uses a queue. Dijkstra's algorithm uses a priority queue with nodes ordered by distance. This is the only difference.

for row from 0 to num_rows-1 {
  for column from 0 to num_columns-1 {
    color[row][column] = white;
    distance[row][column] = MAXINT;
  }
}
q = new PriorityQueue();
q.enqueue(start_row,start_column);
color[start_row][start_column] = gray;
distance[start_row][start_column] = 0;
pred[start_row][start_column] = null;
while (q.head != q.tail) {
  v = q.dequeue();
  color[v.row][v.column] = black;
  for each (r,c) adjacent to (row,column) {
    if (maze[r][c]!='#' && color[r][c]!=black) {
      d = distance[row][column] + edge_length[row][column][r][c];
      if (color[r][c]==white) {
        q.enqueue(r,c);
        color[r][c] = gray;
        distance[r][c] = d;
        pred[r][c] = vertex(row,column);
      }
      if (color[r][c]==gray && d < distance[r][c]) { 
        distance[r][c] = d;
        push up vertex (r,c) in priority queue;
        pred[r][c] = vertex(row,column);
      }
    }
  }
}

What if the maze is 3-dimensional?

• No reason to worry. The algorithm stays the same.
• The vertices will have three components (e.g. (row,column,level)) instead of two.
• The arrays maze, color, distance and pred will all be 3-dimensional.

Why don't we use depth-first search?

• Depth-First search could be used to answer our first question: "Is the exit reachable from the start?"
• However, depth-first search is not suitable for the other two problems. Only breadth-first search finds the shortest solution.

Hoppers

###################
#.....#############
#..##.#############
#..##.#############
#..##.#############
#S.##............E#
###################

• Hoppers can fly over any square, but they can only land on empty squares.
• At any point in time, a hopper has a velocity (v_x,v_y).
• In each move, a hopper can change speed from (v_x,v_y) to (v_x +/- 1, v_y +/- 1).
• Exercise: In a maze of size rows*cols, how fast can a hopper get at most?

It's just another graph problem!

• A hopper's state can be described by a 4-tuple (x,y,vx,vy).
• We set up a graph with one node for each possible state.
• The start node is (start_x, start_y, 0, 0).
• The exit nodes are all states of the form (exit_x, exit_y, ..., ...).
• Two nodes u and v are connected, if the state v can be reached from u in one step.

• class vertex {
    int x;
    int y;
    int vx;
    int vy;
  }
  
  int color[num_rows][num_cols][num_speeds][num_speeds];
  int distance[num_rows][num_cols][num_speeds][num_speeds];
  vertex pred[num_rows][num_cols][num_speeds][num_speeds];
  

Rubik's Cube

• Given an initial configuration of Rubik's Cube, how many moves does it take to solve it?
• The cube configurations are the vertices of the graph.
• There's an edge between two configurations A and B, if there's a move that turns A and B.
• Since the number of nodes in this graph is huge, we cannot use arrays for color, distance, or pred. We have to use hashtables.
• To be honest, if the initial configuration is too far away from the solution, the queue will get too large, and your machine will run out of memory in this problem.

Last modified 2001-02-12