Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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();
    }

}
share|improve this question
1  
You should write more - what have failed? Give us some output :) –  zacharmarz Feb 24 '12 at 9:26
    
Well the matrix remains the same after dfs although it should set the some of the elements to -1. –  Fofole Feb 24 '12 at 9:28
    
ok I fixed it.:D –  Fofole Feb 24 '12 at 9:36
    
i am trying to implement same in objective C , but facing same issue. –  Hemant Oct 28 '13 at 18:19
add comment

2 Answers

up vote 7 down vote accepted

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;
    }
share|improve this answer
    
Oh. Nice! With code and everything. After a first look this seems legit so good answer. I'll provide some feedback after trying it. –  Fofole Feb 23 '12 at 16:30
    
Please see my edit. :D –  Luis Estrada Feb 23 '12 at 16:35
    
You call dfs(nr, nc, color) need 1 more param :D –  Fofole Feb 23 '12 at 16:48
    
fixed recursive call parameter –  Luis Estrada Feb 23 '12 at 16:51
2  
+1. Be aware that recursive functions can hit performance due to the ongoing assignment of stack frames at each recursion level. You can easily modify the basic algorithm to use a stack data structure to take the place of the system stack, see this. But I wouldn't change it unless you've profiled and seen that this is impacting performance more than a little. –  Nick Wiggill Feb 24 '12 at 17:50
show 6 more comments

I think it would be easy to implement BFS or DFS to search same colors. You can just go to all of it's neighbours and then to their neighbours (if they are of the same color) etc.

So you will create graph, where every point is connected to its four- (or eight-) neighborhood.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.