CS 242 Fall 2009 : Assignment 2.1

This page last changed on Sep 22, 2009 by cemeyer2.

Assignment 2.1 – Designing and testing a maze solving library

Note, always remember to check this assignment description for Update markers over the course of the next week or so for changes to the assignment specification.

Objective: Write a spec for a library to solve mazes and then write unit tests for how that library will function

Goals:

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

Language: Java with jUnit or C# with csUnit

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.

Since the intention is to eventually design a GUI, you should consider using either Java or C# to complete this assignment. Bear in mind that you should be able to run your code during class, so please bring in whatever you need to demonstrate your code (especially important if you decide to use an IDE such as Eclipse or Visual Studio).

The assignment will span three weeks, and 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, we will only be concerned with stubbing out our functions for our library and writing unit tests. The library will eventually need to implement a wall-following (or right-hand rule) 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 able to be pluggable to support new algorithms for solving mazes. See the questions to consider portion of the assignment near the bottom to see all the things you should keep in mind when working on this assignment.

The assignment is due on Wednesday September 23 at 8am in SVN. Please place all files files needed for compilation and demo’ing of your assignment (but no executables) into a folder in your repository called Assignment2.1, that is, you should be able to bring up https://csil-projects.cs.uiuc.edu/svn/fa09/cs242/NETID/Assignment2.1/ in a web browser (replacing NETID with your actual netid) and see all of your code.

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. You will then write unit tests to build a “living documentation” of the desired functionality of that code. As usual, your code will be required to compile without errors.

Defining A Maze

The mazes will be defined in a BMP image. White (255) will denote walls and black (0) will denote eligible paths. The start and end points of a maze will correspond to points along the edges of the maze where the color is black. You may assume that there will only ever be two such areas. Note that these areas may be several pixels wide, and you will be expected to enter via one path and exit via a different path. Below are some examples:

Maze1.bmp

Maze2.bmp

Maze3.bmp

Maze4.bmp

Not all mazes are solvable. Of the ones that are solvable, you may not enter and exit via the same path. For example, in the first maze above, you must either enter via the topmost path and exit via the bottomost path, or vice versa.

Solving the Maze

For this first week, you will be expected to have a design that can implement a wall-following algorithm. You can imagine that this algorithm works as if you were to traverse the maze yourself, and keep your right hand on a wall at all times. The result is that you will be able to find your way out of simply connected mazes. We will only expect you to be able to solve mazes that are solvable via this algorithm.

A slightly more detailed description is provided on Wikipedia: http://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower

But when you lay out your design, you should think carefully about modularity. What if we asked you to change the algorithm used to solve the maze? How would your design be able to adapt to change? See the questions to consider section for this and other things you should keep in mind when coming up with and writing your design.

Unit Testing

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 have a comment header block the explains exactly what the test does, including objects it works on, specific methods it tests, and any preconditions and postconditions that must be met and are set if the test passes. An example of a valid jUnit test would look like (for an imaginary Phone object):

public class PhoneTests {
        //note these are jUnit 4 style tests, the naming convention is different for jUnit 3 style tests

        /** 
	* The constructor is supplied with valid values so no exceptions
	* should be thrown. We test the constructor of the Phone object to see if the values
        * passed in actually are set properly and can be retrieved. If there is an error, such
        * as when the data passed into the constructor does not match what the getter methods of
        * the Phone object return, the test will fail, otherwise it will pass.
	*/
	@Test
	public void ValidConstructor1() throws Exception {
                String number = "1-555-555-5555"
                String name = "Charlie Meyer"
		Phone phone = new Phone(name,number);
		assertEquals(number, phone.getNumber());
                assertEquals(name, phone.getName());
		
	}

	/**
	* This test also tests the constructor of the Phone object, but
        * checks the case where it was supplied a phone number with too many dashes. The
        * expected behavior of the phone object when supplied with a number that has too
        * many dashes is to throw an InvalidPhoneNumberException. If this type of exception
        * is thrown when the invalid number is passed into the constructor, then the test
        * passes, otherwise the test will fail.
	*/
        @Test(expected=InvalidPhoneNumberException.class)
	public void TooManyDashes() throws Exception {
                String number = "9-9-999-999-9999";
                String name = "Charlie Meyer";
		Phone phone = new Phone(name,number);
	}

        //more tests below of course, you can never have too many!
}

