Saya memiliki kotak ubin dengan ukuran terbatas yang diketahui yang membentuk peta. Beberapa ubin di dalam peta dimasukkan ke dalam set yang dikenal sebagai wilayah. Wilayah ini terhubung, tetapi tidak ada yang diketahui tentang bentuknya. Sebagian besar waktu akan menjadi gumpalan yang cukup teratur, tetapi bisa sangat memanjang dalam satu arah, dan bahkan berpotensi memiliki lubang. Saya tertarik menemukan perbatasan (luar) wilayah tersebut.
Yaitu, saya ingin daftar semua ubin yang menyentuh salah satu ubin di wilayah itu tanpa dirinya berada di wilayah itu. Apa cara yang efisien untuk menemukan ini?
Untuk kesulitan tambahan, kebetulan bahwa ubin saya adalah heks, tapi saya menduga ini tidak membuat banyak perbedaan, setiap ubin masih diberi label dengan bilangan bulat x dan koordinat y dan, mengingat ubin, saya dapat dengan mudah menemukan tetangganya. Berikut adalah beberapa contoh: Hitam adalah wilayah, dan biru yang ingin saya temukan di perbatasan.
Ini sendiri, bukan masalah yang sulit, Satu algoritma sederhana untuk ini, dalam pseudo-python, adalah:
def find_border_of_territory(territory):
border = []
for tile in territory:
for neighbor in tile.neighbors():
if neighbor not in territory and neighbor not in border:
border.add(neighbor)Namun ini lambat dan saya ingin sesuatu yang lebih baik. Saya memiliki O (n) loop di atas wilayah, loop lain (yang pendek, tapi masih) di atas semua tetangga, dan kemudian saya harus memeriksa keanggotaan lebih dari dua daftar, yang salah satunya berukuran n. Itu memberikan skala O yang mengerikan (n ^ 2). Saya dapat menguranginya menjadi O (n) dengan menggunakan set alih-alih daftar untuk perbatasan dan wilayah sehingga keanggotaan cepat untuk memeriksa, tetapi masih tidak bagus. Saya berharap akan ada banyak kasus di mana wilayahnya besar tetapi perbatasannya kecil karena area sederhana vs penskalaan garis. Misalnya jika wilayah tersebut adalah heksa jari-jari 5, ukurannya 91 tetapi batasnya hanya ukuran 36.
Adakah yang bisa mengusulkan sesuatu yang lebih baik?
Edit:
Untuk menjawab beberapa pertanyaan di bawah ini. Wilayah ini dapat berkisar dalam ukuran, dari sekitar 20 hingga 100 atau lebih. Himpunan ubin yang membentuk wilayah adalah atribut dari suatu objek, dan objek inilah yang membutuhkan serangkaian semua ubin perbatasan.
Awalnya wilayah itu dibuat sebagai blok, dan kemudian sebagian besar mendapatkan ubin satu per satu. Dalam hal ini, memang benar bahwa cara tercepat adalah hanya dengan menjaga satu set perbatasan dan hanya memperbaruinya pada ubin yang diperoleh. Kadang-kadang perubahan besar pada wilayah mungkin terjadi - jadi itu perlu dihitung ulang sepenuhnya.
Saya sekarang berpendapat bahwa melakukan algoritma pencarian perbatasan sederhana adalah solusi terbaik. Satu-satunya kompleksitas tambahan yang timbul adalah untuk memastikan bahwa perbatasan dihitung ulang setiap kali mungkin perlu, tetapi tidak lebih dari itu. Saya cukup yakin bahwa ini dapat dilakukan dengan andal dalam kerangka kerja saya saat ini.
Adapun waktu, dalam kode saya saat ini, saya memiliki beberapa rutinitas yang perlu memeriksa setiap ubin wilayah. Tidak setiap belokan, tetapi pada penciptaan dan kadang-kadang sesudahnya. Itu membutuhkan lebih dari 50% dari waktu berjalan sesuai kode tes saya meskipun itu adalah bagian yang sangat kecil dari program lengkap. Karena itu saya ingin meminimalkan pengulangan. NAMUN, kode tes melibatkan lebih banyak pembuatan objek daripada menjalankan normal program (secara alami), jadi saya menyadari ini mungkin tidak terlalu relevan.
sumber
Jawaban:
Menemukan algoritma biasanya paling baik dilakukan dengan struktur data yang membuat algoritma mudah.
Dalam hal ini, wilayah Anda.
Wilayah harus berupa kumpulan batas dan elemen yang tidak teratur (O (1)).
Setiap kali Anda menambahkan elemen ke wilayah, Anda beralih ke ubin yang berdekatan dan melihat apakah mereka harus ubin perbatasan; dalam hal ini, mereka adalah ubin batas jika mereka bukan ubin elemen.
Setiap kali Anda mengurangi elemen dari wilayah, Anda memastikan bahwa ubin yang berdekatan masih berada di wilayah tersebut, dan Anda melihat apakah diri Anda harus menjadi ubin perbatasan. Jika Anda ingin ini cepat, minta ubin perbatasan melacak "jumlah yang berdekatan".
Ini membutuhkan O (1) berfungsi setiap kali Anda menambah atau menghapus ubin ke atau dari suatu wilayah. Mengunjungi perbatasan membutuhkan O (panjang perbatasan). Selama Anda ingin tahu "apa perbatasannya" secara signifikan lebih sering daripada Anda menambahkan / menghapus elemen dari wilayah, ini harus menang.
sumber
Jika Anda perlu menemukan tepi lubang di tengah-tengah wilayah Anda juga, maka linier Anda di area batas wilayah adalah yang terbaik yang bisa kami lakukan. Setiap ubin di interior berpotensi menjadi lubang yang perlu kita hitung, jadi kita perlu melihat setiap ubin di area yang dibatasi oleh garis besar wilayah setidaknya sekali untuk memastikan kita telah menemukan semua lubang.
Tetapi jika Anda hanya ingin menemukan perbatasan luar (bukan lubang interior), maka kita dapat melakukan ini sedikit lebih efisien:
Temukan satu sisi yang memisahkan wilayah Anda. Anda dapat melakukannya dengan ...
(jika Anda tahu setidaknya satu petak wilayah, dan tahu bahwa Anda memiliki tepat satu gumpalan wilayah yang terhubung di peta Anda)
... mulai dari ubin sewenang-wenang di wilayah Anda, dan bergerak ke tepi terdekat peta Anda. Saat Anda melakukannya, ingat tepi terakhir tempat Anda beralih dari ubin wilayah ke ubin non-wilayah. Setelah Anda menyentuh tepi peta, tepi yang diingat ini adalah tepi awal Anda.
Pemindaian ini linear dalam diameter peta.
atau (jika Anda tidak tahu di mana ubin wilayah Anda sebelumnya, atau peta Anda mungkin berisi beberapa wilayah yang terputus)
... mulai dari tepi peta Anda, pindai di sepanjang setiap baris sampai Anda menekan ubin medan. Tepi terakhir yang Anda lintasi dari non-medan ke medan adalah tepi awal Anda.
Pemindaian ini mungkin paling buruk linier di area peta (kuadrat dengan diameternya), tetapi jika Anda memiliki batas untuk membatasi pencarian Anda (katakanlah, Anda tahu wilayah hampir selalu melintasi baris tengah) Anda dapat meningkatkan terburuk ini- perilaku kasus.
Mulai dari tepi awal Anda ditemukan di langkah 1, ikuti di sekeliling perimeter medan Anda, tambahkan setiap ubin non-medan di luar ke koleksi perbatasan Anda, hingga Anda kembali ke tepi awal.
Langkah mengikuti-tepi ini linear dalam garis keliling medan Anda, bukan bidangnya. Kelemahannya adalah bahwa kode ini lebih rumit karena Anda perlu memperhitungkan setiap jenis putaran yang dapat dilakukan, dan menghindari penghitungan ganda ubin perbatasan di lubang masuk.
Jika contoh Anda mewakili ukuran data Anda yang sebenarnya dalam beberapa urutan besarnya, maka saya sendiri akan pergi untuk pencarian area naif - itu masih akan sangat cepat pada sejumlah kecil ubin, dan secara substansial lebih mudah untuk menulis , pahami, dan pelihara (biasanya mengarah ke lebih sedikit bug!)
sumber
Perhatikan : Apakah ubin berada pada batas atau tidak hanya tergantung padanya dan tetangganya.
Karena itu:
Mudah menjalankan kueri ini dengan malas. Misalnya: Anda tidak perlu mencari batas pada seluruh peta, hanya pada apa yang terlihat.
Mudah menjalankan kueri ini secara paralel. Bahkan, saya bisa gambar beberapa kode shader yang melakukan ini. Dan jika Anda membutuhkannya untuk visualisasi lain, Anda dapat membuat tekstur dan menggunakannya.
Jika ubin berubah, batas hanya berubah secara lokal, yang berarti Anda tidak perlu menghitung semuanya lagi.
Anda juga bisa menghitung batas terlebih dahulu. Artinya, jika Anda mengisi hex, Anda dapat memutuskan apakah ubin batas pada saat itu. Itu berarti:
Jangan gunakan daftar untuk batas. Gunakan satu set jika Anda benar-benar harus ( saya tidak tahu untuk apa batasnya. ). Namun, jika Anda membuat ubin apa pun yang merupakan batas atau bukan atribut ubin maka Anda tidak harus pergi ke struktur data lain untuk memeriksa.
sumber
Pindahkan area Anda ke atas satu ubin, lalu ke kanan, lalu ke bawah kanan, dll. Setelah itu hapus area asli.
Menggabungkan semua enam set harus O (n), menyortir O (n.log (n)), mengatur perbedaan O (n). Jika ubin asli disimpan dalam beberapa format yang diurutkan, himpunan yang digabungkan dapat diurutkan dalam O (n) juga.
Saya tidak berpikir ada algoritma dengan kurang dari O (n), karena Anda perlu mengakses setiap ubin setidaknya sekali.
sumber
Saya baru saja menulis posting blog tentang bagaimana melakukan ini. Ini menggunakan metode pertama yang disebutkan @DMGregory dimulai dengan sel tepi dan berbaris di sekeliling. Itu dalam C # bukan Python tetapi harus cukup mudah untuk beradaptasi.
https://dillonshook.com/hex-city-borders/
sumber
POST ASLI:
Saya tidak dapat mengomentari situs ini jadi saya akan mencoba menjawab dengan algoritma pseudocode.
Anda tahu setiap wilayah memiliki paling tidak enam tetangga yang merupakan bagian dari perbatasan. Untuk setiap ubin di wilayah itu, tambahkan enam ubin tetangga ke daftar perbatasan potensial. Kemudian kurangi setiap ubin di wilayah dari perbatasan dan Anda hanya memiliki ubin perbatasan. Ini akan bekerja paling baik jika Anda menggunakan set yang tidak terurut untuk menyimpan setiap daftar. Semoga saya bisa membantu.
EDIT Ada banyak cara yang lebih efektif daripada iterasi sederhana. Ketika saya mencoba untuk menyatakan jawaban saya (sekarang dihapus) di bawah ini, Anda dapat mencapai O (1) dalam kasus terbaik dan O (n) dalam kasus terburuk.
Menambahkan ubin ke wilayah O (1) - O (N):
Dalam hal tidak ada tetangga, Anda cukup membuat wilayah baru.
Dalam hal satu tetangga Anda menambahkan ubin baru ke wilayah yang ada.
Dalam kasus 5 atau 6 tetangga Anda tahu semuanya terhubung, jadi Anda menambahkan ubin baru ke wilayah yang ada. Ini semua adalah operasi O (1), dan memperbarui wilayah perbatasan yang baru adalah O (1) juga, karena ini merupakan gabungan sederhana dari satu set dengan yang lain.
Dalam hal 2, 3, atau 4 wilayah tetangga, Anda mungkin harus menggabungkan hingga 3 wilayah unik. Ini adalah O (N) pada ukuran wilayah gabungan.
Menghapus ubin dari wilayah O (1) - O (N):
Dengan nol tetangga menghapus wilayah itu. O (1)
Dengan satu tetangga menghapus ubin dari wilayah tersebut. O (1)
Dengan dua atau lebih tetangga, hingga 3 wilayah baru dapat dibuat. Ini adalah O (N).
Saya menghabiskan waktu luang saya selama beberapa minggu terakhir mengembangkan program demonstrasi yang merupakan permainan wilayah sederhana berbasis hex. Cobalah untuk meningkatkan penghasilan Anda dengan menempatkan wilayah di samping satu sama lain. 3 pemain, Merah, Hijau, dan Biru bersaing untuk menghasilkan pendapatan terbanyak dengan menempatkan ubin secara strategis di bidang permainan terbatas.
Anda dapat mengunduh game di sini (dalam format .7z) hex.7z
Kontrol mouse sederhana LMB menempatkan ubin (hanya dapat menempatkan tempat yang disorot dengan kursor). Skor di atas, penghasilan di bawah. Lihat apakah Anda dapat menemukan strategi yang efektif.
Kode dapat ditemukan di sini:
Elang / Elang
Untuk membangun dari kode sumber Anda perlu Elang dan Allegro 5. Keduanya membangun dengan cmake. Hex game dibangun dengan proyek CB saat ini.
Balikkan suara-suara itu. :)
sumber