14.6: Case Study- The Game of Pong

The game of Pong was one of the first computer video games and was all the rage in the 1970s. The game consists of a ball that moves horizontally and vertically within a rectangular region, and a single paddle, which is located at the right edge of the region that can be moved up and down by the user. When the ball hits the top, left, or bottom walls or the paddle, it bounces off in the opposite direction. If the ball misses the paddle, it passes through the right wall and re-emerges at the left wall. Each time the ball bounces off a wall or paddle, it emits a pong sound.

A Multithreaded Design

Let’s develop a multithreaded GUI to play the game of Pong.

Figure 14.29 shows how the game’s GUI should appear. There are three objects involved in this program: the frame, which serves as the GUI, the ball, which is represented as a blue circle in the program, and the paddle, which is represented by a red rectangle along the right edge of the frame. What cannot be seen in this figure is that the ball moves autonomously, bouncing off the walls and paddle. The paddle’s motion is controlled by the user by pressing the up- and down-arrow keys on the keyboard.

We will develop class definitions for the ball, paddle, and the frame. Following the example of our dot-drawing program earlier in the Chapter, we will employ two independent threads, one for the GUI and one for the ball. Because the user will control the movements of the paddle, the frame will employ a listener object to listen for and respond to the user’s key presses.

Figure [fig-pongdesign] provides an overview of the object-oriented design of the Pong program. The PongFrame class is the main class. It uses instances of the Ball and Paddle classes. PongFrame is a subclass of JFrame and

implements the KeyListener interface. This is another of the several event handlers provided in the java.awt library. This one handles KeyEvents and the KeyListener interface consists of three abstract methods: keyPressed(), keyTyped(), and keyReleased(), all of which are associated with the act of pressing a key on the keyboard. All three of these methods are implemented in the PongFrame class. A key-typed event occurs when a key is pressed down. A key-release event occurs when a key that has been pressed down is released. A key-press event is a combination of both of these events.

The Ball class is a Thread subclass. Its data and methods are designed mainly to keep track of its motion within the program’s drawing panel. The design strategy employed here leaves the drawing of the ball up to the frame. The Ball thread itself just handles the movement within the program’s drawing panel. Note that the Ball() constructor takes a reference to the PongFrame. As we will see, the Ball uses this reference to set the dimensions of the frame’s drawing panel. Also, as the Ball moves, it will repeatedly call the frame’s repaint() method to draw the ball.

The Paddle class is responsible for moving the paddle up and down along the drawing panel’s right edge. Its public methods, moveUP() and moveDown(), will be called by the frame in response to the user pressing the up and down arrows on the keyboard. Because the frame needs to know where to draw the paddle, the paddle class contains several public methods, getX(), getY(), and resetLocation(), whose tasks are to report the paddle’s location or to adjust its location in case the frame is resized.

The PongFrame controls the overall activity of the program. Note in particular its ballHitsPaddle() method. This method has the task of determining when the ball and paddle come in contact as the ball continuously moves around in the frame’s drawing panel. As in the ThreadedDotty example earlier in the chapter, it is necessary for the Ball and the the frame to be implemented as separated threads so that the frame can be responsive to the user’s key presses.

Implementation of the Pong Program

We begin our discussion of the program’s implementation with the Paddle class implementation (Fig. [fig-paddle]).

public class Paddle {
    public static final int HEIGHT = 50;  // Paddle size
    public static final int WIDTH = 10;       
    private static final int DELTA = HEIGHT/2; // Move size
    private static final int BORDER = 0;
    private int gameAreaHeight;
    private int locationX, locationY;
    private PongFrame frame;

