The Board Class
Before we implement the Board
class, we'll need to tackle two interesting problems. First we have to
decide on a data structure. A Meteor puzzle board is basically a
5-by-10 grid of regular hexagons, which we can represent as an array of
50 Cell objects. Instead of using the Cell class directly, we'll use the BoardCell subclass, shown in Listing 5, which keeps track of the piece that occupies the cell:
Listing 5. The BoardCell subclass
public class BoardCell extends Cell {
private Piece piece = null;
public Piece getPiece() {
return piece;
}
public void setPiece(Piece piece) {
this.piece = piece;
}
}
|
If we store all 50 board
cells of the board in an array, we'll have to write some tedious
initialisation code. This initialisation identifies the neighbouring
board cells for each cell of the board, as illustrated in Figure 3. For
instance, cell 0 has two neighbours: cell 1 in the east and cell 5 in
the southeast. Listing 6 shows the initializeBoardCell() method that is called from the constructor of the Board class to do this initialisation.
Figure 3. The board represented as an array of cells
Now that we've implemented the data structure for the board, we move on to the next problem: writing a placePiece()
method that puts a piece on the board. The hardest part of writing this
method is deciding whether the piece fits on the board at the given
position. One way to determine whether the piece fits is to first find
all the board cells that would be occupied by the cells of the piece if
it were placed on the board. After we have this set of board cells, we
can easily determine if the new piece would fit: all corresponding
board cells need to be empty and the piece needs to fit completely on
the board. This process is implemented by the findOccupiedBoardCells() method and placePiece() method shown in Listing 6. Note that we use the processed field of the PieceCell objects to avoid an infinite recursion in the findOccupiedBoardCells() method.
Listing 6. The Board class
public class Board {
public static final int NUMBEROFCELLS = 50;
public static final int NUMBEROFCELLSINROW = 5;
private BoardCell[] boardCells = new BoardCell[NUMBEROFCELLS];
public Board() {
for (int i = 0; i < NUMBEROFCELLS; i++) {
boardCells[i] = new BoardCell();
}
for (int i = 0; i < NUMBEROFCELLS; i++) {
initializeBoardCell(boardCells[i], i);
}
}
/**
* Initialize the neighbours of the given boardCell at the given
* index on the board
*/
private void initializeBoardCell(BoardCell boardCell, int index) {
int row = index/NUMBEROFCELLSINROW;
// Check if cell is in last or first column
boolean isFirst = (index%NUMBEROFCELLSINROW == 0);
boolean isLast = ((index+1)%NUMBEROFCELLSINROW == 0);
if (row%2 == 0) { // Even rows
if (row != 0) {
// Northern neighbours
if (!isFirst) {
boardCell.setNeighbour(Cell.NORTHWEST, boardCells[index-6]);
}
boardCell.setNeighbour(Cell.NORTHEAST, boardCells[index-5]);
}
if (row != ((NUMBEROFCELLS/NUMBEROFCELLSINROW)-1)) {
// Southern neighbours
if (!isFirst) {
boardCell.setNeighbour(Cell.SOUTHWEST, boardCells[index+4]);
}
boardCell.setNeighbour(Cell.SOUTHEAST, boardCells[index+5]);
}
}
else { // Uneven rows
// Northern neighbours
if (!isLast) {
boardCell.setNeighbour(Cell.NORTHEAST, boardCells[index-4]);
}
boardCell.setNeighbour(Cell.NORTHWEST, boardCells[index-5]);
// Southern neighbours
if (row != ((NUMBEROFCELLS/NUMBEROFCELLSINROW)-1)) {
if (!isLast) {
boardCell.setNeighbour(Cell.SOUTHEAST, boardCells[index+6]);
}
boardCell.setNeighbour(Cell.SOUTHWEST, boardCells[index+5]);
}
}
// Set the east and west neighbours
if (!isFirst) {
boardCell.setNeighbour(Cell.WEST, boardCells[index-1]);
}
if (!isLast) {
boardCell.setNeighbour(Cell.EAST, boardCells[index+1]);
}
}
public void findOccupiedBoardCells(
ArrayList occupiedCells, PieceCell pieceCell, BoardCell boardCell) {
if (pieceCell != null && boardCell != null && !pieceCell.isProcessed()) {
occupiedCells.add(boardCell);
/* Neighbouring cells can form loops, which would lead to an
infinite recursion. Avoid this by marking the processed
cells. */
pieceCell.setProcessed(true);
// Repeat for each neighbour of the piece cell
for (int i = 0; i < Cell.NUMBEROFSIDES; i++) {
findOccupiedBoardCells(occupiedCells,
(PieceCell)pieceCell.getNeighbour(i),
(BoardCell)boardCell.getNeighbour(i));
}
}
}
public boolean placePiece(Piece piece, int boardCellIdx) {
// We will manipulate the piece using its first cell
return placePiece(piece, 0, boardCellIdx);
}
public boolean
placePiece(Piece piece, int pieceCellIdx, int boardCellIdx) {
// We're going to process the piece
piece.resetProcessed();
// Get all the boardCells that this piece would occupy
ArrayList occupiedBoardCells = new ArrayList();
findOccupiedBoardCells(occupiedBoardCells,
piece.getPieceCell(pieceCellIdx),
boardCells[boardCellIdx]);
if (occupiedBoardCells.size() != Piece.NUMBEROFCELLS) {
// Some cells of the piece don't fall on the board
return false;
}
for (int i = 0; i < occupiedBoardCells.size(); i++) {
if (((BoardCell)occupiedBoardCells.get(i)).getPiece() != null)
// The board cell is already occupied by another piece
return false;
}
// Occupy the board cells with the piece
for (int i = 0; i < occupiedBoardCells.size(); i++) {
((BoardCell)occupiedBoardCells.get(i)).setPiece(piece);
}
return true; // The piece fits on the board
}
public void removePiece(Piece piece) {
for (int i = 0; i < NUMBEROFCELLS; i++) {
// Piece objects are unique, so use reference equality
if (boardCells[i].getPiece() == piece) {
boardCells[i].setPiece(null);
}
}
}
}
|
This completes the implementation of our initial solution. Let's put it to the test.
