# FloodFill for Game Algorithm

I was wondering if this FloodFill algorithm was correct for this game I am trying to create it is in the selectColor method of my GameController.java class:

import java.awt.*;

public class GameController /*implements ActionListener*/ {

private GameModel model;
private MyStack dots;
private int size;

/**
* Constructor used for initializing the controller. It creates the game's view
* and the game's model instances
*
* @param size
*            the size of the board on which the game will be played
*/
public GameController(int size) {
this.size = size;
model = new GameModel(size);
dots = new MyStack(size);
}

/**
* resets the game
*/
public void reset(){
model.reset();
System.out.println(model);
}

/**
* Callback used when the user clicks a button (reset or quit)
*
* @param e
*            the ActionEvent
*/

/*public void actionPerformed(ActionEvent e) {

}*/

/**
* <b>selectColor</b> is the method called when the user selects a new color.
* If that color is not the currently selected one, then it applies the logic
* of the game to capture possible locations. It then checks if the game
* is finished, and if so, congratulates the player, showing the number of
* moves, and gives two options: start a new game, or exit
* @param color
*            the newly selected color
*/
public void selectColor(int color){
DotInfo d;
DotInfo below;
DotInfo right;
MyStack newStack = new MyStack(size*size);
for (int i=0;i<size;i++) {
for (int j=0;i<size;i++) {
if (model.isCaptured(i, j)==true) {
newStack.push(model.dots[i]);
}
}
}
while (newStack.isEmpty()==false) {
d = newStack.pop();
for (int i=0;i<size;i++) {
for (int j=0;j<size;j++) {
below = model.get(i, j+1);
right = model.get(i+1, j);
if ((d==below && below.isCaptured()==false && below.getColor()==color)) {
below.setCaptured(true);
dots.push(below);
} else if ((d==right && right.isCaptured()==false && right.getColor()==color)) {
right.setCaptured(true);
dots.push(right);
}
}
}
}
}
}


DotInfo is an instance of the class DotInfo.java which has a Constructor:

DotInfo(int x, int y, int color)


I was wondering if this algorithm is missing anything and if it can be improved as well.

The game is a version of Flood-It. The game starts at the upper left corner and you choose which colors you want to flood the grid with. Hopefully choosing correctly in a certain number of moves to flood the whole grid. I found out that I only need to represent the board with one array but inserting a new line each time it is needed for example in my twoString method of GameModel.java:

import java.util.Random;

