On this page:
Problem 1: Visitors
Problem 2: Rush Hour, Part 1
Submission notes
A note about randomness

Assignment 5: Building a game; Visitors🔗

Goals: To build a non-trivial Big-bang game from scratch, and practice with visitors


Be very, very careful with naming! Again, the solution files expect your submissions to be named a certain way, so that they can define their own Examples class with which to test your code. Therefore, whenever the assignment specifies:
  • the names of classes,

  • the names and types of the fields within classes,

  • the names, types and order of the arguments to the constructor,

  • the names, types and order of arguments to methods, or

  • filenames,

...be sure that your submission uses exactly those names.

Make sure you follow the style guidelines that Bottlenose enforces. For now the most important ones are: using spaces instead of tabs, indenting by 2 characters, following the naming conventions (data type names start with a capital letter, names of fields and methods start with a lower case letter), and having spaces before curly braces.

You will submit this assignment by the deadline using the Bottlenose submission system. You may submit as many times as you wish. Be aware of the fact that close to the deadline the Bottlenose system may slow down to handle many submissions - so try to finish early.

There will be a separate submission for each problem - it makes it easier to grade each problem, and to provide you with the feedback for each problem you work on.

The submissions will be organized as follows:

Due Dates:
  • Problem 1, arithmetic visitors: Friday, Feb 16th, at 9:00pm

  • Problem 2, Rush Hour implementation: Friday, Feb 16th, at 9:00pm

  • Problem 2 peer review: Saturday, Feb 17th, at 9:00pm

Problem 1: Visitors🔗

In a new file Visitors.java, implement the following class diagram:
      | IArith            |
          /_\      /_\
           |        |--------------------------------------------------------------
           |        |                                                             |
+-------------+  +------------------------------+           +-----------------------------------------+
| Const       |  | UnaryFormula                 |           |              BinaryFormula              |
+-------------+  +------------------------------+           +-----------------------------------------+
| double num  |  | Function<Double,Double> func |           | BiFunction<Double, Double, Double> func |
+-------------+  | String name                  |           | String name                             |
                 | IArith child                 |           | IArith left                             |
                 +------------------------------+           | IArith right                            |

Specifically, the above represents an arithmetic expression. The Function and BiFunction in UnaryFormula and BinaryFormula respectively denote the arithmetic operation to be applied to their respective operands (child and left,right). In class, we defined these interfaces as IFunc and IFunc2, but they’re actually predefined for you in Java. To use them, you will need to write import java.util.function.*; at the top of your file among the other import statements. As in class, these interfaces require that you implement a method named apply, whose parameters are (in this problem) all Doubles.

You must support 4 binary formulas (named "plus", "minus", "mul" and "div" representing addition, subtraction, multiplication and division respectively), and 2 unary formulas (named "neg" and "sqr" representing negation and squaring respectively).

Problem 2: Rush Hour, Part 1🔗

We’re going to build Rush Hour, a logic/puzzle game invented in the 1970s, over the next few weeks. There are many variations on this game in existence, so we’ll be adding features as we go. Adding features may mean that you have to redesign earlier parts of your code, so the cleaner your initial design is, the easier it will be to modify later. Spending time early on careful, clean design will pay off!

Note: This assignment is not written in the same style as other problems; we are not specifying class or interface names for you, or demanding a specific set of method signatures on them. Instead, we are giving you Exercises of the functionality to design and implement this week. Don’t try to implement “the whole game” this week, since those functionality requirements haven’t been specified yet.

A Rush Hour level is played on a rectangular grid of square cells. For now we’ll only consider a few kinds of pieces; we’ll add more later. Here is an example board:


The board (currently) consists of cars and trucks stuck in a parking lot. Each car is two squares long; each truck is three squares long. All vehicles can only move forwards or backwards — they can’t “change lanes”, nor can they turn. As in real life, two vehicles can’t share the same space. The gray area shows the boundaries of the parking lot, and the goal of the game is to get the target car (usually shown in red) out of the traffic jam and through the parking lot’s exit; no other vehicles can exit the parking lot. You can play a version of this game online at https://www.thinkfun.com/rush-hour-online-play/. Be aware that our game may (currently or eventually) differ in some details from this online version.

In fact, the general case of the game is provably known to be very hard indeed...

It’s worth pointing out that not all possible levels of the game are solvable; here is a trivial traffic jam:


You do not have to determine if a given game is in fact solvable!


