Java Games tutorial #4
In this section, we're going to write the code that allows the computer player to place its ships. Since this involves the computer making decisions, it's technically "artificial intelligence" code. You had no idea you'd be getting into such advanced topics so quickly, did you?
To be honest, the code isn't going to be that smart (after all, this is the first time we've ever done any game AI, so we shouldn't expect genius-level results right away). Basically, the computer is going to randomly pick a space on the board and an orientation for each ship in turn. If the ship can fit onto the board at that point, great--we'll use that space. Otherwise, we'll pick a new point and try again.
Let's go ahead and write a code outline based on the ideas we've covered so far. After that, we'll turn the outline into full-on game code.
Making a List, Checking it Twice When we summarize the computer's ship-placement algorithm into a list of steps, we get something like this:
The first couple of steps are pretty tame (don't worry about the "random" stuff--we'll cover that in a minute), so let's skip right to step number 3: "Test to see if the ship can fit on the board given the current row, column, and orientation". How will that work, exactly?
Given a position on the grid and an orientation, there are two ways a ship can fail to fit onto the board. First, there might not be enough cells to hold the ship. For instance, suppose you try to put the battleship in cell (0, 0) with an orientation of "up" (see figure 5).
Figure 5--Placing the battleship in a bad position.
Second, a ship might "collide" with another ship that's already on the board (see figure 6).
Figure 6--Collision between the carrier (gray) and battleship (green).
Assuming we can detect these cases, we should be able to write the computer placement code fairly easily.
Do Do that Voodoo that You Do Let's start writing code. We'll use the outline above to create a skeleton of a method called placeComputerShips in Board.java (cyan comments make places where we'll be inserting code a little later on): public void placeComputerShips() {
int i = 0;
do {
int row;
int col;
int orientation;
// Randomly generate a row, column, and
// orientation.
boolean bFitsOnBoard = false;
// Check to see if the ship fits on the
// board at the given row and column.
boolean bHitsOtherShips = false;
// Check to see if the ship hits any
// other ships on the board.
if ((bFitsOnBoard == true) &&
(bHitsOtherShips == false)) {
// Place this ship on the board.
// Go on to the next ship.
i++;
}
} while (i < SHIPS_PER_FLEET);
}
Before we write more code, consider what we have so far. Look carefully at the structure of this do loop--notice how we increment i only if the ship fits on the board and doesn't hit other ships. That's a very important concept. If the ship doesn't fit on the board or it collides with another ship, we execute the loop without changing the value of i. In other words, we choose a second random row, column and orientation for the current ship and check to see if the piece can fit on the board. We keep repeating this process over and over until the ship fits, at which point we increment i and go on to the next ship.
Time to move on. Let's start replacing the cyan sections.
Eenie, Meenie, Minie, Moe Somehow, we have to generate random values for the row, column, and orientation of the computer's ships. Fortunately, Java provides a means to do this. We need to use the Random class, found in the util package. This means we'll have to add an import statement in order to use it:
import java.util.*;
Before we start using the Random class, there are a few new concepts we need to cover. First off, there is no such thing as a "random number" on a computer. Java, like all languages, uses a "pseudo-random number generator" to create series of seemingly random numbers. You can think of it like this: somewhere, deep inside Java, is a piece of software that spits out a series of numbers:
1, 12, -77, 32, 109, 0, 0, -2, -2, 45, ...
When you ask for a random number, Java gives you the next one in the series. You can pass special parameters to affect which one it gives you next, but, at its core, the series is always the same.
This means that, if you start Java 15 times using exactly the same initial conditions, you'll get the same series of numbers out of Random every time.
Generally, that's not the behavior we want from a "random" number generator.
To get around this, Random understands the idea of a "seed". The seed is a number you can pass to Random that controls where in the series you start reading. If you pass in different seeds, you start at different points in the series and receive different numbers.
I can already hear you saying, "But wait! If we use the same seed every time, we'll still get identical series out. Somehow, we need to use a random number for the seed--but if we could generate a truly random number for the seed, we wouldn't need the seed in the first place!"
True enough. Fortunately, we have a way of generating a truly random seed--we can use the current local time. That way, if the user has been on her computer for 15 minutes before starting battleship, she'll get different results than she would if she'd been on for 14.9 minutes, or 2 hours, or 3 seconds.
So much for the theory of random number generators--let's look at how to use them.
public void placeComputerShips() {
long seed = System.currentTimeMillis();
Random randomizer = new Random(seed);
int i = 0;
do {
int row;
int col;
int orientation;
// Randomly generate a row, column, and
// orientation.
row = randomizer.nextInt(ROW_COUNT);
col = randomizer.nextInt(COLUMN_COUNT);
orientation = randomizer.nextInt(4);
boolean bFitsOnBoard = false;
// Check to see if the ship fits on the
// board at the given row and column.
boolean bHitsOtherShips = false;
// Check to see if the ship hits any
// other ships on the board.
if (bFitsOnBoard && !bHitsOtherShips) {
// Place this ship on the board.
// Go on to the next ship.
i++;
}
} while (i < SHIPS_PER_FLEET);
}
The yellow code demonstrates the use of the Random class. This line:
long
seed = System.currentTimeMillis(); just gets the current system time in milliseconds (1/1000ths of a second) and stores it in the variable seed. The long data type is just like int except that it can hold much larger numbers.
This line:
Random
randomizer = new Random(seed); creates a new instance of Random and stores it in the container called randomizer. By passing the seed into the constructor, we're ensuring that we start at different places in the random number series every time we play the game.
The real meat of the random number creation rests here:
row
= randomizer.nextInt(ROW_COUNT);
where we use Random to generate arbitrary rows, columns, and orientations. In particular, we're using the nextInt method to retrieve the next integer value in the random number series. The integer value we pass in to nextInt tells Java that we want numbers between 0 and the value minus 1. For instance,
orientation
= randomizer.nextInt(4);
will generate values from 0 to 3.
Why did we pick that value for our orientation? Look back at Ship.java, where we defined the orientation constants: public static final int ORIENTATION_UP = 0;
public static final int ORIENTATION_RIGHT = 1;
public static final int ORIENTATION_DOWN = 2;
public static final int ORIENTATION_LEFT = 3;
So you can see that we're really generating ORIENTATION_UP, ORIENTATION_RIGHT, ORIENTATION_DOWN, or ORIENTATION_LEFT.
It should be pretty easy to figure out what these lines do:
row
= randomizer.nextInt(ROW_COUNT);
That takes care of the random numbers. Go ahead and compile, just to make sure you haven't made any obvious mistakes. Don't run the program, though--right now we have an infinite loop in our logic (can you find it?).
Now, how can we check to see if the ship fits on the board?
One Size Fits All Fortunately, the code that checks if the ship fits the board isn't too difficult. Here's the new placeComputerShips method with that code (and a little extra) in place:
public void placeComputerShips() {
long seed = System.currentTimeMillis();
Random randomizer = new Random(seed);
int [] shipType = {Ship.TYPE_AIRCRAFT_CARRIER,
Ship.TYPE_BATTLESHIP,
Ship.TYPE_CRUISER,
Ship.TYPE_SUBMARINE,
Ship.TYPE_PT_BOAT};
int[] shipLength = {5, 4, 3, 3, 2};
int i = 0;
do {
int row;
int col;
int orientation;
// Randomly generate a row, column, and
// orientation.
row = randomizer.nextInt(ROW_COUNT);
col = randomizer.nextInt(COLUMN_COUNT);
orientation = randomizer.nextInt(4);
boolean bFitsOnBoard = false;
// Check to see if the ship fits on the
// board at the given row and column.
int testLength = shipLength[i] - 1;
if (orientation == Ship.ORIENTATION_UP) {
if (row >= testLength) {
bFitsOnBoard = true;
}
}
else if (orientation == Ship.ORIENTATION_RIGHT) {
if (COLUMN_COUNT - col > testLength) {
bFitsOnBoard = true;
}
}
else if (orientation == Ship.ORIENTATION_DOWN) {
if (ROW_COUNT - row > testLength) {
bFitsOnBoard = true;
}
}
else if (orientation == Ship.ORIENTATION_LEFT) {
if (col >= testLength) {
bFitsOnBoard = true;
}
}
boolean bHitsOtherShips = false;
// Check to see if the ship hits any
// other ships on the board.
if (bFitsOnBoard && !bHitsOtherShips) {
// Place this ship on the board.
Ship newShip = new Ship(shipType[i],
orientation,
row,
col,
shipLength[i]);
this.addShip(newShip);
// Go on to the next ship.
i++;
}
} while (i < SHIPS_PER_FLEET);
}
Before we discuss the code, let's think about the algorithm in plain English. Imagine you're placing a ship--maybe the third one (the Cruiser), and you want to see if it fits on the board. The Cruiser occupies three spaces--the starting cell, and two others. You can figure out if the Cruiser fits using four questions:
We can almost translate this into code, but we have one problem to resolve first. We need to decide the order in which the computer will place its ships. The order doesn't matter, so let's go largest-to-smallest:
When i equals 0, place the aircraft carrier. When i equals 1, place the battleship. When i equals 2, place the cruiser. When i equals 3, place the submarine. When i equals 4, place the PT boat.
To enforce this order, we have to introduce the following code to our routine:
public
void placeComputerShips() {
// ... More code goes here ... Notice these lines in particular:
Ship
newShip = new Ship(shipType[i],
Notice that when i equals 0, we access the first element of shipType and shipLength, which are TYPE_AIRCRAFT_CARRIER and 5, respectively. Similarly, when i equals 2 (the third ship), the we're accessing TYPE_CRUISER and 3. In this way, we're using 1 dimensional arrays to define the order in which we're placing our ships.
With that in mind, we can now decipher the following code:
boolean
bFitsOnBoard = false;
First off, notice that we initially set bFitsOnBoard to false. The variable bFitsOnBoard is type boolean, which means it can have only one of two values: true or false. Given that we're setting it to false, we're assuming the ship doesn't fit right off the bat. The code that follows will have to prove otherwise.
Next, we come to:
int
testLength = shipLength[i] - 1;
Recall in our example of the cruiser, we pointed out that the ship had a length of three, meaning that we have to check 2 cells above, below, left, or right of the ship's position (depending on orientation) to see if it fit on the board. Notice that 2 is 3 - 1. The line above is a general way of figuring out how many cells around the ship's position to check to see if there's room on the board.
For example, when i equals 4, testLength = shipLength[4] - 1, or 2 - 1 equals 1. So, when we're placing the PT Boat (i = 4), we have to check 1 cell above, below, left, or right of the position.
Similarly, when i equals 1, testLength = 4 - 1, or 3, so we have to check 3 spaces to make sure the battleship fits.
Finally, consider the if...else code. We're only going to cover the first two cases. You should be able to figure out the others on your own.
First, we have
if
(orientation == Ship.ORIENTATION_UP) {
where the funky sumbol ">=" reads as "is greater than or equal to".
So, if the ship is pointing up from the random row and column, we execute these statements:
if
(row >= testLength) {
If the random row is greater than the testLength, we set bFitsOnBoard to true--meaning that the ship fits. Consider the case of placing the Battleship on row 2 (the third tow, because we start numbering them at 0). For the battleship, testLength is 4 - 1 = 3. In that case,
if
(row >= testLength) {
reduces to
if
(2 >= 3) { and 2 is not greater than or equal to (>=) 3, so we skip over
bFitsOnBoard
= true;
without executing it.
Now consider placing the PT Boat on row 8 (the ninth row). In this case, testLength is 2 - 1 = 1, so
if
(row >= testLength) {
reduces to
if
(8 >= 1) {
which is true, so we reach the statement
bFitsOnBoard
= true;
indicating that the PT Boat fits at this position.
Now suppose that orientation equals Ship.ORIENTATION_RIGHT. In this case, we reach the code contained here:
else
if (orientation == Ship.ORIENTATION_RIGHT) {
(where '>' reads as "is greater than").
Consider the case where we're placing the sub (i = 3) on column 6 (the seventh column). In that case, testLength equals 2, and
if
(COLUMN_COUNT - col > testLength) {
reduces to
if
(10 - 6 > 2) {
Since 4 is greater than 2, Java executes the code inside the brackets, setting bFitsOnBoard to true.
If we tried to put the sub on row 8 (i.e., in the 9th column), this would become
if
(10 - 8 > 2) {
which isn't true and doesn't set bFitsOnBoard to true.
You get the idea. The other two cases behave in the same manner.
Try compiling, but don't run. Even though our game logic isn't complete, compiling allows us to check to typos and other silly (but all too common) mistakes.
Ships Passing in the Night Finally, we can write the last bit of code--the one that checks to see if the ship we're placing hits one that's already there. Fortunately, this is easy. Recall that when we call addShip, we store the ship's type in the board's grid cells. So, all we have to do to detect a collision is read the values stored in the grid cells we want to occupy. If we find something other than Ship.TYPE_NONE, we know we've hit someone else.
The following code takes care of this:
public void placeComputerShips() {
long seed = System.currentTimeMillis();
Random randomizer = new Random(seed);
int [] shipType = {Ship.TYPE_AIRCRAFT_CARRIER,
Ship.TYPE_BATTLESHIP,
Ship.TYPE_CRUISER,
Ship.TYPE_SUBMARINE,
Ship.TYPE_PT_BOAT};
int[] shipLength = {5, 4, 3, 3, 2};
int i = 0;
do {
int row;
int col;
int orientation;
// Randomly generate a row, column, and
// orientation.
row = randomizer.nextInt(ROW_COUNT);
col = randomizer.nextInt(COLUMN_COUNT);
orientation = randomizer.nextInt(4);
// Check to see if the ship fits on the
// board at the given row and column.
boolean bFitsOnBoard = false;
int testLength = shipLength[i] - 1;
if (orientation == Ship.ORIENTATION_UP) {
if (row >= testLength) {
bFitsOnBoard = true;
}
}
else if (orientation == Ship.ORIENTATION_RIGHT) {
if (COLUMN_COUNT - col > testLength) {
bFitsOnBoard = true;
}
}
else if (orientation == Ship.ORIENTATION_DOWN) {
if (ROW_COUNT - row > testLength) {
bFitsOnBoard = true;
}
}
else if (orientation == Ship.ORIENTATION_LEFT) {
if (col >= testLength) {
bFitsOnBoard = true;
}
}
boolean bHitsOtherShips = false;
// Check to see if the ship hits any
// other ships on the board.
if (bFitsOnBoard == true) {
int j;
if (orientation == Ship.ORIENTATION_UP) {
j = 0;
while (j < shipLength[i]) {
if (this.gridCells[row - j][col] !=
Ship.TYPE_NONE) {
bHitsOtherShips = true;
break;
}
j++;
}
}
else if (orientation == Ship.ORIENTATION_RIGHT) {
j = 0;
while (j < shipLength[i]) {
if (this.gridCells[row][col + j] !=
Ship.TYPE_NONE) {
bHitsOtherShips = true;
break;
}
j++;
}
}
else if (orientation == Ship.ORIENTATION_DOWN) {
j = 0;
while (j < shipLength[i]) {
if (this.gridCells[row + j][col] !=
Ship.TYPE_NONE) {
bHitsOtherShips = true;
break;
}
j++;
}
}
else if (orientation == Ship.ORIENTATION_LEFT) {
j = 0;
while (j < shipLength[i]) {
if (this.gridCells[row][col - j] !=
Ship.TYPE_NONE) {
bHitsOtherShips = true;
break;
}
j++;
}
}
}
if (bFitsOnBoard && !bHitsOtherShips) {
// Place this ship on the board.
Ship newShip = new Ship(shipType[i],
orientation,
row,
col,
shipLength[i]);
this.addShip(newShip);
// Go on to the next ship.
i++;
}
} while (i < SHIPS_PER_FLEET);
}
Since most of this code should look familiar, we're not going to analyze it heavily. We'll hit some high points, then move on.
First, notice that the whole section is wrapped by
if (bFitsOnBoard == true) {
// ...more code in
here...
This causes the collision code to execute only when the ship already fits on the board. If it doesn't fit, there's no need to check for collision because the ship can't go in that position anyway.
Next, we check for collision for each of the four orientations (up, down, left, and right). Let's examine the "up" case--the others behave similarly.
if (orientation == Ship.ORIENTATION_UP) {
Notice that we loop from j=0 until j equals the length of the ship. We check the grid cells one at a time with these lines:
if (this.gridCells[row - j][col] != Ship.TYPE_NONE) {
(recall that '!=' means "is not equal to").
Notice how [row-j] gets smaller as j gets bigger. That's the part that build the ship "upward". Think of this code executing for the Cruise at row 4, column 5. When:
j = 0, [row - j] = [4 - 0] = 4, and we check cell (4, 5) j = 1, [row - j] = [4 - 1] = 3, and we check cell (3, 5) j = 2, [row - j] = [4 - 2] = 2, and we check cell (2, 5) j = 3, [row - j] = [4 - 3] = 1, and we check cell (1, 5)
which moves us up column 5 from row 4 to row 1.
See how that works?
So, as j changes, we check different grid cells. In each case, we ask "does the current grid cell contain any kind of ship?" (or, to interpret the code literally, "is the contents of the current grid cell not equal to an empty space?"). If so, we set bHitsOtherShips to true and...
...break?
What does this mean, exactly? If we run it, will light bulbs go out in our house? Will Java suddenly stop working?
Fortunately (or unfortunately, if you're of that turn of mind), it's nothing so dramatic. The keyword break tells Java to exit the current loop, no matter what the ordinary loop conditions are. In this case, break causes us to bail from the loop no matter what the current value of j.
You might wonder why we'd do such a thing. It's mostly just an efficiency thing. Once we've detected our first collision, there's no need to look at the rest of the grid cells--we immediately know that we can't put the ship in the current position.
Getting Testy That's a lot of code we just wrote--it's past time we tested it. This is very easy to do--we just have to call placeComputerShips() from somewhere. We'll place that code in BattleshipApp, as shown:
public void mouseReleased(MouseEvent event) {
if (this.gameState == GAME_STATE_INTRO) {
this.gameState = GAME_STATE_SETUP;
this.blueBoard.placeComputerShips();
this.repaint();
}
}
We'll say nothing more about this except to note that the if...else block ensures that the computer player (blue) places its ships only during the transition into the setup phase.
One final note--the current code in placeComputerShip() is very long, which makes it sort of hard to read--especially for people other than the author. Good programmers keep their methods short, breaking them into smaller pieces when they start to get large (or "bloat", as they say).
We've prepared working code for both Board and BattleshipApp here. Furthermore, we have an optional version of BattleshipApp here. We've broken placeComputerShips() up into smaller pieces in the alternate version. Take a look here and see if you can figure out how we did it.
You might want to take a short breather. The next section is a lulu that combines the grid, mouse code, and red hot gypsies into one roller-coaster ride to the finish! |