    public Paddle (PongFrame f) {
       frame = f;
       gameAreaHeight  = f.getHeight();
       locationX = f.getWidth()-WIDTH;
       locationY = gameAreaHeight/2;
    } // Paddle()
    public void resetLocation() {
       gameAreaHeight  = frame.getHeight();
       locationX = frame.getWidth()-WIDTH;
    }
    public int getX() {
         return locationX;
    }
    public int getY() {
         return locationY;
    }
    public void moveUp () {
       if (locationY > BORDER )
           locationY -= DELTA;
    } // moveUp()
    public void moveDown() {
       if (locationY + HEIGHT < gameAreaHeight - BORDER)
           locationY += DELTA;
    } // moveDown()
} // Paddle

Class constants, HEIGHT and WIDTH are used to define the size of the Paddle, which is represented on the frame as a simple rectangle. The frame will use the Graphics.fillRect() method to draw the paddle:

g.fillRect(pad.getX(),pad.getY(),Paddle.WIDTH,Paddle.HEIGHT);

Note how the frame uses the paddle’s getX() and getY() methods to get the paddle’s current location.

The class constants DELTA and BORDER are used to control the paddle’s movement. DELTA represents the number of pixels that the paddle moves on each move up or down, and BORDER is used with gameAreaHeight to keep the paddle within the drawing area. The moveUp() and moveDown() methods are called by the frame each time the user presses an up- or down-arrow key. They simply change the paddle’s location by DELTA pixels up or down.

The Ball class (Fig. [fig-ball]) uses the class constant SIZE to determine the size of the oval that represents the ball, drawn by the frame as follows:

g.fillOval(ball.getX(),ball.getY(),ball.SIZE,ball.SIZE);

As with the paddle, the frame uses the ball’s getX() and getY() method to determine the ball’s current location.

import javax.swing.*;
import java.awt.Toolkit;

public class Ball extends Thread {
  public static final int SIZE = 10;   // Diameter of the ball
  private PongFrame frame;           // Reference to the frame
  private int topWall, bottomWall, leftWall, rightWall;  // Boundaries
  private int locationX, locationY;     // Current location of the ball
  private int directionX = 1, directionY = 1; //x- and y-direction (1 or -1)
  private Toolkit kit = Toolkit.getDefaultToolkit(); //For beep() method

  public Ball(PongFrame f) {
    frame = f;
    locationX = leftWall + 1;                // Set initial location
    locationY = bottomWall/2;
  } // Ball()
  public int getX() {
    return locationX;
  } // getX()
  public int getY() {
    return locationY;
  } // getY()
  public void move() {
    rightWall = frame.getWidth() - SIZE;   // Define bouncing region
    leftWall = topWall = 0;                 // And location of walls
    bottomWall = frame.getHeight() - SIZE;
    locationX = locationX + directionX; // Calculate a new location
    locationY = locationY + directionY;

    if (frame.ballHitsPaddle()){
      directionX = -1;   //  move toward left wall
      kit.beep();
    } //if ball hits paddle
    if (locationX <= leftWall){
      directionX = + 1;   //  move toward right wall
      kit.beep();
    } //if ball hits left wall
    if (locationY + SIZE >= bottomWall || locationY <= topWall){
      directionY = -directionY;      //  reverse direction
      kit.beep();
    } //if ball hits top or bottom walls
    if (locationX  >= rightWall + SIZE) {
      locationX = leftWall + 1;   // jump back to left wall
    } //if ball goes through right wall
  } // move()
  public void run() {
    while (true) {
      move();                // Move
      frame.repaint();
      try {  sleep(15);
      } catch (InterruptedException e) {}
    } // while
  } // run()
} // Ball

Unlike the paddle, however, the ball moves autonomously. Its run() method, which is inherited from its Thread superclass, repeatedly moves the ball, draws the ball, and then sleeps for a brief interval (to slow down the speed of the ball’s apparent motion). The run() method itself is quite simple because it consists of a short loop. We will deal with the details of how the ball is painted on the frame when we discuss the frame itself.

The most complex method in the Ball class is the move() method. This is the method that controls the ball’s movement within the boundaries of the frame’s drawing area. This method begins by moving the ball by one pixel left, right, up, or down by adjusting the values of its locationX and locationY coordinates:

locationX = locationX + directionX; // Calculate location
locationY = locationY + directionY;

The directionX and directionY variables are set to either \(+1\) or \(-1\), depending on whether the ball is moving left or right, up or down. After the ball is moved, the method uses a sequence of if statements to check whether the ball is touching one of the walls or the paddle. If the ball is in contact with the top, left, or bottom walls or the paddle, its direction is changed by reversing the value of the directionX or directionY variable. The direction changes depend on whether the ball has touched a horizontal or vertical wall. When the ball touches the right wall, having missed the paddle, it passes through the right wall and re-emerges from the left wall going in the same direction.

Note how the frame method, ballHitsPaddle() is used to determine whether the ball has hit the paddle. This is necessary because only the frame knows the locations of both the ball and the paddle.

The KeyListener Interface

The implementation of the PongFrame class is shown in figure [fig-pongapplet]. The frame’s main task is to manage the drawing of the ball and paddle and to handle the user’s key presses. Handling keyboard events is a simple matter of implementing the KeyListener interface. This works in much the same way as the ActionListener interface, which is used to handle button clicks and other ActionEvents. Whenever a key is pressed, it generates KeyEvents, which are passed to the appropriate methods of the KeyListener interface.

-6pc

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;

public class PongFrame extends JFrame implements KeyListener {
     private Ball ball;
     private Paddle pad;

     public PongFrame() {
         setBackground(Color.white);
         addKeyListener(this);
         pad = new Paddle(this);  // Create the paddle
         ball = new Ball(this);      // Create the ball
         ball.start();
     } // PongFrame()

     public void paint (Graphics g ) {
          g.setColor(getBackground());   // Erase the drawing area
          g.fillRect(0,0,getWidth(),getHeight());

          g.setColor(Color.blue);       // Paint the ball
          g.fillOval(ball.getX(),ball.getY(),ball.SIZE,ball.SIZE);

          pad.resetLocation();          // Paint the paddle
          g.setColor(Color.red);
          g.fillRect(pad.getX(),pad.getY(),Paddle.WIDTH,Paddle.HEIGHT);
     } // paint()

      public boolean ballHitsPaddle() {
          return ball.getX() + Ball.SIZE >= pad.getX()
             && ball.getY() >= pad.getY()
             && ball.getY() <= pad.getY() + Paddle.HEIGHT;
     } // ballHitsPaddle()

