|
| |
A Game of TicTacToe
In this assignment, we'll be building a game of TicTacToe
NOTE: TicTacToe is the American name for this game. The British call it
Noughts
and Crosses, which makes much more sense.
Introduction
The game of TicTacToe is very simple: You have a board of
three by three squares, which starts out empty. There are two
players: one is designated as X and the other is designated
as O. Each player takes turns placing and X or an O
(depending on the player designation) in one of the
unoccupied squares. Once a player has placed an X or an O in
a square, it may not be changed.
The goal of the game is to place a line of three Xs (or
three Os) in a straight line, horizontally,
vertically, or diagonally. Whichever of the two players does
this first wins the game.
Here's my implementation, in the form of an applet:
Click here to see a live applet (I'm using Swing, so
the applet uses the Java PlugIn, and that might cause your browser
problems. For this reason, I'm moving the applet to a separate page.)
| In case your browser can't handle the above applet, here's an
image of what it should look like:
The above is merely an image; don't try to
click on it to get it work!
|
As you can see, this applet actually has two boards, one
for each player. The board on the left is the player X's board,
while the board on the right is O's. Either player can make the
first move by clicking the mouse in one of his/her squares.
Players must alternate between the two boards -- clicking on the left board causes an X to be placed in the
appropriate square of X's board, while clicking on the right board causes
an O to be placed in the appropriate square of O's board. If you click
twice on the same board, the second click is ignored, until
the other player makes his/her move. Clicking on an already
occupied square has no effect.
If you play the game, you'll see that both boards are
updated whenever either player makes a move. You can also
click on the Restart button to clear the
boards and start from the beginning. Finally, the AutoPlay
button tells the applet to play itself (I introduced a delay
between moves here to slow things down to human speed, so you
can see what's happening.). If the game is already in progress, AutoPlay
will continue the game; if it is not started, then AutoPlay
will play the game from the beginning; If the game is already
completed, AutoPlay will clear the board first, and then start from
the beginning. When you click on AutoPlay, it disables
the Restart button until the game is complete, and then re-enables
it.
So the goal of the assignment is to produce the code to do
this. However, don't panic!
- I'll provide you with the code that implements
the algorithm for the game
- I'll provide a specification for how I want you
to construct it. (It won't be constructed in the most
obvious way, because we'll be using it in
later assignments to explore other aspects of Java.)
Requirements and Design
Let's look at how we might construct such a game. First,
let's look at the requirements:
NOTE: We eventually will want to be able to
play the game in an environment where the players may be
physically separated from each other. For example, over
the Internet, perhaps in a browser on each player's
machine. Each player would then have his/her own board
displayed on his/her computer screen.
A simple object-oriented analysis comes up with some
possible classes:
- Game -- This class will maintain the
game state, and provide the algorithms and logic
necessary to enforce the rules of the game. There
will be exactly one instance of this class per game.
- Board -- Each board should provide a
mechanism for its player to see the state of the
game, by displaying the appropriate set of X's and
O's. There will be at least two instances of this
class per game -- one per player.
We also need some way for the Game and the two Boards to
communicate with each other:
- Each player would like to be able to click on his/her
board to indicate a move. This involves some way of
telling the Game that the player wishes to make a
move, and specifying what square was chosen.
- The game needs to communicate with the Boards so that
they can keep their displays up to date with the game
state.
- It is possible that there may be a need for other
classes to be able to keep track of game play. For
example, perhaps we may require some games to be
observed by a Referee, to ensure that proper decorum
is maintained, or a Kibitzer, who might be a
TicTacToe groupie, and can't resist observing
TicTacToe masters in important matches. (I don't want you to
actually do this -- just write the code to allow for this in the
future.)
A standard mechanism to allow
multiple class instances to be kept informed of certain
actions is to use an e of the appropriate type. The javax.swing.event
package contains a convenient class called EventListenerList
which we'll use to handle the adding and removing of listeners, and to call the
appropriate listeners' methods when certain GameEvents
occur.
- GameEvent -- a class to represent
any one of several possible game events.
- GameListener -- an interface that
specifies what methods a listener for game events
must implement.
- GameAdapter -- a class that
implements trivial (do nothing) methods for a GameListener.
Implementation
Now, for reasons that will become clearer later in
the course, I decided that Game
should actually be an interface. Here it is, in all its
glory:
package tictactoe;
/**
* Interface to a TicTacToe game.
*
* @author Bryan J. Higgs, 9-Jan-2000
*/
public interface Game
{
/**
* The possible game states:
* <br>IN_PROGRESS -- game in progress
* <br>WIN -- nought won
* <br>LOSE -- cross won
* <br>STALEMATE -- a draw
*/
public static final int INACTIVE = -1;
public static final int IN_PROGRESS = 0;
public static final int WIN = 1;
public static final int LOSE = 2;
public static final int STALEMATE = 3;
/**
* Cross's move.
* @param row the row number of the square (0 to 2)
* @param col the col number of the square (0 to 2)
* @return true if legal move
*/
public boolean crossMove(int row, int col);
/**
* Nought's move.
* @param row the row number of the square (0 to 2)
* @param col the col number of the square (0 to 2)
* @return true if legal move
*/
public boolean noughtMove(int row, int col);
/**
* Automatically plays a game.
*/
public void autoPlay();
/**
* Figure out what the status of the game is.
*
* @return WON if nought has won; LOSE if cross has won;
* STALEMATE if game ended in a stalemate;
* IN_PROGRESS otherwise (still in progress).
*/
public int getStatus();
/**
* Restarts the game.
*/
public void restart();
/**
* Adds the specified game listener to receive game events from
* this game.
* @param l the game listener.
*/
public void addGameListener(GameListener l);
/**
* Removes the specified game listener so that it no longer
* receives game events from this game.
* @param l the game listener.
*/
public void removeGameListener(GameListener l);
} |
As promised, I'll provide the implementation of the
TicTacToe game, GameImpl (which, of course, implements interface Game). Here is the
code for GameImpl:
package tictactoe;
import java.awt.AWTEvent;
import java.awt.Component;
import java.awt.EventQueue;
import java.awt.Toolkit;
import java.awt.event.MouseEvent;
import javax.swing.event.EventListenerList;
/**
* Class to implement a TicTacToe game.
* <p>
* This class represents just the game play; the representation of
* the board(s) is elsewhere.
* <p>
* Algorithm from the TicTacToe game written by Arthur van Hoff.
*
* @author Bryan J. Higgs, 9-Jan-2000, modified 3-Feb-2007
*/
public class GameImpl
extends Component // So it can be used as the source for AWTEvents
implements Game,
Runnable // So it can support the autoplay in a thread
{
public GameImpl()
{
enableEvents(0); // Ensure that the event queue delivers GameEvents
}
/**
* Cross's move.
* @param row the row number of the square (0-2)
* @param col the col number of the square (0-2)
* @return true if legal move
*/
public boolean crossMove(int row, int col)
{
if (m_crossNext == null)
m_crossNext = new Boolean(true); // First move
if (!m_crossNext.booleanValue())
return false; // Not cross's turn
boolean legal = true;
int move = col + row * 3; // Convert to internal representation
if ((move < 0) || (move > 8))
{
legal = false; // Out of range
}
else if (((m_cross | m_nought) & (1 << move)) != 0)
{
legal = false; // Position already occupied
}
if (legal)
{
m_cross |= 1 << move; // Set the bit for this move
// Tell all the GameListeners that a cross in now in that square
postGameEvent( new GameEvent(this, GameEvent.CROSS_IN_SQUARE, row, col) );
// If Cross won, tell all the GameListeners
if (won[m_cross])
postGameEvent( new GameEvent(this, GameEvent.CROSS_WINS) );
legal = true;
}
if (legal)
m_crossNext = new Boolean(false);
if (STALEMATE == getStatus())
postGameEvent( new GameEvent(this, GameEvent.STALEMATE) );
return legal;
}
/**
* Nought's move.
* @param row the row number of the square (0-2)
* @param col the col number of the square (0-2)
* @return true if legal move
*/
public boolean noughtMove(int row, int col)
{
if (m_crossNext == null)
m_crossNext = new Boolean(false); // First move
if (m_crossNext.booleanValue())
return false; // Not nought's turn
boolean legal = true;
int move = col + row * 3; // Convert to internal representation
if ((move < 0) || (move > 8))
{
legal = false; // Out of range
}
else if (((m_cross | m_nought) & (1 << move)) != 0)
{
legal = false; // Position already occupied
}
if (legal)
{
m_nought |= 1 << move; // Set the bit for this move
// Tell all the GameListeners that a cross in now in that square
postGameEvent( new GameEvent(this, GameEvent.NOUGHT_IN_SQUARE, row, col) );
// If Cross won, tell all the GameListeners
if (won[m_nought])
postGameEvent( new GameEvent(this, GameEvent.NOUGHT_WINS) );
legal = true;
}
if (legal)
m_crossNext = new Boolean(true);
if (STALEMATE == getStatus())
postGameEvent( new GameEvent(this, GameEvent.STALEMATE) );
return legal;
}
/**
* Automatically plays a game.
*/
public void autoPlay()
{
// Don't do more than one autoplay at a time
if (m_autoPlayThread == null)
{
// We need to do this in a separate thread, to ensure there are
// no conflicts with the AWT event thread. (Otherwise, all the
// moves will only be shown at the very end of the game.)
m_autoPlayThread = new Thread(this, "AutoPlay");
m_autoPlayThread.start();
}
}
/**
* Autoplay the game in a separate thread.
*/
public void run()
{
// Abritrarily start with cross first
if (m_crossNext == null)
m_crossNext = new Boolean(true);
// If the game is not in progress, restart the game to clear the board
if (getStatus() != IN_PROGRESS)
{
synchronized (this)
{
restart();
// Wait for status to change to IN_PROGRESS
while (getStatus() != IN_PROGRESS)
{
try
{
wait();
}
catch (InterruptedException ie)
{
// Do nothing
}
}
// Ensure that we know whose move it is.
if (m_crossNext == null)
m_crossNext = new Boolean(true); // First move
}
}
while (getStatus() == IN_PROGRESS)
{
computedMove();
// Sleep a while to slow things down to human timescales
try
{
Thread.sleep(500);
}
catch(InterruptedException e)
{
}
}
m_autoPlayThread = null;
}
/**
* Return the status of the game.
*
* @return WON if nought has won;
* LOSE if cross has won;
* STALEMATE if game ended in a stalemate;
* IN_PROGRESS otherwise (still in progress).
*/
public int getStatus()
{
if (won[m_nought])
{
return WIN;
}
if (won[m_cross])
{
return LOSE;
}
if ((m_cross | m_nought) == DONE)
{
return STALEMATE;
}
return IN_PROGRESS;
}
/**
* Restarts the game.
*/
public void restart()
{
m_nought = m_cross = 0;
m_crossNext = null;
// Inform all the GameListeners
postGameEvent( new GameEvent(this, GameEvent.CLEAR_BOARD) );
}
/**
* Adds the specified game listener to receive game events from
* this game.
* @param listener the game listener.
*/
public synchronized void addGameListener(GameListener listener)
{
m_listenerList.add(GameListener.class, listener);
}
/**
* Removes the specified game listener so that it no longer
* receives game events from this game.
* @param listener the game listener.
*/
public synchronized void removeGameListener(GameListener listener)
{
m_listenerList.remove(GameListener.class, listener);
}
/**
* Processes AWTEvents occurring on this component.
* This method detects GameEvents and passes them on to processGameEvent();
* For all other events, it delegates to the superclass' processEvent().
* @param event the event.
*/
protected void processEvent(AWTEvent event)
{
if (event instanceof GameEvent)
processGameEvent((GameEvent)event);
else
super.processEvent(event);
}
/**
* Processes game events occurring on this component.
* Dispatches to the appropriate method in the GameListener(s).
* @param event the event.
*/
private void processGameEvent(GameEvent event)
{
// Guaranteed to return a non-null array
GameListener[] listeners = m_listenerList.getListeners(GameListener.class);
// Process all the listeners, notifying them at the appropriate
// entry point for this event.
for (GameListener listener : listeners) // Java 1.5 specific foreach loop
{
switch(event.getID())
{
case GameEvent.CROSS_IN_SQUARE:
listener.crossInSquare(event.getRow(), event.getColumn());
break;
case GameEvent.NOUGHT_IN_SQUARE:
listener.noughtInSquare(event.getRow(), event.getColumn());
break;
case GameEvent.CROSS_WINS:
listener.crossWins();
break;
case GameEvent.NOUGHT_WINS:
listener.noughtWins();
break;
case GameEvent.STALEMATE:
listener.stalemate();
break;
case GameEvent.CLEAR_BOARD:
listener.clearBoard();
synchronized (this)
{
notify(); // Notify any waiting autoplay thread
}
break;
}
}
}
/**
* Posts a GameEvent to the system event queue.
* @param event the GameEvent
*/
private void postGameEvent(GameEvent event)
{
dispatchEvent(event);
}
/**
* Computes a "best" move for the next player.
* @return true if legal move
*/
private boolean computedMove()
{
if ((m_cross | m_nought) == DONE)
{
return false; // All squares occupied
}
boolean ret = false;
// Find best move for next player
if (m_crossNext.booleanValue())
{
int best = bestMove(m_cross, m_nought);
ret = crossMove(best/3, best%3);
}
else
{
int best = bestMove(m_nought, m_cross);
ret = noughtMove(best/3, best%3);
}
return ret;
}
/**
* Mark all positions with these bits set as winning.
*/
private static void isWon(int pos)
{
for (int i = 0 ; i < DONE ; i++)
{
if ((i & pos) == pos)
{
won[i] = true;
}
}
}
/**
* Compute the best move for white.
* @return the square to take
*/
private int bestMove(int white, int black)
{
int bestmove = -1;
loop:
for (int i = 0 ; i < 9 ; i++)
{
int mw = moves[i];
if (((white & (1 << mw)) == 0) && ((black & (1 << mw)) == 0))
{
int pw = white | (1 << mw);
if (won[pw])
{
// white wins, take it!
return mw;
}
for (int mb = 0 ; mb < 9 ; mb++)
{
if (((pw & (1 << mb)) == 0) && ((black & (1 << mb)) == 0))
{
int pb = black | (1 << mb);
if (won[pb])
{
// black wins, take another
continue loop;
}
}
}
// Neither white nor black can win in one move, this will do.
if (bestmove == -1)
{
bestmove = mw;
}
}
}
if (bestmove != -1)
{
return bestmove;
}
// No move is totally satisfactory, try the first one that is open
for (int i = 0 ; i < 9 ; i++)
{
int mw = moves[i];
if (((white & (1 << mw)) == 0) && ((black & (1 << mw)) == 0))
{
return mw;
}
}
// No more moves
return -1;
}
/////////// Private Data ////////////////
/**
* The winning positions.
*/
private static boolean won[] = new boolean[1 << 9];
private static final int DONE = (1 << 9) - 1;
/**
* Initialize all winning positions.
* NOTE: This must follow the above two definitions.
*/
static
{
isWon((1 << 0) | (1 << 1) | (1 << 2));
isWon((1 << 3) | (1 << 4) | (1 << 5));
isWon((1 << 6) | (1 << 7) | (1 << 8));
isWon((1 << 0) | (1 << 3) | (1 << 6));
isWon((1 << 1) | (1 << 4) | (1 << 7));
isWon((1 << 2) | (1 << 5) | (1 << 8));
isWon((1 << 0) | (1 << 4) | (1 << 8));
isWon((1 << 2) | (1 << 4) | (1 << 6));
}
/**
* Nought's current positions.
*/
private int m_nought;
/**
* Cross's current positions.
*/
private int m_cross;
/**
* Next to move.
* <p>
* true means cross is next; false means nought is next
* null means the first to call decides.
*/
private Boolean m_crossNext = null;
/**
* The squares in order of importance...
*/
private final static int moves[] = {4, 0, 2, 6, 8, 1, 3, 5, 7};
/**
* The autoPlayThread (when active)
*/
private Thread m_autoPlayThread = null;
/**
* The event listener list.
* <p>
* This is used as a convenience class, so we can add and remove
* listeners and invoke those listeners when an appropriate event occurs.
*/
private EventListenerList m_listenerList = new EventListenerList();
}
|
I'll even be really generous, and throw in the GameEvent class:
package tictactoe;
import java.awt.AWTEvent;
import java.awt.Component;
/**
* Class GameEvent. Provides a set of custom game events for TicTacToe.
*
* @author Bryan J. Higgs, 12 Jan 2000
*/
public class GameEvent
extends AWTEvent
{
public static final int GAME_EVENT_FIRST = AWTEvent.RESERVED_ID_MAX + 1;
public static final int CROSS_IN_SQUARE = GAME_EVENT_FIRST;
public static final int NOUGHT_IN_SQUARE= GAME_EVENT_FIRST + 1;
public static final int CROSS_WINS = GAME_EVENT_FIRST + 2;
public static final int NOUGHT_WINS = GAME_EVENT_FIRST + 3;
public static final int STALEMATE = GAME_EVENT_FIRST + 4;
public static final int CLEAR_BOARD = GAME_EVENT_FIRST + 5;
public static final int PLAYS_CROSS = GAME_EVENT_FIRST + 6;
public static final int PLAYS_NOUGHT = GAME_EVENT_FIRST + 7;
public static final int GAME_EVENT_LAST = PLAYS_NOUGHT;
/**
* Constructs a GameEvent instance.
* @param source the source of the event.
* @param id the event id.
*/
public GameEvent(Component source, int id)
{
this(source, id, -1, -1);
}
/**
* Constructs a GameEvent instance.
* @param source the source of the event.
* @param id the event id.
* @param squareRow the row number of the square
* @param squareCol the column number of the square
*/
public GameEvent(Component source, int id, int squareRow, int squareCol)
{
super(source, id);
m_row = squareRow;
m_col = squareCol;
}
/**
* Gets the row number of the square.
* @return the row number of the square.
*/
public int getRow()
{
return m_row;
}
/**
* Gets the column number of the square.
* @return the column number of the square.
*/
public int getColumn()
{
return m_col;
}
///// Private data ////
/**
* The row and column numbers of the square.
*/
private int m_row = -1, m_col = -1;
} |
and even the GameListener
interface:
package tictactoe;
import java.util.EventListener;
/**
* Interface GameListener.
*
* @author Bryan J. Higgs, 12 Jan 2000
*/
public interface GameListener
extends EventListener
{
/**
* Called when the Game determines that a cross has been added to a square.
* @param row the row number of the square
* @param col the column number of the square
*/
public void crossInSquare(int row, int col);
/**
* Called when the Game determines that a nought has been added to a square.
* @param row the row number of the square
* @param col the column number of the square
*/
public void noughtInSquare(int row, int col);
/**
* Called when the Game determines that cross has won the game.
*/
public void crossWins();
/**
* Called when the Game determines that nought has won the game.
*/
public void noughtWins();
/**
* Called when the Game ends in a stalemate.
*/
public void stalemate();
/**
* Called when the Game determines that the board needs to be cleared.
*/
public void clearBoard();
/**
* Called when the Game determines that this player plays cross
*/
public void playsCross();
/**
* Called when the Game determines that this player plays nought.
*/
public void playsNought();
} |
What to do for the assignment
So what's left for you to do? PLENTY! Here's what you will
need to do:
Create a project in your Java IDE, and then add the above classes
into the project (Simply copy and
paste them from this web page.)
Create the remaining class to support GameEvents
- GameAdapter -- a
convenience class that implements GameListener,
and provides empty method implementations (i.e. methods with empty bodies)
for all the methods specified by GameListener.
This class may be used as a superclass for a class that wishes to
implement the GameListenerinterface, but
only wishes to provide implementations for a subset of the methods
specified in GameListener. The class
would then only need to implement those methods it needs by overriding
those methods from the GameAdapter class.
Note:
You may find that you don't actually use GameAdapter
in this assignment. However, you should create it
anyway. Think of yourself as being the provider of a
TicTacToe game service; you may not need to use this class,
but others might (or you yourself might use it in a
later project). (Note that I did use GameAdapter in my applet,
above!)
Create the Board class
The Board
class should be declared something like:
package tictactoe:
public class Board
extends JPanel
implements GameListener
{
// ...
}
It should have the following constructor:
/**
* Constructs a Board, and associates it with a Game.
* @param game the game to associate with the board.
* @param noughtImage the image for nought
* @param crossImage the image for cross
*/
public Board(Game game, Image noughtImage, Image crossImage)
{
// ...
}
Note: Board should only know about
Game,
not GameImpl. That's
why I'm specifying the Board constructor to accept a parameter of type
Game. You'll most likely store a reference to this
Game inside Board
-- do not make it a reference to GameImpl!
Here are some tips/suggestions, based on my
implementation:
- I implemented an inner class, Square, to handle each
square on the board separately. Each Square
took care
of mouse clicks inside itself, and called a common method in the
enclosing Board class when it received a click.
- I had the Board instance contain a 2-dimensional
array of Squares, to represent the board squares
- Inside the Board class, placed a JTextField below the board to contain
messages such as "Cross wins!", etc.
- I used GridLayout to lay out the squares in the board panel. I used a
GridLayout hgap and vgap, with a
panel background of black and a square background of
white to cause the black lines to appear, rather than
having to draw them explicitly.
- Naturally, since Board implements GameListener, it
must implement each of the GameListener
methods.
Certain events would cause the text in the text field
below the board to change to indicate something like
"Nought wins!" or "Stalemate!".
- Other
events would cause the appropriate Square to display
an X image or a O image. Here are some images to use:
 |
 |
(You can usually right click
on these images in the browser and extract
them to your machine; consult your browser
help for details.) |
Note: If you're writing an
application (which I strongly recommend you do, rather than
trying to write applets), you can load
an image using the createImage() or getImage() methods in the
java.awt.Toolkit class. There is a getDefaultToolkit() static
method in the Toolkit class which you use instead of trying to
create an instance of the Toolkit class yourself.
I recommend that you do this using a URL relative to the class loading
the images. Then, you can place your images in a known location
relative to the class, rather than have to hardcode the filename.
This has the additional advantage that IDEs (like NetBeans) that create
.jar files will place the images in the.jar file, so that everything you
need is within that .jar file. Just create a subfolder under the
src folder (not the classes folder) and place your image files in that
folder.
- Note that there is only a need to load a single
instance of each of these images; you can simply
reference them from wherever you need to in your
program in order to display them. Your paintComponent()
method in the Square class can draw the image conditionally, depending
on whether it's been set.
- I found it useful to implement getPreferredSize()
in the Square class, so that it "naturally"
sized itself to the size of an image. Alternatively, you can call setPreferredSize().
Then you can
use pack()
at the the appropriate time to size things appropriately. (Note: pack()
probably won't help in an applet.)
- I'll leave it up to you how you want to implement the
layout, but you'll find that you have to use
nested layout managers.
- If you use the Square class approach, you should not
need to implement the paintComponent() method for the
Board class (but you will for the Square
class, of course).
Create a TestTicTacToe class to put it all
together
Having done the layout of the Board,
you'll then need to create a class TestTicTacToe
(or some similar name) to pull everything together. In my
implementation, I had one instance of GameImpl, and two
instances of Board,
one specifying that it was playing X,
and the other playing O --
note the playsCross() and playsNought() methods.
I laid these out, together with the two buttons, and the images indicating which Board
was which.
If you do things right here, all this class should need to
do is to instantiate the GameImpl,
create the two Boards, the two buttons, lay them out, and set up an action
listener for each button for it to do the proper thing. The
behavior of each Board
should be totally transparent to the test program.
I strongly recommend that you do this in a Java application, rather
than a Java applet.
Note: You'll
probably find that you won't be able to implement the above items in strict order,
because you'll need to implement
a test program to test out what you have, and then
augment the test program as you add functionality.
Also, the Board class will depend on the
GameEvent
classes, etc.
Do NOT try to implement everything in one go!
Instead, incrementally add features, and test as you
go.
See here
for what I expect to see for submission of this assignment.
|
