Advertisement
  1. Game Development
  2. Programming

Bagaimana Mempercepat A* Pathfinding Dengan Algoritma Pencarian Langsung

by
Difficulty:IntermediateLength:LongLanguages:

Indonesian (Bahasa Indonesia) translation by Sap (you can also view the original English article)

Pathfinding ada di mana-mana dalam game. Jadi penting untuk memahami implikasi yang ada saat menggunakan algoritma seperti A *. Dalam tutorial ini kita akan membahas metode yang relatif baru untuk mencari dunia berbasis grid: Jump Point Search, yang dapat mempercepat A * berdasarkan urutan besarnya.

Catatan: Meskipun tutorial ini ditulis menggunakan AS3 dan Flash, Anda harus bisa menggunakan teknik dan konsep yang sama di hampir semua lingkungan pengembangan game.

Implementasi ini didasarkan pada makalah asli dan artikel tentang JPS yang ditemukan di sini: Jump Point Search.   -
Implementasi berbasis Lua, Jumper, digunakan untuk membantu beberapa bagian pelaksanaannya.


Demo Pencarian Langsung

Klik SWF untuk memberikan fokusnya, lalu gerakkan mouse kalian ke area yang tidak bisa menghalangi agar NCP mencoba melakukan. Tekan Spasi untuk merubah antara A *, Jump Point Search, dan keduanya.

Belum Jelas? Lihat video YouTube sebagai gantinya:


Mempersiapkan

Implementasi demo di atas menggunakan AS3 dan Flash dengan Starling Framework untuk rendering GPU yang dipercepat dan library poligonal-ds untuk struktur data.


Pathfinding

Pathfinding sering digunakan dalam video game dan kalian pasti akan menemukan di beberapa titik selama kenaikan level permainan kalian. Fungsi utamanya adalah memberikan perilaku gerakan cerdas ke entitas buatan (NPC), untuk menghindari mereka menabrak barang (sering).

Dalam beberapa permainan, avatar pemain juga tunduk pada pencarian jalan (game strategi, RPG orang ketiga dan game petualangan). Sehingga kalian mungkin berpikir bahwa masalah pathfinding dipecahkan, tapi sayangnya bukan itu masalahnya; Tidak ada tombol perak yang bisa Anda gunakan dan hanya bisa dilakukan dengan itu.

Dan bahkan didalam permainan big AAA, kalian tetap akan menemukan hal lucu seperti injli

Mungkin tidak ada peluru perak, tapi ada peluru: algoritma A * (A star). Didalam tutorial ini kita akan melihat gambaran singkat tentang A * dan bagaimana cara mempercepatnya menggunakan algoritma lain, Jump Point Search.

Pertama kita membutuhkan jalan untuk mewakili dunia permainan kita dengan cara pathfinding algoritma yang dapat kita gunakan


Gambaran Dunia

Salah satu hal yang paling penting untuk diperhitungkan ketika mencari jalan untuk game kalian adalah gambaran dunia Bagaimana data dari area yang dilalui dan rintangan yang terorganisir dengan struktur pemrograman di memori?

Gambaran paling sederhana yang dapat kalian gunakan adalah struktur berbasis dalam sebuah grid, di mana simpul jalur diatur dalam kotak dan dapat ditunjukkan oleh 2D array. Kita akan mulai menggunakan ini dalam gambaran di tutorial ini. Secara khusus, ini akan menjadi gambaran grid delapan arah: memungkinkan pergerakan lurus dan arah diagonal.


Kotak hitam dalam gambar ini menunjukkan daerah tertutup

Kebutuhan kalian bisa saja berbeda, jadi struktur ini bisa saja tidak cocok untuk kalian. Hal ini adalah dengan beberapa proses (biasanya dilakukan secara offline) kalian bisa mengubah ukuran pencarian jalan dengan format lainnya. Alternatif untuk pendekatan berbasis grid akan mencakup hal-hal seperti poligon (rintangan yang ditunjukkan oleh poligon) atau jala navigasi (area navigasi yang ditunjukkan oleh poligon); Ini bisa mewakili data yang sama dengan lebih sedikit persimpangan jalan.

Data lain yang dapat disimpan dalam gambaran peta biasanya berbayar: berapa biaya untuk melakukan perjalanan dari satu persimpangan ke persimpangan lainnya. Al ni bisa digunakan untuk menentukan jalur yang, misalnya lebih memilih jalan di atas medan reguler (membuat biaya jalan kurang dari medan).

