CSE 382 Algorithms and Data Structures

Barbara Nostrand, Ph.D.

Electrical Engineering and Computer Science


Laboratory 9 - Maze Runner

Introduction

In ancient Greek legend,  Daedalus built a complicated maze called the Labyrinth and Minos put the Minotaur in it.  To make sure no one would ever know the secret of the Labyrinth,  Minos imprisoned Daedalus and his son,  Icarus,  in a tower.  Daedalus and Icarus flew away on wings Daedalus invented,  but Icarus' wings melted because he flew too close to the sun.  Icarus fell into the sea and drowned. 

In recent years,  there has been a resurgence of interest in labyrinths.  Daedalus, the quarterly journal of the American Academy of Arts and Sciences,  uses a labyrinth for its logo.  Many colleges construct a temporary labyrinth for its students each year,  and a labyrinth or more correctly a maze appears in a Harry Potter novel.  The labyrinth revival has extended to architecture,  notably at Willen Park,  Milton Keynes; Grace Cathedral,  San Francisco; Tapton Park,  Chesterfield; and the Labyrinthe de Harbor 16 in Montreal.  Computer games often depict mazes and labyrinths.  The difference between a labyrinth and a maze is that a labyrinth typically has one clear path from the exterior to the center,  while a maze is true puzzle and the begining and end points may appear anywhere in the map. 

A perfect maze consists of a collection of connected rooms with a unique path from every room to every other room.  perfect' means that not only is the maze solvable, and well-connected such that any point within it is reachable from any other point, the maze also contains no loops. In other words, the solvable path between any two points is unique. These mazes contain no loops and a graph which represents cells in the maze as points and connections between cells as vertices is a Tree.  There are several simple algorithms to construct these mazes,  and they are fairly simple for a computer to solve them.  We will construct mazes which are a bit more complicated.  Our mazes may have more than one solution,  and the goal is to find the shortest path through the maze. 

Perfect Maze
Imperfect Maze

Getting Started

Create a new directory for the files of this exercise.  You will be constructing several new classes for this exercies.  Two of these new classes correspond to standard Java interfaces.  The Set class is used to represent mathematical sets and is part of the Collection class hierarchy.  The Set interface is described begining on page 464 of our text.  You will use the set concept to create mazes.  Priority queues are described begining on page 439 of the text.  A priority queue is different from in ordinary queue in that higher priority items will emerge from the priority queue before low priority items do.  Typically,  priority is represented by a positive integer where lower values represent higher priorities. 

Abstract Set Class

You do not need to implement or even use the AbstractSet class.  The point is that you need to use the set concept.  Initially, each of the cells belongs to its own unique set.  You may be able to simply declare this as an integer called set in your Cell class definition and have your constructor initialize it to the hashCode value for the cell.  Recall that all objects have an integer hashCode value which is retrieved by the hashCode() method.  The important thing is that each of these cells has to start out with a unique hashCode.  While this allows you to avoid the AbstractSet class entirely,  the AbstractSet class may significantly simplify your maze constructor. 

Constructor Summary
protected AbstractSet()
          Sole constructor.
 
Method Summary
 boolean add(Object o)
          Adds the specified element to this set if it is not already present (optional operation).
 boolean addAll(Collection c)
          Adds all of the elements in the specified collection to this set if they're not already present (optional operation).
 void clear()
          Removes all of the elements from this set (optional operation).
 boolean contains(Object o)
          Returns true if this set contains the specified element.
 boolean containsAll(Collection c)
          Returns true if this set contains all of the elements of the specified collection.
 boolean equals(Object o)
          Compares the specified object with this set for equality.
 int hashCode()
          Returns the hash code value for this set.
 boolean isEmpty()
          Returns true if this set contains no elements.
 Iterator iterator()
          Returns an iterator over the elements in this set.
 boolean remove(Object o)
          Removes the specified element from this set if it is present (optional operation).
 boolean removeAll(Collection c)
          Removes from this set all of its elements that are contained in the specified collection (optional operation).
 boolean retainAll(Collection c)
          Retains only the elements in this set that are contained in the specified collection (optional operation).
 int size()
          Returns the number of elements in this set (its cardinality).
 Object[] toArray()
          Returns an array containing all of the elements in this set.
 Object[] toArray(Object[] a)
          Returns an array containing all of the elements in this set; the runtime type of the returned array is that of the specified array.

Representing a Maze

You can represent a maze in a way very similar to you represented the playing field for the Life game that you constructed several weeks ago. However,  this time each cell needs to keep track of more information.  In particular,  each cell needs to keep track of its walls and which other cells it is connected to,  along with display information.  The start cell will be coloured green while the destination cell will be coloured red.  You should pick contrasting colours for the walls,  empty cells,  and cells included in the path between the start cell and the finish cell. 

