Think Java: How to Think Like a Computer Scientist by Allen B. Downey - HTML preview

Chapter 16

GridWorld: Part 3

If you haven’t done the exercises in Chapters 5 and 10, you should do them be-

fore reading this chapter. As a reminder, you can find the documentation for

the GridWorld classes at http://www.greenteapress.com/thinkapjava/

javadoc/gridworld/.

Part 3 of the GridWorld Student Manual presents the classes that make up

GridWorld and the interactions among them. It is an example of object-

oriented design and an opportunity to discuss OO design issues.

But before you read the Student Manual, there are a few more things you

need to know.

16.1

ArrayList

GridWorld uses java.util.ArrayList, which is an object similar to an ar-

ray. It is a collection, which means that it’s an object that contains other

objects. Java provides other collections with different capabilities, but to use

GridWorld we only need ArrayLists.

To see an example, download http://thinkapjava.com/code/BlueBug.

java

and

http://thinkapjava.com/code/BlueBugRunner.java.

A

BlueBug is a bug that moves at random and looks for rocks. If it finds a

rock, it makes it blue.

204

Chapter 16. GridWorld: Part 3

Here’s how it works. When act is invoked, BlueBug gets its location and a

reference to the grid:

Location loc = getLocation();

Grid<Actor> grid = getGrid();

The type in angle-brackets (<>) is a type parameter that specifies the

contents of grid. In other words, grid is not just a Grid, it’s a Grid that

contains Actors.

The next step is to get the neighbors of the current location. Grid provides

a method that does just that:

ArrayList<Actor> neighbors = grid.getNeighbors(loc);

The return value from getNeighbors is an ArrayList of Actors. The size

method returns the length of the ArrayList, and get selects an element. So

we can print the neighbors like this.

for (int i=0; i<neighbors.size(); i++) {

Actor actor = neighbors.get(i);

System.out.println(actor);

}

Traversing an ArrayList is such a common operation there’s a special syntax

for it. So we could write:

for (Actor actor: neighbors) {

System.out.println(actor);

}

We know that the neighbors are Actors, but we don’t know what kind:

they could be Bugs, Rocks, etc. To find the Rocks, we use the instanceof

operator, which checks whether an object is an instance of a class.

for (Actor actor: neighbors) {

if (actor instanceof Rock) {

actor.setColor(Color.blue);

}

}

To make all this work, we need to import the classes we use:

import info.gridworld.actor.Actor;

import info.gridworld.actor.Bug;

16.2. Interfaces

205

import info.gridworld.actor.Rock;

import info.gridworld.grid.Grid;

import info.gridworld.grid.Location;

import java.awt.Color;

import java.util.ArrayList;

Exercise 16.1. Starting with a copy of BlueBug.java, write a class defi-

nition for a new kind of Bug that finds and eats flowers. You can “eat” a

flower by invoking removeSelfFromGrid on it.

16.2

Interfaces

GridWorld uses Java interfaces, so I want to explain what they are. “Inter-

face” means different things in different contexts, but in Java it refers to a

specific language feature: an interface is a class definition where the methods

have no bodies.

In a normal class definition, each method has a prototype and a body (see

Section 8.5). A prototype is also called a specification because it specifies

the name, parameters and return type of the method; the body is called the

implementation because it implements the specification.

In a Java interface the methods have no bodies, so it specifies the methods

without implementing them.

For example, java.awt.Shape is an interface with prototypes for contains,

intersects, and several other methods. java.awt.Rectangle provides im-

plementations for those methods, so we say that “Rectangle implements

Shape.” In fact, the first line of the Rectangle class definition is:

public class Rectangle extends Rectangle2D implements Shape, Serializable

Rectangle inherits methods from Rectangle2D and provides implementations

for the methods in Shape and Serializable.

In GridWorld the Location class implements the java.lang.Comparable in-

terface by providing compareTo, which is similar to compareCards in Sec-

tion 13.5.

206

Chapter 16. GridWorld: Part 3

GridWorld also defines a new interface, Grid, that specifies the methods a

Grid should provide. And it includes two implementations, BoundedGrid

and UnboundedGrid.

The Student Manual uses the abbreviation API, which stands for “ap-

plication programming interface.”

The API is the set of methods that

are available for you, the application programmer, to use.

See http:

//en.wikipedia.org/wiki/Application_programming_interface.

16.3

public and private

Remember in Chapter 1 I said I would explain why the main method has the

keyword public? Finally, the time has come.

public means that the method can be invoked from other classes.

The

alternative is private, which means the method can only be invoked inside

the class where it is defined.

