Advertisement
  1. Game Development
  2. Pathfinding
Gamedevelopment

Bagaimana Mengubah A * Pathfinding ke Platformer Berbasis Grid 2D: Pelaksanaan

by
Difficulty:IntermediateLength:LongLanguages:
This post is part of a series called How to Adapt A* Pathfinding to a 2D Grid-Based Platformer.
How to Adapt A* Pathfinding to a 2D Grid-Based Platformer: Theory
A* Pathfinding for 2D Grid-Based Platformers: Adding One-Way Platforms

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

Sekarang kita mempunyai idea yang baik tentang bagaimana algoritma A * platforming kami akan berfungsi, sudah tiba masanya untuk benar-benar kod itu. Daripada membina dari awal, kami akan menyesuaikan sistem laluan laluan A * yang sedia ada untuk menambah keserasian platfomer baharu.

Pelaksanaan yang kita akan menyesuaikan diri dengan tutorial ini adalah sistem laluan laluan A * berasaskan grid Gustavo Franco, yang ditulis dalam C; jika anda tidak biasa dengannya, baca penjelasannya tentang semua bahagian yang berasingan sebelum meneruskan. Sekiranya anda belum membaca tutorial sebelumnya dalam siri ini, yang memberikan gambaran keseluruhan tentang bagaimana penyesuaian ini akan berfungsi, baca terlebih dahulu.

Nota: kod sumber lengkap untuk tutorial ini boleh didapati di repo GitHub ini, dalam folder Implementation.

Demo

Anda boleh memainkan demo Unity, atau versi WebGL (64MB), untuk melihat hasil akhir tindakan. Gunakan WASD untuk memindahkan watak, klik kiri di tempat untuk mencari jalan yang anda boleh ikuti untuk sampai ke sana, dan klik kanan sel untuk bertukar-tukar tanah pada ketika itu.

Menyediakan Projek Permainan

Kita perlu menetapkan beberapa peraturan untuk projek permainan contoh yang digunakan dalam tutorial ini. Anda sudah tentu boleh mengubah peraturan ini apabila melaksanakan algoritma ini dalam permainan anda sendiri!

Menyediakan Fizik

Peraturan fizik yang digunakan dalam projek contoh sangat mudah.

Apabila ia datang kepada kelajuan mendatar, tidak ada momentum sama sekali. Watak boleh menukar arah dengan segera, dan segera bergerak ke arah itu pada kelajuan penuh. Ini menjadikannya lebih mudah untuk algoritma untuk mencari jalan yang betul, kerana kita tidak perlu peduli dengan kelajuan mendatar watak semasa. Ia juga menjadikannya lebih mudah untuk mencipta AI laluan, kerana kita tidak perlu membuat watak mendapatkan apa-apa momentum sebelum melakukan lompatan.

Kami menggunakan empat pemalar untuk menentukan dan menyekat pergerakan watak:

  • Gravity
  • Kelajuan maksimum yang jatuh
  • Berjalan pantas
  • Kelajuan melompat

Begini bagaimana mereka ditakrifkan untuk projek contoh ini:

Unit asas yang digunakan dalam permainan adalah piksel, maka watak itu akan bergerak 160 piksel per saat secara mendatar (ketika berjalan atau melompat); apabila melompat, kelajuan menegak watak akan ditetapkan kepada 410 piksel sesaat. Dalam projek ujian kelajuan jatuh watak itu terhad kepada 900, jadi tidak ada kemungkinan ia jatuh melalui jubin. Tarik graviti ditetapkan -1030 piksel per second2.

Ketinggian lompat watak tidak ditetapkan: semakin lama kunci melompat ditekan, semakin tinggi watak akan melompat. Ini dicapai dengan menetapkan kelajuan watak untuk tidak melebihi 200 piksel sesaat sekali apabila kunci melompat tidak lagi ditekan:

Menyediakan Grid

The grid is a simple array of bytes which represent the cost of movement to a specific cell (where 0 is reserved for blocks which the character cannot move through).

