Advertisement
  1. Game Development
  2. Programming
Gamedevelopment

Cara Mempercepat A * Pathfinding Dengan Jump Point Mencari Algoritma

by
Difficulty:IntermediateLength:LongLanguages:

Malay (Melayu) translation by Seurion (you can also view the original English article)

Pathfinding adalah di mana-mana permainan. Oleh itu, penting untuk memahami implikasi yang terdapat ketika menggunakan algoritma seperti A *. Dalam tutorial ini, kita akan menampung satu kaedah yang agak baru untuk mencari dunia berasaskan grid: Jump Point Search, yang boleh mempercepatkan A * dengan arahan magnitud.

Nota: Walaupun tutorial ini ditulis menggunakan AS3 dan Flash, anda harus menggunakan teknik dan konsep yang sama dalam hampir semua persekitaran pembangunan permainan.

Pelaksanaan ini adalah berdasarkan kertas dan artikel asal mengenai JPS yang terdapat di sini: Jump Point Search. Sebuah
pelaksanaan berasaskan Lua, Jumper, digunakan untuk bantuan dengan beberapa bahagian pelaksanaan.


Demo Pencarian Titik Langsung

Klik SWF untuk memberi tumpuan, kemudian alihkan tetikus anda ke atas kawasan yang tidak menyekat peta untuk mempunyai NPCs cuba mendapatkannya. Tekan Ruang untuk bertukar antara A *, Jump Point Search, dan kedua-duanya.

Tiada Flash? Lihat video YouTube sebaliknya:


Setup

Pelaksanaan demo di atas menggunakan AS3 dan Flash dengan Rangka Kerja Starling untuk mempercepat GPU dan pustaka poligonal-ds untuk struktur data.


Pemfailan jalan

Pathfinding sering digunakan dalam permainan video dan anda pasti akan bertemu dengannya pada satu ketika semasa kerjaya pembangunan permainan anda. Penggunaan utamanya adalah untuk memberi tingkah laku pergerakan yang cerdas kepada entiti buatan (NPC), untuk mengelakkannya menimbulkan sesuatu (sering).

Dalam sesetengah permainan, avatar pemain juga tertakluk kepada laluan laluan (permainan strategi, banyak orang RPGs dan permainan petualangan ketiga). Jadi, anda mungkin mengandaikan bahawa masalah laluan laluan diselesaikan, tetapi malangnya itu bukan kes itu; tiada peluru perak yang boleh anda gunakan dan hanya dilakukan dengannya.

Dan walaupun dalam permainan AAA yang besar, anda masih akan mencari perkara-perkara lucu seperti ini:

Mungkin tidak ada peluru perak, tetapi ada peluru: algoritma A * (A star). Dalam tutorial ini, kita akan melihat gambaran ringkas A * dan bagaimana mempercepatkannya menggunakan algoritma lain, Jump Point Search.

Mula-mula kita memerlukan satu cara untuk mewakili dunia permainan kita dengan cara algoritma pathfinding dapat menggunakannya.


Perwakilan Dunia

Salah satu perkara yang paling penting untuk dipertimbangkan ketika memikirkan tentang laluan laluan untuk permainan anda adalah perwakilan dunia. Bagaimanakah data kawasan dan halangan yang boleh dilalui dengan struktur pengaturcaraan dalam ingatan?

Perwakilan paling mudah yang anda boleh gunakan adalah struktur berasaskan grid, di mana nod jalan diatur dalam grid dan boleh diwakili oleh array 2D. Kami akan menggunakan perwakilan ini dalam tutorial ini. Khususnya ia akan menjadi representasi grid lapan arah: membolehkan pergerakan dalam arah lurus dan pepenjuru.


Piksel hitam dalam imej mewakili sel-sel yang menyekat.

Keperluan anda mungkin berbeza, jadi struktur ini mungkin tidak sesuai dengan anda. Perkara yang baik ialah dengan beberapa pemprosesan (biasanya dilakukan di luar talian), anda boleh menukar perwakilan laluan ke format lain. Alternatif kepada pendekatan berasaskan grid akan termasuk perkara-perkara seperti poligon (halangan yang diwakili oleh poligon) atau meshes navigasi (kawasan navigasi diwakili oleh poligon); ini boleh mewakili data yang sama dengan nod yang lebih sedikit.

Satu lagi data yang boleh disimpan dalam perwakilan peta adalah kos: berapa banyak kos untuk perjalanan dari satu nod ke yang lain. Ini boleh digunakan untuk AI untuk menentukan jalan yang, sebagai contoh, lebih suka jalan raya di atas medan biasa (membuat kos jalan kurang daripada medan).

