CS 242 Spring 2010 : Assignment 1.1
CS 242 Spring 2010 : Assignment 1.1
This page last changed on Feb 03, 2010 by m3rabb.
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.
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.
Read these two tutorials on the A* search algorithm:
They will make understanding the rest of this assignment so much easier!
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.
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.
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
Note that you will have to import some classes (Eclipse will tell you this, but so will I just for completeness):
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* 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:
where accumulated(currentPosition) and estimated(currentPosition) are as follows:
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.
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:
Here is a good demonstration of A* pathfinding. Try setting the “steps per frame” to 1.
The following are choices you should consider in your implementation. Be sure to justify your design decisions.
We don't expect any fancy, enhanced versions of A* or any other bold approaches. The most important neccessity for your program is to output some answer; specifically, your program should be able to stop and give some error message if it cannot find a solution. If there is a solution, the program should output the corresponding maze path in some readable format, and this should be the optimal solution. To make it easier to deal with, we have defined the idea of perfect mazes. Refer to the lecture notes on mazes for clarification on this. If you have implemented A* properly, you should be able to satisfy these three requirements.
Unit testing is a great way to ensure that, given an implementation, the code works correctly. This is enforced by creating small (unit) tests for each function. Each test should be able to call the function it is testing, and determine if the function worked according to specification.
This can be a funny concept at first, but it is really quite simple: If you know the input to a function, and you know how the function works, you should know exactly what the output of the function is. Since you know what the output should be before even calling the function, you can compare the output you get from making the function call to the expected output. If they match up, then the test has succeeded. Otherwise, it fails.
In general, one test is not sufficient to be confident in the correctness of a function. While it is better than nothing, a complete test suite would try all corner-cases, as well as the common case. For instance, if a function operates on positive integers, and it is called with a negative parameter, does it do the right thing? The success and failure of tests are completely defined by the person designing the application. Therefore, it is necessary to clearly understand what a function should do in order to test it.
Each test should named is such a fashion that it obvious what it does. Each test should be written in such a way that it is immediately apparent from the prose of its statements:
If it doesn't, the test most include comments that fully explain what is missing.
An example of a valid jUnit test would look like (for an imaginary Phone object):
Good testing requires you to test for the unexpected. Every function should have at least one test. However to get full credit, you should write tests which cover all corner cases and other possibilities that your library may eventually encounter. You do not need to write tests for extremely trivial, small functions (5 lines or less).
You should write tests to cover all of the following issues:
Finally, you should include tests that:
Remember, test-driven development meaning write your tests before you write their implementation!
When writing your functions always keep in mind writing them so that they are easy to test. The more focused each individual function is, the easier it will be to test, and the more correct your code will be. Modularity is key to unit-testing. It may even be a good idea to split your library into multiple classes depending on the data structure you use as an internal representation for a maze.
There are some resources which aid in the unit testing process, such as JUnit for Eclipse. You are free to use these if you would like. Eclipse and JUnit are available on the CSIL Linux computers, and an introduction to using JUnit with Eclipse is provided in this assignment description.
An example of jUnit 4 tests was shown above. Generally, developers put all unit tests for one type in one file, with multiple files of tests composing a test suite for the library or application. It will be much easier for you to keep things organized if you follow a similar pattern. Although Eclipse will let you run a single file containing jUnit tests directly, it takes a bit more effort to have Eclipse run all tests in all files at once (your test suite). For example, say I had tests for a Phone object in a file called PhoneTests and tests for an Address object in a file called AddressTests, I could have the Eclipse jUnit runner run them both by creating a file called something like ContactInfoTests and have it contain:
If I was to then instruct Eclipse to run ContactInfoTests as a jUnit test, it would run all the tests in both the PhoneTests class and the AddressTests class. You might not need to, but you can chain it up even further if you divide your tests into subcategories and have a master suite file like:
You are encouraged to use the Eclipse which is installed on the CSIL Linux Terminal Servers. If you would like, you may download and install Eclipse on your own machine. Once you have downloaded eclipse, there is a great plug-in called Subversive that integrates subversion into the IDE for you, so you do not have to worry about using the command line client or tortoisesvn. In addition, it is smart in that it only will commit the files that we require and nothing more, so you do not have to worry about accidentally committing binaries to the repository. Instructions on how to install Subversive can be found here.
There is a good tutorial at http://www.vogella.de/articles/JUnit/article.html. You may ignore section 5 on Easy Mock, as it is not a requirement for this assignment. Also note that the JUnit4.x.jar file is included with Eclipse 3.5, so you should not have to download the file from the JUnit website to add it to your classpath.
After writing some JUnit tests, you can run them by right-clicking the project in the Package Explorer, and select Run As > JUnit Test. This will bring up the JUnit view which shows information on which tests were run, and how many passed.
First, ask questions on the newsgroup. If you have a question, there is a pretty good chance someone else has the some one and an even better chance that someone else in the class or one of the TAs will be able to answer it for you. If you are still having a problem, email your moderator or one of the TAs to get advice. Remember, its best to ask questions early on so they have time to be answered. Don't wait until the last second to get started then realize that you are confused.
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.
|Document generated by Confluence on Feb 22, 2012 18:15|