Is there an algorithm to detect the “mainland” on a 2D map?

Question

On this map, the "mainland" is all the land that can be connected to the center of the map in the four cardinal directions (north, south, east, west -- not diagonally).

I would like to detect the mainland and fill the holes in it. I thought of three things:

1. Search in every non-water (dark cells) cell if can be connected to the center of the map using a path finding algorithm. Too expensive! But this could work for the islands.

2. The mainland is filled with a bucket of green paint. Each hole is surrounded by paint... now what? If i check every water point inside the mainland for adjacency i'll delete some peninsulas and other geographical features displayed on the shoreline.

3. Some kind of edge detection to figure out the mainland. Keep whatever is inside, fill it if it's water, remove what's outside. Complex?

Perhaps some game experienced developer can help me out with this, possibly giving me the name of some known algorithm or technique?

Answer 1

Removing Islands

I've done this sort of thing before in one of my games. To get rid of outer islands, the process was basically:

1. First there must be a guarantee the center of the map will always belong to the main land, and each pixel starts out either as "Land" or "Water" (i.e. different colors).
2. Then do a four direction flood fill starting from the center the map and spreading throughout any "Land" tiles. Mark every pixel visited by this flood fill as a different type such as "MainLand".
3. Finally go over the entire map and convert any remaining "Land" pixel to "Water to get rid of other islands.

Removing Lakes

As for getting rid of the holes (or lakes) inside the island, you do a similar process but starting from the corners of the map and spreading through "Water" tiles instead. This will allow you to distinguish the "Sea" from the other water tiles, and then you can get rid of them just like you got rid of the islands before.

Example

Let me dig up my implementation of the flood fill that I have here somewhere (disclaimer, I didn't care about efficiency, so I'm sure there are many more efficient ways to implement it):

private void GenerateSea()
{
    // Initialize visited tiles list
    visited.Clear();

    // Start generating sea from the four corners
    GenerateSeaRecursive(new Point(0, 0));
    GenerateSeaRecursive(new Point(size.Width - 1, 0));
    GenerateSeaRecursive(new Point(0, size.Height - 1));
    GenerateSeaRecursive(new Point(size.Width - 1, size.Height - 1));
}

private void GenerateSeaRecursive(Point point)
{
    // End recursion if point is outside bounds
    if (!WithinBounds(point)) return;

    // End recursion if the current spot is a land
    if (tiles[point.X, point.Y].Land) return;

    // End recursion if this spot has already been visited
    if (visited.Contains(point)) return;

    // Add point to visited points list
    visited.Add(point);

    // Calculate neighboring tiles coordinates
    Point right = new Point(point.X + 1, point.Y);
    Point left = new Point(point.X - 1, point.Y);
    Point up = new Point(point.X, point.Y - 1);
    Point down = new Point(point.X, point.Y + 1);

    // Mark neighbouring tiles as Sea if they're not Land
    if (WithinBounds(right) && tiles[right.X, right.Y].Empty)
        tiles[right.X, right.Y].Sea = true;
    if (WithinBounds(left) && tiles[left.X, left.Y].Empty)
        tiles[left.X, left.Y].Sea = true;
    if (WithinBounds(up) && tiles[up.X, up.Y].Empty)
        tiles[up.X, up.Y].Sea = true;
    if (WithinBounds(down) && tiles[down.X, down.Y].Empty)
        tiles[down.X, down.Y].Sea = true;

    // Call the function recursively for the neighboring tiles
    GenerateSeaRecursive(right);
    GenerateSeaRecursive(left);
    GenerateSeaRecursive(up);
    GenerateSeaRecursive(down);
}

I used this as a first step to get rid of lakes in my game. After calling that, all I'd have to do was something like:

private void RemoveLakes()
{
    // Now that sea is generated, any empty tile should be removed
    for (int j = 0; j != size.Height; j++)
        for (int i = 0; i != size.Width; i++)
            if (tiles[i, j].Empty) tiles[i, j].Land = true;
}

Edit

Adding some extra information based on the comments. In case your search space is too big, you might experience a stack overflow when using the recursive version of the algorithm. Here's a link on stackoverflow (pun intended :-)) to a non recursive version of the algorithm, using a Stack<T> instead (also in C# to match my answer, but should be easy to adapt to other languages, and there are other implementations on that link too).

Answer 2

Modify the four direction flood fill algorithm http://en.wikipedia.org/wiki/Flood_fill

Answer 3

This is a standard operation in image processing. You use a two-phase operation.

Start by creating a copy of the map. From this map, turn into sea pixels all land pixels that border the sea. If you do this once, it will eliminate 2x2 islands, and shrink bigger islands. If you do it twice, it will eliminate 4x4 islands, etcetera.

In phase two, you do almost the reverse: turn into land pixels all sea pixels that border the land, but only if they were land pixels in the original map (That's why you made a copy in phase 1). This regrows islands to their original form, unless they were entirely eliminated in phase 1.

Answer 4

I had a similar issue but not in game development. I had to find pixels in an image that were adjacent to each other and had the same value (connected regions). I tried using a recursive floodfill but kept causing stack overflows (I am a novice programmer :P). Then I tried this method http://en.wikipedia.org/wiki/Connected-component_labeling it was actually much more efficient, for my problem anyway.