- Home /
how to detect a closed shape in a grid (2d)
So, I'm making a grid game that if you surround a group of cells with your color, those cells are converted to your color, but I can't find a good algorithm to do that online. any ideas? (and let me know if I need to provide any more information)
EDIT: Here's some more information: my tiles are all separate GameObjects and not in an array (mainly because I don't know how to). A tile can be one of 3 colors: grey (none), red, or blue, and I'm trying to detect a closed shape of red or blue (that includes corners) and fill that in with the respective color, I am kind of a beginner at c# coding, so I would appreciate it if you could summarize what your code does so I know how to implement it properly into what I already have
Answer by CrazyNito · Sep 30, 2020 at 10:01 PM
If you have cells stored in array or multidimensional array you could just check all the neighbouring tiles.
Put all surrounding tiles in one array, iterate it, and check if they are all same color and that they are not same as tile in the middle.
bool IsTileSurrounded(Cell cell, List<Cell> surroundingCells)
{
var colorToCheck = surroundingCells[0].color;
for (i = 0; i < surroundingCells.Count; i++)
{
if (lastColor != surroundingCells[i].color)
{
return false;
}
}
if (colorToCheck == cell.color)
{
return false;
}
return true;
}
Ok, that is ok, but it that would only work if there is only one space in the middle, if there was a 3x3 space in the middle, for example then this system wouldn't work, also, if the player(s) changed the color of the middle tile the whole system would break
Do this check for every cell in the grid after you do the move
Answer by Bunny83 · Sep 30, 2020 at 11:11 PM
Maybe something like this? I provided some sample code in a comment to this answer. Since this shape detector works on image data it would also work on an arbitrary grid with a few modifications. Though keep in mind that in order to avoid dead ends the traversing of the boundary has a threshold. So shapes that are too narrow wouldn't be detected correctly (requires at least 1 pixel interior). You can have a look at my webgl example for reference. You can toggle the shape display and the source texture seperately (mouse wheel to zoom).
Note the detector scans the image from bottom left to the top right. If a shape pixel is detected it will simply crawl along the "outer" edge. Closed shapes should always be traversed counter clockwise. Though open shapes could be traversed the other way round or it could be splitted into several shapes depending where the opening is.
I forgot to link the updated code that was actually used in the webgl example.
Your answer
Follow this Question
Related Questions
Filling array with gameObjects 2 Answers
how to Reverse VR gaze fill image HandleOut exit? 0 Answers
Cell-based Lighting? 2 Answers
Bomberman like movement 1 Answer
Grid-based movement *without* smooth movement between tiles? 0 Answers