Instance variables can also be public or private, with the same result: a

private instance variable can be accessed only inside the class where it is

defined.

The primary reason to make methods and instance variables private is to

limit interactions between classes in order to manage complexity.

For example, the Location class keeps its instance variables private. It has

accessor methods getRow and getCol, but it provides no methods that mod-

ify the instance variables. In effect, Location objects are immutable, which

means that they can be shared without worrying about unexpected behavior

due to aliasing.

Making methods private helps keep the API simple. Classes often include

helper methods that are used to implement other methods, but making those

methods part of the public API might be unnecessary and error-prone.

Private methods and instance variables are language features that help pro-

grammers ensure data encapsulation, which means that objects in one

class are isolated from other classes.

Exercise 16.2. Now you know what you need to know to read Part 3 of the

GridWorld Student Manual and do the exercises.

16.4. Game of Life

207

16.4

Game of Life

The mathematician John Conway invented the “Game of Life,” which he

called a “zero-player game” because no players are needed to choose strategies

or make decisions. After you set up the initial conditions, you watch the game

play itself. But that turns out to be more interesting than it sounds; you can

read about it at http://en.wikipedia.org/wiki/Conways_Game_of_Life.

The goal of this exercises is to implement the Game of Life in GridWorld.

The game board is the grid, and the pieces are Rocks.

The game proceeds in turns, or time steps. At the beginning of the time

step, each Rock is either “alive” or “dead”. On the screen, the color of the

Rock indicates its status.

The status of each Rock depends on the status of its neighbors. Each Rock

has 8 neighbors, except the Rocks along the edge of the Grid. Here are the

rules:

❼ If a dead Rock has exactly three neighbors, it comes to life! Otherwise

it stays dead.

❼ If a live Rock has 2 or 3 neighbors, it survives. Otherwise it dies.

Some consequences of these rules: If all Rocks are dead, no Rocks come to

life. If you start with a single live Rock, it dies. But if you have 4 Rocks in

a square, they keep each other alive, so that’s a stable configuration.

Most simple starting configurations either die out quickly or reach a stable

configuration. But there are a few starting conditions that display remarkable

complexity. One of those is the r-pentomino: it starts with only 5 Rocks,

runs for 1103 timesteps and ends in a stable configuration with 116 live Rocks

