CS 631 - Computer Science II - Spring 2007
Flood Fill


Loyola College > Department of Computer Science > Dr. James Glenn > CS 631 > Examples and Lecture Notes > Flood Fill

There is a Java archive with the complete code.

MineSweeperBoard.java

import java.awt.Color;
import java.util.Random;

/**
 * A Mine Sweeper board.  A Mine Sweeper board contains mines and
 * empty spaces.  The contents of a square can be revealed one at a time.
 * The player wins by revealing all the empty squares before revealing
 * a mine.
 *
 * @author Jim Glenn
 * @version 0.1 1/16/2007
 */

public class MineSweeperBoard extends GameBoardModel
{
    /**
     * Default attributes of boards.
     */

    public static final int DEFAULT_SIZE = 10;
    public static final int DEFAULT_MINES = 10;

    /**
     * The number of mines on this board.
     */

    private int numMines;

    /**
     * The number of empty squares that have been revealed on this board.
     */

    private int foundEmpties;

    /**
     * Creates a new board of the default size with the default number
     * of mines.
     */

    public MineSweeperBoard()
    {
	this(DEFAULT_SIZE, DEFAULT_SIZE, DEFAULT_MINES);
    }

    /**
     * Initializes a board of the given size with the default number of mines.
     *
     * @param width a positive integer
     * @param height a positive integer
     */

    public MineSweeperBoard(int width, int height)
    {
	this(width, height, DEFAULT_MINES);
    }

    /**
     * Initializes a board of the given size with the given number of mines.
     *
     * @param width a positive integer
     * @param height a positive integer
     * @param m a positive integer less than width * height
     */

    public MineSweeperBoard(int width, int height, int m)
    {
	super(width, height);

	numMines = m;
	foundEmpties = 0;

	setupBoard();
    }

    /**
     * Returns the color of this board at the given location.  The board
     * is gray everywhere.
     *
     * @param r a row on this board
     * @param c a column on this board
     * @return <CODE>Color.GRAY</CODE>
     */

    public Color getBoardColor(int r, int c)
    {
	return Color.GRAY;
    }

    /**
     * Randomly places mines on this board and counts the adjacent mines
     * at the other locations.
     */

    public void setupBoard()
    {
	// we ought to check here whether there are enough spaces for
	// us to place all of our mines

	Random rand = new Random();

	// for each mine, randomly pick a place to put it

	for (int m = 0; m < numMines; m++)
	    {
		int r;
		int c;

		do
		    {
			r = rand.nextInt(getHeight());
			c = rand.nextInt(getWidth());
		    }
		while (getPieceAt(r, c) != null);

		pieces[r][c] = new Mine();
	    }

	// for each other place, determine the number of adjacent mines

	for (int r = 0; r < getHeight(); r++)
	    {
		for (int c = 0; c < getWidth(); c++)
		    {
			if (getPieceAt(r, c) == null)
			    {
				pieces[r][c] = new Empty(countAdjacentMines(r, c));
			    }
		    }
	    }
    }
    
    /**
     * Counts the mines adjacent to the given location.
     *
     * @param r a row on this board
     * @param c a column on this board
     * @return the number of mines adjacent to that location
     */

    private int countAdjacentMines(int r, int c)
    {
	int mineCount = 0;

	for (int dr = -1; dr <= 1; dr++)
	    {
		for (int dc = -1; dc <= 1; dc++)
		    {
			if ((dr != 0 || dc != 0)
			    && (inBounds(r + dr, c + dc))
			    && getPieceAt(r + dr, c + dc) instanceof Mine)
			    {
				mineCount++;
			    }
		    }
	    }

	return mineCount;
    }

    /**
     * Returns false.
     */

    public boolean isLegalMove(int fromR, int toR, int fromC, int toC)
    {
	return false;
    }

    /**
     * Determines if the given move is legal.  It is legal to reveal
     * the contents of a location if the contents are currently hidden.
     *
     * @param r a row on this board
     * @param c a column on this board
     * @return true iff that block at that location hasn't been revealed
     */

    public boolean isLegalMove(int r, int c)
    {
	return (!isOver() && !getBlockAt(r, c).isVisible());
    }

