CS 242 Spring 2010 : Assignment 1.1

This page last changed on Feb 03, 2010 by m3rabb.

Assignment 1.1 – Writing a maze solving library

Sample code and tests
To assist you in your efforts, here are two sample files SquareTest.java and Square.java. The square objects represent the nodes that the pathfinder traverses. The squares are held by a maze object. Each square is identified by a unique position object. When we solved this assignment, we did in fact write all of the test before the methods they test. After we wrote the tests, we wrote stub implementations of the tests that call them. The code would then compile without errors, but the tests would fail since they didn’t do anything yet. This is normal. Then one by one, we wrote the implementation for each of the methods until all of the test passed.

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 it both on the front page of the course website as well as on the newsgroup.

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.

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

Language: Java with jUnit

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 (especially important if you decide to use an IDE such as Eclipse).

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. 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 Wednesday February 3rd at 10pm 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://csil-projects.cs.uiuc.edu/svn/sp10/cs242/NETID/Assignment1.1/ in a web browser (replacing NETID with your actual netid) and see all of your code.

If you are planning on using Eclipse for this assignment, we highly recommend that you use the Subversive Subversion plugin for Eclipse 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.

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 credit.

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 the 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