On this page:
Problem 1: Rush Hour, Part 2
7.1 Design reflection:
7.2 Design cleanup:
7.3 Player motion:
7.4 Obstacles:
7.5 Irregularly shaped levels:
7.6 Submission notes:
Problem 2: Cellular Automata and Mutable World Programs
7.1 Individual cells
7.2 Different kinds of cells
7.2.1 Inert cells
7.2.2 Rule-based cells
7.3 Populations of cells
7.4 Animating your world
7.5 Optional Enhancements

Assignment 7: Mutable Worlds🔗

Goals: Further practice with ArrayLists; mutable worlds.


This assignment is long. Start early.

As always, be very careful with your naming conventions.

The submissions will be organized as follows:

Due Date: Tuesday, March 12th at 9:00pm

Problem 1: Rush Hour, Part 2🔗

In this assignment, you’ll add enough behavior to Rush Hour to make it a playable game. Plus, you’ll add a new extension to the game so far.

7.1 Design reflection:🔗

You and your new partner each have an implementation of part 1 of the project. You will merge the best parts of your two designs together, as the starting point for this part of the project. You are allowed to revise any part of your prior designs: you can change data definitions, implementations, etc. You may change from Funworld to Impworld (see problem 2 below). You may use mutation...

...carefully! You are still expected to design your code well, meaning it should still be testable, readable, and understandable. Gratuitous use of mutability, untested void methods, etc., will be considered bad design. You now have lots of tools to express yourselves: part of the challenge of this problem is to express your design clearly.


In a file Merging.txt, describe the similarities and differences between your two implementations. Explain which parts of whose implementations were kept (and why), and which parts were discarded (and why). Explain what primary changes you plan to make to your prior designs.


Update your Design.txt file to describe the current design that you’re now using.

7.2 Design cleanup:🔗

You should likely have noticed that cars and trucks are nearly identical in terms of their behavior. Revise your merged code as needed to eliminate as much duplicate code as possible.

You likely had one of two representations for the space your vehicles occupy:
  • Either a Posn representing one of the corners, as well as a width and a height,

  • Or a Posn representing one corner and a second Posn representing the diagonally-opposite corner.

You might have consolidated these representation choices into an Area class, such that every vehicle has an Area field.


If you have not done so already, you should do so: create a class to represent a rectangular area of the board, and move into that class all the arithmetic for computing overlaps between areas. You will likely want to add more methods to this new class, in support of the functionality below. Make sure that regardless of which representation choice you made above, you document clearly whether the coordinates represent the cells or their corners, and whether the area is open, closed, or semi-open – review Lecture 22: ArrayLists for why these distinctions matter.

7.3 Player motion:🔗

In the previous part of the game, you implemented the ability for players to select and deselect vehicles in the game. Now, you should add the ability to play the game:


Implement any methods needed to produce the above functionality and make the game playable. Update your UserGuide.txt file to more-fully explain how a player might play your game.

7.4 Obstacles:🔗

While parking lots are often just empty wide-open expanses of pavement, there are usually obstacles that make driving trickier. (You can think of these as traffic cones, or potholes, or just as pillars in a parking garage.)


Extend your design from part 1 to support placing obstacles anywhere within the game area. These 1x1-cell obstacles should prevent vehicles from driving through them in any direction. (Hint: do you also need to update the string-to-level convenience constructor? Or does it/could it already work with this new requirement?)


In a file Changes.txt, explain:
  • What changes did you have to make to your data definitions from the previous assignment, and why?

  • Had you known in the prior assignment that obstacles would be arriving now, would you have designed your data differently?

  • If we were to enhance the game with new kinds of items in the next assignment, would your revised data definitions accommodate those changes more easily?

7.5 Irregularly shaped levels:🔗

Not all parking lots are rectangular.


Design two example levels whose playable area is not a straightforward rectangle. In your Design.txt file, explain what new implementation support, if any, you needed to build to make this work.

7.6 Submission notes:🔗

Include all the code needed for your game, and any image files you might be using.

Include the Merging.txt, Design.txt, Changes.txt and UserGuide.txt files.

Problem 2: Cellular Automata and Mutable World Programs🔗

A cellular automaton is a simplified model of a biological cell: it has a state, a short lifespan, and can produce a child cell in some state in response to its own state and to the state of its neighbors. When a collection of cellular automata are arranged in some fashion (in a line, or on a plane, or in a 3-d grid...), interesting collective behaviors can emerge. In this problem, we’re going to work with the simplest kind of cellular automaton, which has only two states (on or off), and we’re only going to work with a 1-dimensional collection of cells. As it turns out, even this simplified setting is enough for impressive patterns to emerge.

Before you begin the assignment below, add the following lines to the top of your Automata.java file:

import tester.*; // The tester library import javalib.worldimages.*; // images, like RectangleImage or OverlayImages import javalib.impworld.*; // the abstract World class and the big-bang library for imperative worlds import java.awt.Color; // general colors (as triples of red,green,blue values) // and predefined colors (Red, Green, Yellow, Blue, Black, White)

Be sure to use impworld, not funworld.

7.1 Individual cells🔗