Jump Point Search direka khusus untuk perwakilan peta berasaskan grid lapan arah supaya kami menggunakannya. Juga, dalam bentuk vanila ia tidak menyokong peta berwajaran. (Di bahagian terakhir saya akan membincangkan cara yang mungkin untuk membetulkannya.)


Menyegarkan A* Pathfinding

Sekarang kita mempunyai perwakilan dunia mari kita lihat dengan cepat melaksanakan A *. Ia adalah algoritma carian graf berwajaran yang menggunakan heuristik (sedikit "petua") tentang cara terbaik untuk mencari kawasan dari nod mula hingga nod akhir.

Saya amat mengesyorkan bahawa anda melihat visualisasi algoritma pathfinding ini:
PathFinding.js - visual. Bermain dengannya boleh meningkatkan gerak hati anda tentang apa yang sebenarnya dilakukan algoritma - ditambah keseronokan!

Untuk laluan laluan menggunakan A * dalam grid segi empat tepat, kita lakukan perkara berikut:

Heuristik pada dasarnya membuat meneka pada kemungkinan bahawa nod yang dinilai akan membawa kepada matlamat. Heuristik boleh membuat perbezaan besar dalam kecekapan algoritma pathfinding kerana mereka cenderung untuk menghadkan bilangan nod yang perlu dilawati. Kami akan menggunakan jarak Manhattan untuk tujuan kami (bererti bahawa nod lebih dekat dengan matlamat akan mempunyai bilangan yang lebih kecil):

Ini lebih kurang. Kami menghentikan algoritma apabila kita mencari nod matlamat, dan kemudian mengesan kembali menggunakan pembolehubah nod induk untuk membina jalan.

Algoritma carian boleh digunakan untuk perkara lain juga. A * ialah algoritma carian graf berwajaran am, dan boleh digunakan pada mana-mana grafik sedemikian. Ini boleh meliputi bidang lain dalam AI, seperti mencari langkah-langkah yang optimum untuk mencapai matlamat tertentu: membuang bom atau berlari untuk perlindungan dan cuba menyelinap di belakang musuh?

Dalam perkembangan permainan, kita perlu melakukan perkara-perkara yang cepat, apabila mengemas kini permainan kami pada 60 bingkai sesaat setiap hitungan milisaat. Walaupun A * melakukan cukup baik untuk kegunaan beberapa terdapat keperluan untuk membuatnya lebih cepat atau menggunakan memori yang kurang.


Pengoptimuman

Memilih perwakilan adalah perkara pertama yang akan memberi impak kepada prestasi laluan laluan dan pilihan algoritma pathfinding anda. Saiz graf yang sedang dicari akan mempunyai korelasi yang besar tentang cara menjalankan laluan laluan anda (yang masuk akal, lebih mudah untuk mencari jalan di bilik anda daripada di bandar besar).

Kemudian anda akan mempertimbangkan pengoptimuman tahap yang lebih tinggi yang biasanya melibatkan data clustering ke kawasan-kawasan yang lebih kecil dan kemudian mencari mereka sementara jalan penapisan kemudian di daerah yang lebih kecil berjalan. Sebagai contoh, jika anda ingin pergi ke sebuah restoran di bandar jiran, anda mula-mula mempertimbangkan bagaimana anda mendapatkan dari bandar anda ke tempat itu, dan apabila anda berada di bandar yang anda batasi "mencari" anda ke kawasan di mana restoran itu terletak , mengabaikan selebihnya. Ini termasuk perkara-perkara seperti swamps, penghapusan mati dan HPA*.

Pada tahap terendah anda perlu melakukan carian. Anda memilih perwakilan data anda dan abstraksi yang mungkin dan kemudian pasangkannya dalam algoritma yang akan memilih nod, perjalanan ke sana sini mencari matlamat. Algoritma ini biasanya berdasarkan pada algoritma carian A* dengan pengubahsuaian yang mungkin. Dalam kes mudah anda boleh lari dengan menggunakan A* lurus yang menawarkan kesederhanaan. Saya telah menyediakan pelaksanaan berasaskan grid dalam muat turun sumber.


Pencarian Titik Langsung

Oleh kerana tutorial ini adalah tentang melaksanakan Jump Point Search, grafik pathfinding akan diwakili dengan grid. Dan ia secara khusus perlu menjadi grid lapan arah kerana algoritma menggunakannya secara langsung.

Apa yang Jump Point Search sebenarnya adalah untuk menghapuskan banyak nod perantaraan dalam jenis kombinasi grid tertentu. Ia melompat sekumpulan ini yang anda akan menambah ke senarai terbuka dan senarai tertutup, serta pengiraan lain, memihak kepada melakukan lebih banyak pemprosesan apabila memilih nod seterusnya.