Kami tidak akan masuk ke dalam berat dalam tutorial ini; kita akan menggunakan hanya dua nilai: 0 untuk blok pepejal, dan 1 untuk sel kosong.

Algoritma yang digunakan dalam tutorial ini memerlukan lebar dan ketinggian grid menjadi kuasa dua, jadi ingatlah itu.

Berikut adalah contoh array grid dan perwakilan dalam permainan itu.

Nota mengenai Threading

Biasanya kami akan menubuhkan proses penandatangan dalam benang yang berasingan, jadi tidak ada yang membeku dalam permainan semasa ia berfungsi, tetapi dalam tutorial ini kami akan menggunakan versi satu thread, kerana batasan platform WebGL yang demo ini berjalan terus.

Algoritma itu sendiri boleh dijalankan dalam benang yang berasingan, jadi anda tidak sepatutnya mempunyai masalah dengan menggabungkannya ke dalam kod anda dengan cara itu jika anda perlu.

Menambah Nilai Lompat ke Nod

Ingatlah dari gambaran teori bahawa nod dibezakan bukan hanya dengan koordinat x dan y, tetapi juga dengan melompat nilai. Dalam pelaksanaan standard A *, koordinat x dan y adalah mencukupi untuk menentukan nod, jadi kita perlu mengubahnya untuk menggunakan nilai lompat juga.

Dari sini, kita akan mengubahsuai fail sumber PathFinderFast.cs teras dari pelaksanaan Gustavo Franco.

Penstrukturan semula industri perkhidmatan senarai nod

Pertama, kita akan menambah senarai baru nod bagi setiap sel grid; Senarai ini akan menggantikan mCalcGrid dari algoritma yang asal:

Ambil perhatian bahawa PathFinderFast menggunakan dimensi arrays, dan bukannya pelbagai 2D seperti yang kami jangkakan untuk digunakan semasa mewakili grid.

Ini bukanlah satu masalah, kerana kita tahu grid yang lebar dan tinggi, jadi daripada mencapai data dengan X dan Y Indeks, kita akan mencapainya dengan int tunggal yang dikira menggunakan location = (y << gridWidthLog2) + x. (ini adalah versi sedikit lebih pantas dari location = (y * gridWidth) + x).

Kerana kita perlu grid yang tiga dimensi (untuk menggabungkan nilai lompat sebagai ketiga 'dimensi'), kita perlu menambah satu lagi integer, yang akan menjadi Indeks satu nod dalam senarai tertentu X dan Y kedudukan.

Ambil perhatian bahawa kami tidak menggabungkan semua tiga koordinat ke dalam satu integer, kerana dimensi ketiga daripada grid tidak mempunyai saiz yang berterusan. Kami boleh pertimbangkan untuk menggunakan hanya tiga dimensi grid, yang akan mengehadkan bilangan nod yang mungkin pada kedudukan yang tertentu (x, y) — tetapi jika saiz tatasusunan pada 'z-axis' adalah terlalu kecil, maka algoritma boleh kembali keputusan yang betul, jadi kami akan bermain selamat.

Di sini, maka, adalah struktur yang akan kita gunakan untuk indeks nod tertentu:

Perkara seterusnya yang perlu kita ubah suai ialah struktur PathFinderNodeFast. Terdapat dua perkara yang kita perlu Tambah di sini:

  • Yang pertama ialah Indeks node's parent, yang pada dasarnya node yang terdahulu daripada kami tiba ke node semasa. Kita perlu mempunyai Indeks itu kerana kita tidak dapat mengenalpasti parent silely oleh para x - dan y-koordinat. Koordinat x dan y akan menunjukkan kepada kita nod yang berada pada kedudukan tertentu, jadi kita juga perlu mengetahui indeks induk kita dalam senarai itu. Kita akan namakan indeks PZ itu.
  • Perkara lain yang perlu kita tambahkan kepada struktur adalah nilai melompat.

Berikut adalah struct lama:

Dan inilah yang akan kami ubah ke:

Masih ada satu masalah, walaupun. Apabila kita menggunakan algoritma sekali, ia akan mengisi senarai sel-sel nod. Kita perlu mengosongkan senarai tersebut selepas setiap kali penandatangan jalan dijalankan, kerana jika tidak, maka senarai tersebut akan berkembang sepanjang masa dengan setiap penggunaan algoritma, dan penggunaan memori akan meningkat dengan tidak terkawal.

Perkara itu, kami tidak mahu menghapus setiap senarai setiap kali penandatangan laluan dijalankan, kerana grid boleh menjadi besar dan laluannya mungkin tidak akan menyentuh kebanyakan nod grid. Ia akan menyebabkan overhead yang besar, jadi lebih baik hanya untuk memadamkan senarai yang algoritma itu dilalui.

Untuk itu, kita memerlukan bekas tambahan yang akan kita gunakan untuk mengingati sel yang mana telah disentuh:

Stack akan berfungsi dengan baik; kita hanya perlu membersihkan semua senarai yang terkandung di dalamnya satu persatu.

Mengemas kini Giliran Keutamaan

Kini mari kita dapatkan giliran utama kami mOpen untuk bekerja dengan indeks baru.

Perkara pertama yang perlu kita lakukan ialah mengubah perisytiharan untuk menggunakan Lokasi daripada integer-jadi, dari:

kepada:

Selanjutnya, kita perlu menukar pengatur cara untuk membuatnya menggunakan struktur baru. Sekarang ia hanya menggunakan pelbagai nod; kita perlu mengubahnya supaya ia menggunakan pelbagai senarai nod sebaliknya. Kita juga perlu memastikan ia membandingkan nod menggunakan Lokasi dan bukan sekadar integer.

Inilah kod lama:

Dan inilah yang baru:

Sekarang, mari kita mulakan senarai nod dan susunan lokasi yang disentuh apabila penanda laluan dibuat. Sekali lagi, inilah kod lama:

Dan inilah yang baru:

Akhir sekali, mari buat giliran keutamaan kami menggunakan pembina baru:

Memulakan Algoritma

Apabila kita memulakan algoritma, kita ingin memberitahu berapa besar watak kita (dalam sel) dan juga bagaimana tinggi watak itu boleh melompat.

(Perhatikan bahawa, untuk tutorial ini, kita tidak akan menggunakan characterWidth atau characterHeight kita akan mengandaikan saiz watak adalah blok 1x1.)

Tukar baris ini:

Untuk ini:

Perkara pertama yang perlu kita lakukan ialah membersihkan senarai di lokasi yang pernah disentuh:

Seterusnya, kita mesti memastikan bahawa watak itu boleh dimuatkan di lokasi akhir. (Jika tidak, tidak ada gunanya menjalankan algoritma, kerana tidak mustahil untuk mencari jalan yang sah.)

Sekarang kita boleh membuat nod mula. Daripada menetapkan nilai dalam mCalcGrid, kita perlu menambah nod ke senarai nod pada kedudukan tertentu.

Pertama, mari kita menghitung lokasi nod. Sudah tentu, untuk dapat melakukan ini, kita juga perlu mengubah jenis mLocation Location.

Tukar baris ini:

Untuk ini:

Penyelarasan mEndLocation boleh ditinggalkan seperti; kami akan gunakan ini untuk memeriksa sama ada kami telah mencapai matlamat kami, jadi kami hanya perlu menyemak kedudukan X dan Y dalam kes itu:

Untuk permulaan nod permulaan, kita perlu menetapkan semula induk PZ kepada 0 dan tetapkan nilai melompat yang sesuai.

Apabila titik permulaan berada di atas tanah, nilai melompat harus sama dengan 0-tetapi bagaimana jika kita mula di udara? Penyelesaian yang paling mudah adalah untuk menetapkannya kepada nilai yang jatuh dan tidak perlu terlalu risau; mencari laluan apabila bermula di tengah-tengah udara mungkin agak menyusahkan, jadi kami akan mengambil jalan mudah.