     public void keyPressed( KeyEvent e) { // Check for arrow keys
         int keyCode = e.getKeyCode();
         if (keyCode == e.VK_UP)            // Up arrow
             pad.moveUp();
         else if (keyCode == e.VK_DOWN)     // Down arrow
             pad.moveDown();
     } // keyReleased()
     public void keyTyped(KeyEvent e) {}     // Unused
     public void keyReleased( KeyEvent e) {} // Unused
     public static void main(String[] args) {
       PongFrame f = new PongFrame();
       f.setSize(400,400);
       f.setVisible(true);
} // PongFrame

There’s a bit of redundancy in the KeyListener interface in the sense that a single key press and release generates three KeyEvents: A key-typed event, when the key is pressed, a key-released event, when the key is released, and a key-pressed event, when the key is pressed and released. While it is important for some programs to be able to distinguish between a key-typed and key-released event, for this program, we will take action whenever one of the arrow keys is pressed (typed and released). Therefore, we implement the keyPressed() method as follows:

public void keyPressed( KeyEvent e) { // Check arrow keys
   int keyCode = e.getKeyCode();
   if (keyCode == e.VK_UP)            // Up arrow
      pad.moveUp();
   else if (keyCode == e.VK_DOWN)     // Down arrow
      pad.moveDown();
} // keyReleased()

Each key on the keyboard has a unique code that identifies the key. The key’s code is gotten from the KeyEvent object by means of the getKeyCode() method. Then it is compared with the codes for the up-arrow and down-arrow keys, which are implemented as class constants, VK_UP and VK_DOWN, in the KeyEvent class. If either of those keys were typed, the appropriate paddle method, moveUP() or moveDown(), is called.

Note that even though we are not using the keyPressed() and keyReleased() methods in this program, it is still necessary to provide implementations for these methods in the frame. In order to implement an interface, such as the KeyListener interface, you must implement all the abstract methods in the interface. That is why we provide trivial implementations of both the keyPressed() and keyReleased() methods.

Animating the Bouncing Ball

Computer animation is accomplished by repeatedly drawing, erasing, and re-drawing an object at different locations on the drawing panel. The frame’s paint() method is used for drawing the ball and the paddle at their current locations. The paint() method is never called directly. Rather, it is called automatically after the constructor method PongFrame(), when the program is started. It is then invoked indirectly by the program by calling the repaint() method, which is called in the run() method of the Ball class. The reason that paint() is called indirectly is because Java needs to pass it the frame’s current Graphics object. Recall that in Java all drawing is done using a Graphics object.

In order to animate the bouncing ball, we first erase the current image of the ball, then we draw the ball in its new location. We also draw the paddle in its current location. These steps are carried out in the frame’s paint() method. First, the drawing area is cleared by painting its rectangle in the background color. Then the ball and paddle are painted at their current locations. Note that before painting the paddle, we first call its resetLocation() method. This causes the paddle to be relocated in case the user has resized the frame’s drawing area. There is no need to do this for the ball because the ball’s drawing area is updated within the Ball.move() method every time the ball is moved.

One problem with computer animations of this sort is that the repeated drawing and erasing of the drawing area can cause the screen to flicker. In some drawing environments a technique known as double buffering is used to reduce the flicker. In double buffering, an invisible, off-screen, buffer is used for the actual drawing operations and it is then used to replace the visible image all at once when the drawing is done. Fortunately, Java’s Swing components, including JApplet and JFrame, perform an automatic form of double buffering, so we needn’t worry about it. Some graphics environments, including Java’s AWT environment, do not perform double buffering automatically, in which case the program itself must carry it out.

Like the other examples in this chapter, the game of Pong provides a simple illustration of how threads are used to coordinate concurrent actions in a computer program. As most computer game fans will realize, most modern interactive computer games utilize a multithreaded design. The use of threads allows our interactive programs to achieve a responsiveness and sophistication that is not possible in single-threaded programs. One of the great advantages of Java is that it simplifies the use of threads, thereby making thread programming accessible to programmers. However, one of the lessons that should be drawn from this chapter is that multithreaded programs must be carefully designed in order to work effectively.

Modify the PongFrame program so that it contains a second ball that starts at a different location from the first ball.

asynchronous

blocked

busy waiting

concurrent

critical section

dispatched

fetch-execute cycle

lock

monitor

multitasking

multithreaded

mutual exclusion

priority scheduling

producer/consumer model

quantum

queue

ready queue

round-robin scheduling

scheduling algorithm

task

thread

thread life cycle

time slicing

=11.9pt

Multitasking is the technique of executing several tasks at the same time within a single program. In Java we give each task a separate thread of execution, thus resulting in a multithreaded program.

A sequential computer with a single central processing unit (CPU) can execute only one machine instruction at a time. A parallel computer uses multiple CPUs operating simultaneously to execute more than one instruction at a time.

Each CPU uses a fetch-execute cycle to retrieve the next machine instruction from memory and execute it. The cycle is under the control of the CPU’s internal clock, which typically runs at several hundred megahertz—where 1 megahertz (MHz) is 1 million cycles per second.

Time slicing is the technique whereby several threads can share a single CPU over a given time period. Each thread is given a small slice of the CPU’s time under the control of some kind of scheduling algorithm.

In round-robin scheduling, each thread is given an equal slice of time, in a first-come–first-served order. In priority scheduling, higher-priority threads are allowed to run before lower-priority threads are run.

There are generally two ways of creating threads in a program. One is to create a subclass of Thread and implement a run() method. The other is to create a Thread instance and pass it a Runnable object—that is, an object that implements run().

The sleep() method removes a thread from the CPU for a determinate length of time, giving other threads a chance to run.

The setPriority() method sets a thread’s priority. Higher-priority threads have more and longer access to the CPU.

Threads are asynchronous. Their timing and duration on the CPU are highly sporadic and unpredictable. In designing threaded programs, you must be careful not to base your algorithm on any assumptions about the threads’ timing.

To improve the responsiveness of interactive programs, you could give compute-intensive tasks, such as drawing lots of dots, to a lower-priority thread or to a thread that sleeps periodically.

A thread’s life cycle consists of ready, running, waiting, sleeping, and blocked states. Threads start in the ready state and are dispatched to the CPU by the scheduler, an operating system program. If a thread performs an I/O operation, it blocks until the I/O is completed. If it voluntarily sleeps, it gives up the CPU.

According to the producer/consumer model, two threads share a resource, one serving to produce the resource and the other to consume the resource. Their cooperation must be carefully synchronized.

An object that contains synchronized methods is known as a monitor. Such objects ensure that only one thread at a time can execute a synchronized method. The object is locked until the thread completes the method or voluntarily sleeps. This is one way to ensure mutually exclusive access to a resource by a collection of cooperating threads.

The synchronized qualifier can also be used to designate a method as a critical section, whose execution should not be preempted by one of the other cooperating threads.

In designing multithreaded programs, it is useful to assume that if a thread can be interrupted at a certain point, it will be interrupted there. Thread coordination should never be left to chance.

One way of coordinating two or more cooperating threads is to use the wait/notify combination. One thread waits for a resource to be available, and the other thread notifies when a resource becomes available.

public class PrintOdds implements Runnable {
  private int bound;
  public PrintOdds(int b) {
   bound = b;
  }

