Algoritma untuk menyebarkan label dengan cara yang menarik secara visual dan intuitif

24

Versi pendek

Apakah ada pola desain untuk mendistribusikan label kendaraan dengan cara yang tidak tumpang tindih, menempatkannya sedekat mungkin dengan kendaraan yang dimaksud? Jika tidak, adakah metode yang saya sarankan dapat digunakan? Bagaimana Anda menerapkannya sendiri?

Versi diperpanjang

Dalam game yang saya tulis ini, saya memiliki visi mata-burung dari kendaraan udara saya. Saya juga memiliki label kecil dengan kunci-data di samping masing-masing kendaraan. Ini adalah tangkapan layar aktual:

Dua kendaraan dengan label mereka

Sekarang, karena kendaraan bisa terbang di ketinggian yang berbeda, ikon mereka bisa tumpang tindih. Namun saya tidak ingin label mereka tumpang tindih (atau label dari kendaraan 'A' tumpang tindih dengan ikon kendaraan 'B').

Saat ini, saya dapat mendeteksi tabrakan antara sprite dan saya cukup menjauhkan label yang menyinggung ke arah yang berlawanan dengan sprite yang tumpang tindih . Ini berfungsi dalam sebagian besar situasi, tetapi ketika wilayah udara penuh sesak, label dapat didorong sangat jauh dari kendaraannya, bahkan jika ada alternatif "cerdas" alternatif. Misalnya saya mendapatkan:

  B - label
A -----------label
  C - label

di mana akan lebih baik (= label lebih dekat ke kendaraan) untuk mendapatkan:

          B - label
label - A
          C - label

EDIT: Ini juga harus dipertimbangkan bahwa di samping kasus kendaraan yang tumpang tindih, mungkin ada konfigurasi lain di mana label kendaraan bisa tumpang tindih (contoh ASCII-art menunjukkan misalnya tiga kendaraan yang sangat dekat di mana label Aakan tumpang tindih dengan ikon Bdan C).

Saya punya dua ide tentang bagaimana memperbaiki situasi saat ini, tetapi sebelum menghabiskan waktu untuk mengimplementasikannya, saya berpikir untuk meminta saran kepada masyarakat (setelah semua itu kelihatannya seperti "masalah yang cukup umum" sehingga pola desain untuk itu bisa ada).

Untuk apa nilainya, inilah dua ide yang saya pikirkan:

Slot-isasi ruang label

Dalam skenario ini saya akan membagi semua layar menjadi "slot" untuk label. Kemudian, setiap kendaraan akan selalu menempatkan labelnya di tempat kosong terdekat (kosong = tidak ada sprite lain di lokasi itu).

Pencarian spiral

Dari lokasi kendaraan di layar, saya akan mencoba untuk menempatkan label pada sudut yang meningkat dan kemudian pada peningkatan radius, sampai lokasi yang tidak tumpang tindih ditemukan. Sesuatu di baris:

try 0°, 10px
try 10°, 10px
try 20°, 10px
...
try 350°, 10px
try 0°, 20px
try 10°, 20px
...
Mac
sumber
1
Berapa banyak pesawat yang mungkin tumpang tindih pada satu waktu?
Wangburger
1
@wangburger - Tidak pernah berpikir ini akan relevan (akan tertarik untuk mengetahui lebih banyak tentang garis pemikiran Anda), tetapi jawabannya adalah: itu tergantung dari strategi permainan pemain. Secara teknis dunia bisa memiliki 24 kendaraan yang tumpang tindih, tetapi angka yang realistis di sebagian besar kondisi permainan adalah 3-4.
mac
3
Bukankah lebih membingungkan untuk memiliki label yang bergerak relatif terhadap pesawat daripada yang tumpang tindih tetapi statis untuk jangka waktu yang wajar?
Maik Semder
3
Anda mungkin tertarik pada en.wikipedia.org/wiki/… - ini bukan masalah yang mudah untuk dipecahkan. Jangan berharap menemukan solusi yang sempurna.
Blecki
2
GraphViz adalah seperangkat alat untuk meletakkan grafik dengan cara yang menyenangkan secara visual, dengan kecenderungan untuk menghindari tumpang tindih dalam label. Meskipun mungkin tidak dapat digunakan secara langsung, Anda mungkin dapat mengumpulkan beberapa informasi dari dokumentasi atau kode sumber mereka tentang jenis algoritma apa yang mereka gunakan untuk mengatur grafik mereka. Mereka tampaknya memiliki model berbasis energi dan model berbasis pegas, misalnya.
Lars Viklund