Jump Point Search dirancang khusus untuk gambaran peta berbasis grid delapan arah jadi, kita akan menggunakannya Selain itu, dalam bentuk vanilla tak tersedia peta berbobot. (Pada bagian akhir saya akan menjelaskan bagaimana cara untuk mengulanginya kembali)


Memulihkan Pathfinding A*

Sekarang kita memiliki sebuah gambaran dunia. Sekarang mari kita lihat sekilas penerapan A*. Ini adalah algoritma pencarian grafik berbobot yang menggunakan heuristik (sedikit "petunjuk") tentang cara mencari yang terbaik dari jalan awal ke jalan akhir.

Saya sangat berharap agar Anda melihat dulu.
PathFinding.js - visual. Bermain dengan ini dapat menambah kepekaanmu akan apa yang sebenarnya sedang dilakukan - ditambah lagi ini sangat menyenangkan!

Untuk pathfinding menggunakan A* dalam grid persegi panjang kita menggunakan cara berikut:

Heuristics pada dasarnya membuat menebak pada kemungkinan bahwa node yang dievaluasi akan mengarah pada tujuan.  Heuristics dapat membuat perbedaan besar dalam efisiensi algoritma pathfinding karena mereka cenderung membatasi jumlah node yang perlu dikunjungi. Kita akan menggunakan Manhattan distance untuk tujuan kita (artinya nodes yang mendekati tujuan akan memiliki jumlah yang lebih kecil ) :

Ini lebih atau kurang. Kita menghentikan algoritma ketika kita menemukan node tujuan, dan kemudian melacak kembali menggunakan variabel induk node untuk membangun path.

Algoritma pencarian dapat digunakan untuk hal-hal lain juga. A* adalah algoritma pencarian grafik berbobot umum, dan dapat digunakan pada grafik semacam itu. Ini bisa mencakup bidang lain di Al, seperti menemukan langkah optimal untuk mencapai tujuan tertentu: melempar bom atau lari ke tempat penampungan dan mencoba menyelinap di belakang musuh ?

Dalam pengembangan game kita perlu melakukan sesuatu dengan cepat, saat memperbarui permainan kita pada 60 frame per detik setiap hitungan milidetik. Meskipun A* berkinerja cukup baik untuk beberapa penggunaan, ada kebutuhan untuk membuatnya lebih cepat atau menggunakan sedikit memori.


Optimizations

Memilih representasi adalah hal pertama yang akan berdampak pada kinerja pathfinding dan pilihan algoritma pathfinding Anda. Ukuran grafik yang sedang dicari akan memiliki korelasi besar tentang bagaimana kinerja pathfinding Anda (yang masuk akal; lebih mudah menemukan jalan di kamar Anda daripada di kota besar).

Maka Anda akan mempertimbangkan optimasi tingkat yang lebih tinggi yang biasanya melibatkan data clustering ke daerah yang lebih kecil dan kemudian mencari mereka sementara kemudian memperbaiki jalur di daerah-daerah yang lebih kecil. Misalnya, jika Anda ingin pergi ke restoran di kota tetangga, pertama-tama Anda mempertimbangkan bagaimana Anda bisa pergi dari kota ke kota itu, dan begitu Anda berada di kota itu, Anda membatasi "pencarian" Anda ke tempat restoran tersebut berada, mengabaikan sisanya. Ini termasuk hal-hal seperti swamps, dead end elimination dan HPA*

Pada tingkat terendah Anda harus melakukan pencarian.  Anda memilih representasi data dan abstraksi yang mungkin dan kemudian memasukkannya ke dalam algoritma yang akan memilih node, melakukan perjalanan ke sana-sini mencari sasarannya. Algoritma ini biasanya didasarkan pada algoritma pencarian A* dengan kemungkinan modifikasi. Dalam kasus sederhana Anda bisa lolos dengan menggunakan A* lurus yang menawarkan kesederhanaan. Saya telah menyediakan sebuah implementasi berbasis grid di source download.


Point Pencarian Loncatan

Karena tutorial ini adalah tentang penerapan Jump Point Search, grafik pathfinding akan diwakili dengan grid.  Dan secara khusus perlu menjadi grid delapan arah sejak algoritma menggunakannya secara langsung.

Apa Jump Point Search benar-benar adalah untuk menghilangkan banyak node perantara dalam kombinasi grid tertentu. Ini melewatkan banyak hal yang akan Anda tambahkan ke daftar terbuka dan daftar tertutup, serta perhitungan lainnya, yang mendukung pemrosesan lebih lanjut saat memilih node berikutnya.

