CSCI 151 - Lab 13
Heap Maze Search

Overview

In this lab, we will implement a Heap for performing an intelligent search of a maze.

Materials

Setup

  1. Download the skeleton for this project.
  2. Unpack the code into a new Eclipse Java project.

Description

It is possible to do more than just find a solution trail in a maze. We now wish to find the minimum length path from the explorer to the goal state. While the Stack interface would be optimal in space, it was not guaranteed to find the minimum length trail. The Queue interface performed better, but at the expense of remembering all possible trails at a given level.

With a Heap that implements a Priority Queue, we can balance both space and time in our search. In this lab, we will implement this Heap, organized to always have the minimum element available in constant time. If we assign priority in a certain way, we will be implementing A* Search, a classic pathfinding algorithm.

Step 1 - TrailEstimator

Our first step is to create the heuristic function for comparing trails. We are familiar with using a compareTo method in sorting algorithms, but a Trail cannot be properly compared to another trail without the context of a puzzle. Java lets us compare in another way for this circumstance. In the TrailEstimator class, you will find two methods. This class is a Comparator for the Trail objects, which will have the proper Puzzle object available.

The estimateFor method should return the length of the given Trail, plus an estimate for the remaining length of the trail. This estimate should be calculated using the manhattanDistanceTo method of the Position class.

The compare method will then be able to compare two Trail objects, using using the estimate for each Trail calculated in the above method. Return -1 if the first Trail estimate is less than the second, 0 if they are equal, and 1 if the first Trail estimate is greater than the second.

Step 2 - peek and add

With a Comparator object, we can proceed with implementing the Heap. This Heap will be implementing the Searcher interface. In particular, we will be implementing a Heap where the minimum node will be the root of the Heap. Our implementation will use an ArrayList to store all the elements of our Heap.

The first method to implement is peek. This should return the root element, which will always be stored in the first position of the ArrayList.

Second, you should implement the add method. New elements are added to the end of the ArrayList, and then filtered up repeatedly when the element is found to be less than its parent. Use the Comparator object to calculate if an element is greater or less than another element. Based on the structure of the Heap, you should be able to calculate the index of the parent for any node using a few mathematical operations.

Step 3 - remove

Elements can be removed from the heap through a similar filtering process. First, save a copy of the first element of the list. Next, move the element that is last up to the first position. This could cause a violation of the Heap property that all parents must be smaller than their children. If the element is less than only one of its children, swap these two elements. If the element is less than both of its children, swap the smaller of the two children with the element, so that we don't break the Heap property any further. Finally, when a swap was made, repeatedly check the subsequent descendents to guarantee that the Heap property is always preserved.

Step 4 - isHeap

Finally, you will write a method to check that all of the properties of a Heap are present. Namely, you must verify that each element is smaller than its children elements. Because of our use of an ArrayList to track the elements, we will always assume that the elements form a Heap that is as compact as possible.

Step 5 - Evaluation

Compare the new Heap Searcher to the earlier Stack and Queue implementations. Create 10 random mazes of size 50x50. For each maze, use the new Shotgun button to remove some of the walls. Now, for each maze and strategy (Stack, Queue, and Heap), record the number of visited nodes as a percentage of the total number of open spaces in the initial maze. Discuss the differences you see between the Stack, Queue, and Heap.

What to Hand In

Submit your TrailEstimator.java and MinHeap.java implementations on Moodle, along with your evaluation document.

Grading

© Mark Goadrich, Hendrix College