  public void print() {
    if (int k = 1; k < bound; k+=2)
      System.out.println(k);
  }

  public void run() {
    print();
  }
}

On my system, the experiment yielded the following output, if each thread printed its number after every 100,000 iterations:

1111112222222211111111333333322222221111113333333
222224444444433333344444445555555544444555555555555

This suggests that round-robin scheduling is being used.

If each thread is given 50 milliseconds of sleep on each iteration, they tend to run in the order in which they were created:

123451234512345...

The garbage collector runs whenever the available memory drops below a certain threshold. It must have higher priority than the application, since the application won’t be able to run if it runs out of memory.

To improve the responsiveness of an interactive program, the system could give a high priority to the threads that interact with the user and a low priority to those that perform noninteractive computations, such as number crunching.

If the JVM were single threaded, it wouldn’t be possible to break out of an infinite loop, because the program’s loop would completely consume the CPU’s attention.

If round-robin scheduling is used, each thread will be get a portion of the CPU’s time, so the GUI thread will eventually get its turn. But you don’t know how long it will be before the GUI gets its turn, so there might still be an unacceptably long wait before the user’s actions are handled. Thus, to guarantee responsiveness, it is better to have the drawing thread sleep on every iteration.

If Dotty’s priority is set to 1, a low value, this does improve the responsiveness of the interface, but it is significantly less responsive than using a sleep() on each iteration.

In a real bakery only one customer at a time can take a number. The take-a-number gadget “enforces” mutual exclusion by virtue of its design: There’s room for only one hand to grab the ticket and there’s only one ticket per number. If two customers got “bakery rage” and managed to grab the same ticket, it would rip in half and neither would benefit.

One experiment to run would be to make the clerk’s performance very slow by using large sleep intervals. If the algorithm is correct, this should not affect the order in which customers are served. Another experiment would be to force the clerk to work fast but the customers to work slowly. This should still not affect the order in which the customers are served.

You should observe that the waiting line builds up as customers enter the bakery, but the clerk should still serve the customers in the correct order.

A two-ball version of Pong would require the following changes to the original version:

1. A new Ball() constructor that has parameters to set the initial location and direction of the ball.
2. The PongFrame should create a new Ball instance, start it, and draw it.

Explain the difference between the following pairs of terms:

2

Blocked and ready.

Priority and round-robin scheduling.

Producer and consumer.

Monitor and lock.

Concurrent and time slicing.

Mutual exclusion and critical section.

Busy and nonbusy waiting.

Fill in the blanks.

=12pt

---

happens when a CPU’s time is divided among several different threads.

A method that should not be interrupted during its execution is known as a

---