Jawaban:

14

Pada dasarnya masalah ini mirip dengan masalah penghindaran tabrakan. Ya, pesawat bisa terbang di ketinggian berbeda, tetapi label mereka semua pada "ketinggian" yang sama.

Ada algoritma seperti Unaligned Collision Avoidance , yang akan menjadi langkah ke arah yang tepat untuk Anda. Tentu saja untuk situasi Anda, label "ditambatkan" ke pesawat mereka, sehingga mereka memiliki rentang gerakan terbatas.

Jika Anda melihat Perilaku Berkelompok , Anda ingin menerapkan "aturan" pertama dalam berkelompok: tolakan jarak pendek. Namun, alih-alih "mengarahkan" ke arah yang jauh dari tetangga terdekat, Anda akan menggunakan vektor "jauh" sebagai lokasi penempatan label Anda.

Sebagai contoh:

masukkan deskripsi gambar di sini

Lingkaran hitam besar mewakili area pengaruh Anda, lingkaran hijau mewakili penempatan yang valid untuk label, titik hijau tengah adalah bidang yang saat ini Anda pertimbangkan, titik hijau kecil adalah titik pada lingkaran yang dipilih untuk penempatan label.

Sekarang titik-titik hitam bisa mewakili label lain, atau bidang lain. Saya tidak yakin yang mana yang akan bekerja paling baik, Anda mungkin mendapatkan penghindaran yang lebih baik jika mereka label lain, tapi saya tidak yakin. Jelas panah "force" adalah vektor arah antara pesawat Anda saat ini dan "objek pengaruh". Akhirnya, kotak adalah labelnya.

Jadi menggunakan contoh Anda di atas, saya pikir ini akan menghasilkan sesuatu seperti:

            - label
           / 
          B 
label - A
          C 
           \
            - label

Menggunakan metode ini ada beberapa situasi Anda harus membuat kasus khusus, seperti tiga pesawat sejajar secara vertikal:

          - label       label -
          |                   |
          B                   B
  label - A                   A - label
          C                   C
          |                   |
          - label       label -

Ketiga label dapat flip flop dari kanan ke kiri, tergantung pada bagaimana Anda menentukan sudut label Anda. Pada dasarnya, Anda hanya perlu berhati-hati terhadap sudut-sudut di sekitar lingkaran tempat label Anda dapat beralih dari sudut mana mereka diambil: 0, 90, 180, 270.

masukkan deskripsi gambar di sini

Saya pikir pada akhirnya, ini akan terlihat agak rapi, menonton label saling menghindari. Jika terlalu mengganggu, mungkin Anda bisa membulatkan ke 10 derajat terdekat untuk gerakan yang kurang sering.

Maaf untuk detail aneh, sebagian besar dari hal ini saya pikirkan ketika saya membuat menu radial untuk permainan saya, tapi saya pikir dalam bentuk "dinamis" ini akan bekerja dengan cukup baik.

MichaelHouse
sumber
1
Sebenarnya contoh saya bahkan tidak memperhitungkan pesawat akun yang langsung di atas satu sama lain, karena dalam koordinat x dan z mereka sama persis (tetapi jika Anda menggunakan pelampung ini kemungkinan tidak akan terjadi). Contoh yang saya berikan adalah pesawat yang saling berdekatan. Selain itu, Anda bisa, seperti yang saya katakan, memikirkan titik-titik hitam pada gambar di atas sebagai label lain.
MichaelHouse
1
Oh, sepertinya Anda menghapus komentar Anda?
MichaelHouse
1
Apa yang saya maksudkan dengan komentar saya sebelumnya [yang dirumuskan dengan buruk dan sekarang dihapus], adalah bahwa Anda dapat memiliki skenario di mana label "terperangkap / dikelilingi" oleh sprite-sprite yang tidak dapat dipindahkan (kendaraan). Dalam hal ini label mungkin harus "melompat" di luar lingkaran penutup, tetapi tidak jelas bagi saya bagaimana ini harus terjadi. BTW: Saya awalnya berpikir bahwa titik hijau gambar Anda adalah beberapa pesawat ditumpuk satu di atas yang lain, tetapi setelah komentar Anda, saya menyadari saya salah ... maaf!).
mac
1
Ah, begitu. Jadi, Anda akan memperlakukan titik-titik hitam sebagai pesawat DAN label itu. Jika posisi yang ditemukan oleh iterasi pertama tidak baik, gandakan jari-jari dan periksa lagi. Atau Anda sudah memiliki vektor yang menunjukkan jauh dari mayoritas orang banyak, Anda bisa mengikuti itu sampai Anda menemukan tempat yang berfungsi. Namun saya pikir metode pertama akan memiliki hasil yang lebih baik.
MichaelHouse
9

Setelah beberapa pemikiran, saya akhirnya memutuskan untuk menerapkan metode pencarian spiral yang saya jelaskan secara singkat dalam pertanyaan asli.

Alasannya adalah bahwa metode Byte56 membutuhkan perawatan khusus untuk kondisi tertentu, sedangkan pencarian spiral tidak, dan kode dengan cara yang sangat kompak . Juga, pencarian spriralling menekankan menemukan tempat yang lebih dekat ke kendaraan untuk menempatkan label, yang IMO adalah faktor utama dalam membuat peta dapat dibaca.

Namun tolong terus upvote jawabannya, karena ini tidak hanya berguna, tetapi juga ditulis dengan sangat baik!

Berikut screenshot dari hasil yang dicapai dengan kode spiral:

masukkan deskripsi gambar di sini

Dan inilah kode yang - meskipun tidak mandiri - memberikan ide tentang seberapa sederhana implementasinya:

def place_tags(self):
    for tag in self.tags:
        start_angle = tag.angle
        while not tag.place() or is_colliding(tag):  #See note n.1
            tag.angle = (tag.angle + angle_step) % 360
            if tag.angle == start_angle:
                tag.radius += radius_step
        tag.connector.update()                       #See note n.2

Catatan 1 - tag.place()mengembalikan True jika tag sepenuhnya pada area layar / radar yang terlihat. Jadi baris itu berbunyi seperti "terus berputar jika tag berada di luar radar atau tumpang tindih dengan yang lain ..."

Catatan 2 - tag.connector.updateadalah metode yang menggambar garis yang menghubungkan ikon pesawat ke label / tag dengan informasi teks.

Mac
sumber
Bagus sekali, itu memang sangat kompak. Terima kasih atas pujiannya. Juga terima kasih telah memposting tentang apa yang akhirnya Anda lakukan, itu selalu berguna untuk orang yang mencari jawaban nanti. Dari tangkapan layar sepertinya itu bekerja dengan sangat baik! Pastikan untuk menerima jawaban Anda, karena itulah yang akhirnya Anda terima.
MichaelHouse
@ Byte56 - Terima kasih untuk "retro-pujian";) Saya menunggu untuk memilih jawaban yang diterima karena saya masih ingin kode solusi Anda juga dan bandingkan hasilnya. Pertama, saya menduga bahwa solusi Anda dapat menghasilkan kode yang lebih lama tetapi juga lebih cepat untuk dieksekusi. Juga, saya ingin melihat bagaimana keduanya membandingkan di wilayah udara yang sangat padat ... jadi masih ada kemungkinan saya bisa merilis kode dengan algoritma Anda. Perhatikan ruang ini! ;)
mac
@ Byte56 - Saya mencoba menerapkan algoritma Anda. Ini bekerja dengan baik dan cepat dalam kepadatan rendah, tetapi segera setelah ruang penuh, saya punya masalah dalam menemukan implementasi langsung yang akan mengelola situasi tertentu di mana label harus "melompat" ke blok label lain atau terjebak oleh non- sprite bergerak (yaitu ikon pesawat). Saya menandai jawaban ini sebagai yang dipilih saat itu, tetapi sekali lagi: terima kasih banyak atas waktu dan kontribusinya! :)
mac