Every function should have at least one test, but to get full points you should ensure that you cover all corner cases and other possibilities that your library might eventually encounter. For the purposes of this assignment, you do not need to write tests for VERY trivial, small functions (5 lines or less). As an example, below are some functions you should implement:

  • Read a grid
  • Clean the grid
  • Find start position
  • Find start direction
  • Test forward cell
  • Test right cell
  • Test end of maze
  • Turn left
  • Turn right
  • Move forward
  • Record cell entering data
    • Direction
  • Report(s):
    • Cells visited
    • Count of visits to cell
    • Directions from which cell was entered

Of course, these method-tasks are a very rough guide. You should further split up these tasks into sub-tasks depending on your specific implementation. These sub-tasks will be performed by helper functions which will be easier to test. Modularity is key to unit-testing. The less that each individual function does, the easier it will be to test each one fully, and the more correct your code will be as a result. 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: JUnit for Eclipse, CSUnit for C#, as well as others. 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.

Introduction to Eclipse and JUnit

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:

package contactInfo.tests;

import org.junit.runner.RunWith;
import org.junit.runners.Suite;

/**
 * Runs all tests for classes in the <code>contactInfo</code> package 
 * @author Jerome Bell
 *
 */
@RunWith(Suite.class)
@Suite.SuiteClasses({AddressTests.class, PhoneTests.class})
public class ContactInfoTests {
}

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:

package allTests;

import junit.framework.TestSuite;
import org.junit.runner.RunWith;
import org.junit.runners.Suite;
import contactInfo.tests.ContactInfoTests;
import persistence.tests.DatabaseInterfaceTests;

@RunWith(Suite.class)
@Suite.SuiteClasses({ContactInfoTests.class, DatabaseInterfaceTests.class})
public class RunAllTests extends TestSuite{
}

Resources

Getting Eclipse

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.

Building JUnit test cases

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.

Running JUnit tests

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. For this assignment, all tests should fail.

Using CSUnit

Visual Studio is free to all engineers to download from the Cites Software Webstore under the departments tab. We are not very familiar with the specifics of setting up and running csUnit like we are with jUnit, but if you plan on using C#, csUnit is a good choice to use. See http://www.csunit.org/tutorials/ for more information about getting up and running with csUnit.

Questions to Consider

  • If we asked you to drop in a new algorithm instead of the wall following algorithm, how much would your code have to change? Can you make algorithms be “plug n play” (hint: think about inheritance)?
  • If the input format of the maze changed from a simple bitmap to something more complex or completely different, how would your design adapt?
  • How easy will it be to have your library be the basis for a GUI in the future? What kind of functionality will a GUI require and how do you want to expose data to it? Your design should make it trivial to explain how a GUI would interact with it.
  • Remember to keep the Model-View-Controller design pattern in mind when creating your library design. We won’t be worrying about the view this week (that will be the GUI), but you should think about which parts of your design will be the model and which parts will be the controller. How will you keep them distinct and how will they interact?
  • Since we are only asking you to write function stubs and not implementation details, how will your function stubs convey the data structures that you plan to use? Are you going to create your own objects to hold data? Are you going to rely on structures built into the language’s library? Your design should make it clear how data will be input, output, and accessed.
  • Java and C# are great examples of object oriented languages. How are you going to leverage this feature to increase your code’s modularity? Will you use inheritance or polymorphism?
  • Do you have unit tests for all your functions? Do they cover all the base cases? What about boundary cases? What about error cases?

Still confused or need help?

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.

Requirements

Below are the exact requirements for completing this assignment. You will be graded primarily on the thoroughness of your unit tests, and on your design, documentation, and usability of your library. You must be able to run all your unit tests and inform the user if they have passed or failed. Note, we expect all unit tests to fail the first week since your library will have no implementation, only function definitions. You should be prepared to defend your design decisions and let your section know exactly how your implementation will work once it is defined.

  • 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
    • Your code contains comments for each unit test specifying exactly what the test does, including objects it works on, specific methods it tests, and any preconditions and postconditions that must be met and are set if the test passes: 6
  • Code Design
    • Your code is modular: 4
    • Functions only do one thing: 4
  • Functionality
    • Each library function has a unit test (minimum of 15 tests): 15
    • Unit tests are thorough well thought out: 6
  • Participation
    • You submitted your code on time and to the correct location: 4
    • You came prepared to ask questions based off your assigned code reading: 4
    • You were able to give solid reasoning for all of your design decisions and explain to your section how your implementation will function: 4
Total 53 Points

Maze1.bmp (image/bmp)

Maze2.bmp (image/bmp)

Maze4.bmp (image/bmp)

Maze3.bmp (image/bmp)

AstarExample.gif (image/gif)
Document generated by Confluence on Feb 22, 2012 18:18

  1. No comments yet.

  1. No trackbacks yet.