    /**
     * Reveals the contents of the block at the given location.
     * The location must not be visible yet.
     *
     * @param r a row on this board
     * @param c a column on this board
     */

    public void makeMove(int r, int c)
    {
	MineSweeperBlock block = getBlockAt(r, c);

	if (block instanceof Mine)
	    {
		block.makeVisible();
		endGame();
	    }
	else
	    {
		// reveal empty space, and if block is adjacent to 0 mines,
		// reveal adjacent spaces

		revealEmptySpace(r, c);

		// check that all empty squares have been clicked on

		if (foundEmpties + numMines == getWidth() * getHeight())
		    {
			revealMines();
			endGame();
		    }
	    }

	update();
    }

    /**
     * Reveals and counts as empty the square at the given position on
     * this board.  If that square is not adjacent to any mines, all
     * adjacent squares are revealed as well.  The square must not
     * contain a mine and it must not have been counted as empty yet.
     * There is no effect if the position is not on this board or if
     * that position is already visible.
     *
     * @param r a row index
     * @param c a column index
     */

    private void revealEmptySpace(int r, int c)
    {
	if (inBounds(r, c) && !getBlockAt(r, c).isVisible())
	    {
		getBlockAt(r, c).makeVisible();
		foundEmpties++;

		if (((Empty)getBlockAt(r, c)).getAdjacentMines() == 0)
		    {
			revealEmptySpace(r - 1, c - 1);
			revealEmptySpace(r - 1, c);
			revealEmptySpace(r - 1, c + 1);
			revealEmptySpace(r, c - 1);
			revealEmptySpace(r, c + 1);
			revealEmptySpace(r + 1, c - 1);
			revealEmptySpace(r + 1, c);
			revealEmptySpace(r + 1, c + 1);
		    }
	    }
    }

    /**
     * Makes all the mines on this board visible.
     */

    private void revealMines()
    {
	for (int r = 0; r < getHeight(); r++)
	    for (int c = 0; c < getWidth(); c++)
		if (getBlockAt(r, c) instanceof Mine)
		    getBlockAt(r, c).makeVisible();
    }

    /**
     * Returns the block at the given position on this board.
     *
     * @param r a row on this board
     * @param c a column on this board
     * @return the block at that position
     */

    protected MineSweeperBlock getBlockAt(int r, int c)
    {
	return (MineSweeperBlock)(getPieceAt(r, c));
    }

    /**
     * Returns a printable representation of this board.
     *
     * @return a printable represenation of this board
     */

    public String toString()
    {
	StringBuffer result = new StringBuffer();
	for (int r = 0; r < getHeight(); r++)
	    {
		for (int c = 0; c < getWidth(); c++)
		    {
			if (!getBlockAt(r, c).isVisible())
			    result.append('.');
			else
			    {
				if (getBlockAt(r, c) instanceof Mine)
				    result.append('*');
				else
				    {
					int adjacentMines = ((Empty)getBlockAt(r, c)).getAdjacentMines();
					if (adjacentMines > 0)
					    result.append(String.valueOf(adjacentMines));
					else
					    result.append(' ');
				    }
			    }
		    }
		result.append('\n');
	    }

	return result.toString();
    }

    public static void main(String[] args)
    {
	MineSweeperBoard b = new MineSweeperBoard();
	b.makeMove(0, 0);

	System.out.println(b);
    }
}

    

GameBoardModel.java

import java.awt.Color;

/**
 * A model of a 2-D grid-based game board.
 *
 * @author Jim Glenn
 * @verion 0.1 9/1/2004
 */

public class GameBoardModel
{
    /**
     * Stores what game piece is at each position.
     */
    
    protected GamePiece[][] pieces;

    /**
     * The view that should be notified of changes in this model.
     */

    protected GameBoardView view;

    /**
     * A flag that indicates whether this game is over.
     */

    private boolean gameOver;

    /**
     * Creates an empty board of the given size.
     *
     * @param w the width, in squares, of this new board
     * @param h the height, in squares, of this new board
     */

    public GameBoardModel(int w, int h)
    {
	pieces = new GamePiece[h][w];

	view = null;

	gameOver = false;
    }

    /**
     * Registers a view that will be notified of changes to this model.
     *
     * @param v a view
     */

    public void setView(GameBoardView v)
    {
	view = v;
    }

