Assignment 5: Building a game; Visitors🔗

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

Instructions🔗

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:

• Homework 5 Problem 1: The IArith.java file

• Homework 5 Problem 2: Your Rush Hour game

• Homework 5 Problem 2 review: Your peer review of other students’ designs

Problem 1: Visitors🔗

      +-------------------+
      | 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).

• Design an interface IArithVisitor<R> representing a visitor that visits an IArith and produces a result of type R. The visitor must be usable as a Function object on IArith producing a result of type R. For example, given an IArith object named iObj, and a SomeVisitor class, we should be able to write new SomeVisitor().apply(iObj).

• Design an accept(IArithVisitor<R>) method for the IArith interface and implement it on Const, UnaryFormula and BinaryFormula.

• Design an EvalVisitor that visits an IArith and evaluates the tree to a Double answer.

• Design a PrintVisitor that visits an IArith and produces a String showing the fully-parenthesized expression in Racket-like prefix notation (i.e. "(div (plus 1.0 2.0) (neg 1.5))"), using the name for Formulas and using Double.toString(num) on Consts.

• Design a DoublerVisitor that visits an IArith and produces another IArith, where every Const in the tree has been doubled.

• Design an AllSmallVisitor that visits an IArith and produces a Boolean that is true if every constant in the tree is less than 10.

• Tricky! Design a NoDivBy0 visitor that visits an IArith and produces a Boolean that is true if anywhere there is a Formula named "div", the right argument does not evaluate to roughly zero. Since all values here are double, define “roughly zero” as “absolute value less than 0.0001”.

• When evaluating the result, the computer on which this program will run has no support for negative numbers. Design a NoNegativeResults visitor that visits an IArith and produces a Boolean that is true, if a negative number is never encountered at any point during its evaluation.

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.

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

Exercise

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.

• The letter "T" will represent the start of a vertical truck, and the letter "t" will represent the start of a horizontal truck.

• The letter "C" will represent the start of a vertical car, and the letter "c" will represent the start of a horizontal car.

• The letter "X" will represent the exit.

• For visibility, the characters "+", "-" and "|" will be used to indicate the walls of the parking lot. (They all mean the same thing, but it’s useful to have all three for ASCII-art purposes, as visible below.)

• Linebreaks "\n" separate rows within the level.

• Spaces " " indicate nothing is in a given cell.

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

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

Exercise

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:

Exercise

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.

Exercise

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.)

Exercise

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

Exercise

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:

• UserGuide.txt should be a short file describing how to play the game (so far! – you’ll update this in future parts as more of the game gets implemented).

• Design.txt should describe each of the interfaces and classes in your design, and what they all do. If you think it’s helpful, include an ASCII-art class diagram to show the relationships between the classes.

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).

• One of them, to be used for testing, should take in a Random object whose seed value you specify. This way your game will be utterly predictable every single time you test it.

• The second constructor should not take in a Random object, but should call the other constructor, and pass along a really random object:

  import java.util.Random;

  class YourWorld {

  Random rand

  // The constructor for use in "real" games YourWorld() { this(new Random()); }

  // The constructor for use in testing, with a specified Random object YourWorld(Random rand) { this.rand = rand; ... }

  }

  Now, your tests can be predictable while your game can still be random, and the rest of your code doesn’t need to change at all.