Advertisement
  1. Game Development
  2. Pathfinding
Gamedevelopment

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

by
Difficulty:IntermediateLength:MediumLanguages:
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: Implementation

Malay (Melayu) translation by Adjatay Bashroh Aldad (you can also view the original English article)

A* berasaskan grid berfungsi dengan baik untuk permainan di mana watak-watak boleh bergerak dengan bebas di sepanjang kedua-dua paksi x dan y. Masalah dengan menggunakan ini kepada platformer adalah bahawa pergerakan pada paksi-y adalah sangat terhad, kerana kuasa graviti simulasi.

Dalam tutorial ini, saya akan memberikan gambaran keseluruhan tentang cara mengubah suai algoritma A * standard untuk bekerja dengan platformer dengan mensimulasikan sekatan graviti ini. (Di bahagian seterusnya, saya akan berjalan dengan betul mengetik algoritma.) Algoritma yang disesuaikan boleh digunakan untuk membuat aksara AI yang mengikuti pemain, atau untuk menunjukkan pemain laluan ke matlamat mereka, contohnya.

Saya menganggap bahawa anda sudah biasa dengan A * pathfinding, tetapi jika anda memerlukan pengenalan, Patrick Lester A * Pathfinding for Beginners sangat baik.

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.

Menjelang akhir siri ini, kami juga akan menambah platform sehala, memperluaskan kod untuk menangani pelbagai saiz watak, dan mengodkan bot yang secara automatik boleh mengikuti laluan! Semak demo Unity di sini (atau versi 100MB+ WebGL).

Menetapkan Peraturan

Sebelum kita dapat mengadaptasi algoritma pathfinding, kita perlu mendefinisikan secara jelas apa bentuk laluan yang boleh diambil sendiri.

Apa yang boleh dilakukan oleh Watak?

Katakan watak kita mengambil satu sel, dan boleh melompat tiga sel tinggi.

Kami tidak akan membenarkan watak kami bergerak secara menyerong melalui sel, kerana kami tidak mahu ia melalui medan pepejal. (Iaitu, kita tidak akan membenarkannya bergerak melalui sudut sel, hanya melalui bahagian atas, bawah, kiri, atau kanan.) Untuk bergerak ke sel bersebelahan yang menyerong, watak mesti memindahkan satu sel ke atas atau ke bawah, dan satu sel ke kiri atau ke kanan.

Oleh kerana ketinggian lompat watak adalah tiga sel, maka apabila ia melompat, selepas ia bergerak tiga kali, ia tidak boleh bergerak ke mana-mana sel lagi, tetapi ia masih dapat bergerak ke sisi.

Berdasarkan peraturan ini, inilah contoh laluan yang akan diambil oleh watak semasa lompat jarak maksimumnya:

Sudah tentu watak itu boleh melompat lurus, atau dengan mana-mana gabungan gerakan kiri dan kanan, tetapi contoh ini memperlihatkan jenis penghampiran yang kita perlukan untuk merangkul ketika mengira laluan menggunakan grid.

Mewakili Jalur Lompat Dengan Nilai Lompat

Setiap sel dalam laluan perlu menyimpan data tentang ketinggian melompat, supaya algoritma kami dapat mengesan bahawa pemain dapat melompat tidak lebih tinggi dan harus mulai jatuh.

Mari kita mulakan dengan menetapkan setiap nilai lompat sel dengan meningkatkannya dengan satu, setiap sel, selagi lompatan berterusan. Sudah tentu, apabila wataknya berada di atas tanah, nilai lompatan mestilah 0.

Inilah peraturan yang diterapkan pada laluan lompat jarak jauh yang sama dari sebelumnya:

Sel yang mengandungi 6 menandakan titik tertinggi dalam laluan. Ini masuk akal, kerana itu dua kali nilai ketinggian maksimum lompat watak, dan bergantian watak menggerakkan satu sel ke atas dan satu sel ke sisi, dalam contoh ini.

Perhatikan bahawa, jika watak melompat lurus, dan kita terus meningkatkan nilai lompat oleh satu setiap sel, maka ini tidak lagi berfungsi, kerana dalam kes itu sel tertinggi akan mempunyai nilai melompat 3.

Mari ubah suai peraturan kami untuk meningkatkan nilai lompat ke nombor seterusnya  apabila watak bergerak ke atas. Kemudian, jika nilai melompat adalah sama, watak boleh bergerak sama ada kiri, kanan, atau bawah (atau naik, jika mereka belum mencapai nilai melompat 6 lagi), dan jika nilai melompat adalah ganjil, watak itu hanya bergerak atas atau ke bawah (bergantung kepada sama ada mereka telah mencapai puncak melompat lagi).

Inilah yang kelihatan seperti untuk lompat terus:

Dan inilah satu kes yang lebih rumit:

Begini bagaimana nilai lompat dihitung:

  1. Mulakan di tanah: nilai melompat ialah 0.
  2. Lompat mendatar: meningkatkan nilai lompat sebanyak 1, jadi nilai melompat ialah 1.
  3. Lompat menegak: meningkatkan nilai lompat ke nombor seterusnya seterusnya: 2.
  4. Lompat menegak: meningkatkan nilai lompat ke nombor seterusnya seterusnya: 4.
  5. Lompat mendatar: meningkatkan nilai lompat sebanyak 1; nilai melompat sekarang 5.
  6. Lompat menegak: tambah nilai ke nombor seterusnya seterusnya: 6. (Aksara tidak lagi boleh bergerak ke atas, jadi hanya kiri, nod kanan dan bawah tersedia.)
  7. Jatuh secara mendatar: meningkatkan nilai lompat sebanyak 1; nilai melompat sekarang 7.
  8. Kejatuhan menegak: meningkatkan nilai lompat ke nombor seterusnya seterusnya: 8.
  9. Kejatuhan menegak: menambah nilai ke nombor seterusnya: 10.
  10. Kejatuhan menegak: kerana wataknya sekarang berada di tanah. tetapkan nilai lompat kepada 0.

Seperti yang dapat anda lihat, dengan penomboran jenis ini kita tahu betul-betul apabila watak itu mencapai ketinggian lompat maksimum: ia adalah sel dengan nilai lompat bersamaan dengan dua kali lompat ketinggian maksimum aksara. Jika nilai melompat kurang daripada ini, watak itu masih boleh bergerak ke atas; sebaliknya, kita perlu mengabaikan simpul secara langsung di atas.

Menambah Selaras

Sekarang kita sedar akan jenis pergerakan watak yang boleh dibuat pada grid, mari kita pertimbangkan persediaan berikut:

Sel hijau di kedudukan (3, 1) adalah watak; sel biru di kedudukan (2, 5) adalah matlamat. Mari kita buat laluan yang boleh dipilih oleh algoritma A * terlebih dahulu untuk mencapai matlamat@

Nombor kuning di sudut kanan atas sel ialah nilai lompat sel. Seperti yang anda dapat lihat, dengan melompat lurus ke atas, watak itu boleh melompat tiga jubin, tetapi tidak lagi. Ini tidak baik.

Kami mungkin mendapati lebih banyak nasib dengan laluan lain, jadi mari kita gulung semula carian kami dan mulakan semula dari simpul (3, 2).

Seperti yang anda dapat lihat, melompat di blok ke kanan wataknya membolehkannya melompat cukup tinggi untuk sampai ke matlamat! Walau bagaimanapun, terdapat masalah besar di sini ...

Lagipun, laluan pertama yang akan diambil oleh algoritma adalah yang pertama kita periksa. Selepas mengambilnya, algoritma tidak akan jauh, dan akan berakhir kembali pada nod (3, 2). Ia kemudian boleh mencari melalui nod (4, 2), (4, 3), (3, 3) (sekali lagi), (3, 4) (lagi), (3, 5), dan akhirnya sel sasaran,(2 , 5).

Dalam versi asas algoritma A *, jika nod telah dikunjungi sekali lagi, maka kita tidak perlu memprosesnya lagi. Walau bagaimanapun, dalam versi ini, kita lakukan. Ini kerana nod tidak dibezakan semata-mata oleh koordinat x dan y, tetapi juga dengan melompat nilai.

Dalam percubaan pertama kami untuk mencari laluan, nilai lompatan pada simpul (3, 3) ialah 4; dalam percubaan kedua kami, adalah 3. Oleh kerana dalam percubaan kedua, nilai melompat pada sel itu lebih kecil, itu bermakna bahawa kita berpotensi mendapat lebih tinggi daripada sana daripada yang kita boleh semasa percubaan pertama.

Ini pada dasarnya bermakna nod (3, 3) dengan nilai lompat 4 adalah nod yang berbeza daripada nod pada (3, 3) dengan nilai melompat 3. Grid pada dasarnya perlu menjadi tiga dimensi di beberapa koordinat untuk menampung untuk perbezaan ini, seperti:

Kita tidak boleh menukar nilai lompat node pada (3, 3) dari 4 hingga 3, kerana beberapa laluan menggunakan nod yang sama beberapa kali; jika kita berbuat demikian, kita pada dasarnya akan mengatasi nod terdahulu dan yang tentunya akan merosakkan keputusan akhir.

Kami akan mempunyai masalah yang sama jika laluan pertama akan mencapai matlamat walaupun nilai lompat yang lebih tinggi; jika kita telah mengatasi salah satu nod dengan yang lebih menjanjikan, maka kita tidak akan mempunyai cara untuk memulihkan jalan asal.

