Cara tercepat untuk mengelompokkan unit yang dapat saling melihat?

Dalam game 2D yang saya kerjakan, mesin game dapat memberi saya, untuk setiap unit, daftar unit lain yang berada dalam jangkauan pandangannya.

Saya ingin tahu apakah ada algoritma yang ditetapkan untuk mengurutkan unit dalam kelompok , di mana setiap kelompok akan ditentukan oleh semua unit yang "terhubung" satu sama lain (bahkan melalui yang lain).

Contoh mungkin membantu memahami pertanyaan dengan lebih baik (E = musuh, O = unit sendiri). Pertama data yang akan saya dapatkan dari mesin game:

E1 can see E2, E3, O5
E2 can see E1
E3 can see E1
E4 can see O5
E5 can see O2
E6 can see E7, O9, O1
E7 can see E6
O1 can see E6
O2 can see O5, E5
O5 can see E1, E4, O2
O9 can see E6

Maka saya harus menghitung kelompok sebagai berikut:

G1 = E1, E2, E3, E4, E5, O2, O5
G2 = O1, O9, E6, E7

Dapat diasumsikan dengan aman bahwa ada properti komutatif untuk bidang pandang: [jika A melihat B, maka B melihat A].

Hanya untuk memperjelas: Saya sudah menulis implementasi naif yang berulang pada setiap baris info mesin gim, tetapi dari tampilan itu, tampaknya masalah yang cukup umum untuk dipelajari secara mendalam dan memiliki berbagai algoritma yang telah mapan (mungkin lewat melalui beberapa struktur seperti pohon?). Masalah saya adalah bahwa saya tidak dapat menemukan cara untuk menggambarkan masalah saya yang mengembalikan hit google yang bermanfaat.

Terima kasih sebelumnya atas bantuan Anda!

Jika hubungan "dapat melihat" Anda simetris, sehingga "A dapat melihat B" menyiratkan "B dapat melihat A", maka grup yang ingin Anda hitung adalah komponen yang terhubung dari grafik yang ditentukan oleh hubungan "bisa melihat". Seperti yang telah dicatat orang lain, ada algoritma sederhana untuk menghitung ini, seperti:

while ungrouped units remain:
    let u = arbitrary ungrouped unit
    let g = new group
    let s = temporary stack
    assign u to g
    push u onto s
    while s is not empty:
        let v = topmost unit in s
        remove v from s
        for each unit w that v can see:
            if w is ungrouped:
                assign w to g
                push w onto s
            end if
        end for
    end while
 end while

(Sebuah antrian atau koleksi lain yang secara efisien mengimplementasikan operasi "tambah elemen baru" dan "hapus dan kembalikan beberapa elemen" dapat digunakan sebagai pengganti tumpukan di satas.)

Jika hubungan "bisa melihat" Anda tidak simetris, Anda perlu memutuskan apakah Anda ingin grup Anda menjadi komponen yang kuat atau lemah . Untuk komponen yang terhubung lemah, algoritma di atas akan berfungsi apa adanya, kecuali bahwa baris for each unit w that v can seeharus diganti for each unit w that can see v, or that v can see. Untuk komponen yang sangat terhubung , Anda dapat menggunakan salah satu algoritma ( Kosaraju , Tarjan atau Gabow ) yang disebutkan di halaman Wikipedia yang ditautkan.

Untuk hubungan non-simetris, Anda mungkin juga ingin menghitung penutupan transitif dari relasi, atau komponen-komponennya yang sangat terhubung. Untuk ini, Anda dapat menggunakan algoritma Floyd-Warshall ; lihat jawaban ini pada SO untuk (sedikit) informasi lebih lanjut.

Ps. Karena artikel Wikipedia yang saya tautkan dengan catatan di atas, mungkin lebih efisien untuk memperbarui grup secara dinamis karena perubahan relasi visibilitas. Saya tidak terbiasa dengan algoritme lanjutan (?) Yang disebutkan di Wikipedia, tetapi tidak semestinya sulit untuk menyatukan sesuatu yang setidaknya mengalahkan ketukan ulang grup dari awal setiap kali.