Cell Class

The Cell Class is the workhorse of this program.  This class extends Comparable so that its objects can be entered into a PriorityQueue.  Comparable objects are very useful.  They can be entered into a variety of structures and processed by methods which are sensitive to order. 

Field Summary
Color color
          Identifies the Set to which the Cell belongs.  Initially,  each Cell has a unique Set which contains only one Cell
AbstractSet component
          Initially,  each cell has a unique Set which contains only the one node. 
Cell east
          Initially a null.  After the wall has been removed,  contains a link to the Cell immediately to the right of the current Cell
int metric
          Contains the Manhattan distance from this Cell to the destination CellManhattan distance is computed as the sum of the distances between two nodes in the vertical and horizontal directions. 
Cell north
          Initially a null.  After the wall has been removed,  contains a link to the Cell immediately above the current Cell
Cell parent
          Initially a null.  This link is used to construct the path through the maze. 
int pathLength
          Contains the measured distance for the shortest path from the start Cell to this Cell
Cell south
          Initially a null.  After the wall has been removed,  contains a link to the Cell immediately below the current Cell
Cell west
          Initially a null.  After the wall has been removed,  contains a link to the Cell immediately to the left of the current Cell
 
Constructor Summary
protected Cell()
          Sole constructor.
 
Method Summary
 Color color()
          Retrieves the color parameter.  Used to mark cell status. 
 void color(Color color)
          Sets the color parameter.  Used to mark cell status. 
 int compareTo(Cell cell)
          Compares this cell with the specified cell for order.  The comparison is based on the value of pathLength+metric. 
 Cell east()
          Retrieves the cell to the right of this cell.  Returns null if there is a wall. 
 boolean east(Cell cell)
          Links this cell to the cell to its right.  Returns true if successful. 
 Cell north()
          Retrieves the cell above this cell.  Returns null if there is a wall. 
 boolean north(Cell cell)
          Links this cell to the one above it.  Returns true if successful. 
 Cell parent()
          Retrieves the cell linked to by the path field.  Returns null at the end of the path. 
 void parent(Cell cell)
          Links the parent field to cell.  Modifies both pathLength and parent
 Cell south()
          Retrieves the cell below this cell.  Returns null if there is a wall. 
 boolean south(Cell cell)
          Links this cell to the one below it.  Returns true if successful. 
 Cell west()
          Retrieves the cell to the left of this cell.  Returns null if there is a wall. 
 boolean west(Cell cell)
          Links this cell to the cell to its left.  Returns true if successful. 
 

Constructing a Maze

You will use a modified version of Kruskal's Algorithm to construct an imperfect maze.  This algorithm uses the AbstractSet class to detect when S and F are connected.  Then,  you will draw the maze in a GUI window.  Consider an M-by-N grid of cells,  initially with each cell surrounded on all sides by "walls".  For example, the picture for M=4 and N=5 would look like:


   0  1  2  3  4
  +--+--+--+--+--+
0 |S |  |  |  |  |
  +--+--+--+--+--+
1 |  |  |  |  |  |
  +--+--+--+--+--+
2 |  |  |  |  |  |
  +--+--+--+--+--+
3 |  |  |  |  | F|
  +--+--+--+--+--+
S and F mark the start and finish cells.  These will be coloured green and red respectively in the final GUI version.  Number the cells as follows:
	index = row * columns + column;
In the example above,  S is in cell 0 and F is in cell 19.  Initially,  each of the cells is in its own equivalence class.  We build the maze by randomly selecting an interior wall and removing it.  When we remove the wall,  we perform a union on the equivalence classes represented by the adjacent cells.  The disjoint set data structure keeps track of equivalence classes of cells that are reachable from each other through paths in the maze.  Note that we also need to keep track of which walls are left in the maze so that we will be able to draw it later;  thus,  the disjoint set data structure alone will not suffice to build the tree.  We keep randomly removing edges until S and F are in the same equivalence class AND at least (rows * columns - 1) walls have been removed. 
	  Accept the dimensions of the maze from the user.
	  Accept a factor in the range 0 to 100.
	  Create a rows x columns array of cells.   
	  Put every cell in its own set.
	  Iterate
	    Choose an interior wall at random by randomly selecting one cell and randomly seleting a neighbor
	    If the adjacent cells are not in the same set
	      Mark the corresponding wall of both cells as removed.
	      Perform set union on the adjacent cells
	  until S and F are in the same set
	  Continue iterating unconditionally removing selected walls
	  until a total of (rows * columns - 1) walls have been removed
	  Continue iterating unconditionally removing selected walls
	  until an additional factor percent of the remaining walls have been removed

