Java 2D Array, find containing elements

Question

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:

Dots can be connected diagonally
The path can be as long as the player wants
The closed path can be of any shape

Edit 1: This is how the game looks:

Edit 2: This is what I mean with:

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

@uoyilmaz I've been trying to think of the algorithm for more than an hour now, I was thinking of getting all the tiles at the top first which don't have a blue neighbour directly below them first and they going down untill they hit one but I'm not sure if it's going to work, I'm afraid of not. — Jordi
– Jordi, Commented Mar 10, 2017 at 8:17
Have you looked into the code of a minesweeper game? I think it's something alike if I understand the question correctly. As it also fills up the empty spaces in a surrounded area. — Nick Bleyen
– Nick Bleyen, Commented Mar 10, 2017 at 8:24
When you say finding all dots contained inside a closed path you mean the count of those dots, right?, if yes then dots on all four sides will never contribute to the count. (e.g. (0,0),(3,0),(0,5)) — skY
– skY, Commented Mar 10, 2017 at 9:42
I don't really need the count, I need their indexes in the 2D array — Jordi
– Jordi, Commented Mar 10, 2017 at 9:44
@skY Exactly :) the linkedlist contains the selected dots, but I can easily do a getX() and getY() to get their position in the 2D array — Jordi
– Jordi, Commented Mar 10, 2017 at 10:34

Gewure · Accepted Answer · 2017-03-10 09:51:43Z

1

Solid Solution:

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

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

edited Mar 10, 2017 at 9:51

answered Mar 10, 2017 at 8:34

Gewure

1,26820 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Gewure Over a year ago

yes, but can me made to work in every case. eg add another boolean and the proper conditionals inside the loop thus adapting the statemachine. - and i think its more adequate to lead into the right direction and supply a basis rather than to deliver a finished turnkey solution..^

Jordi Over a year ago

@Gewure the flood fill algorithm will surely help alot, but how would I go about not having 'an original' (see example answer code) color, and I don't see how they implement the 'border' in the example you provided

Gewure Over a year ago

color the matrix initially all white, then iterate and color the path-dots in the matrix blue, then run my naive solution or the floodfill.

Gewure Over a year ago

@the resulting matrix of dots will hold the border as well as the grey dots indicating the fields to be deleted. Do you only accept a turnkey-ready solution as answer..? :)

skY · Accepted Answer · 2017-03-10 13:03:00Z

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

Collectives™ on Stack Overflow

Java 2D Array, find containing elements

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related