 .

The scheduling algorithm in which each thread gets an equal portion of the CPU’s time is known as

---

 .

The scheduling algorithm in which some threads can preempt other threads is known as

---

.

A

---

is a mechanism that enforces mutually exclusive access to a synchronized method.

A thread that performs an I/O operation may be forced into the

---

state until the operation is completed.

=11pt

Describe the concept of time slicing as it applies to CPU

What’s the difference in the way concurrent threads would be implemented on a computer with several processors and on a computer with a single processor?

Why are threads put into the blocked state when they perform an I/O operation?

What’s the difference between a thread in the sleep state and a thread in the ready state?

Deadlock is a situation that occurs when one thread is holding a resource that another thread is waiting for, while the other thread is holding a resource that the first thread is waiting for. Describe how deadlock can occur at a four-way intersection with cars entering from each branch. How can it be avoided?

Starvation can occur if one thread is repeatedly preempted by other threads. Describe how starvation can occur at a four-way intersection and how it can be avoided.

Use the Runnable interface to define a thread that repeatedly generates random numbers in the interval 2 through 12.

Create a version of the Bakery program that uses two clerks to serve customers.

Modify the Numbers program so that the user can interactively create NumberThreads and assign them a priority. Modify the NumberThreads so that they print their numbers indefinitely (rather than for a fixed number of iterations). Then experiment with the system by observing the effect of introducing threads with the same, lower, or higher priority. How do the threads behave when they all have the same priority? What happens when you introduce a higher-priority thread into the mix? What happens when you introduce a lower-priority thread into the mix?

Create a bouncing ball simulation in which a single ball (thread) bounces up and down in a vertical line. The ball should bounce off the bottom and top of the enclosing frame.

Modify the simulation in the previous exercise so that more than one ball can be introduced. Allow the user to introduce new balls into the simulation by pressing the space bar or clicking the mouse.

Modify your solution to the previous problem by having the balls bounce off the wall at a random angle.

Challenge: One type of producer/consumer problem is the reader/writer problem. Create a subclass of JTextField that can be shared by threads, one of which writes a random number to the text field, and the other of which reads the value in the text field. Coordinate the two threads so that the overall effect of the program will be to print the values from 0 to 100 in the proper order. In other words, the reader thread shouldn’t read a value from the text field until there’s a value to be read. The writer thread shouldn’t write a value to the text field until the reader has read the previous value.

Challenge: Create a streaming banner thread that moves a simple message across a panel. The message should repeatedly enter at the left edge of the panel and exit from the right edge. Design the banner as a subclass of JPanel and have it implement the Runnable interface. That way it can be added to any user interface. One of its constructors should take a String argument that lets the user set the banner’s message.

Challenge: Create a slide show program, which repeatedly cycles through an array of images. The action of displaying the images should be a separate thread. The frame thread should handle the user interface. Give the user some controls that let it pause, stop, start, speed up, and slow down the images.

Challenge: Create a horse race simulation, using separate threads for each of the horses. The horses should race horizontally across the screen, with each horse having a different vertical coordinate. If you don’t have good horse images to use, just make each horse a colored polygon or some other shape. Have the horses implement the Drawable interface, which we introduced in Chapter chapter-inheritance.

Challenge: Create a multithreaded digital clock application. One thread should keep time in an endless while loop. The other thread should be responsible for updating the screen each second.