Kekuatan dan Kelemahan Menggunakan Pathfinding Berdasarkan Grid

Ingat, itu adalah algoritma yang menggunakan pendekatan berasaskan grid; secara teori, permainan anda dan tahapnya tidak perlu.

Kekuatan

  • Bekerja dengan baik dengan permainan berasaskan ubin.
  • Memperluaskan algoritma A * asas, jadi anda tidak perlu mempunyai dua algoritma yang berbeza untuk watak terbang dan tanah.
  • Bekerja dengan baik dengan medan dinamik; tidak memerlukan proses membina nod yang rumit.

Kelemahan

  • Ketidaktepatan: jarak minimum ialah saiz satu sel tunggal.
  • Memerlukan perwakilan grid bagi setiap peta atau peringkat.

Keperluan Engine dan Fizik

Kebebasan Watak vs Algoritma Kebebasan

Adalah penting bagi watak untuk mempunyai sekurang-kurangnya kebebasan pergerakan kerana algoritma menjangkakan-dan sebaik—baiknya sedikit lebih daripada itu.

Memiliki padanan pergerakan watak dengan tepat kekangan algoritma bukan pendekatan yang berdaya maju, kerana sifat diskret grid dan saiz sel grid. Ia adalah mungkin untuk kod fizik sedemikian rupa sehingga algoritma akan sentiasa mencari jalan jika ada, tetapi itu memerlukan anda untuk membina fizik untuk tujuan itu.

Pendekatan yang saya ambil dalam tutorial ini adalah untuk menyesuaikan algoritma kepada fizik permainan, bukan sebaliknya.

Masalah utama berlaku pada kes kelebihan apabila kebebasan gerakan kebebasan yang diharapkan oleh algoritma tidak sesuai dengan kebebasan pergerakan karakter dalam permainan.

Apabila Karakter Mempunyai Kebebasan Lebih Daripada Algoritma Yang Diharapkan

Katakan AI membolehkan lompatan enam sel panjang, tetapi fizik permainan membolehkan lompatan tujuh sel. Sekiranya terdapat laluan yang memerlukan lompat lagi untuk mencapai matlamat dalam masa yang paling cepat, maka bot akan mengabaikan laluan itu dan memilih yang lebih konservatif, memikirkan bahawa lompat yang lebih lama tidak mungkin.

Sekiranya terdapat laluan yang memerlukan lompat yang lebih panjang dan tidak ada cara lain untuk mencapai matlamat, maka penemudi akan menyimpulkan bahawa matlamatnya tidak dapat dicapai.

Apabila Algoritma Mengharapkan Kebebasan Lebih Daripada Watak Yang Telah

Jika, sebaliknya, algoritma itu menganggap bahawa ia adalah mungkin untuk melompat tujuh sel lagi, tetapi fizik permainan sebenarnya membenarkan hanya untuk melompat enam sel, maka bot mungkin mengikuti jalan yang salah dan jatuh ke tempat yang tidak dapat keluar, atau cuba mencari laluan sekali lagi dan terima hasil yang tidak betul yang sama, menyebabkan gelung.

(Daripada dua masalah ini, lebih baik untuk membenarkan fizik permainan membolehkan lebih banyak pergerakan bergerak daripada algoritma yang diharapkan.)

Menyelesaikan Masalah Ini

Cara pertama untuk memastikan bahawa algoritma sentiasa betul adalah untuk mempunyai tahap yang pemain tidak boleh mengubah suai. Dalam kes ini, anda hanya perlu memastikan bahawa apa jua bidang yang anda reka atau menghasilkan kerja dengan baik dengan laluan laluan AI.

Penyelesaian kedua untuk masalah ini adalah untuk mengubah taraf algoritma, fizik, atau kedua-duanya, untuk memastikan bahawa ia sepadan. Seperti yang saya nyatakan sebelum ini, ini tidak bermakna mereka perlu dipadankan dengan tepat; contohnya, jika algoritma itu memikirkan watak itu boleh melompat lima sel ke atas, ia adalah baik untuk menetapkan lompatan maksimum sebenar pada 5.5 sel tinggi. (Tidak seperti algoritma, fizik permainan boleh menggunakan nilai fraksional.)

Bergantung kepada permainan, ia juga boleh menjadi kenyataan bahawa bot AI tidak mencari jalan yang ada tidak banyak masalah; ia hanya akan menyerah dan kembali kepada jawatannya, atau duduk dan menunggu pemain.

Kesimpulan

Pada ketika ini, anda harus mempunyai pemahaman konseptual yang baik tentang bagaimana A * pathfinding dapat disesuaikan dengan platformer. Dalam tutorial saya yang akan datang, kami akan membuat konkrit ini, dengan sebenarnya menyesuaikan algoritma A * pathfinding yang ada untuk melaksanakannya dalam permainan!

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.