Seperti dengan A* kita memilih dari adegan terbuka nod dengan skor F paling rendah. Tetapi ini adalah tempat yang mula menarik. Daripada memilih nod bersebelahan, kami akan memanggil fungsi ini untuk melakukannya untuk kami:

Apa yang dilakukannya ialah menghilangkan nod yang tidak menarik untuk laluan kita. Untuk ini kami menggunakan arahan dari ibu bapa sebagai panduan utama. Berikut adalah contoh pemangkasan nodus yang akan kita abaikan untuk arah mendatar dan menegak:

Contoh salah satu keadaan pemangkasan mendatar.

Dalam kod ini akan berakhir sebagai satu siri if pernyataan menyemak situasi ini. Anda dapat melihat contoh di sini, menerangkan kes yang betul dari gambar:


Contoh keadaan pemangkasan pepenjuru.

Selepas kita memilih tetangga kita cuba mencari titik lompat, yang merupakan simpul yang boleh dicapai dari semasa, tetapi tidak semestinya dengan satu cara sahaja. Untuk meletakkannya secara lebih formal, apa yang JPS lakukan adalah untuk menghapuskan simetri antara laluan - masing-masing mempunyai permutasi yang berbeza bergerak yang sama:


Contoh simetri jalan.

Jadi untuk ruang terbuka yang besar kita boleh menang besar. Inilah cara kerja kaedah lompat:

Saya telah mengeluarkan cek jiran terpaksa dari jika pernyataan kerana mereka agak besar. Mereka pada dasarnya terdiri daripada pemeriksaan yang serupa dengan yang pertama kali kita memilih jiran untuk nod baru (banyak pemeriksaan untuk melihat jika sel-sel disekat). Mereka berkhidmat untuk tujuan mengesan apabila kita dibenarkan mempunyai andaian pada simetri.


Contoh tingkah laku fungsi melompat.

Kes diagonal adalah istimewa dan kita perlu melihat bukan sahaja untuk jiran terpaksa di arah pepenjuru, tetapi juga dalam arah mendatar dan menegak, dan jika ada yang gagal, kita perlu meletakkan nod terpaksa sebagai titik melompat. Kami juga perlu mempertimbangkan kes khas nod matlamat, di mana kaedah melompat berakhir.

Setiap kali kita tidak mencari nod carian kita memanggil fungsi lompat secara rekursif dalam arah yang ditentukan. Dalam demo saya sebenarnya telah membuka panggilan rekursif ini kerana ini akan dipanggil banyak. (Dalam ujian saya, peningkatan prestasi ini dengan faktor dua.)

Inilah yang dilakukan oleh JPS; hasil akhir adalah nod baru untuk A* untuk memeriksa dan kami meneruskan dengan algoritma. Apabila nod gol didapati, kita membina semula jalan dan mengembalikannya.


Harta benda

JPS boleh melangkau banyak nod apabila mencari, yang boleh memberikan peningkatan kelajuan bagus (dalam projek saya sekitar 30x ke atas A*), tetapi ia datang dengan kos.

Ia berfungsi dengan baik pada grid seragam, tetapi boleh dibuat untuk bekerja dengan seragam tanpa menggunakan tweaking tambahan, menandakan jiran seperti yang dipaksa di mana terdapat peralihan kepada simpul kos yang berbeza (terbaik untuk menggunakan kos diskret).

Dalam permainan saya sedang bekerja, grid adalah seragam kecuali jalan raya, yang lebih murah daripada berjalan di medan biasa. (Ia kelihatan lebih baik apabila watak menghormati itu.) Pada akhirnya saya telah menyelesaikannya dengan mendahului beberapa nilai kedudukan jalan raya. Apabila pathfinding dimulakan, algoritma mencari kemungkinan titik-titik terdekat ke laluan dari nod awal dan matlamat, dan kemudian mencari graf peringkat tinggi khas jalan (yang diprakirakan), dan kemudian menggunakan JPS untuk mencari kawasan medan.


Debugging

Nota cepat mengenai penyahpepijatan. Debug jenis algoritma ini boleh menjadi sangat sukar, dan hampir pasti bahawa pelaksanaan pertama akan mempunyai beberapa sukar untuk mencari bug. Anda boleh membuat kebaikan dan membina beberapa jenis visualisasi secara fungsional dan menarik apa yang berlaku ketika algoritma berjalan.

Sekiranya anda mendapat pepijat, anda harus mengurangkan domain (saiz grid) ke minimum yang membolehkan anda mengeluarkan semula masalah dan ujian dari sana. Seperti mana yang anda boleh meneka, pelaksanaan JPS pertama saya tidak berfungsi langsung!

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.