An individual cell should implement the following interface:
interface ICell {
// gets the state of this ICell int getState();
// render this ICell as an image of a rectangle with this width and height WorldImage render(int width, int height);
// produces the child cell of this ICell with the given left and right neighbors ICell childCell(ICell left, ICell right);

Every cell has a state, but it might be computed in various ways, so ICells provide a getState method to compute it. We make the return type int in case you want to experiment with more sophisticated cell states than just on/off. For now, use 0 for an “off” cell, and 1 for an “on” cell.

Additionally, every cell needs to produce a picture of itself somehow. The render method should produce a picture that fits into a rectangle of the given width and height. You will use this method to render a collection of cells at various locations. You may draw cells however you like; in the pictures below, an “on” cell is drawn as a black square, while an “off” cell is white.

Finally, the childCell method lets a cell produce its child cell, in response to its own state and its neighbors’ states. We’ll describe this method in more detail, below.

7.2 Different kinds of cells🔗
7.2.1 Inert cells🔗

Define a class InertCell that implements ICell, and is always off. Its state is always 0. When it produces a child, it ignores its neighbors entirely and produces another InertCell.

7.2.2 Rule-based cells🔗

A rule-based cell takes the states of its left and right neighbors, along with its own state, into account when producing a child cell. Since each of these three cells can be in one of two states, there are eight possible situations. For each of these eight possible situations, the child cell could be either on or off. Accordingly, there are 28 = 256 possible “rules” for implementing a rule-based cell. We can conveniently name these rules by reading off the outputs as bits, in order from left to right, and treating them as an 8-bit binary number. For example, here is rule 60:


Read each of these images as saying (for example): “if the left cell is in state 1, this cell is in state 0, and the right cell is in state 1, then output a child cell in state 1.”

(We get the number 60 by reading the outputs as bits from left to right, so 0 * 27 + 0 * 26 + 1 * 25 + 1 * 24 + 1 * 23 + 1 * 22 + 0 * 21 + 0 * 20 = 60. We get the exponents by reading off the inputs as bits of a binary number, too.)

Design a class Rule60 that implements ICell, and implements the rule above.

Design a class Rule30 that implements ICell, and implements the rule below:


(Again, we get the number 30 by reading the outputs as bits from left to right, so 0 * 27 + 0 * 26 + 0 * 25 + 1 * 24 + 1 * 23 + 1 * 22 + 1 * 21 + 0 * 20 = 30.)

Abstract as much as you can. Implementing new classes, such as Rule182 or Rule54, should be much easier than copy-paste-modifying your existing code! Instead, look carefully for repeated code in these rule-based classes, and abstract it into an abstract base class (that still implements ICell). Then, simplify your concrete classes as much as possible. You may find this easier to do once you’ve finished the rest of the assignment and have it working, and can confirm (via tests!) that you won’t break anything.

7.3 Populations of cells🔗

A population of cells will be a CellArray, which takes in just an ArrayList<ICell> in its constructor. Design a method CellArray nextGen() that produces a new generation of cells from the current population. Cells at the start and end of the list are treated as having InertCells as left and right neighbors, respectively.

It should also have a draw method, which takes in two numbers, representing the width and the height of an indiviual cell.

7.4 Animating your world🔗

This code introduces two new keywords, static and final. For now, treat them as “magic words” and use these definitions as given. A partial explanation for them is that static lets you define things associated with a class rather than with an object, and final prohibits you from modifying a value once it’s been initialized. Taken together, and when used properly, they allow you to define constants like these, and the naming convention is to use ALL_CAPS_AND_UNDERSCORES.

Design a class CAWorld that extends World. Complete the class definition below:
class CAWorld extends World {
// constants static final int CELL_WIDTH = 10;
static final int CELL_HEIGHT = 10;
static final int INITIAL_OFF_CELLS = 20;
static final int TOTAL_CELLS = INITIAL_OFF_CELLS * 2 + 1;
static final int NUM_HISTORY = 41;
// the current generation of cells CellArray curGen;
// the history of previous generations (earliest state at the start of the list) ArrayList<CellArray> history;
// Constructs a CAWorld with INITIAL_OFF_CELLS of off cells on the left, // then one on cell, then INITIAL_OFF_CELLS of off cells on the right CAWorld(ICell off, ICell on) {
//TODO: Fill in }
// Modifies this CAWorld by adding the current generation to the history // and setting the current generation to the next one public void onTick() {
//TODO: Fill in }
// Draws the current world, ``scrolling up'' from the bottom of the image public WorldImage makeImage() {
// make a light-gray background image big enough to hold 41 generations of 41 cells each WorldImage bg = new RectangleImage(TOTAL_WIDTH, TOTAL_HEIGHT,
OutlineMode.SOLID, new Color(240, 240, 240));
// build up the image containing the past and current cells WorldImage cells = new EmptyImage();
for (CellArray array : this.history) {
cells = new AboveImage(cells, array.draw(CELL_WIDTH, CELL_HEIGHT));
cells = new AboveImage(cells, this.curGen.draw(CELL_WIDTH, CELL_HEIGHT));
// draw all the cells onto the background return new OverlayOffsetAlign(AlignModeX.CENTER, AlignModeY.BOTTOM,
cells, 0, 0, bg);
public WorldScene makeScene() {
WorldScene canvas = new WorldScene(TOTAL_WIDTH, TOTAL_HEIGHT);
canvas.placeImageXY(this.makeImage(), TOTAL_WIDTH / 2, TOTAL_HEIGHT / 2);
return canvas;

The 5th, 15th and 25th generations for Rule 60 should look like this (shrunk to fit side-by-side here):

image image image

Likewise, the 5th, 15th and 25th generations for Rule 30 should look like this:

image image image

7.5 Optional Enhancements🔗

Try designing a three-valued cell (states are 0, 1, 2), or a four-valued cell. Make up coloring rules for them, and make up rules for how the childCell method should work.

Try designing differently-sized neighborhoods, so that cells can see their four nearest neighbors (two on each side).