8 Replies - 8574 Views - Last Post: 02 July 2011 - 11:52 AM Rate Topic: -----

#1 TheNinj  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 02-July 11

Detecting adjacent cells in 2D array

Posted 02 July 2011 - 03:46 AM

I'm working on a simple puzzle game and I'm not quite sure how to approach this problem.

Basically I have 2 dimensional array of int (grid = new int[5][5]). Each int represents a different type of block on the grid and I want to find the largest, connected group of the same int on a 5x5 grid.

For example, if this is the grid, I would want to find the location of the red 2s.

1 2 3 4 1
4 2 2 3 1
4 4 2 2 4
1 2 2 3 2
1 4 3 3 1


I originally tried to solve this recursively, by iterating through the array and checking each block's adjacent blocks. This proved to very difficult because I would have to check the bounds and also prevent the function from calling upon the same block twice. I thought I would ask around for a better approach before trying to get this to work.

Is This A Good Question/Topic? 0
  • +

Replies To: Detecting adjacent cells in 2D array

#2 kiwi_steve  Icon User is offline

  • D.I.C Head

Reputation: 31
  • View blog
  • Posts: 109
  • Joined: 26-September 09

Re: Detecting adjacent cells in 2D array

Posted 02 July 2011 - 04:13 AM

My first thought (thinking in simple array terms) would be to make another array of the same size, then recursively check L, R, U, and D (where available) for each cell in the game array, but mark the checked cells in the new array so you don't have to re-check them in the game array when you hit a number that has been checked due to being connected. I can't think of a better method off-hand, but thanks for the puzzle - it should keep my brain amused for quite a while thinking of a better way... if I think of anything I'll post it :)
Was This Post Helpful? 0
  • +
  • -

#3 CasiOo  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1414
  • View blog
  • Posts: 3,136
  • Joined: 05-April 11

Re: Detecting adjacent cells in 2D array

Posted 02 July 2011 - 04:28 AM

What I would do is, I would have an array where each index represent a number. For example if we take array[1], then it will contain all the connections of the number 1. Also you must find a way of starting a new 'group', so maybe this won't work by adding all connections to this array =o

To check if they are connected, I would simply check the area around the current and check if any have the same number. You may get an IndexOutOfBounds exception, but this can easily be avoided by making a 'blank' edge for example:
0 0 0 0 0 0 0
0 1 2 3 4 1 0
0 4 2 2 3 1 0
0 4 4 2 2 4 0
0 1 2 2 3 2 0
0 1 4 3 3 1 0
0 0 0 0 0 0 0

Following shows kind of how to implement it, but it is not complete :)
int[] connections = new int[5];

for (int y=0; y<array.length; y++) {
	for (int x=0; x<array[y].length; x++) {
		if ( isConnected(array[y][x]) ) 
			connections[array[y][x]]++;
	}
}

public boolean isConnected( int numb ) {
	if ( array[y-1][x] == numb )
		return true;
	if ( array[y+1][x] == numb )
		return true;
	if ( array[y][x-1] == numb )
		return true;
	if ( array[y][x+1] == numb )
		return true;
	return false;
}


This post has been edited by CasiOo: 02 July 2011 - 04:47 AM

Was This Post Helpful? 1
  • +
  • -

#4 immeraufdemhund  Icon User is offline

  • D.I.C Regular

Reputation: 79
  • View blog
  • Posts: 495
  • Joined: 29-March 10

Re: Detecting adjacent cells in 2D array

Posted 02 July 2011 - 04:33 AM

my thought is if you don't want to use recursion you could force each row of your array into a String. Then look for the index of "22" and use that number to return the location in your array
Was This Post Helpful? 0
  • +
  • -

#5 CasiOo  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1414
  • View blog
  • Posts: 3,136
  • Joined: 05-April 11

Re: Detecting adjacent cells in 2D array

Posted 02 July 2011 - 04:35 AM

View Postimmeraufdemhund, on 02 July 2011 - 04:33 AM, said:

my thought is if you don't want to use recursion you could force each row of your array into a String. Then look for the index of "22" and use that number to return the location in your array


I don't see how this should make it any easier than having an array with the numbers :)
Was This Post Helpful? 0
  • +
  • -

#6 immeraufdemhund  Icon User is offline

  • D.I.C Regular

Reputation: 79
  • View blog
  • Posts: 495
  • Joined: 29-March 10

Re: Detecting adjacent cells in 2D array

Posted 02 July 2011 - 04:44 AM

I like your approach as it is more clean, and is quicker because you don't have to convert. But it isn't all that hard to convert it to string then check for index of.

int[][] someArray = new int[5][5];
String testForMatch = "";
for (int i=0; i<someArray.length; i++){
  for (iny j=0; j<someArray[0].length; j++){
    testForMath.concat(someArray[i][j]);
  }
  System.out.println(testForMath.indexOf("22"));
  //or if you want it to return the location
  Point p = new Point(i,testForMath.indexOf("22"));
  System.out.println(p);
  testForMath = "";
}



EDIT: Thought of how to add location

This post has been edited by immeraufdemhund: 02 July 2011 - 04:49 AM

Was This Post Helpful? 0
  • +
  • -

#7 TheNinj  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 02-July 11

Re: Detecting adjacent cells in 2D array

Posted 02 July 2011 - 05:12 AM

Thanks for the help, the blank edge should make recursion much easier although I'll have to change a lot of the code because I planned on the grid being a constant size. I came up with this and it should work with a bit of modification. This is supposed to return the length of a certain chain and at the same time mark off which blocks are already inside a chain. The inChain[5][5] array is an array of boolean that checks off which blocks have been checked already.

There can only be one chain at a time so after findChain() I check if the chain is longer than the current longest chain and save the position.

	public int findChain(int color, int x, int y){
//if color is the same and not already checked
		if((color == grid[x][y])&&(!inChain[x][y])){	
			inChain[x][y] = true;
			return findChain(color, x-1,y) + findChain(color, x,y+1) + findChain(color, x+1,y) + findChain(color, x,y-1);
		} else {
			return 0;
		}
	}
if(findChain(color,x,y) > currentlongestchain){
//save position
}


This post has been edited by TheNinj: 02 July 2011 - 05:15 AM

Was This Post Helpful? 0
  • +
  • -

#8 TheNinj  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 02-July 11

Re: Detecting adjacent cells in 2D array

Posted 02 July 2011 - 05:28 AM

That actually wont return anything. I should add a +1 in the return value, but the edit button is gone.
Was This Post Helpful? 0
  • +
  • -

#9 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10785
  • View blog
  • Posts: 40,160
  • Joined: 27-December 08

Re: Detecting adjacent cells in 2D array

Posted 02 July 2011 - 11:52 AM

You could always design a Tile class to encapsulate int value, boolean visited, and the Color. Then store a Tile[][]. Makes it much easier to visit unvisited Tiles and check the Colors.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1