Rute mana yang paling aman, di mana musuh terbanyak dan di mana kit P3K terdekat? Semua masalah hubungan spasial yang sering ditemui ini dapat dipecahkan secara efektif menggunakan partisi matematika yang disebut "diagram Voronoi". Dari pos ini Anda akan belajar bagaimana menganalisis kartu permainan dan menerima informasi yang memastikan realisme dan keberhasilan kecerdasan buatan.
Hubungan spasial
Hubungan spasial adalah setiap informasi yang menjelaskan bagaimana satu objek di ruang terkait dengan yang lain. Contoh: jarak di antara mereka, area yang dicakup oleh masing-masing ruang dan persimpangan dari area-area ini, jumlah objek yang terletak di satu area.
Hubungan seperti itu terus-menerus digunakan dalam gim video dan dapat memberikan informasi AI yang sangat berguna, juga bagi pemain itu sendiri.
Voronoi punya jawaban
Diagram Voronoi menggambarkan hubungan spasial antara titik yang berjarak dekat atau tetangga terdekat mereka. Ini adalah satu set poligon terhubung yang diperoleh dari titik atau lokasi. Setiap baris "area" Voronoi terletak di tengah di antara dua titik.
Untuk memahami, lihat gambar:
Seperti yang Anda lihat, setiap baris persis di tengah antara dua titik, dan semuanya terhubung di tengah. Tambahkan beberapa poin lagi ke TKP dan lihat apa yang terjadi:
Gambarnya menjadi lebih menarik! Kami sudah memiliki area nyata.
Apa yang disampaikan masing-masing area kepada kita? Kita tahu bahwa berada di area dijamin berada paling dekat dengan satu titik, yang juga ada di area tersebut. Ini memberi tahu kita banyak tentang apa yang ada di sekitarnya; seperti itulah hubungan spasial mendasar dalam diagram Voronoi.
Balikkan Voronoi: Triangulasi Delaunay
Sistem yang berlawanan dengan diagram Voronoi disebut triangulasi Delaunay. Diagram ini terdiri dari garis-garis dari setiap titik ke tetangga terdekatnya, dan setiap garis tegak lurus terhadap tepi Voronoi yang bersilangan. Begini tampilannya:
Putih menandai garis Delaunay. Setiap baris Delaunay sesuai dengan satu dan hanya satu tepi Voronoi. Pada awalnya tampak bahwa beberapa dari mereka melintasi beberapa sisi, tetapi melihat dengan seksama, Anda akan menyadari bahwa ini tidak benar.
Dalam gambar, garis Delaunay hijau sesuai dengan tulang rusuk merah muda Voronoi. Bayangkan saja iga merah muda melangkah lebih jauh dan Anda melihat bahwa mereka berpotongan.
Berkat triangulasi Delaunay, kita melihat bahwa alih-alih poligon kita sekarang memiliki banyak segitiga. Ini sangat berguna karena kami membagi area menjadi segitiga yang dapat diterjemahkan. Teknik ini dapat digunakan untuk tessellation atau triangulasi angka. Hebat!
Selain itu, ini adalah cara terbaik untuk membuat grafik dari banyak titik jika kami ingin berpindah dari satu titik ke titik lainnya. Misalnya, titik dapat menunjukkan kota.
Struktur data Voronoi
Kita sudah tahu seperti apa diagram Voronoi; Sekarang mari kita lihat bagaimana struktur datanya akan terlihat. Pertama, kita perlu menyimpan poin yang menjadi dasar diagram Voronoi:
class VoronoiPoint { float x float y VoronoiRegion* region }
Setiap
VoronoiPoint memiliki lokasi
(x, y) dan tautan ke area di mana ia berada.
Selanjutnya kita perlu menggambarkan
VoronoiRegion :
class VoronoiRegion { VoronoiPoint* point Edge *edges[]
Area menyimpan tautan ke
VoronoiPoint -
VoronoiPoint , serta daftar tepian
VoronoiEdges .
Mari kita lihat seperti apa bentuk
VoronoiEdges :
class VoronoiEdge { VoronoiPoint* pointA VoronoiPoint* pointB float distance
Tepi tahu dua titik yang mendefinisikannya, serta jarak di antara mereka. Untuk tampilan visual, serta untuk membangun bentuk wilayah poligonal, kita perlu menyimpan titik awal dan akhir tepi.
Dan itu saja. Dengan informasi ini, kita dapat dengan mudah membuat diagram Voronoi. Di bawah ini kita akan belajar bagaimana diagram Voronoi dihasilkan. Tetapi untuk sekarang, mari kita lihat beberapa contoh bagaimana data ini dapat digunakan.
Temukan lemari obat terdekat
Sekali lagi, lihat diagram Voronoi untuk poin.
Jika setiap titik menunjukkan kit pertolongan pertama, maka kita dapat dengan cepat menentukan di mana yang terdekat dengan kita, tetapi pertama-tama kita perlu menentukan area di mana kita berada. Diagram Voronoi tidak menyediakan cara yang efektif untuk mendefinisikan suatu wilayah, namun, untuk mempercepat pencarian, kita dapat menyimpan tautan ke setiap wilayah di
pohon kuadran atau di
pohon-R . Dan setelah mempelajari wilayah tersebut, kita akan dapat mengenali tetangganya, dan tetangga tetangganya.
Misalnya, jika tidak ada lagi perlengkapan P3K di daerah Anda, maka Anda perlu menemukan jalur ke yang terdekat lainnya. Dari struktur data dan pseudo-code yang ditunjukkan di atas, kita dapat memahami bahwa dengan mengetahui wilayah, kita dapat mengenali tepinya. Dan dengan bantuan tulang rusuk ini kita bisa mendapatkan tetangga. Kami akan mengambil tetangga terdekat dan melihat apakah ada kotak P3K di dalamnya.
Anda juga dapat menerapkan triangulasi Delaunay di sini. Terdiri dari garis-garis di antara kotak P3K. Kemudian Anda bisa mengatasinya menggunakan algoritma pencarian A * path untuk menemukan kit pertolongan pertama terdekat.
Cari rute yang aman
Ganti semua kotak P3K dengan menara pengawal musuh. Anda perlu menemukan rute teraman di antara mereka agar tidak tertangkap. Cara standar traversal grafik dalam gim video adalah dengan menggunakan
algoritma A * . Karena diagram Voronoi adalah grafik, sangat mudah untuk mengimplementasikan pencarian. Kami hanya memerlukan algoritma A *, yang mendukung struktur grafik umum; rencanakan ke depan dan itu akan membantu Anda di masa depan.
Setelah menyiapkan grafik, Anda perlu menetapkan bobot untuk setiap sisi. Bagi kami, nilai bobot akan menjadi jarak ke menara arloji ini, dan Anda bisa mendapatkannya langsung dari struktur data: setiap
VoronoiEdge sudah mengetahui jarak antara dua titik. Biasanya, semakin kecil nilainya di tepi A *, semakin baik, tetapi dalam kasus kami, semakin besar nilainya, karena ini menunjukkan jarak ke menara.
Seperti inilah grafik awal jika kita ingin berpindah dari titik A ke titik B:
Dengan menerapkan bobot pada setiap sisi, kita akan melihat rute mana yang lebih baik untuk dipilih:
Iga merah menunjukkan kontak terdekat dengan menara. Oranye menunjukkan yang lebih panjang; kuning bahkan lebih jauh, dan akhirnya, hijau - yang paling aman. Setelah mengeksekusi A * dengan bobot ini, kami mendapatkan jalur berikut:
Dengan penggunaan skala ini, bukan
yang tercepat , tetapi cara
teraman akan dipilih, yang kita butuhkan. AI harus mematuhi jalur ini dan tidak menyimpang darinya!
Anda dapat mengambil langkah lain untuk
menjamin jalur yang aman: menghilangkan semua tepi yang lebih dekat dari jarak aman minimum. Misalnya, jika setiap menara pengawal memiliki radius visibilitas 30 unit, maka semua tepi, jarak ke titik yang lebih pendek, dapat dihilangkan dari grafik dan tidak dilewati.
Anda juga dapat menggunakan metode ini untuk menemukan rute terluas untuk unit besar yang tidak dapat melewati kemacetan. Setiap tepi memiliki jarak antara dua titik, jadi kami tahu apakah mereka bisa lewat di ruang ini.
Anda juga dapat melakukan operasi yang berlawanan - gunakan diagram triangulasi Delaunay, dan dapatkan garis yang berasal dari setiap menara pengawas. AI penjaga akan dapat dengan cepat menentukan menara lain di dekatnya dan, jika perlu, pergi ke bantuan mereka.
Cari satu set barang yang sangat padat
Misalkan kita perlu menjatuhkan bungkusan catnip dari pesawat untuk seikat segel yang duduk di tanah. Di mana cara terbaik untuk menjatuhkannya sehingga jumlah terbesar kucing bisa menggunakannya? Ini bisa sangat mahal. Tetapi, untungnya, kita dapat membuat asumsi yang masuk akal menggunakan triangulasi Delaunay.
Petunjuk: jangan lupa bahwa triangulasi Delaunay hanyalah kebalikan dari diagram Voronoi. Itu dibentuk dengan menghubungkan setiap titik Voronoi dengan titik tetangga yang diperoleh dari daftar tepi.
Dengan koleksi segitiga ini, Anda dapat menjelajahi area yang dicakup oleh masing-masing segitiga. Jika kita menemukan segitiga dengan area terkecil, maka kita memiliki tiga titik terdekat, atau kucing. Ini mungkin bukan cluster rata-rata terpadat di permukaan, tetapi itu akan menjadi asumsi yang baik. Jika kita dapat membuang beberapa paket dengan mint, kita hanya akan menandai segitiga yang sudah dipilih dan beralih ke yang berikutnya dalam ukuran yang semakin besar.
Penunjukan bidang-bidang tersebut juga disebut
lingkaran terbatas dari triangulasi Delaunay. Setiap lingkaran adalah lingkaran terbesar yang dapat ditampung pada titik-titik segitiga. Berikut adalah gambar lingkaran terbatas untuk diagram Voronoi:
Anda dapat menggunakan pusat lingkaran yang tepat untuk menentukan pusat area tempat pengiriman catnip. Sebenarnya, jari-jari lingkaran adalah cara yang lebih cocok untuk menentukan segitiga terbaik untuk dilipat daripada luas segitiga, terutama jika dua titik segitiga sangat dekat satu sama lain dan yang ketiga jauh; lalu kita mendapatkan segitiga yang sangat tajam dengan area kecil, tetapi titik-titik yang mendefinisikannya sebenarnya sangat berjauhan.
Implementasi diagram Voronoi
Ada beberapa cara untuk menghasilkan diagram Voronoi, dan pilihan metode yang digunakan tergantung pada waktu kami menerima data.
Algoritma Keberuntungan
Cara tercepat disebut
algoritma Fortune . Ini berjalan di
O(n log(n)) dan mensyaratkan bahwa semua titik yang digunakan untuk menghasilkan grafik diketahui pada saat generasi dimulai. Jika Anda menambahkan poin baru nanti, Anda harus membuat ulang seluruh grafik. Jika ada beberapa poin, maka ini mungkin tidak menimbulkan masalah, tetapi jika Anda memiliki 100 ribu poin, maka ini bisa memakan banyak waktu!
Implementasi dari algoritma ini adalah nontrivial. Lintas parabola dan kasing khusus. Namun, ini adalah metode tercepat. Untungnya, ada banyak implementasi dari algoritma open source ini yang dapat Anda gunakan, dan saya telah memberikan tautan kepada mereka di bawah ini.
Mari kita lihat cara kerjanya.
Algoritma terdiri dalam menggeser garis (vertikal atau horizontal) di atas area dengan titik-titik. Ketika dia bertemu suatu titik, dia mulai menarik parabola darinya, yang berlanjut dengan garis menyapu. Berikut ini animasi proses ini:
Parabola yang berpotongan membentuk tulang rusuk Voronoi. Tapi mengapa parabola?
Untuk memahami hal ini, bayangkan setiap titik mengandung balon tiup yang membengkak hingga bertabrakan dengan bola lain. Anda dapat mentransfer ide ini ke lingkaran yang meluas pada bidang 2D. Kami akan membuat bola lain maju dan menempatkan di setiap titik kerucut terbalik dengan sudut kemiringan 45 derajat, meningkat hingga tak terbatas. Kemudian bayangkan sebuah garis menyapu dalam bentuk garis, juga pada 45 derajat, yang meluncur sepanjang sampai bertabrakan dengan kerucut. Karena bidang dan kerucut terletak pada sudut yang sama, ketika mereka melintas, mereka membentuk parabola.
Tumbuh, kerucut cepat atau lambat berpotongan dengan satu atau lebih kerucut lainnya. Jika kita melihat persimpangan kerucut, atau lingkaran, kita mendapatkan garis lurus tepi Voronoi. Pada gambar, garis merah menunjukkan persimpangan kerucut. Jika kerucut tumbuh lebih jauh (vertikal hingga tak terbatas), maka garis merah akan terus meregang.
Ketika pesawat meluncur dan kontak pertama dengan kerucut terjadi, garis yang dihasilkan akan seperti ini:
Dengan gerakan lebih lanjut dari pesawat di sepanjang kerucut, kita akan melihat bagaimana bentuk parabola:
Pesawat terus bergerak di sekitar tempat kejadian. Untuk setiap titik yang dihadapinya, ia memeriksa titik-titik tetangga pada garis sapuan yang sudah memiliki parabola dan memulai parabola baru pada titik itu. Dia terus bergerak dan tumbuh sampai parabola baru ini mulai tumpang tindih dengan yang parabola sebelumnya. Kemudian parabola sebelumnya ditutup. Ini adalah titik di mana garis tiga titik Voronoi bertemu.
Seperti yang dinyatakan di atas, ini cukup sulit untuk dipahami, jadi di sini ada tautan ke implementasi open source yang dapat Anda gunakan dan pelajari:
Penyisipan Segitiga Tambahan
Metode lain adalah secara bertahap memasukkan satu titik pada satu waktu, dimulai dengan segitiga dasar tiga titik di luar area yang memungkinkan dari semua titik lainnya. Metode ini berjalan dengan
O(n^2) dan tidak memerlukan semua poin pada saat generasi.
Ketika Anda memasukkan titik baru, itu mendefinisikan area yang ada di mana ia jatuh. Area ini kemudian dibagi lagi dan area baru dibuat.
Berikut ini adalah contoh sumber terbuka untuk digunakan dan dipelajari:
Kesimpulan
Sekarang Anda harus membayangkan apa yang bisa diberikan diagram Voronoi pada gim Anda dan AI-nya. Jika Anda memiliki grafik node dan pinggiran yang terstruktur dengan baik, Anda dapat meminta informasi penting sehingga semua orang mendapatkan peralatan P3K, catnip, dan melewati menara musuh.