Apakah ada algoritma untuk mendeteksi "daratan" pada peta 2D?

Pada peta ini, "daratan" adalah semua tanah yang dapat dihubungkan ke pusat peta dalam empat arah mata angin (utara, selatan, timur, barat - tidak secara diagonal).

Saya ingin mendeteksi daratan dan mengisi lubang di dalamnya. Saya memikirkan tiga hal:

1. Cari di setiap sel non-air (sel gelap) jika dapat dihubungkan ke pusat peta menggunakan algoritma pencarian jalur. Terlalu mahal! Tetapi ini bisa berhasil untuk pulau-pulau itu.

2. Daratan diisi dengan seember cat hijau. Setiap lubang dikelilingi oleh cat ... sekarang bagaimana? Jika saya memeriksa setiap titik air di dalam daratan untuk kedekatan saya akan menghapus beberapa semenanjung dan fitur geografis lainnya yang ditampilkan di garis pantai.

3. Beberapa jenis deteksi tepi untuk mencari tahu daratan. Simpan apa pun yang ada di dalamnya, isi jika air, lepaskan apa yang ada di luar. Kompleks?

Mungkin beberapa pengembang berpengalaman game dapat membantu saya dengan ini, mungkin memberi saya nama beberapa algoritma atau teknik yang dikenal?

Menghapus Pulau

Saya telah melakukan hal semacam ini sebelumnya di salah satu permainan saya. Untuk menghilangkan pulau-pulau terluar, prosesnya pada dasarnya adalah:

1. Pertama, harus ada jaminan bahwa pusat peta akan selalu menjadi bagian dari tanah utama, dan setiap piksel dimulai sebagai "Tanah" atau "Air" (yaitu warna yang berbeda).
2. Kemudian lakukan pengisian banjir empat arah mulai dari pusat peta dan menyebar ke seluruh ubin "Tanah". Tandai setiap piksel yang dikunjungi oleh isian banjir ini sebagai jenis berbeda seperti "MainLand".
3. Akhirnya, pergilah ke seluruh peta dan ubah piksel "Tanah" yang tersisa menjadi "Air untuk menyingkirkan pulau-pulau lain.

Menghapus Danau

Sedangkan untuk menyingkirkan lubang (atau danau) di dalam pulau, Anda melakukan proses serupa tetapi mulai dari sudut peta dan menyebar melalui ubin "Air" sebagai gantinya. Ini akan memungkinkan Anda untuk membedakan "Laut" dari ubin air lainnya, dan kemudian Anda dapat menyingkirkannya seperti Anda menyingkirkan pulau-pulau sebelumnya.

Contoh

Biarkan saya menggali implementasi pengisian banjir yang saya miliki di suatu tempat (penafian, saya tidak peduli dengan efisiensi, jadi saya yakin ada banyak cara yang lebih efisien untuk mengimplementasikannya):

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

Saya menggunakan ini sebagai langkah pertama untuk menyingkirkan danau di game saya. Setelah memanggil itu, yang harus saya lakukan adalah sesuatu seperti:

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

Menambahkan beberapa informasi tambahan berdasarkan komentar. Jika ruang pencarian Anda terlalu besar, Anda mungkin mengalami stack overflow saat menggunakan versi algoritme rekursif. Berikut ini adalah tautan pada stackoverflow (maksud kata :-)) ke versi algoritma yang tidak rekursif, menggunakan Stack<T>bukan (juga dalam C # untuk mencocokkan jawaban saya, tetapi harus mudah untuk beradaptasi dengan bahasa lain, dan ada implementasi lain pada itu tautan juga).

Ubah algoritma pengisian banjir empat arah http://en.wikipedia.org/wiki/Flood_fill

Ini adalah operasi standar dalam pemrosesan gambar. Anda menggunakan operasi dua fase.

Mulailah dengan membuat salinan peta. Dari peta ini, ubah menjadi piksel lautan semua piksel daratan yang berbatasan dengan laut. Jika Anda melakukan ini sekali, itu akan menghilangkan pulau 2x2, dan menyusut pulau-pulau yang lebih besar. Jika Anda melakukannya dua kali, itu akan menghilangkan pulau 4x4, dan sebagainya.

Pada fase dua, Anda melakukan hampir kebalikannya: berubah menjadi piksel daratan semua piksel laut yang berbatasan dengan tanah, tetapi hanya jika piksel tersebut merupakan piksel daratan di peta asli (Itulah sebabnya Anda membuat salinan di fase 1). Ini menumbuhkan kembali pulau-pulau ke bentuk aslinya, kecuali jika mereka sepenuhnya dihilangkan dalam fase 1.

Saya memiliki masalah serupa tetapi tidak dalam pengembangan game. Saya harus menemukan piksel dalam gambar yang berdekatan satu sama lain dan memiliki nilai yang sama (wilayah yang terhubung). Saya mencoba menggunakan TPA rekursif tetapi terus menyebabkan stack overflows (Saya seorang programmer pemula: P). Kemudian saya mencoba metode ini http://en.wikipedia.org/wiki/Connected-component_labeling itu sebenarnya jauh lebih efisien, untuk masalah saya.