Separuh dari ini mudah: jika dua unit dalam kelompok yang berbeda memperoleh garis pandang di antara mereka, gabungkan kelompok. Berurusan dengan unit yang kehilangan pandangan satu sama lain sedikit lebih rumit; satu solusi sederhana tapi mungkin tidak optimal adalah menjalankan kembali algoritma pengelompokan untuk unit-unit dalam kelompok yang terkena dampak kapan pun itu terjadi. Ada beberapa optimasi yang dapat Anda lakukan untuk itu, jika perubahan visibilitas terjadi satu pasang unit sekaligus:

• Jika sebuah unit hanya bisa melihat satu unit lain, dan kehilangan pandangan, cukup keluarkan saja dari grup sebelumnya dan tetapkan ke grup baru.
• Kalau tidak, Anda bisa mulai dari salah satu unit yang terpengaruh dan menjalankan pencarian A * pada grafik visibilitas (menggunakan mis. Jarak garis lurus sebagai heuristik) untuk unit lainnya. Jika Anda menemukannya, grup tidak putus; jika tidak, kumpulan unit yang dikunjungi akan membentuk grup baru.
• Anda dapat mencoba menebak yang mana dari dua unit yang lebih mungkin untuk menjadi bagian dari kelompok yang lebih kecil, jika itu terbagi, dan memulai pencarian dari unit itu. Satu kemungkinan adalah untuk selalu mulai dari unit yang secara langsung dapat melihat lebih sedikit unit lainnya.

Apa yang Anda miliki adalah grafik konektivitas. Dan umumnya, cara terbaik untuk mengelompokkan node yang terhubung (yaitu: karakter) bersama-sama adalah dengan algoritma pencarian grafik. Kedalaman-pertama, luas-pertama, mana saja. Yang Anda lakukan hanyalah membuat daftar node yang dapat dijangkau dari yang lainnya. Selama grafik Anda tidak diarahkan (jika A terlihat ke B, maka B terlihat ke A), ini berfungsi dengan baik.

Mungkin ada beberapa algoritma untuk meningkatkan ini untuk kasus-kasus tertentu. Misalnya, jika terkadang karakter tidak bergerak (dan medan tidak bergerak juga, sehingga karakter tidak bergerak tetap terlihat) maka Anda dapat memilih untuk tidak mengujinya lagi untuk memperbarui grafik konektivitas mereka.

Namun secara umum, Anda harus menguji ulang visibilitas setiap frame. Kemungkinannya, itu akan lebih lambat daripada grafik traversal untuk menemukan grup visibilitas.

Sepertinya masalah konektivitas grafik standar. Mungkin ada semacam algoritma untuk ini, dan mungkin terlihat seperti berikut:

remaining units = all units
for each unit in remaining units:
    current group = create a new group
    add this unit to current group
    for each unit visible to this unit:
        if unit is in a group already:
            merge current group into that existing group
            set current group as that existing group
        else:
            remove that unit from remaining units
            add that unit to current group

Saya berharap dimungkinkan untuk mengimplementasikan ini melalui pohon, seperti pengelompokan hierarkis, tapi saya ragu itu akan bekerja lebih cepat - pohon cenderung menjadi O (log N) sedangkan sebagian besar cek yang saya berikan di atas dapat diimplementasikan sebagai O (1) .

Saya setuju dengan semua orang lain yang menanggapi dalam hal ini menjadi masalah konektivitas grafik, namun izinkan saya menunjukkan bahwa apa yang Anda butuhkan di sini adalah Triangulasi Delaunay grafik dihasilkan dari semua unit Anda yang relevan. Apa yang dilakukan adalah memastikan bahwa hanya unit yang paling dekat satu sama lain yang akan terhubung dalam grafik yang Anda hasilkan. Anda akan merasa sangat sulit untuk melakukan hal ini dengan cara lain, karena penyeberangan grafik (non-planaritas) akan menyebabkan unit terlalu jauh satu sama lain untuk tidak terhubung dengan benar dalam grafik.

Di atas hanya berlaku jika Anda menggunakan ruang kontinu (seperti pada sebagian besar FPS gerakan bebas); namun jika Anda sudah memiliki kisi dasar (grafik planar) tempat unit Anda bergerak, maka Anda bisa menggunakannya untuk mengevaluasi konektivitas saja.