Seperti A* kita pilih dari scene terbuka node dengan nilai F terendah. Tapi disinilah segala sesuatunya mulai menarik.  Alih-alih memilih node yang berdekatan, kita akan memanggil fungsi ini untuk melakukannya untuk kita:

Apa yang dilakukan ini adalah menghilangkan simpul yang tidak menarik bagi jalan kita. Untuk ini kita menggunakan arahan dari orang tua sebagai pedoman utama. Berikut adalah contoh pemangkasan nodus yang akan kita abaikan untuk arah horizontal dan vertikal: 

Contoh salah satu situasi pemangkasan horisontal.

Dalam kode ini akan berakhir sebagai serangkaian jika pernyataan memeriksa situasi ini. Anda bisa melihat contohnya di sini, menggambarkan kasus yang tepat dari gambar:


Contoh situasi diagonal pruning.

Setelah kita memilih tetangga kita mencoba mencari titik loncat, yaitu sebuah simpul yang bisa dicapai dari yang sekarang, tapi belum tentu hanya dengan satu cara saja. Untuk membuatnya lebih formal, apa yang dilakukan JPS adalah menghilangkan simetri di antara jalur - masing-masing memiliki permutasi yang berbeda dengan gerakan yang sama:


Contoh simetri jalan.

Jadi untuk ruang terbuka besar kita bisa mendapat banyak kemenangan. Inilah cara kerja metode melompat:

Saya telah menghapus cek tetangga paksa dari pernyataan jika mereka cukup besar. Mereka pada dasarnya terdiri dari cek yang serupa dengan saat pertama kita memilih tetangga untuk node baru (banyak pemeriksaan untuk melihat apakah sel diblokir).  Mereka melayani tujuan mendeteksi kapan kita diijinkan untuk memiliki asumsi kita tentang simetri.


Contoh perilaku lompat fungsi. 

Kasus diagonal itu istimewa dan kita harus melihat bukan hanya untuk tetangga yang dipaksa di arah diagonal, tapi juga pada arah horizontal dan vertikal, dan bila ada yang gagal kita harus memasukkan simpul paksa sebagai titik lompat. Kita juga harus mempertimbangkan kasus khusus dari simpul tujuan, di mana metode lompatan berakhir.

Setiap kali kita tidak menemukan node pencarian kita sebut fungsi lompatan secara rekursif pada arah yang ditentukan. Dalam demo saya benar-benar membuka gulungan panggilan rekursif ini karena ini akan disebut banyak. (Dalam pengujian saya, peningkatan kinerja ini dengan faktor dua.)

Inilah yang dilakukan JPS; Hasil akhirnya adalah node baru untuk A* untuk memeriksa dan kita lanjutkan dengan algoritma. Ketika simpul tujuan ditemukan, kita merekonstruksi jalan dan mengembalikannya.


Alat-alat

JPS dapat melewati banyak node saat mencari, yang dapat memberikan peningkatan kecepatan yang bagus (dalam proyek saya sekitar 30x lebih dari A*), namun hal itu menggunakan biaya.

Ini bekerja paling baik pada jaringan yang seragam, namun dapat dilakukan untuk bekerja dengan seragam non menggunakan tweaker tambahan, menandai tetangga yang dipaksa di mana ada transisi ke node dengan biaya yang berbeda (paling baik menggunakan biaya diskrit).

Dalam permainan yang sedang saya kerjakan, grid itu seragam kecuali jalan, yang harganya jauh lebih murah daripada berjalan di medan reguler. (Terlihat jauh lebih baik bila karakter menghormatinya.)  Pada akhirnya saya telah menyelesaikan ini dengan mendahului beberapa nilai posisi jalan.  Ketika pathfinding dimulai, algoritma mencari kemungkinan poin terdekat ke jalur dari simpul awal dan sasaran, dan kemudian mencari grafik jalan tingkat tinggi khusus (yang precomputed), dan kemudian menggunakan JPS untuk mencari daerah medan.


Debugging

Sebuah catatan ringkas tentang debugging. Debugging jenis algoritma ini bisa sangat sulit, dan hampir pasti bahwa implementasi pertama akan sulit ditemukan bug. Anda dapat membantu diri sendiri dan membangun semacam visualisasi secara fungsional dan menarik apa yang terjadi saat algoritma berjalan.

Jika Anda mendapatkan bug Anda harus mengurangi domain (ukuran grid) seminimal mungkin sehingga memungkinkan Anda mereproduksi masalah dan melakukan tes dari sana. Seperti yang mungkin bisa Anda duga, implementasi JPS pertama saya tidak langsung bekerja!

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.