Inilah kod lama:

Dan yang baru:

Kita juga mesti menambah nod ke senarai pada kedudukan mula:

Dan kita juga perlu ingat bahawa senarai nod mula harus dibersihkan pada jangka masa berikutnya:

Akhirnya, lokasi itu beratur dan kita boleh mulakan dengan algoritma teras. Untuk kesimpulannya, inilah inisiasi menjalankan laluan pathfinder seperti:

Mengira Pengganti

Memeriksa Posisi

Kami tidak perlu mengubah banyak bahagian pemprosesan nod; kita hanya perlu menukar mLocation ke mLocation.xy supaya mLocationX dan mLocationY dapat dihitung.

Ubah ini:

Untuk ini:

Perhatikan bahawa, apabila kita mengubah status nod dalam senarai nod, kita menggunakan fungsi UpdateStatus (byte newStatus). Kita tidak boleh mengubah mana-mana ahli struktur dalam senarai, kerana senarai itu mengembalikan salinan nod; kita perlu menggantikan keseluruhan nod. Fungsi ini hanya mengembalikan nod yang disalin dengan Status diubah menjadi newStatus:

Kita juga perlu mengubah cara pengganti dikira:

Di sini kita hanya mengira lokasi salah seorang pengganti; kita perlu ini supaya kita dapat mencari kedudukan relatif nod pengganti.

Menentukan Jenis Kedudukan

Perkara seterusnya yang perlu kita ketahui adalah jenis kedudukan yang digambarkan pengganti.

Kami berminat dengan empat varian di sini:

  1. Watak tidak sesuai dengan kedudukannya. Kami mengandaikan bahawa kedudukan sel bertindak balas kepada 'sel' bawah watak. Jika ini berlaku, maka kita boleh membuang pengganti, kerana tidak ada cara untuk memindahkan watak melaluinya.
  2. Watak itu sesuai dengan kedudukannya, dan di atas tanah. Ini bermakna nilai lompat pengganti perlu ditukar kepada 0.
  3. Watak sesuai dengan kedudukannya, dan hanya di bawah siling. Ini bermakna walaupun watak mempunyai kelajuan yang cukup untuk melompat lebih tinggi, ia tidak boleh, jadi kita perlu menukar nilai lompat dengan sewajarnya.
  4. Watak itu hanya sesuai di tempat dan tidak di atas tanah mahupun di siling.

Pertama, mari kita anggap bahawa watak itu tidak berada di tanah atau di siling:

Mari kita periksa sama ada watak sesuai dengan tempat baru. Sekiranya tidak, kami selamat melangkau pengganti dan menyemak yang seterusnya.

Untuk memeriksa sama ada watak itu berada di lapangan semasa di lokasi baru, kita hanya perlu melihat jika ada blok padu di bawah pengganti:

Begitu juga, kita periksa sama ada watak itu berada di siling:

Mengira Nilai Lompat

Perkara seterusnya yang perlu kita lakukan ialah melihat sama ada pengganti ini adalah yang sah atau tidak, dan jika kemudiannya, maka hitungan JumpLength yang sesuai untuknya.

Pertama, mari kita dapatkan JumpLength nod induk:

Kami juga akan mengisytiharkan newJumpLength untuk pengganti yang sedang diproses:

Sekarang kita boleh mengira newJumpLength. (Bagaimana kita melakukan ini dijelaskan pada permulaan teori keseluruhan).

Jika nod pengganti berada di atas tanah, maka newJumpValue baru bersamaan dengan 0:

Tiada apa yang perlu dibimbangkan di sini. Adalah penting untuk memeriksa sama ada watak itu berada di tanah terlebih dahulu, kerana jika wataknya berada di tanah dan di siling maka kita mahu menetapkan nilai melompat ke 0.

Sekiranya kedudukan berada di siling maka kita perlu mempertimbangkan dua kes:

  1. watak perlu turun lurus ke bawah, atau
  2. watak masih boleh memindahkan satu sel ke kedua-dua belah pihak.

