Friday, November 16, 2018

game mechanics - Bubble shooter search alghoritm


So I have a Matrix of NxM. At a given position (for ex. [2][5]) I have a value which represents a color. If there is nothing at that point the value is -1. What I need to do is after I add a new point, to check all his neighbours with the same color value and if there are more than 2, set them all to -1.


If what I said doesn't make sense what I'm trying to do is an alghoritm which I use to destroy all the same color bubbles from my screen, where the bubbles are memorized in a matrix where -1 means no bubble and {0,1,2,...} represent that there is a bubble with a specific color.



This is what I tried and failed:


public class Testing {

static private int[][] gameMatrix=
{{3, 3, 4, 1, 1, 2, 2, 2, 0, 0},
{1, 4, 1, 4, 2, 2, 1, 3, 0, 0},
{2, 2, 4, 4, 3, 1, 2, 4, 0, 0},
{0, 1, 2, 3, 4, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},

};

static int Rows=6;
static int Cols=10;
static int count;
static boolean[][] visited=new boolean[15][15];
static int NOCOLOR = -1;
static int color = 1;

public static void dfs(int r, int c, int color, boolean set)

{
for(int dr = -1; dr <= 1; dr++)
for(int dc = -1; dc <= 1; dc++)
if(!(dr == 0 && dc == 0) && ok(r+dr, c+dc))
{
int nr = r+dr;
int nc = c+dc;

// if it is the same color and we haven't visited this location before
if(gameMatrix[nr][nc] == color && !visited[nr][nc])

{
visited[nr][nc] = true;
count++;

dfs(nr, nc, color, set);

if(set)
{
gameMatrix[nr][nc] = NOCOLOR;
}

}
}
}

static boolean ok(int r, int c)
{
return r >= 0 && r < Rows && c >= 0 && c < Cols;
}

static void showMatrix(){

for(int i = 0; i < gameMatrix.length; i++) {
System.out.print("[");
for(int j = 0; j < gameMatrix[0].length; j++) {
System.out.print(" " + gameMatrix[i][j]);
}
System.out.println(" ]");
}
System.out.println();

}


static void putValue(int value,int row,int col){
gameMatrix[row][col]=value;
}

public static void main(String[] args){
System.out.println("Initial Matrix:");
putValue(1, 4, 1);
putValue(1, 5, 1);
showMatrix();


for(int n = 0; n < 15; n++)
for(int m = 0; m < 15; m++)
visited[n][m] = false;

//reset count
count = 0;
//dfs(bubbles.get(i).getRow(), bubbles.get(i).getCol(), color, false);

// get the contiguous count

dfs(5,1,color,false);
//if there are more than 2 set the color to NOCOLOR
for(int n = 0; n < 15; n++)
for(int m = 0; m < 15; m++)
visited[n][m] = false;
if(count > 2)
{
//dfs(bubbles.get(i).getRow(), bubbles.get(i).getCol(), color, true);
dfs(5,1,color,true);
}


System.out.println("Matrix after dfs:");
showMatrix();
}

}

Answer



What you need here is a depth first search.


  int R, C;
int[][] matrix;

int count;
boolean[][] visited;
int NOCOLOR = -1;
public int main()
{
int startR = 0;
int startC = 0;
int color = 1 // red
int R = 10;
int C = 20;



matrix = new int[R][C];
visited = new boolean[R][C];

matrix = LoadLevel(); // get a starting matrix with colors

//reset visited matrix to false.
for(int i = 0; i < R; i++)
for(int j = 0; j < C; j++)

visited[i][j] = false;

//reset count
count = 0;
dfs(startR, startC, color, false); // get the contiguous count

//if there are more than 2 set the color to NOCOLOR
if(count > 2)
{
dfs(startR, startC, color, true);

}
}

public void dfs(int r, int c, int color, boolean set)
{
for(int dr = -1; dr <= 1; dr++)
for(int dc = -1; dc <= 1; dc++)
if((dr == 0 ^ dc == 0) && ok(r+dr, c+dc)) // 4 neighbors
{
int nr = r+dr;

int nc = c+dc;

// if it is the same color and we haven't visited this location before
if(matrix[nr][nc] == color && !visited[nr][nc])
{
visited[nr][nc] = true;
count++;

dfs(nr, nc, color, set);


if(set)
{
matrix[nr][nc] = NOCOLOR;
}
}
}
}

boolean ok(int r, int c)
{

return r >= 0 && r < R && c >= 0 && c < C;
}

No comments:

Post a Comment

Simple past, Present perfect Past perfect

Can you tell me which form of the following sentences is the correct one please? Imagine two friends discussing the gym... I was in a good s...