Pekan lalu, kami berbicara di blog kami tentang perubahan yang akan memungkinkan musuh (biters) tidak saling bertemu, tapi ini bukan satu-satunya pembaruan yang terkait dengan biters. Secara kebetulan, pembaruan minggu ini mencakup apa yang kami kerjakan selama beberapa minggu sebelumnya - memperbarui sistem pencarian musuh.
Cari cara
Ketika sebuah unit ingin pindah ke suatu tempat, pertama-tama perlu memahami bagaimana menuju ke sana. Dalam kasus yang paling sederhana, Anda bisa bergerak langsung ke gawang, tetapi kadang-kadang muncul rintangan di jalan - batu, pohon, sarang musuh (petelur), unit pemain. Untuk membuka jalan, kita perlu memberi tahu fungsi pathfinder posisi saat ini dan akhir, dan pathfinder akan kembali kepada kita (mungkin setelah banyak tindakan)
jalur yang hanya berupa serangkaian titik arah bahwa unit harus bergerak untuk sampai ke tujuan
Untuk menyelesaikan pekerjaannya, pathfinder menggunakan algoritma yang disebut A * (dilafalkan "A star"). Contoh sederhana menemukan jalur menggunakan A * ditunjukkan dalam video: penggigit ingin menemukan jalur di sekitar batu. Fungsi pencarian jalur mulai mengeksplorasi peta di sekitar penggigit (penelitian ditunjukkan oleh titik putih). Pada awalnya dia mencoba untuk langsung menuju ke gawang, tetapi segera setelah dia mencapai tebing, dia “tumpah” di kedua arah, mencoba menemukan posisi dari mana lagi akan mungkin untuk pindah ke gawang.
Algoritme dalam video ini diperlambat sehingga Anda dapat lebih melihat cara kerjanya.Setiap titik dalam animasi mewakili sebuah
simpul . Setiap node mengingat jarak dari awal pencarian dan perkiraan jarak dari node ini ke target (estimasi ini dihitung oleh
fungsi heuristik ). Berkat fungsi heuristik A * berfungsi - ia mengarahkan algoritma ke arah yang benar.
Dalam kasus yang paling sederhana, fungsi ini hanya menghitung jarak dalam garis lurus dari node ke posisi target - ini adalah pendekatan yang kami gunakan di Factorio sejak awal pengembangan, dan berkat itu, algoritma awalnya bergerak dalam garis lurus. Namun, ini bukan satu-satunya pilihan - jika fungsi heuristik tahu tentang beberapa kendala, itu bisa mengarahkan algoritma di sekitarnya, yang akan mempercepat pencarian, karena tidak perlu memeriksa node tambahan. Jelas, semakin pintar heuristik, semakin sulit untuk diterapkan.
Fungsi estimasi jarak lurus heuristik sederhana baik untuk menemukan jalur pada jarak yang relatif pendek. Itu cocok dengan kami di versi Factorio sebelumnya - hampir selalu menggigit bergerak jarak jauh hanya karena mereka marah dengan polusi, dan ini tidak sering terjadi. Namun, kami sekarang memiliki artileri. Artileri dapat dengan mudah menembak biters dalam jumlah besar di sisi lain dari sebuah danau besar (dan "mengagetkan mereka"), setelah itu mereka mencoba membuka jalan di sekitar danau. Video di bawah ini menunjukkan bagaimana algoritma A * sederhana yang kami gunakan sebelumnya mencoba untuk berkeliling danau.
Video ini menunjukkan kecepatan algoritma pada kenyataannya; dia tidak melambat.Reduksi blok
Menemukan jalan adalah tugas sejarah yang panjang, dan ada banyak teknik untuk memperbaikinya. Beberapa teknik ini termasuk dalam kategori
pencarian jalur hirarkis : dalam hal ini, peta disederhanakan pada awalnya, jalur tersebut terletak pada peta yang disederhanakan ini, yang kemudian digunakan untuk menemukan jalur nyata. Saya ulangi, ada beberapa implementasi spesifik dari teknik semacam itu, tetapi semuanya membutuhkan penyederhanaan ruang pencarian.
Bagaimana Anda bisa menyederhanakan dunia Factorio? Peta kami dibuat secara acak dan terus berubah: menempatkan dan menghapus entitas (misalnya, kolektor, dinding, atau menara) - ini mungkin merupakan mekanisme paling dasar dari seluruh permainan. Kami tidak ingin menghitung ulang seluruh peta yang disederhanakan setiap kali kami menambah atau menghapus suatu entitas. Pada saat yang sama, jika kita menyederhanakan peta lagi setiap kali kita perlu menemukan jalan, maka kita dapat dengan mudah kehilangan semua keuntungan dalam kinerja.
Salah satu orang dengan akses ke kode sumber permainan (Allaizn) datang dengan sebuah ide. yang saya implementasikan sebagai hasilnya. Sekarang ide ini tampak jelas.
Permainan ini didasarkan pada blok 32x32 ubin. Proses penyederhanaan menggantikan setiap blok dengan satu atau lebih
node abstrak . Karena tujuan kami adalah meningkatkan penelusuran untuk jalur di sekitar danau, kami dapat mengabaikan semua entitas dan hanya mempertimbangkan ubin: Anda tidak dapat bergerak di atas air, di tanah yang Anda bisa. Kami memisahkan setiap blok menjadi
komponen yang terpisah. Komponen adalah area ubin di mana unit bisa mendapatkan dari satu ubin di dalam komponen ke ubin lain dari komponen yang sama. Pada gambar di bawah, blok dibagi menjadi dua komponen yang terpisah, merah dan hijau. Setiap komponen ini akan menjadi satu simpul abstrak - pada kenyataannya, seluruh blok dikurangi menjadi dua "titik".
Pikiran Allaizn yang paling penting adalah bahwa kita tidak perlu menyimpan komponen untuk setiap petak peta - ingat saja komponen petak di sepanjang perimeter setiap blok, karena kita hanya tertarik pada komponen lain apa (di blok tetangga) dari masing-masing komponen yang terhubung, dan ini hanya bergantung pada ubin yang ada di batas blok.
Pencarian Jalur Hirarkis
Jadi, kami menemukan cara menyederhanakan peta, tetapi bagaimana menggunakan ini untuk menemukan jalur? Seperti yang saya katakan, ada banyak teknik pencarian jalur hirarkis. Gagasan paling sederhana adalah menemukan jalur menggunakan simpul abstrak dari awal hingga tujuan, yaitu jalur tersebut akan menjadi daftar komponen blok yang perlu Anda kunjungi. Kemudian kami menggunakan serangkaian pencarian lama yang baik A * untuk secara khusus mencari cara untuk berpindah dari satu komponen blok ke yang lain.
Masalahnya di sini adalah kita terlalu menyederhanakan peta: bagaimana jika bergerak dari satu blok ke blok lainnya tidak mungkin, karena beberapa entitas (misalnya, batu) memblokir jalan? Ketika mengurangi blok, kita mengabaikan semua entitas, oleh karena itu kita hanya tahu bahwa ubin di antara blok entah bagaimana terhubung, tetapi kita sama sekali tidak tahu apa-apa tentang apakah mungkin untuk berpindah dari satu ke yang lain.
Solusinya adalah menggunakan penyederhanaan hanya sebagai "rekomendasi" untuk pencarian nyata. Secara khusus, kami akan menggunakannya untuk membuat versi pintar dari fungsi pencarian heuristik.
Akibatnya, kami mendapat skema berikut: kami memiliki dua pathfinder: pathfinder
dasar , yang menemukan jalur nyata, dan
pathfinder abstrak , yang menyediakan fungsi heuristik ke pathfinder dasar. Setiap kali pathfinder dasar membuat simpul basis baru, ia memanggil pathfinder abstrak untuk mendapatkan perkiraan jarak ke target. Pathfinder abstrak bertindak dalam urutan yang berlawanan - dimulai dengan target pencarian dan membuka jalan ke awal, bergerak dari satu komponen blok ke yang lain. Ketika pencarian abstrak menemukan blok dan komponen di mana simpul basis baru dibuat, ia menggunakan jarak dari awal pencarian abstrak (yang, seperti yang saya katakan, adalah posisi tujuan dari seluruh pencarian) untuk menghitung perkiraan jarak dari simpul dasar baru ke target umum.
Namun, mengeksekusi seluruh pathfinder untuk masing-masing node akan jauh dari cepat, bahkan jika pathfinder abstrak bergerak dari satu blok ke yang lain. Karenanya, kami menggunakan skema yang disebut "Reverse Resumable A *". "Mundur" berarti bahwa, seperti yang saya katakan di atas, dilakukan dari tujuan hingga awal. "Terbarukan" berarti bahwa setelah menemukan blok yang menarik untuk pathfinder dasar, kami menyimpan semua node dalam memori. Lain kali pathfinder dasar membuat simpul baru dan membutuhkan perkiraan jarak, kita hanya melihat simpul abstrak yang disimpan dari pencarian sebelumnya. Pada saat yang sama, ada kemungkinan besar bahwa simpul abstrak yang diperlukan masih ada di memori (pada akhirnya, satu simpul abstrak mencakup sebagian besar blok, dan seringkali seluruh blok).
Bahkan jika pathfinder dasar membuat sebuah node yang terletak di blok yang tidak tercakup oleh salah satu node abstrak, kita tidak perlu melakukan seluruh pencarian abstrak lagi. Fitur nyaman dari algoritma A * adalah bahwa bahkan setelah "selesai bekerja" dan menemukan jalan, itu melanjutkan eksekusi, menjelajahi node di sekitar node yang telah dipelajari. Dan ini persis apa yang kita lakukan jika kita membutuhkan perkiraan jarak untuk basis node yang terletak di blok yang belum tercakup oleh pencarian abstrak: kita melanjutkan pencarian abstrak dari node yang disimpan dalam memori sampai diperluas ke node yang kita butuhkan.
Video di bawah ini menunjukkan sistem pathfinding baru dalam aksi. Lingkaran biru adalah simpul abstrak; titik putih - pencarian dasar. Pathfinder dalam video jauh lebih lambat daripada gim untuk menunjukkan cara kerjanya. Pada kecepatan normal, seluruh pencarian hanya membutuhkan beberapa kutu. Perhatikan bahwa pencarian dasar, yang masih menggunakan algoritma lama yang selalu kami gunakan, secara ajaib “tahu” bagaimana bergerak di sekitar danau.
Karena pathfinder abstrak hanya digunakan untuk memperoleh perkiraan heuristik jarak, pencarian dasar dapat dengan mudah berangkat dari jalur yang diusulkan oleh pencarian abstrak. Ini berarti bahwa meskipun skema pengurangan blok mengabaikan semua entitas, pathfinder dasar dapat mem-bypassnya hampir tanpa masalah. Karena mengabaikan entitas dalam proses menyederhanakan peta, kita tidak perlu mengulanginya lagi setiap kali entitas ditambahkan atau dihapus, cukup untuk menutupi hanya ubin yang telah diubah (misalnya, seperti halnya dengan tempat pembuangan sampah), yang lebih jarang terjadi daripada menempatkan entitas.
Selain itu, ini berarti bahwa kita pada dasarnya menggunakan pathfinder yang sama dengan yang telah kita gunakan selama bertahun-tahun, hanya fungsi heuristik yang telah diperbarui. Artinya, perubahan ini tidak akan memengaruhi banyak sistem lain, dan hanya akan memengaruhi kecepatan pencarian.