    /**
     * Returns the color of the board at the specified position.
     * This implementation colors the board in a black and red checkerboard
     * pattern.
     *
     * @param r the row
     * @param c the column
     * @return the color of the board at row <CODE>r</CODE>, column
     * <CODE>c</CODE>
     */

    public Color getBoardColor(int r, int c)
    {
	if (r % 2 == c % 2)
	    return Color.RED.darker();
	else
	    return Color.BLACK;
    }

    /**
     * Returns the piece at the specified position, or <CODE>null</CODE>
     * if that position is empty.
     *
     * @param r the row
     * @param c the column
     * @return the piece at row <CODE>r</CODE>, column <CODE>c</CODE>
     */

    public GamePiece getPieceAt(int r, int c)
    {
	return pieces[r][c];
    }
 
    /**
     * Returns the width of this board.
     *
     * @return the width
     */

    public int getWidth()
    {
	return pieces[0].length;
    }

    /**
     * Returns the height of this board.
     *
     * @return the height
     */

    public int getHeight()
    {
	return pieces.length;
    }

    /**
     * Determines if the given position is on this board.
     *
     * @param r the row
     * @param c the column
     * @return true iff that row and column is on the board
     */

    protected boolean inBounds(int r, int c)
    {
	return (r >= 0 && c >= 0 && r < getHeight() && c < getWidth());
    }

    /**
     * Determines if the given move is legal.  This implementation
     * disallows all single-space moves.
     *
     * @param r the row of the move
     * @param c the column of the move
     */

    public boolean isLegalMove(int r, int c)
    {
	return false;
    }

    /**
     * Determines if the given move is legal.  This implementation
     * allows any piece to move to any location on the board.
     *
     * @param fromR the starting row of the piece to be moved
     * @param fromC the starting column of the piece to be moved
     * @param toR the ending row
     * @param toC the ending column
     * @return true iff the move is legal
     */

    public boolean isLegalMove(int fromR, int fromC, int toR, int toC)
    {
	// check that the game is not over

	if (isOver())
	    return false;

	// check if all spaces are on the board

	if (!inBounds(fromR, fromC) || !inBounds(toR, toC))
	    return false;

	// check that there is a piece at the starting position

	GamePiece piece = getPieceAt(fromR, fromC);
	if (piece == null)
	    return false;

	return true;
    }

    /**
     * Updates the board to reflect the results of the given move.
     * The move must be legal.  This implementation does nothing.
     *
     * @param r the row of the move
     * @param c the column of the move
     */

    public void makeMove(int r, int c)
    {
	update();
    }

    /**
     * Updates the board to reflect the results of the given move.
     * The move must be legal.  This implementation moves a piece
     * from the from position to the to position, removing any piece
     * that was previously at the to position.
     *
     * @param fromR the row to move from
     * @param fromC the column to move from
     * @param toR the row to move to
     * @param toC the column to move to
     */

    public void makeMove(int fromR, int fromC, int toR, int toC)
    {
	movePiece(fromR, fromC, toR, toC);

	update();
    }

    /**
     * Notifies the view associated with this model that the model had
     * changed and the view should be redrawn.
     */

    protected void update()
    {
	if (view != null)
	    view.updateView();
    }

    /**
     * Moves the piece at the first position to the second position,
     * leaving the first empty.  Both positions must be valid.
     *
     * @param fromR the row to move from
     * @param fromC the column to move from
     * @param toR the row to move to
     * @param toC the column to move to
     */

    protected void movePiece(int fromR, int fromC, int toR, int toC)
    {
	pieces[toR][toC] = pieces[fromR][fromC];
	pieces[fromR][fromC] = null;
    }

    /**
     * Removes the piece at the given position, leaving that position empty.
     * The position must be valid.
     *
     * @param row the row
     * @param col the column
     */

    protected void removePiece(int row, int col)
    {
	pieces[row][col] = null;
    }

    /**
     * Tells whether this game is over.
     */

    public boolean isOver()
    {
	return gameOver;
    }

    /**
     * Ends this game.
     */

    public void endGame()
    {
	gameOver = true;
    }
}
This code can also be downloaded from the files MineSweeperBoard.java, and GameBoardModel.java.