CS 242 Fall 2009 : Assignment 2.2

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

Assignment 2.2 – Implementing Your Maze Solving Library

Part I

For the first part of this assignment, you are expected to implement all of the design suggestions that your moderator and fellow students suggested in discussion regarding your library. Make these changes before moving on to part II of this assignment.

Part II

For the second part of this assignment, you are going to actually fill in the implementation of your library. By the time you are done, all of your unit tests that you wrote last week should pass.

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. Use the mazes that we provided on last week’s assignment description to test with. 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.

For this first week, you will be expected to 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

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();

// Get a grid of data
Raster raster = image.getData();
int[][] data = new int[height][width];

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.image.Raster;


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:


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 (they should all pass this week). You should have some way to demonstrate that the code you wrote works (perhaps a small sample program that uses the library to solve a maze). You will be secondarily graded on your implementation.

This assignment is due in subversion in a folder called Assignment2.2 by 0800 on Wednesday, 30 September 2009

  • Usabaility
    • Your program exit cleanly in all cases: 2
    • It is clear how your program should be used: 2
    • There are no unwanted side effects (i.e. clobbered files): 2
  • Documentation
    • Your code contains ample comments: 4
    • Your program provides useful feedback to the user: 4
  • Code Design
    • Your code is modular: 4
    • Functions only do one thing: 4
    • Each function is no longer than 25 lines of code: 2
  • Functionality
    • Library can solve a maze with BMP input: 4
    • Library can output the solution in a readable manner: 4
    • You wrote a test program in addition to your unit tests to demonstrate your library in action: 4
  • Participation:
    • you came to class prepared to ask questions based off of your assigned code reading: 4
    • you asked questions and actively participated in discussion: 4
    • you turned your assignment in on time and to the proper location in svn: 4
Total 48 points
Document generated by Confluence on Feb 22, 2012 18:18

  1. No comments yet.

  1. No trackbacks yet.