CODEWITHSUNDEEP
javaarraysalgorithmmath2d
Jordi
Jordi

Reputation: 166

Java 2D Array, find containing elements

I have a 2D array declared like this:

private Dots[][] dots = new Dots[8][8];

I'm making a game for educational purposes where the 2D array gets filled with dots, each having a color randomly selected out of a pool of four colors. The goal for the game is to connect the dots. When you connect dots of the same color, they get deleted and you get points for them. At the moment that's all working fine but I would like to add a new feature:

When you close the path, all dots contained in that path will be deleted aswell. (see image):

I'm thinking of an algorithm to find all dots contained in that path but I can't come up with one.

The path is stored in a LinkedList (probably irrelevant but I'm just saying it to be sure :) )

So to to summarize my question: I'm trying to come up with an algorithm to select the grey dots between the blue dots.

Note:

8x8 grid with path

Edit 1: This is how the game looks:

dots

Edit 2: This is what I mean with:

When you close the path, all dots contained in that path will be deleted aswell.

enter image description here

Upvotes: 2

Views: 796

Answers (2)

skY
skY

Reputation: 111

Dynamic Programming Approach (n^2)

For any cell to be eligible for count you need (i,j-1),(i-1,j) and (i,j+1),(i+1,j).
NOTE: This cell could not exactly be there it could be down the line as well.

Create a Boolean 2D array.
Let's take example of below 6 by 6 sample.
/*
T T T - - -
T - T - - -
T T T - - -
- T - - - -
- T - - - -
*/
where T marks the closed path.

2 Iterations:
1st

First traverse through the matrix and if you find (i,j-1) and (i-1,j) to be true then include that Point in Set (Or whichever collection). For Boundary conditions do not include them in Set as they'll never be inside closed path, so at the end of first iteration you'll have

/*
T T T F F F
T 1 T F F F
T T T F F F
F T 1 F F F
F T 1 F F F
*/
where 1 indicates points included in set.
(Here you may want to use char 2d matrix rather than boolean. However if you use boolean then also it works just you need to perform set.contains(new Point(i,j)))

2nd

Do the same but start from (n-1,n-1) and this time you check for (i+1,j),(i,j+1) points to be true. for any point in 2-d matrix if you find that it should be 'F' but it is '1' then remove that point from set.

/*
T T T F F F
T 1 T F F F
T T T F F F
F T F F F F
F T F F F F
*/

Thus after 2 times n^2 operations. you'll have set that contains desired Points.

And yes 1 will also act as T for subsequent iterations.
In short Unlike DP here we are traversing from TOP-LEFT to BOTTOM-RIGHT and BOTTOM-RIGHT to TOP-LEFT in order to find out exactly which points are inside the closed path.
F - Not Eligible
T - Eligible for Counting only
1 - same as T but also gets added in Output Set

Upvotes: 0

Gewure
Gewure

Reputation: 1268

  • Solid Solution:

The proper solution for this would be to implement the 4-connected/4-Neighbour version of the FloodFill Algorithm.

enter image description here

It is very nicely explained in the Wikipedia article. An example in java can be found here.

  • Naive Solution:

row by row, coloring all the fields initially white, then the user-selected ones blue and iterate row-by-row, coloring the fields inbetween ( state: boolean select = true ) grey :

enum COLOR { BLUE, GREY, WHITE}; 

boolean select = false;

// iterate row by row
for(int x = 0; x < 8; x++) {
       for(int y = 0; y <8; y++) {
           //select mode...
           if(dots[x][y].color == COLOR.BLUE  && !change) {
                select = true;
           }
           //if we are in select and the current field is white -> make GREY
           if(select && dots[x][y].color == COLOR.WHITE) {
                dots[x][y].color = COLOR.GREY;
           }
           // if we hit another blue and are in select -> select = false
           if(select && dots[x][y].color == COLOR.BLUE) {
                select = false;
           }
    }
}

Note there are still some cases open to cover:

e.g. if the the current iterated row is a vertical blue wall and the length is odd it turns falsely into select mode

Upvotes: 1

Related Questions