public class GameModel {

/**
* predefined values to capture the color of a DotInfo
*/
public static final int COLOR_0           = 0;
public static final int COLOR_1           = 1;
public static final int COLOR_2           = 2;
public static final int COLOR_3           = 3;
public static final int COLOR_4           = 4;
public static final int COLOR_5           = 5;
public static final int NUMBER_OF_COLORS  = 6;

public DotInfo[] dots;
private int size;
private int currentColor;
private Random generator;
private int steps;

/**
* Constructor to initialize the model to a given size of board.
*
* @param size
*            the size of the board
*/
public GameModel(int size) {
this.size = size;
dots = new DotInfo[size*size];
generator = new Random();
}

/**
* Resets the model to (re)start a game. The previous game (if there is one)
* is cleared up .
*/
public void reset(){
generator = new Random();
int color = 0;
int j = 0;
for (int i=0;i<size*size;i++) {
dots[i] = new DotInfo(i, j, generator.nextInt(NUMBER_OF_COLORS)+1);
if (i+1==size) {
j++;
}
}
}

/**
* Getter method for the size of the game
*
* @return the value of the attribute sizeOfGame
*/
public int getSize(){
return size;
}

/**
* returns the current color  of a given dot in the game
*
* @param i
*            the x coordinate of the dot
* @param j
*            the y coordinate of the dot
* @return the status of the dot at location (i,j)
*/
public int getColor(int i, int j){
int color=0;
for (int x=0;x<size*size;x++) {
if (dots[x].getX()==i && dots[x].getY()==j) {
color=dots[x].getColor();
}
}
return color;
}

/**
* returns true is the dot is captured, false otherwise
*
* @param i
*            the x coordinate of the dot
* @param j
*            the y coordinate of the dot
* @return the status of the dot at location (i,j)
*/
public boolean isCaptured(int i, int j){
boolean capture = true;
for (int x=0;x<size*size;x++) {
if (dots[x].getX()==i && dots[x].getY()==j) {
capture=dots[x].isCaptured();
}
}
return capture;
}

/**
* Sets the status of the dot at coordinate (i,j) to captured
*
* @param i
*            the x coordinate of the dot
* @param j
*            the y coordinate of the dot
*/
public void capture(int i, int j){
for (int x=0;x<size*size;x++) {
if (dots[x].getX()==i && dots[x].getY()==j) {
dots[x].setCaptured(true);
}
}
}

/**
* Getter method for the current number of steps
*
* @return the current number of steps
*/
public int getNumberOfSteps(){
return steps;
}

/**
* Setter method for currentSelectedColor
*
* @param val
*            the new value for currentSelectedColor
*/
public void setCurrentSelectedColor(int val) {
currentColor = val;
}

/**
* Getter method for currentSelectedColor
*
* @return currentSelectedColor
*/
public int getCurrentSelectedColor() {
return currentColor;
}

/**
* Getter method for the model's dotInfo reference
* at location (i,j)
*
* @param i
*            the x coordinate of the dot
* @param j
*            the y coordinate of the dot
*
* @return model[i][j]
*/
public DotInfo get(int i, int j) {
DotInfo dot = null;
for (int x=0;x<size*size;x++) {
if (dots[x].getX()==i && dots[x].getY()==j) {
dot = dots[x];
}
}
return dot;
}

/**
* The metod <b>step</b> updates the number of steps. It must be called
* once the model has been updated after the payer selected a new color.
*/
public void step(){
steps++;
}

/**
* The metod <b>isFinished</b> returns true iff the game is finished, that
* is, all the dats are captured.
*
* @return true if the game is finished, false otherwise
*/
public boolean isFinished(){
boolean flag=true;
for (int x=0;x<size*size;x++) {
if (dots[x].isCaptured()==false) {
flag=false;
}
}
return flag;
}

/**
* Builds a String representation of the model
*
* @return String representation of the model
*/
public String toString(){
String rep = "";
int k=0;
for (int x=0;x<size*size;x++) {
rep += dots[x].getColor()+" ";
k++;
if (k==size) {
k=0;
rep+="\n";
}
}
return rep;
}
}


For FloodFill to work the user chooses a color. then that color is chosen to be in the top left corner. The computer then checks the bottom and right next to it to see if there are any other colors that are the same.

• Could you explain this game more? It's unclear what you are trying to do. Also, I'm not understanding what is model.dots[i] since you have a 2D board. I don't know why it isn't model.dots[i][j].
– JS1
Feb 23, 2017 at 23:27

Some spots in the first block of the method selectColor:

for (int i=0;i<size;i++) {
for (int j=0;i<size;i++) {
if (model.isCaptured(i, j)==true) {
newStack.push(model.dots[i]);
}
}
}


Line 2: copy+paste error - it should be rather:

    for (int j=0; j < size; j++) {


(j instead of i).

Line 3: useless condition (==true) - should be simplified as:

        if (model.isCaptured(i, j)) {


Line 4: dots index calculated incorrectly - I would rather expect:

            newStack.push( model.dots[i * size + j] );


Good luck with the game!

• How would I be able to use isFinished() in GameModel.java if i didnt want to call it in GameController.java but instead in a main function of a different class? Thank you so much by the way Jonatan Feb 26, 2017 at 5:50
• Garret, you could demonstrate your thankfulness by up-voting my answer ;) Feb 26, 2017 at 23:25