Dalam kes pertama, kita perlu menetapkan newJumpLength menjadi sekurang-kurangnya maxCharacterJumpHeight * 2 + 1, kerana nilai ini bermakna kita jatuh dan langkah seterusnya perlu dilakukan secara menegak.

Dalam kes kedua, nilai perlu sekurang-kurangnya maxCharacterJumpHeight * 2. Oleh kerana nilai itu adalah sama, nod pengganti masih boleh bergerak sama ada kiri atau kanan.

Kes 'atas tanah' dan 'di siling' diselesaikan; kini kita dapat mengira nilai lompat ketika di udara.

Mengira Nilai Lompat di Mid-Air

Pertama, mari kita mengendalikan kes di mana nod pengganti berada di atas nod induk.

Sekiranya panjang melompat adalah lebih tinggi, maka kenaikannya dengan dua; sebaliknya, kita kenaikannya dengan satu. Ini akan menghasilkan nilai yang lebih baik untuk newJumpLength:

Oleh kerana, dalam lompat purata, kelajuan aksara mempunyai nilai tertinggi pada awal dan akhir lompat, kita harus mewakili fakta ini dalam algoritma.

Kami akan menetapkan permulaan lompat dengan memaksa algoritma untuk memindahkan dua sel jika kita baru sahaja turun dari tanah. Ini dapat dicapai dengan mudah dengan menukar nilai lompat 2 hingga 3 pada saat melompat, kerana pada nilai melompat 3, algoritma mengetahui watak tidak boleh pergi ke sisi (kerana 3 adalah nombor ganjil).

Keluk lompat akan diubah kepada yang berikut.

Marilah juga menampung perubahan ini dalam kod:

(Kami akan membetulkan lengkung apabila kelajuan wataknya terlalu tinggi untuk pergi ke sisi apabila kita mengesahkan nod kemudian.)

Sekarang mari kita mengendalikan kes di mana nod baru berada di bawah yang sebelumnya.

Jika koordinat y baru lebih rendah daripada ibu bapa, itu bermakna kita jatuh. Kami mengira nilai lompat dengan cara yang sama seperti yang kita lakukan semasa melompat, tetapi minimum mesti ditetapkan kepada maxCharacterJumpHeight * 2. (Ini kerana watak itu tidak perlu melompat penuh untuk mula jatuh-contohnya, ia hanya boleh berjalan sebuah langkan.) Dalam hal ini nilai lompat harus diubah dari 1 hingga 6 dengan segera (dalam hal ketinggian lompat maksimum karakter adalah 3):


Dengan cara ini, watak itu tidak boleh melepaskan tongkat dan kemudian melompat tiga sel di udara!

Mengesahkan Pengganti

Sekarang kita mempunyai semua data yang kita perlukan untuk mengesahkan pengganti, jadi mari kita dapatkannya.

Pertama, mari kita batalkan nod jika nilai lompatnya ganjil dan ibu bapa sama ada ke kiri atau ke kanan. Itulah sebabnya jika nilai lompat itu ganjil, maka itu bermakna watak itu pergi ke tepi sekali dan kini ia perlu bergerak sama ada satu blok ke atas atau ke bawah:

Sekiranya watak itu jatuh, dan nod anak berada di atas ibu bapa, maka kita harus melangkauinya. Inilah cara kami mencegah infinitum iklan melompat; sekali nilai melompat mencapai ambang kita hanya boleh turun.

Jika nilai lompat simpul lebih besar dari (enam nilai tambah ambang jatuh), maka kita harus berhenti membenarkan perubahan arah pada setiap nilai lompat. Ini akan menghalang algoritma yang memberikan nilai yang salah apabila wataknya jatuh dengan cepat, kerana dalam hal ini bukannya 1 blok ke sisi dan 1 blok ke bawah, ia perlu memindahkan 1 blok ke sisi dan 2 atau lebih blok ke bawah. (Sekarang, watak itu boleh bergerak 3 blok ke sebelah selepas ia mula jatuh, dan kemudian kita membenarkannya bergerak ke sisi setiap 4 blok yang dilalui secara menegak.)