Design data definitions sufficient to describe the board state. You will need several helper data definitions. Note that different boards could easily be of different sizes, so your definitions should not limit themselves to a specific size of board. Be sure to follow the design recipe for all of them, and create sufficient examples. Your data definitions will need to accommodate new features in the future, so be careful not to make your designs too inflexible. Make sure your data definitions have clear interpretations, so that readers of your code can understand and use your definitions.

It will be convenient to have an easy way to write down board levels as text.

So for instance, the first level above can be written as

String demoLevel =
"+------+\n" +
"| |\n" +
"| C T |\n" +
"|c CX\n" +
"|t |\n" +
"|CCC c |\n" +
"| c |\n" +

(Note that this string doesn’t by itself provide enough information to indicate which is the target car.)


Design a class to represent a Rush Hour level. One of the constructors of this class should take in a level-description string like the one above (plus additional information, if you think it’s necessary), and use it to configure the level — it will likely be much easier than trying to write out the IList of contents by hand. (Reminder: not all strings describe valid levels! You do not need to determine if a level is solvable, but you should double-check that the string doesn’t describe a logically-invalid level.)

Hint: There are many plausible ways to represent your board. Don’t assume that your first-draft idea is the best or only way to do it!

Test this constructor carefully on a few examples, and then you can use this constructor to help build your other examples and other test cases. You will likely want to build a utility class, with a method on it that takes the string above and produces the list of game items in it... You will likely need some helper methods, and likely need to use the substring method of String to examine the contents of the string.

Here are some other levels that may be fun to play. In each of them, the red car is the one that must escape:

image image

image image


Design a method on your class to render it as an image. You do not need to reproduce exactly the renderings above, but your level should be recognizable.


Design a method to detect if two vehicles are overlapping. (Hint: Consider the simpler case of one dimensional intervals (l, h), where l is the lower endpoint of the interval and h is the higer endpoint. To check if two intervals (l1, h1) and (l2, h2) are overlapping, you should check whether either l1 is between l2 and h2, or l2 is between l1 and h1. Another, more concise way to phrase this is whether the larger of l1 and l2 is less than the smaller of h1 and h2. Vehicles are two-dimensional, in that they take up width and height, so you should generalize the idea above somehow.)


Design a method to detect if the player has won the level, by getting the target vehicle to the exit.


Design a class that subclasses javalib.funworld.World, that contains a starting Rush Hour level. Design a mouse-click method (read the documentation, or refer back to Lab 1) that detects when the player clicks on a vehicle, and draws that vehicle highlighted yellow instead of its usual color. Clicking on another vehicle should switch the selection; clicking on a cell that has no vehicle in it should deselect the currently-selected vehicle.

Hint: It likely makes sense to have two separate classes: one that subclasses World and handles mouse-clicks and keypresses and such, and one that represents your game logic. Combining these into a single class risks making that class bloated and hard to read. It is not absolutely necessary to have this split, but it likely will simplify your code.

Submission notes🔗

Don’t make the game overly elaborate; we are more interested in your program’s design than your graphic design!

You may, if you wish, separate out different classes into separate files. Make sure you submit them all, though.

Include in your submission two additional files:

Be sure to include all the needed files — source file(s), documentation, etc — or else we won’t be able to run your game. You should submit the files as a single .zip file. To make a zip file, follow these instructions: open Explorer or Finder, select all the relevant files, right-click and choose “Add to zip” or “Compress” or some similarly-named menu item. Do not include the out/ or target/ directories where Eclipse puts your compiled code, or any of the .class files; they are not necessary.

A note about randomness🔗

There are two ways to generate random numbers in Java. The easiest is to use Math.random(), which generates a double between 0 (inclusive) and 1 (exclusive). You can multiply this number by some integer to make it bigger, then coerce to an int to produce a random integer in the range you wish. However, this is not easily testable: you’ll get different random values every time.

The better way to generate random numbers is: First, import java.util.Random at the top of your file. Next, create a new Random() object, and use its nextInt(int maxVal) method, which will give you a random integer between zero (inclusive) and maxVal (exclusive).

This is known as a "pseudorandom number generator", since the numbers aren’t really random if they can be reliably repeated...

The reason this is better is because there is a second constructor, new Random(int initialSeed), which has the property that every time you create a Random with the same initial seed, it will generate the same "random" numbers in the same order every time your program runs. You should therefore design your world classes with two constructors: