¿Existe un algoritmo para detectar el "continente" en un mapa 2D?

En este mapa, el "continente" es toda la tierra que se puede conectar al centro del mapa en las cuatro direcciones cardinales (norte, sur, este, oeste, no en diagonal).

Me gustaría detectar el continente y llenar los agujeros en él. Pensé en tres cosas:

1. Busque en cada celda que no sea de agua (celdas oscuras) si se puede conectar al centro del mapa utilizando un algoritmo de búsqueda de ruta. ¡Muy caro! Pero esto podría funcionar para las islas.

2. El continente está lleno de un cubo de pintura verde. Cada hoyo está rodeado de pintura ... ¿y ahora qué? Si verifico la adyacencia de cada punto de agua dentro del continente, eliminaré algunas penínsulas y otras características geográficas que se muestran en la costa.

3. Algún tipo de detección de bordes para descubrir el continente. Mantenga lo que esté adentro, llénelo si es agua, retire lo que está afuera. ¿Complejo?

¿Quizás algún desarrollador experimentado del juego pueda ayudarme con esto, posiblemente dándome el nombre de algún algoritmo o técnica conocida?

Eliminando islas

He hecho este tipo de cosas antes en uno de mis juegos. Para deshacerse de las islas exteriores, el proceso fue básicamente:

1. Primero debe haber una garantía de que el centro del mapa siempre pertenecerá a la tierra principal, y cada píxel comienza como "Tierra" o "Agua" (es decir, diferentes colores).
2. Luego haga un relleno de inundación de cuatro direcciones comenzando desde el centro del mapa y extendiéndose a través de cualquier mosaico "Tierra". Marque cada píxel visitado por este relleno de inundación como un tipo diferente, como "MainLand".
3. Finalmente, revisa todo el mapa y convierte cualquier píxel "Tierra" restante en "Agua" para deshacerte de otras islas.

Eliminar lagos

En cuanto a deshacerse de los agujeros (o lagos) dentro de la isla, se realiza un proceso similar pero desde las esquinas del mapa y se extiende a través de los mosaicos de "Agua". Esto le permitirá distinguir el "Mar" de las otras baldosas de agua, y luego podrá deshacerse de ellas tal como lo hizo antes con las islas.

Ejemplo

Permítanme desenterrar mi implementación del relleno de inundación que tengo aquí en algún lugar (descargo de responsabilidad, no me importaba la eficiencia, así que estoy seguro de que hay muchas formas más eficientes de implementarlo):

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);
}

Usé esto como un primer paso para deshacerme de los lagos en mi juego. Después de llamar a eso, todo lo que tenía que hacer era algo como:

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;
}

Editar

Agregar información adicional basada en los comentarios. En caso de que su espacio de búsqueda sea demasiado grande, puede experimentar un desbordamiento de pila al usar la versión recursiva del algoritmo. Aquí hay un enlace en stackoverflow (juego de palabras :-)) a una versión no recursiva del algoritmo, usando en su Stack<T>lugar (también en C # para que coincida con mi respuesta, pero debería ser fácil de adaptar a otros idiomas, y hay otras implementaciones en eso enlace también).

Modifique el algoritmo de relleno de inundación de cuatro direcciones http://en.wikipedia.org/wiki/Flood_fill

Esta es una operación estándar en el procesamiento de imágenes. Utiliza una operación de dos fases.

Comience creando una copia del mapa. Desde este mapa, convierta en píxeles marinos todos los píxeles terrestres que bordean el mar. Si hace esto una vez, eliminará las islas 2x2 y reducirá las islas más grandes. Si lo haces dos veces, eliminará las islas 4x4, etc.

En la fase dos, usted hace casi lo contrario: convierte en píxeles terrestres todos los píxeles marinos que bordean la tierra, pero solo si eran píxeles terrestres en el mapa original (es por eso que hizo una copia en la fase 1). Esto hace que las islas vuelvan a su forma original, a menos que se eliminen por completo en la fase 1.

Tuve un problema similar pero no en el desarrollo del juego. Tenía que encontrar píxeles en una imagen adyacentes entre sí y con el mismo valor (regiones conectadas). Intenté usar un relleno de inundación recursivo pero seguí causando desbordamientos de pila (soy un programador novato: P). Luego probé este método http://en.wikipedia.org/wiki/Connected-component_labeling, en realidad era mucho más eficiente, para mi problema de todos modos.