# How to find connected groups in a 2D grid of tiles

Firstly, my English is very bad, sorry for this. That's why I showed my problem with a picture.

Block[,] sameTiles = new Block[
WorldController.Instance.World.Width,
WorldController.Instance.World.Height];


sameTiles keeps the same side-by-side green blocks. My problem is, I need to detect and separate the shapes made of connected blocks so I can access each shape separately. For example, putting each group on a layer of a 3D array:

Block[,,] differentTiles = new Block[
100,
WorldController.Instance.World.Width,
WorldController.Instance.World.Height];


(100 connected shapes are supported at max)

Block[
ShapeNumber,
X Coord,
Y Cood].


Here is my picture, I need to search this array and detect the four shapes of connected green blocks, storing them separately. Picture:

• This is looking like an XY problem. Why do you want to separate the polyomino groups onto layers of a 3D array like this? The array would be 99% empty, so there might be much more efficient solutions to your root problem. – DMGregory Dec 21 '15 at 20:40
• [0,blan,blan], [1,blan,blan], on which logic these numbers (0 and 1) are depending? What are their basis? – Hamza Hasan Dec 21 '15 at 20:54
• Oh, yes, The array would be 99% empty. So thanks, but i am not understant anythink ... Have you sample source code for this ? I want to take a shape on the world randomly but, they must be the same color. (: – Dentrax Dec 21 '15 at 20:56
• @Hamza Hasan, its shape number. When i split this 4 shapes, [0,blah,blah] bottom left, [1,blah,blah] bottom, [2,blah,blah] bottom right, [3,blah,blah] top right etc.. Maybe, I need to find a better solution... – Dentrax Dec 21 '15 at 20:58
• exactly. there might be a better solution as @DMGregory said – Hamza Hasan Dec 21 '15 at 21:01

## 1 Answer

I'm interpreting your problem as follows - please update the question if I've gotten any details incorrect:

1. We are given a grid (world) of size world.Width & world.Height filled with coloured blocks.

2. We want to search this grid to find every group of two or more green blocks connected along their edges (polyominos)

3. We want to store these groups in a structure that lets us quickly identify all the blocks associated with each distinct group.

I'm choosing to reject the form of output described in your question, a 3D array, because this will tend to waste a lot of space and isn't very efficient to iterate over.

Instead, I'd recommend a list of groups, where each group is a list of blocks. There are more compressed formats still, but this hits a nice trade-off of efficiency & ease of use. (I assume each block knows its location in the world - If not, the list can store the coordinates of each block instead of the block itself)

In my example I'll create new lists as needed, but for performance you can modify this to re-use the lists in a pool if you find it's causing excess garbage.

public List<List<Block>> FindConnectedGroups(World world, BlockColor matchColor)
{
var groups = new List<List<Block>>();

// Search the world grid for pairs of connected blocks.
for(int x = 0; x < world.Width; x++)
{
for(int y = 0; y < world.Height; y++)
{
var block = world.GetBlock(x, y);

// Skip blocks we've already grouped.
// If you don't want to add a visited field to every block,
// you can accomplish this with a parallel array instead.
if(block.visited)
continue;

// Remove this check if you want to find groups of any color.
if(block.color == matchColor)
{
// Every group of 2+ blocks has a block to the right or below another,
// so by checking just these two directions we don't exclude any.
if(x > 0)
{
var neighbor = world.GetBlock(x - 1, y);
if(neighbor.color == block.color)
{
var group = new List<Block>();
PopulateGroup(world, group, block);
groups.Add(group);
continue;
}
}
if(y > 0)
{
var neighbor = world.GetBlock(x, y - 1);
if(neighbor.color == block.color)
{
var group = new List<Block>();
PopulateGroup(world, group, block);
groups.Add(group);
}
}
}
}
}

// Set all tiles back to unvisited for the next use.
world.ClearVisitedFlags();

return groups;
}

// Recursively find connected blocks (depth-first search)
void PopulateGroup(World world, List<Block> group, block)
{
group.Add(block);
block.visited = true;

// Check all four neighbors and recurse on them if needed:
if(block.x > 0)
{
var neighbor = world.GetBlock(block.x - 1, block.y);
if(neighbor.color == block.color && neighbour.visited == false)
PopulateGroup(world, group, neighbor);
}
if(block.x < world.Width - 1)
{
var neighbor = world.GetBlock(block.x + 1, block.y);
if(neighbor.color == block.color && neighbour.visited == false)
PopulateGroup(world, group, neighbor);
}
if(block.y > 0)
{
var neighbor = world.GetBlock(block.x, block.y - 1);
if(neighbor.color == block.color && neighbour.visited == false)
PopulateGroup(world, group, neighbor);
}
if(block.y < world.Height - 1)
{
var neighbor = world.GetBlock(block.x, block.y + 1);
if(neighbor.color == block.color && neighbour.visited == false)
PopulateGroup(world, group, neighbor);
}
}


Edit: Added the step to clear visited flags once we're done, so that a subsequent call doesn't skip all the groups we found this time. You can also use a number that's incremented with each FindConnectedGroups() call instead of a boolean and avoid clearing, as long as you never keep a world around for more than Int32.MaxValue calls. ;)

• Thank you, I'll test this code soon.After I tested it, I'll feed-back here. Thanks. (: – Dentrax Dec 22 '15 at 8:15
• Okey, I tested it and successfully working.How can i do some memory optimizations on .NET 2.0 ? – Dentrax Dec 22 '15 at 9:20
• Hello again, when i tried this code more than one, i get "Argument out of range" exception there : tiles[rand].Count. But, no problem in one try... List<List<Tile>> tiles = new List<List<Tile>>(); tiles = FindConnectedTiles(Tile.TileType.Green); int rand = Random.Range(0, tiles.Count); for (int i = 0; i < tiles[rand].Count; i++) { if (tiles[rand][i] != null) { SameSpawnCursor(tiles[rand][i].X, tiles[rand][i].Y); } } – Dentrax Dec 22 '15 at 14:04
• @FurkanTürkal You need to clear the visited flags between uses - I'll edit the answer to be explicit about this. Also, don't forget to check that groups.Count > 0. As for memory optimizations, I'd recommend: 1) Profile this on your target hardware and confirm whether it's even a problem. It's not worth adding complexity to your code to solve non-problems, when that time could be spent adding game features instead. 2) Research the Object Pool and similar design patterns. 3) Ask a new question if you need additional help. – DMGregory Dec 22 '15 at 14:13
• You are awesome. Visited bool is helpfull. Thank you... (: – Dentrax Dec 22 '15 at 15:19