CS 242 Fall 2011 : Assignment 1.1

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

Assignment 1.1 – Writing a maze solving library

Note, always remember to check this assignment description for Update markers over the course of the next few days for changes or clarifications to this assignment specification. If any major changes are made to this spec, we will announce them both on the front page of the course website as well as on the course piazza space.

Objective: Write unit tests to guide the development of your maze solving library, and prove that it works. You will write the tests before you implement the library functions.

Both the unit tests and implementation for your library are due this week!

Goals:

  • Learn about Test Driven Development
  • Learn the value of completely planning out a design before diving into its implementation
  • Learn how to write unit tests
  • Learn how to write a library

Required Reading: Code Complete Chapter 22: Developer Testing

Even though the code for assignments is due on the Thursday the week following the release of the assignment, the readings are due for the lecture on the Monday of that week.
Questions that appear in lecture quizzes may come from the assigned reading, so it is in your best interest to complete it.

Language: Java with jUnit

For this assignment, you MUST either use the Eclipse IDE or IntelliJ IDEA (most likely community edition unless you want to buy a student license). Charlie, as well as a few other staff members, think IntelliJ totally ROCKS!

Both Eclipse and IntelliJ IDEA run on Windows, Mac, and Linux. Download links:

This week we will begin looking into unit testing and test-driven development. Eventually, we’ll explore the Model-View-Controller (MVC) design methodology to help us create a GUI. We’ll be designing and creating a maze-solving library, using the above techniques. We’ll also learn a little bit of AI along the way.

Bear in mind that you should be able to run your code during class, so be sure to bring in whatever you need to demonstrate your code.

The assignment will span three weeks; in this first week, we will cover unit testing and test-driven development. You will be expected to write a maze-solving library. For this first week, you will only be concerned with writing unit tests and implementing basic functionality for your library. Eventually, the library will need to implement the A* algorithm, and any supporting methods. Your library should be able to read in a maze, solve it (if there is a solution) and return the winning path. Also, your library should be “pluggable” to support new algorithms for solving mazes. Be sure to read the entire assignment before beginning. Refer to the questions below in order to learn all of the things you should keep in mind when working on this assignment.

The assignment is due on Thursday September 8th at 10:00 AM CST in your SVN repository. Please place all files needed for compilation and demo’ing of your assignment (but not executable or compiled files) into a folder in your repository called Assignment1.1, that is, you should be able to bring up https://subversion.ews.illinois.edu/svn/fa11-cs242/NETID/Assignment1.1/ in a web browser (replacing NETID with your actual netid) and see all of your code.

You are required to use Eclipse or IDEA to complete this assignment, and we highly recommend that you use the Subversive Subversion plugin for Eclipse (SVN support comes with IDEA by default) to handle adding your code to Subversion and tracking changes. It is easier than the command line svn client, especially if you are new to Subversion. Instructions on how to set up and use the plugin can be found at Using Subversion From Eclipse.

Course collaboration policy

Please read over the course policies in the Syllabus. In particular, please note:

  • You must work individually on assignments
  • You must cite all code you borrowed
  • Your code will be run through automated analysis tools to detect unauthorized collaboration

Also, we realize that this assignment has been given in the past. In particular, you must write your solution from scratch (even if you wrote one last semester and dropped the course). We will be comparing this semesters submissions to submissions from previous semesters. The college considers it to be academically dishonest even to reuse your own work when the course policy forbids such. Please direct any questions you have regarding this policy to the course staff via a private message on our piazza space.

Before you proceed!

Read these two tutorials on the A* search algorithm:

They will make understanding the rest of this assignment so much easier!

Mazes

For this and the next couple assignments, you will write a library for solving mazes. You will be expected to write a library that can solve a maze and return the winning path through the maze. Your first step will be to write unit tests to build a “living documentation” of the desired functionality of that code. Your code must fully compile, without errors, to receive any credit at all.

Defining A Maze

The required mazes are defined by following grayscale BMP images. The black pixels represent “road level” (passable) locations, and the white pixels represent the snow covered tops of (impassable) walls

Your solution should use a variable to enable you to set the grey level threshold of what is considered an open space and what is considered a wall.

Image IO in Java

The basics of image IO in Java are simple if you know what classes to look for. Try the following code sample to open a BMP file

//Create file for the source
File input = new File("c:/temp/image.bmp");

//Read the file to a BufferedImage
// Surround this with try/catch or have your method
// throw an exception
BufferedImage image = ImageIO.read(input);

// Get width/height
int height = image.getHeight();
int width = image.getWidth();

Color color = new Color(image.getRGB(x,y));


Note that you will have to import some classes (Eclipse will tell you this, but so will I just for completeness):

import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import javax.imageio.ImageIO;
import java.awt.Color;

Resources

Sun’s java website is an invaluable resource when working with Java. They post all the documentation for Java classes online. In general you can Goolge “X class” where X is the name of a Java class and the first result will be the documentation for that class. This includes methods, constructors and constants. The following documentation may be useful:

A* algorithm

A* is a graph searching algorithm, where the nodes in the graph represent the positions in the grid. It searches the graph for an optimized path to a goal node marking the end position of the maze. The choice of which intermediate nodes to move to, or expand, next is determined by some overall cost function, Cost(currentPosition). This cost function is defined in terms of two other functions:

cost(currentPosition) = accumulated(currentPosition) + estimated(currentPosition)

where accumulated(currentPosition) and estimated(currentPosition) are as follows:

accumulated(currentPosition) - the total cost so far from the start of the maze to the node currentPosition.
estimated(currentPosition) - an estimate of the distance from node currentPosition to the goal node.

In our case, accumulated(currentPosition) would be a sum of the steps needed to get from starting point to the current position.

The estimated(currentPosition) would be an estimated cost to get from the current position to the goal. For this first assignment, you will use the manhattan distance for this heuristic cost function to estimate the distance from the current position to the end position. For example, if the current position is (2, 3) and the end position is (10, 7) then the cost of traveling the manhattan distance is (10 -2) + (7 -3) = 12. Note that traveling the “manhattan route” representing the estimated path may not actually be a valid path in your maze; you will use this distance only as a rough estimate to the goal in order to find the optimal solution. For the cost function, use the diagonal shortcut.

Clarification

The accumulated cost should include a constant factor of 100 for moves to the north, south, east, or west, and 141 for moves diagonally. This makes your cost function something like:

cost(currentPosition) = accumulated(currentPosition) + (100 or 141) + estimated(currentPosition)

A* Example

Here is a good demonstration of A* pathfinding. Try setting the “steps per frame” to 1.

Example Solved Paths
Below are some output images with solved paths on them so you can have an idea of what your program might produce, your paths may not exactly match ours (the exact output is up to you)

Implementation Notes:

The following are choices you should consider in your implementation. Be sure to justify your design decisions.

  • When searching for a path through the maze, A* can use breadth-first search approach or depth-first search approach. 1