CS 242 Spring 2010 : Assignment 1.2

This page last changed on Feb 08, 2010 by cemeyer2.

Assignment 1.2 – Extending Your Maze Solving Library

Warning!
Though we allowed you to work with a partner on Assignment 1.1, you must end your partnership and work alone for Assignments 1.2 and 1.3.

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.

Submission

This assignment is due Wednesday, February 10th, 2010 at 8AM. 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. This is critical so that we can export everyone’s code for code reviews.

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.
Warning!
If you worked with a partner to solve Assignment 1.1, the heuristics that each of you chose to implement must different heuristics from one another other. For example: if your former partner implements the two Euclidean heuristics, you must implement the diagonal and tie-breaking heuristic.

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 would uphill or downhill from the elevation of the current position. They represent as a percent 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:

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.

Note: This rubric is subject to minor changes in the coming days

Documentation  
Your code contains comments for each function definition specifying what the function does, what its inputs are, what its outputs are, and how it handles error cases (are exceptions thrown, etc) 6
All of your unit tests are well named and organized together well 4
Each of your unit test is self explanatory and/or includes necessary comments to be clear 6
Code Design  
Modular code (high cohesion, low coupling) 4
Focused and clear functions (each function only does one thing) 4
Practicing good naming (using descriptive variable and function names) 4
All functions were <= 25 lines of code 2
Functionality  
Comments and suggestions from last week were applied thoughtfully and completely 6
Two new heuristics were added to your implementation 6
Your implementation can successfully traverse elevation maps with varying scaling factors 8
Your implementation can take as parameters a heuristic and colors that should be impassable 2
Participation  
You submitted your code on time and to the correct location in the repository 4
You were able to give solid reasoning for all of your design decisions and explain to your section how your implementation functions 4
Total 60 Points

RedWoodPoint.bmp (image/bmp)

mountains.bmp (image/bmp)

MountainView.bmp (image/bmp)

PyramidPeak.bmp (image/bmp)

colorado.bmp (image/bmp)

SouthTahoe.bmp (image/bmp)

Tahoe.bmp (image/bmp)

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

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

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

colorado.solved.diagonal.bmp (image/bmp)
Document generated by Confluence on Feb 22, 2012 18:15

  1. No comments yet.

  1. No trackbacks yet.