Sekiranya terdapat keperluan bagi pemeriksaan lompat yang lebih tepat, maka bukannya menolak nod dalam cara yang ditunjukkan di atas, kita boleh membuat jadual carian dengan penentuan data di mana panjang melompat watak itu dapat bergerak ke sisi.

Mengira Kos

Apabila mengira kos nod, kita perlu mengambil kira nilai lompat.

Membuat Watak Bergerak Sensitif

Adalah baik untuk menjadikan watak itu menjadi tanah sebanyak mungkin, kerana ia akan menjadikan pergerakannya kurang melompat ketika bergerak melalui medan datar, dan juga akan menggalakkannya menggunakan jalan yang 'lebih selamat', yang tidak memerlukan panjang jatuh.

Kita boleh dengan mudah membuat watak melakukan ini dengan meningkatkan kos nod mengikut nilai lompatnya. Inilah kod lama:

Dan inilah yang baru:

newJumpLength / 4 berfungsi dengan baik untuk kebanyakan kes; kita tidak mahu wataknya terlalu kuat.

Menghidupkan semula Nod dengan Nilai Lompat Yang Berbeza

Biasanya, apabila kami memproses nod sekali, kami menetapkan statusnya untuk closed dan tidak pernah mengganggu dengannya lagi; Walau bagaimanapun, seperti yang telah kita dibincangkan, kita mungkin perlu melawat satu kedudukan tertentu dalam grid lebih daripada sekali.

Pertama, sebelum kita memutuskan untuk melangkau nod yang sedang diperiksa, kita perlu melihat sama ada terdapat sebarang nod pada kedudukan semasa (x, y). Sekiranya tidak ada nod di sana lagi, maka kami pastinya tidak boleh melangkau masa sekarang:

Satu-satunya syarat yang membolehkan kita melangkau nod adalah ini: nod tidak membenarkan pergerakan baru berbanding dengan nod lain pada kedudukan yang sama.

Pergerakan baru boleh berlaku jika:

  • Nilai lompat nod yang sedang diproses adalah lebih rendah daripada mana-mana nod lain pada kedudukan (x, y) yang sama-dalam kes ini, nod semasa berjanji untuk membiarkan watak melompat lebih tinggi menggunakan laluan ini daripada yang lain.
  • Nilai melompat nod yang sedang diproses adalah sama, dan semua nilai lompat nod lain pada kedudukan tidak. Ini pada asasnya bermakna nod tertentu ini membolehkan pergerakan sisi di kedudukan ini, sementara yang lain memaksa kita bergerak sama ada naik atau turun.

Kes pertama adalah mudah: kita mahu melihat nod dengan nilai lompat yang rendah kerana ini membolehkan kita melompat lebih tinggi. Kes kedua keluar dalam keadaan yang lebih pelik, seperti yang berikut:

Di sini, kita tidak boleh bergerak ke tepi apabila melompat kerana kita mahu memaksa algoritma untuk muncul dua kali selepas memulakan lompatan. Masalahnya adalah, walaupun apabila jatuh, algoritma hanya akan mengabaikan nod dengan nilai melompat 8, kerana kita telah melawat kedudukan itu dan nod sebelumnya mempunyai nilai melompat yang rendah 3. Itulah sebabnya dalam hal ini penting untuk tidak melangkau nod dengan nilai melompat yang lebih tinggi (dan rendah).

Pertama, mari kita menyatakan pembolehubah kami yang akan memberitahu kami apa nilai lompat terendah pada kedudukan semasa (x, y), dan sama ada mana-mana nod di sana membenarkan pergerakan sisi:

Seterusnya, kita perlu melaraskan semua nod dan tetapkan pembolehubah yang diisytiharkan kepada nilai yang bersesuaian:

Seperti yang anda dapat lihat, kami bukan sahaja memeriksa sama ada nilai lompat nod itu adalah sama, tetapi juga sama ada nilai lompat tidak terlalu tinggi untuk bergerak ke sisi.

Akhir sekali, mari kita pergi ke keadaan yang akan menentukan sama ada kita boleh melangkau nod atau tidak:

Seperti yang anda dapat lihat, nod lowestJump jika yang terendahJump kurang atau sama dengan nilai lompat nod yang diproses dan mana-mana nod lain dalam senarai yang dibenarkan untuk pergerakan sisi.

Kita boleh meninggalkan rumus heuristik seperti; kita tidak perlu mengubah apa-apa di sini:

Mengemaskan

Now, finally, since the node has passed all the checks, we can create an appropriate PathFinderNodeFast instance for it.

Dan kita juga boleh akhirnya menambah nod ke senarai nod di mNewLokasi.

Sebelum kita melakukannya, mari kita tambahkan lokasi ke lokasi yang disentuh jika senarai kosong. Kami akan tahu bahawa kami perlu mengosongkan senarai lokasi ini apabila kami menjalankan penunjuk laluan sekali lagi:

Setelah semua kanak-kanak diproses, kita boleh menukar status ibu bapa untuk Closed dan menambah mCloseNodeCounter:

Pada akhirnya, gelung kanak-kanak harus kelihatan seperti ini.

Menapis Nod

Kami tidak semestinya memerlukan semua nod yang akan kami dapatkan dari algoritma. Sesungguhnya, lebih mudah bagi kita untuk menulis AI laluan berikut jika kita menapis nod ke set yang lebih kecil yang boleh kita bekerjasama dengan lebih mudah.

Proses penapisan nod sebenarnya bukan sebahagian daripada algoritma, tetapi agak merupakan operasi untuk mempersiapkan output untuk pemprosesan selanjutnya. Ia tidak perlu dilaksanakan dalam kelas PathFinderFast itu sendiri, tetapi itu akan menjadi tempat yang paling mudah untuk melakukannya untuk tujuan tutorial ini.

Penapisan nod boleh dilakukan bersama kod laluan berikut; ia agak tidak mungkin bahawa kami akan menapis set nod dengan sempurna untuk memenuhi keperluan kami dengan andaian awal kami, jadi, sering, banyak tweak diperlukan. Dalam tutorial ini, kami akan meneruskan dan mengurangkan set ke bentuk akhirnya sekarang, jadi kemudian kami boleh memberi tumpuan kepada AI tanpa perlu mengubah kelas penapis lagi.

Kami mahu penapis kami membiarkan mana-mana nod yang memenuhi syarat berikut:

  1. Ia adalah nod permulaan.
  2. Ia adalah nod akhir.
  3. Ia adalah nod melompat.
  4. Ia adalah nod pertama dalam udara di lompat sampingan (nod dengan nilai melompat sama dengan 3).
  5. Ia adalah nod pendaratan (nod yang mempunyai nilai lompang bukan sifar menjadi 0).
  6. Ia adalah titik tinggi lompat (nod antara bergerak ke atas dan dan jatuh ke bawah).
  7. Ia adalah nod yang menghalang halangan.

Berikut adalah beberapa ilustrasi yang menunjukkan nod yang kita mahu simpan. Nombor merah menunjukkan peraturan mana yang menyebabkan penapis meninggalkan nod dalam laluan:

Menetapkan Nilai

Kami menapis nod apabila mereka ditolak ke senarai mClose, jadi itu bermakna kita akan pergi dari nod akhir ke nod mula.

Sebelum kita memulakan proses penapisan, kita perlu menyediakan beberapa pembolehubah untuk menjejaki konteks nod yang ditapis:

fNode dan fPrevNode adalah Vector2s mudah, manakala fNodeTmp dan fPrevNodeTmp adalah node PathFinderNodeFast. Kita perlukan keduanya; kami akan menggunakan Vector2 untuk mendapatkan kedudukan nod dan objek PathFinderNodeFast untuk mendapatkan lokasi induk, nilai melompat, dan segala yang kami perlukan.