Constructor Summary
Random()
          Creates a new random number generator.
 
Method Summary
 int nextInt()
          Returns the next pseudorandom, uniformly distributed int value from this random number generator's sequence.
 int nextInt(int n)
          Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), drawn from this random number generator's sequence.
 

Removing a Wall

You will randomly select walls to be removed.  Each wall is shared by two cells,  so you will have to "remove" it from both cells.  A wall is removed from a cell by replacing the null in one of the direction fields by the Cell lying in that direction.  A Node is randomly seleced by using a random number generator to select a random node:

	  index = random(rows * columns);
	  row = index / columns;
	  column = index % columns;
Then a direction is chosen:
	  nextNode(Node node) {
	  for(;;) {
	      switch(random(4)) {
	      	case 0: break;
	      	case 1: break;
	      	case 2:
	      	case 3:
	      	}    
	     } 
 

Solving the Maze

You will use the A* algorithm to find the shortest path through the maze.  The A* algorithm uses a PriorityQueue to organize its search for a path.  The algorithm returns null if a path is not found.

	  Create a Priority Queue of Cells which uses the value of path+metric for its priority.
	  Enter the start Cell into the PriorityQueue
	  Iterative Search Algorithm
		  Return null if the PriorityQueue is empty
	  	  Remove the first Cell from the PriorityQueue
	  	  Return the Cell if it is the destination
	  	  Path length through the current Cell to each neighbor is equal to pathLength+1
	  	  Examine each of the Cell's neighbors
	  	  	If the neighbor's parent is null,  
	  	  	or if the length calculated above is less than the current path value
	  	  	for the neighbor,  then 
	  	  		  point parent in the neighbor to the current cell,  
	  	  		  update the pathLength value in the neighbor to pathLength+1,  and
	  	  		  enter the neighbor into the PriorityQueuue. 
	  	  	  
	  	
 

Priority Queue Class

Field Summary
Comparable[] array
          An array which stores the nodes in the priority queue. 
int count
          The number of objects which are currently in the priority queue. 
 
Constructor Summary
PriorityQueue()
          Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering (using Comparable).
PriorityQueue(int capacity)
          Creates a PriorityQueue with specified initial capacity that orders its elements according to their natural ordering (using Comparable).
 
Method Summary
 boolean add(E o)
          Adds the specified element to this queue.
 void clear()
          Removes all elements from the priority queue.
 E element()
          Retrieves, but does not remove, the head of this queue.
 boolean<E> isEmpty()
          Returns an iterator over the elements in this queue.
 Iterator<E> iterator()
          Returns an iterator over the elements in this queue.
 boolean offer(E o)
          Inserts the specified element into this priority queue.
 E peek()
          Retrieves, but does not remove, the head of this queue, returning null if this queue is empty.
 E poll()
          Retrieves and removes the head of this queue, or null if this queue is empty.
 E remove()
          Retrieves and removes the head of this queue.
 boolean remove(Object o)
          Removes a single instance of the specified element from this queue, if it is present.
 int size()
          Returns the number of elements in this collection.
 String toString()
          Returns a String which represents the elements in this collection. 
 

Implementing a Priority Queue

Use an array based heap as shown in class to implement the PriorityQueue class.  Use a counter to track the number of items currently in the queue.  Although arrays in Java are indexed starting with zero,  array based heaps assume an array indexed starting with one.  Consequently,  you should substract one from the heap index to obtain the array index. 

To insert a new element into your PriorityQueue

  1. Handle error if count equals size
  2. Increment count
  3. Store the element into array
  4. Recursively execute the orderUP method to restore the heap order proprerty. 
  5. Return true. 
To remove an element from the front of your PriorityQueue
  1. Handle error if count equals zero. 
  2. Temporarily save the element. 
  3. Copy the last element in the array into the first location in the array. 
  4. Recursively execute the orderDown method to restore the heap order property. 
  5. Remove the element from the last position in the array by storing a null
  6. Decrement count
 

Displaying the Path

Display your solution to the maze by backtracking from the destination node to the start node by following the parent links.  Starting from the destination cell,  change the colour of each node along this path.  Terminate colouring when you encounter a null

 

Phrases you should now understand:

AbstractSet,  PriorityQueue. 

CollaborationYou will complete this project with your lab partner. 
ImplementationYou must implement your system as a Java application.  You may use Jgrasp.  Do not use netbeans or produce a Java applet. 
EnvironmentYour program must execute on the podium computer in our classroom.
Turn inYou must turn in both a report containing complete program sources and an executable electronic version of your program.

Last modified: 2008 FEB 11
bnostran@syr.edu