(see http://www.conwaylife.com/wiki/R-pentomino).

The following sections are my suggestions for implementing GoF in Grid-

World. You can download my solution at http://thinkapjava.com/code/

LifeRunner.java and http://thinkapjava.com/code/LifeRock.java.

208

Chapter 16. GridWorld: Part 3

16.5

LifeRunner

Make a copy of BugRunner.java named LifeRunner.java and add methods

with the following prototypes:

/**

* Makes a Game of Life grid with an r-pentomino.

*/

public static void makeLifeWorld(int rows, int cols)

/**

* Fills the grid with LifeRocks.

*/

public static void makeRocks(ActorWorld world)

makeLifeWorld should create a Grid of Actors and an ActorWorld, then

invoke makeRocks, which should put a LifeRock at every location in the

Grid.

16.6

LifeRock

Make a copy of BoxBug.java named LifeRock.java. LifeRock should ex-

tend Rock. Add an act method that does nothing. At this point you should

be able to run the code and see a Grid full of Rocks.

To keep track of the status of the Rocks, you can add a new instance variable,

or you can use the Color of the Rock to indicate status. Either way, write

methods with these prototypes:

/**

* Returns true if the Rock is alive.

*/

public boolean isAlive()

/**

* Makes the Rock alive.

*/

public void setAlive()

16.7. Simultaneous updates

209

/**

* Makes the Rock dead.

*/

public void setDead()

Write a constructor that invokes setDead and confirm that all Rocks are

dead.

16.7

Simultaneous updates

In the Game of Life, all Rocks are updated simultaneously; that is, each

rock checks the status of its neighbors before any Rocks change their status.

Otherwise the behavior of the system would depend on the order of the

updates.

In order to implement simultaneous updates, I suggest that you write an act

method that has two phases: during the first phase, all Rocks count their

neighbors and record the results; during the second phase, all Rocks update

their status.

Here’s what my act method looks like:

/**

* Check what phase we✬re in and calls the appropriate method.

* Moves to the next phase.

*/

public void act() {

if (phase == 1) {

numNeighbors = countLiveNeighbors();

phase = 2;

} else {

updateStatus();

phase = 1;

}

}

phase and numNeighbors are instance variables. And here are the prototypes

for countLiveNeighbors and updateStatus:

210

Chapter 16. GridWorld: Part 3

/**

* Counts the number of live neighbors.

*/

public int countLiveNeighbors()

/**

* Updates the status of the Rock (live or dead) based on the number

* of neighbors.

*/

public void updateStatus()

Start with a simple version of updateStatus that changes live rocks to dead

and vice versa. Now run the program and confirm that the Rocks change

color. Every two steps in the World correspond to one timestep in the Game

of Life.

Now fill in the bodies of countLiveNeighbors and updateStatus according

to the rules and see if the system behaves as expected.

16.8

Initial conditions

To change the initial conditions, you can use the GridWorld pop-up menus

to change the status of the Rocks by invoking setAlive. Or you can write

methods to automate the process.

In LifeRunner, add a method called makeRow that creates an initial config-

uration with n live Rock in a row in the middle of the grid. What happens

for different values of n?

Add a method called makePentomino that creates an r-pentomino in the

middle of the Grid. The initial configuration should look like this:

16.8. Initial conditions

211

If you run this configuration for more than a few steps, it reaches the end

of the Grid. The boundaries of the Grid change the behavior of the system;

in order to see the fill evolution of the r-pentomino, the Grid has to be big

enough. You might have to experiment to find the right size, and depending

on the speed of your computer, it might take a while.

The Game of Life web page describes other initial conditions that yield in-

teresting results (http://www.conwaylife.com/). Choose one you like and

implement it.

There are also variations of the Game of Life based on different rules. Try

one out and see if you find anything interesting.

Exercise 16.3. If you implemented the Game of Life, you are well prepared

for Part 4 of the GridWorld Student Manual. Read it and do the exercises.

Congratulations, you’re done!

212

Chapter 16. GridWorld: Part 3

Appendix A

Graphics

A.1

Java 2D Graphics

This appendix provides examples and exercises that demonstrate Java graph-

ics. There are several ways to create graphics in Java; the simplest is to use

java.awt.Graphics. Here is a complete example:

import java.awt.Canvas;

import java.awt.Graphics;

import javax.swing.JFrame;

public class MyCanvas extends Canvas {

public static void main(String[] args) {

// make the frame

JFrame frame = new JFrame();

frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

// add the canvas

Canvas canvas = new MyCanvas();

canvas.setSize(400, 400);

frame.getContentPane().add(canvas);

// show the frame

214

Appendix A. Graphics

frame.pack();

frame.setVisible(true);

}

public void paint(Graphics g) {

// draw a circle

g.fillOval(100, 100, 200, 200);

}

}

You

can

download

this

code

from

http://thinkapjava.com/code/

MyCanvas.java.

The first lines import the classes we need from java.awt and javax.swing.

MyCanvas extends Canvas, which means that a MyCanvas object is a kind of

Canvas that provides methods for drawing graphical objects.

In main we

1. Create a JFrame, which is a window that can contain the canvas, but-

tons, menus and other window components;

2. Create MyCanvas, set its width and height, and add it to the frame;

and

3. Display the frame on the screen.

paint is a special method that gets invoked when MyCanvas needs to be

drawn. If you run this code, you should see a black circle on a gray back-

ground.

A.2

Graphics methods

To draw on the Canvas, you invoke methods on the Graphics object. The pre-

vious example uses fillOval. Other methods include drawLine, drawRect

and more.

You can read the documentation of these methods at http:

//download.oracle.com/javase/6/docs/api/java/awt/Graphics.html.

Here is the prototype for fillOval:

A.3. Coordinates

215

public void fillOval(int x, int y, int width, int height)

The parameters specify a bounding box, which is the rectangle in which

the oval is drawn (as shown in the figure). The bounding box itself is not

drawn.

x and y specify the the location of the upper-left corner of the bounding box

in the Graphics coordinate system.

A.3

Coordinates

You are probably familiar with Cartesian coordinates in two dimensions,

where each location is identified by an x-coordinate (distance along the x-

axis) and a y-coordinate. By convention, Cartesian coordinates increase to

the right and up, as shown in the figure.

By convention, computer graphics systems to use a coordinate system where

the origin is in the upper-left corner, and the direction of the positive y-axis

is down. Java follows this convention.

216

Appendix A. Graphics

Coordinates are measured in pixels; each pixel corresponds to a dot on the

screen. A typical screen is about 1000 pixels wide. Coordinates are always

integers. If you want to use a floating-point value as a coordinate, you have

to round it off (see Section 3.2).

A.4

Color

To choose the color of a shape, invoke setColor on the Graphics object:

g.setColor(Color.red);

setColor changes the current color; everything that gets drawn is the current

color.

Color.red is a value provided by the Color class; to use it you have to

import java.awt.Color. Other colors include:

black

blue

cyan

darkGray

gray

lightGray

magenta

orange

pink

red

white

yellow

You can create other colors by specifying red, green and blue (RGB) compo-

nents. See http://download.oracle.com/javase/6/docs/api/java/awt/

Color.html.

You can control the background color of the Canvas by invoking

Canvas.setBackground.

Exercise A.1. Draw the flag of Japan, a red circle on white background that

is wider than it is tall.

A.5

Mickey Mouse

Let’s say we want to draw a picture of Mickey Mouse. We can use the oval we

just drew as the face, and then add ears. To make the code more readable,

let’s use Rectangles to represent bounding boxes.

Here’s a method that takes a Rectangle and invokes fillOval.

public void boxOval(Graphics g, Rectangle bb) {

g.fillOval(bb.x, bb.y, bb.width, bb.height);

}

A.5. Mickey Mouse

217

And here’s a method that draws Mickey:

public void mickey(Graphics g, Rectangle bb) {

boxOval(g, bb);

int dx = bb.width/2;

int dy = bb.height/2;

Rectangle half = new Rectangle(bb.x, bb.y, dx, dy);

half.translate(-dx/2, -dy/2);

boxOval(g, half);

half.translate(dx*2, 0);

boxOval(g, half);

}

The first line draws the face. The next three lines create a smaller rectangle

for the ears. We translate the rectangle up and left for the first ear, then

right for the second ear.

The result looks like this:

You can download this code from http://thinkapjava.com/code/Mickey.

java.

Exercise A.2. Modify Mickey.java to draw ears on the ears, and ears on

those ears, and more ears all the way down until the smallest ears are only

3 pixels wide.

The result should look like Mickey Moose:

218

Appendix A. Graphics

Hint: you should only have to add or modify a few lines of code.

You can download a solution from http: // thinkapjava. com/ code/

MickeySoln. java .

Exercise A.3.

1. Download

http: // thinkapjava. com/ code/

Moire. java and import it into your development environment.

2. Read the paint method and draw a sketch of what you expect it to

do. Now run it. Did you get what you expected? For an explanation

of what is going on, see http: // en. wikipedia. org/ wiki/ Moire_

pattern .

3. Modify the program so that the space between the circles is larger or

smaller. See what happens to the image.

4. Modify the program so that the circles are drawn in the center of the

screen and concentric, as in the following figure (left). The distance

between the circles should be small enough that the Moiré interference

is apparent.

A.5. Mickey Mouse

219

5. Write a method named radial that draws a radial set of line segments

as shown in the figure (right), but they should be close enough together

to create a Moiré pattern.

6. Just about any kind of graphical pattern can generate Moiré-like inter-

ference patterns. Play around and see what you can create.

220

Appendix A. Graphics

Appendix B

Input and Output in Java

B.1

System objects

The System class provides methods and objects that get input from the

keyboard, print text on the screen, and do file input and output (I/O).

System.out is the object that displays on the screen.

When you invoke

print and println, you invoke them on System.out.

You can use System.out to print System.out:

System.out.println(System.out);

The result is:

java.io.PrintStream@80cc0e5

When Java prints an object, it prints the type of the object, PrintStream,

the package where the type is defined, java.io, and a unique identifier for

the object. On my machine the identifier is 80cc0e5, but if you run the same

code, you probably get something different.

There is also an object named System.in that makes it possible to get input

from the keyboard. Unfortunately, it does not make it easy to get input from

the keyboard.

222

Appendix B. Input and Output in Java

B.2

Keyboard input

First, you have to use System.in to create a new InputStreamReader.

InputStreamReader in = new InputStreamReader(System.in);

Then you use in to create a new BufferedReader:

BufferedReader keyboard = new BufferedReader(in);

Finally you can invoke readLine on keyboard, to take input from the key-

board and convert it to a String.

String s = keyboard.readLine();

System.out.println(s);

There is only one problem. There are things that can go wrong when you

invoke readLine, and they might throw an IOException. A method that

throws an exception has to include it in the prototype, like this:

public static void main(String[] args) throws IOException {

// body of main

}

B.3

File input

Here’s a program that reads lines from a file and prints them:

import java.io.*;

public class Words {

public static void main(String[] args)

throws FileNotFoundException, IOException {

processFile("words.txt");

}

public static void processFile(String filename)

throws FileNotFoundException, IOException {

FileReader fileReader = new FileReader(filename);

B.4. Catching exceptions

223

BufferedReader in = new BufferedReader(fileReader);

while (true) {

String