loc points ke kedudukan XY dalam grid node yang akan diproses lelaran seterusnya.

Menentukan Gelung

Kini kita boleh memulakan gelung kami. Kami akan mengekalkan gelung selagi kita tidak dapat nod mula (di mana kedudukan ibu bapa adalah sama dengan kedudukan nod):

Kami akan memerlukan akses kepada nod seterusnya serta yang sebelumnya, jadi mari kita dapatkannya:

Menambah Nod Akhir

Sekarang mari kita mulakan proses penapisan. Nod mula akan ditambah pada senarai pada akhir sekali, setelah semua item lain telah ditangani. Oleh kerana kita pergi dari nod akhir, mari pastikan kita memasukkannya ke dalam laluan akhir kita:

Sekiranya mClose kosong, itu bermakna kita tidak menolak apa-apa nod ke dalamnya lagi, yang bermaksud nod yang sedang diproses adalah nod akhir, dan kerana kita ingin menyertakannya dalam senarai akhir, kita menambahnya kepada mClose.

Menambah Nod Jump

Untuk nod lompat, kami akan menggunakan dua syarat.

Keadaan pertama ialah nilai lompat nod yang sedang diproses adalah 0, dan nilai lompat nod sebelumnya tidak 0:

Keadaan kedua adalah bahawa nilai lompat bersamaan dengan 3. Ini pada dasarnya adalah titik perubahan arah pertama atau pertama di udara dalam lompat tertentu:

Menambah Nod Landing

Sekarang untuk nod pendaratan:

Kami mengesan nod pendaratan dengan melihat nod seterusnya berada di tanah dan nod semasa tidak. Ingat bahawa kami memproses nod dalam urutan terbalik, jadi sebenarnya pendaratan dikesan apabila nod sebelumnya berada di tanah dan current tidak.

Menambah Nod Titik Tertinggi

Sekarang mari kita tambahkan mata tinggi lompat. Kami mengesannya dengan melihat sama ada nod sebelumnya dan nod seterusnya lebih rendah daripada nod semasa:

Perhatikan bahawa, dalam kes terakhir, kita tidak membandingkan koordinat y semasa untuk fPrevNode.y, tetapi pada koordinat y simpulan nod yang terdahulu. Itu kerana mungkin kes nod terdahulu berada pada ketinggian yang sama dengan yang saat ini, jika watak berpindah ke tepi untuk mencapainya.

Menambah Node yang Pergi Sekitar Halangan

Akhirnya, mari kita menjaga nod yang membolehkan kita bergerak sekitar rintangan. Sekiranya kita berada di sebelah halangan dan nod terdorong terdahulu tidak sejajar dengan keadaan semasa sama ada secara melintang atau menegak, maka kita mengandaikan bahawa nod ini akan menyelaraskan kita dengan halangan dan marilah kita bergerak dengan lebih baik jika perlu:

Bersedia untuk Gelung Berikutnya

Selepas menambah nod ke senarai mClose atau mengabaikannya, kami perlu menyediakan pemboleh ubah untuk lelaran berikut:

Seperti yang anda dapat lihat, kami mengira segala-galanya dengan cara yang sama kami menyediakan gelung untuk lelaran pertama.

Menambah Nod Mula

Selepas semua nod telah diproses (dan gelung selesai), kami boleh menambah titik mula ke senarai dan menyelesaikan tugas:

Semua sekali

Prosedur penapisan jalan keseluruhan sepatutnya kelihatan seperti ini.

kesimpulan

Produk terakhir algoritma adalah laluan yang ditemui untuk watak yang satu blok lebar dan satu blok tinggi dengan ketinggian lompat maksimum yang ditetapkan.

Kita boleh memperbaiki ini: kita boleh membenarkan saiz watak itu diubah, kita boleh menambah sokongan untuk platform sehala, dan kita boleh kodkan bot AI untuk mengikuti laluan. Kami akan menangani semua perkara ini di bahagian seterusnya tutorial!

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.