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

28

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). masukkan deskripsi gambar di sini

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?

Gabriel A. Zorrilla
sumber
4
Saya hanya ingin tahu apakah Anda menggunakan semacam algoritma untuk menghasilkan peta ini. Dan jika demikian, apa yang Anda gunakan?
jgallant
Layak untuk dicermati ketika bekerja di lingkungan berbasis web adalah Algoritma Marching Squares . Dengan itu Anda bisa mendeteksi dan menjaga pulau-pulau kecil juga, dan kemudian mengurutkan berdasarkan ukuran membuang pulau sel tunggal, atau kriteria apa pun yang mungkin Anda miliki.
William Mariager
@Jon ya! Algoritma diamond square menghasilkan peta ketinggian, maka semua di bawah satu nilai adalah air, sisanya, tanah. Saya berencana untuk menggunakan ini sebagai bentuk benua, lalu pass lain untuk menambahkan detail medan.
Gabriel A. Zorrilla
Algoritma Marching Squares @Mind akan berguna untuk mengecat perbatasan benua. Terima kasih saran bagus!
Gabriel A. Zorrilla

Jawaban:

32

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).

David Gouveia
sumber
11
Jika Anda tidak dapat menjamin bahwa ubin tengah akan selalu menjadi tanah dan bagian dari daratan, gunakan banjir untuk menandai setiap ubin tanah milik pulau tertentu (isi banjir dari setiap ubin tanpa gumpalan di peta, menandai ubin yang diisi dengan blobid yang sama jika belum memilikinya). Kemudian hapus semua kecuali gumpalan dengan ubin paling.
George Duckett
Sejalan dengan apa yang dikatakan GeorgeDuckett - Anda dapat mencoba algoritme deteksi gumpalan Googling: ini adalah masalah umum dalam multi-touch menggunakan FTIR. Saya ingat saya datang dengan algoritma yang lebih cerdas, tetapi saya tidak bisa mengingat bagaimana saya bekerja.
Jonathan Dickinson
Karena saya telah mengalami masalah tumpukan di PHP saya menerapkan isi banjir LIFO, bekerja dengan sangat baik.
Gabriel A. Zorrilla
Bukankah ini mengisi banjir hanya ketika algoritma DFS dipanggil dari algoritma BFS? Tolong jelaskan seseorang.
jcora
@Bane Apa maksudmu? Perbedaan antara DFS atau BFS hanyalah urutan di mana node dikunjungi. Saya tidak berpikir algoritma pengisian banjir menentukan urutan traversal - itu tidak peduli asalkan mengisi seluruh wilayah tanpa meninjau kembali node. Urutan tergantung pada implementasinya. Lihat bagian bawah entri wikipedia untuk gambar yang membandingkan urutan traversal saat menggunakan antrian versus menggunakan tumpukan. Implementasi rekursif juga dapat dianggap sebagai stack (karena menggunakan call stack).
David Gouveia
5

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.

MSalters
sumber
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.

Elegant_Cow
sumber
Anda harus mencoba versi tumpukan dari algo banjir dan menyimpan masalah tumpukan. Hasilnya menjadi jauh lebih sederhana daripada CCL (yang saya telah bekerja 2 minggu terakhir tanpa hasil.)
Gabriel A. Zorrilla
Ya saya mencoba keduanya, tetapi saya mendapatkan CCL untuk bekerja lebih dulu: P dan berpikir itu ide yang rapi. Senang Anda menyelesaikan masalah Anda :)
Elegant_Cow