Essentially a series of flood fills - one for each cell in the grid, but skipping over any you've already visited, and dropping out early if you find a cell not connected to a group you've already flood-filled/gathered but of the same type as that group.
Written blind, so please excuse any code typos or holes; highlight them in a comment and I will amend. Also assuming a 2D array storing tiles, width
and height
variables detailing dimensions. With this algorithm, you don't need a Tile class at all - just a 2D array of ints would do just fine.
int IndexFromXY(int x, int y)
{
return (y * width) + x;
}
void GatherConnectedTilesOfType(int type, int x, int y, List<int> visitedTiles)
{
if ((x < 0) || (x >= width)) { return; } //Trivial succeed when out of bounds
if ((y < 0) || (y >= height)) { return; }
int index = IndexFromXY(x,y);
if (visitedTiles.Contains(index))
{
//We've already checked this tile, assume that if we're still iterating, it succeeded last time
return;
}
if (tiles[x][y].Type == type)
{
visitedTiles.Add(index);
//Check adjacent tiles
GatherConnectedTilesOfType(type, x+1, y, visitedTiles);
GatherConnectedTilesOfType(type, x, y+1, visitedTiles);
GatherConnectedTilesOfType(type, x-1, y, visitedTiles);
GatherConnectedTilesOfType(type, x, y-1, visitedTiles);
}
else
{
//Don't proceed to adjacent tiles, this one doesn't match
}
}
boolean IsComplete()
{
Map<int, List<int>> connectedTiles = new HashMap<int, List<int>>();
for (int x = 0; x < width; ++x)
{
for (int y = 0; y < height; ++y)
{
int type = tiles[x][y].Type;
if (connectedTiles.containsKey(type))
{
//We've already found at least one contiguous segment of this type,
// so if this tile isn't in that segment, the type has more than
// one segment of that type
int index = IndexFromXY(x,y);
List<int> connectedTilesOfThisType = connectedTiles.get(type);
if (!connectedTilesOfThisType.contains(index))
{
return false; //More than one contiguous segment with this type
}
else
{
//Continue on - we've already covered this cell in a Gather
}
}
else
{
List<int> connectedTilesOfThisType = new ArrayList<int>();
GatherConnectedTilesOfType(type, x, y, connectedTilesOfThisType);
connectedTiles.put(type, connectedTilesOfThisType);
}
}
}
//If we get this far, we only found cells which were contiguous with cells of the same colour (and connectedTiles details the various sets)
return true;
}
get
andset
functions for your variables, use properties instead, which would be something like this: pastebin.com/1TD2BLrV Then, to access these values, you transparently usetile.x
andtile.x = something
instead oftile.getX()
andtile.setX(something)
. It looks cleaner, but works the same. \$\endgroup\$