CS 242 Fall 2011 : Assignment 1.2

This page last changed on Sep 07, 2011 by cemeyer2.

Assignment 1.2 – Extending Your Maze Solving Library

For this assignment you will:

  1. Clean up any problems in your code for Assignment 1.1, and fix any algorithmic shortcomings.
  2. Generalize the calculation of the estimated distance, enabling addition heuristics to your A* path finding.
  3. Extend your library to handle greyscale images representing a more complex traversal scenario.

Assigned Reading: Code Complete chapter 24: Refactoring

Submission

This assignment is due Thursday, September 15th, 2011 at 10AM. Please be sure to submit in SVN, and ask your moderator or TA before the deadline if you have any questions. Also, make sure to place your work in a folder called Assignment1.2.

Part I: Refactoring

Read here and here for further discussion about this topic.

You spent Assignment 1.1 making it work, now you will:

  • Refactor your code to make it right.
  • Make it faster by using proper data structures.

You should refactor your code to eliminate any code smells (e.g. use communicative naming, decompose larger methods into smaller separate methods, etc), add missing tests, or other problems discussed in section. If you haven’t already, you should be using a priority queue and a hashtable for the open and closed sets, respectively. Look here for discussion about these (as well as more advanced data structures) in improving the performance of A*.

Part II: Pluggable Heuristics

You must extend your program to enable the use of different heuristics for calculating the estimated distance for A*.
In addition to the manhattan distance, you must implements at least two of the four following heuristics:

  1. Diagonal distance
  2. Euclidean distance
  3. Euclidean squared distance
  4. Manhattan distance using a tie-breaker
Caution!
As Amit mentions on his page, the squared distance is problematic. However, it can be made workable by not just using the square of the estimated distance, but by using the square of each accumulated cost as well.
Challenge 1:

Implement all four of the heuristics!

Part III: Contour Maps

Elevation

You will now need to also be able to traverse maps representing elevation. Instead of simple black and white maps, the following greyscale images representing contour maps with lighter gray representing higher elevations, and darker representing lower elevations.

The cost to move from one position to another of at the same elevation will be the same as in Assignment 1.1. However, the cost to move to a position at a different elevation will be proportional to the change in elevation. The accumulated cost of each move, and the estimated cost will need to be weighted by an ascending or descending scaling factor, depending upon whether a move goes uphill or downhill. The scaling factors are represented as a percentage of the normal “flatland” unit cost. Your program must accept these scaling factors as input values. The new accumulated and estimated costs are each modified as follows:

cost = xyDistanceCost + (unitElevationChange * elevationScalingFactor)

For example if the ascending factor was 150% and the descending factor was 60%, the cost to traverse one position diagonally going up a height of two units would be:

    141 + (2 * 150)

For an estimated manhattan cost from position (10,5) to (20,3) down an elevation of 7 units would be:

    (100 * ((20-10) + (5-3))) + (7 * 60)

Mountains and Water

Additionally, your path finder algorithm must enable the option of being able to treat pure white and/or pure black pixels as impassable. (Pure white and black representing mountain peaks and water, respectively.) Your program must accept these conditions as input values.

Sample Solutions
Here are several solved paths on the colorado.bmp input file from the upper left to lower right corner using varying heuristics:

If the images do not show up properly, try using another browser (I know they don’t appear in most webkit based browsers such as chrome, chromium, and possibly safari).

Example animated solution

The highlighted yellow are nodes on the closed list, green for the open list, and red for the current found path. You may need to save this image to your computer to view it animate again due to browser caching.

Challenge 2:

Have your program output an animation like this one!

Requirements

We will bias clarity over cleverness in evaluating your code. You should adopt a “teaching” mindset, always asking yourself, “How would I change what I have written to make it as easy as possible for someone else to understand my code without my direct assistance?”

Below are the requirements for the assignment. You should be prepared to defend your design decisions.

We will use the standard Grading rubric for this assignment.

Category Weight Notes
Basic Preparation 1 Ready to go at the start of section
Code Submission 4 Submitted on time and to the correct location in the repository
Requirements Satisfaction 4 Refactoring
Requirements Satisfaction 6 2 new heuristics
Requirements Satisfaction 6 Grayscale maps
Presentation 4  
Participation 6  
Effort 2  
Testing 4 Unit tests written for all new code
Overall Design 4  
Naming 2  
Decomposition 4  
Documentation 4 Comments for each class and each function listing a brief summary, its parameters, and its return value
Cleverness 2 The hardest points on the rubric

colorado.solved.manhattan.bmp (image/bmp)

colorado.solved.euclidean.bmp (image/bmp)

animation.gif (image/gif)

colorado.bmp (image/bmp)

colorado.solved.diagonal.bmp (image/bmp)

RedWoodPoint.bmp (image/bmp)

PyramidPeak.bmp (image/bmp)

colorado.solved.manhattancross.bmp (image/bmp)

mountains.bmp (image/bmp)

MountainView.bmp (image/bmp)

SouthTahoe.bmp (image/bmp)

Tahoe.bmp (image/bmp)
Document generated by Confluence on Feb 22, 2012 18:09

  1. No comments yet.

  1. No trackbacks yet.