A * Algoritma untuk RPG Taktis?

Saya bermain-main dengan menulis RPG taktis yang benar-benar buruk di C ++. Sejauh ini saya memiliki peta ubin 2D dan baru saja mendapatkan algoritma A * yang bekerja berdasarkan pseudocode di wikipedia .

Tetapi RPG taktis yang sebenarnya tidak hanya menemukan jalur terbaik pada bidang datar dan pindah ke sana. Mereka biasanya memiliki rentang pergerakan terbatas dan harus naik atau turun. Jika Anda pernah memainkan Final Fantasy Tactics, ini akan dipengaruhi oleh statistik Move and Jump. Di sinilah saya tersesat. Bagaimana cara mengubah algoritme A * sehingga menemukan jalur terbaik menuju target, tetapi jalur tersebut panjangnya hanya beberapa ubin? Bagaimana saya harus memperhitungkan perbedaan ketinggian dan memasukkan statistik? Bagaimana cara menerapkan melompati celah?

Jika itu membantu, sekarang peta saya diwakili oleh objek Vector of Tile. Setiap ubin memiliki pointer ke ubin Utara, Selatan, Timur, dan Barat, yang diatur ke nullptr jika tidak ada ubin yang ada di sana, seperti di sepanjang tepi peta atau jika ubin diatur ke tidak dapat dilewati.

Pendakian, dan kesenjangan, hanyalah fungsi biaya yang berbeda. Untuk unit yang dapat melompat kesenjangan memiliki biaya normal (?), Sedangkan untuk unit non-melompat memiliki biaya tinggi yang sewenang-wenang. Memanjat biaya tambahan, seperti medan yang sulit, dll. Algoritma A * mampu menangani fungsi biaya dengan baik, jadi jika implementasi Anda belum melakukannya, cukup google untuk cara menerapkan A * dengan fungsi biaya.

Karena itu, saya tidak berpikir A * adalah pendekatan yang sangat baik untuk RPG taktis. Atau lebih tepatnya, ini bukan cerita yang lengkap. Anda tidak ingin unit Anda melakukan kesalahan secara membabi buta terhadap tujuan mereka, Anda ingin mereka memposisikan diri mereka sendiri untuk mengeksploitasi perlindungan, kedudukan tinggi, apa pun, sembari berkembang menuju tujuan akhir dan berusaha untuk mengapit lawan dan sebagainya. Jadi nilai taktis dari titik akhir dari setiap gerakan adalah sangat penting, bukan hanya seberapa dekat itu tujuannya. Ini membutuhkan penyelesaian masalah yang lebih mendalam daripada sekadar merintis jalan.

Saat Anda menginginkan semua opsi gerakan yang dimungkinkan dari suatu unit, gunakan Algoritma Dijkstra .

Perbedaan antara A * dan Dijkstra adalah Dijkstra memberi Anda semua rute terpendek yang mungkin dicapai dengan biaya yang diberikan, dan jika belum ada yang mencapai tujuan Anda, itu akan menambah biaya satu per satu dan berlanjut. A *, di sisi lain, lebih memilih untuk menghitung rute-rute tersebut terlebih dahulu yang memiliki peluang bagus untuk mencapai tujuan.

Jadi, ketika Anda hanya ingin jalur terpendek dari titik A ke titik B, maka A * adalah pilihan yang baik. Tetapi jika Anda menginginkan semua opsi gerakan yang mungkin dan jalur terpendek untuk masing-masingnya, maka Dijkstra adalah yang Anda inginkan.

Yang perlu Anda lakukan adalah menjalankan Algoritma Dijksta tanpa simpul tujuan tertentu, tetapi dengan biaya maksimum yang tidak boleh dilampaui (rentang pergerakan unit). Ketika bepergian ke sebuah simpul akan melebihi biaya maksimum, jangan mengunjunginya. Ketika algoritma berakhir karena kurangnya tepi yang belum dikunjungi, setiap node dalam set yang dikunjungi adalah tujuan yang mungkin, dan penanda node sebelumnya dari node membentuk daftar tertaut yang mewakili jalur kembali ke node awal.

Mengenai lompatan: Itu bisa direpresentasikan sebagai keunggulan lain di A * dan Dijkstra. Mereka dapat memiliki biaya yang sama dengan melintasi tepi reguler atau yang berbeda. Anda juga dapat melewatkan parameter "jump_height" ke algoritma yang memberitahu algoritma untuk mengabaikan jump-edge yang melebihi ketinggian yang diberikan.

Jawaban lain memiliki beberapa informasi yang baik, jadi pastikan untuk membacanya.

Namun, untuk menjawab pertanyaan Anda: berdasarkan pseudocode yang Anda tautkan, Anda memiliki beberapa fungsi heuristic_cost_estimate tautkan mana Anda menghitung biaya dari tileA ke tileB (dengan asumsi mereka berbatasan). Alih-alih menggunakan flat (1) untuk biaya itu, Anda harus menyesuaikannya untuk menyertakan statistik ubin dan statistik unit, dan mungkin statistik tepi.

Sebagai contoh:

if (edge == JUMP && !unit.canJump()) 
    return INF;
if (tile.Type == Forest && unit.moveType == HORSE) 
    return 2;
//Other cases here
//-----
else 
    return 1;

Ini akan memberi Anda jalan Anda. Kemudian, Anda cukup memindahkan unit di sepanjang jalan mereka sambil mengkonsumsi titik gerakan dan menghentikan mereka ketika tetap Points <edgeCost. Perhatikan bahwa ini mungkin tidak sepenuhnya optimal jika Anda berakhir dengan tersisaPoints = 1, tetapi harus cukup baik untuk RPG latihan. Pada kenyataannya, Anda ingin lebih taktis, seperti yang ditunjukkan Jack Aidley!

Tantangan:
Jika Anda ingin menjadi lebih maju, Anda mungkin ingin menggunakan Djikstras seperti yang disarankan untuk menemukan semua ruang dalam jarak X, maka Anda ingin mengevaluasi setiap ruang dalam daftar itu untuk tempat "terbaik", berdasarkan kedekatan dengan target, pertahanan kekuatan, apakah Anda dapat diserang dari posisi itu, dll. Berdasarkan info itu, Anda akan memilih ubin, kemudian pindah ke sana mengikuti jalan yang baru saja Anda hitung menggunakan Djikstras.

Panjat dan celah cukup sepele karena hanya memodifikasi biaya. Pathfinding (dan sebagian besar AI taktis) adalah semua tentang merangkum biaya pada semua node yang harus dikunjungi dan meminimalkan itu. Tebing yang dapat dilewati akan memiliki biaya tak terhingga (sangat, sangat tinggi), lereng akan memiliki biaya lebih tinggi dari biasanya, dll.

Akan tetapi, ini menemukan jalur optimal secara global yang bukan solusi terbaik karena musuh sesungguhnya biasanya tidak menemukan jalur optimal. Ini sangat tidak realistis, kadang-kadang ke titik yang jelas bagi pemain, dan menjengkelkan (terutama ketika AI seperti itu pada dasarnya tak terkalahkan karena ia juga memilih yang optimal).

Simulasi yang baik sengaja tidak menemukan jalan terbaik. Algoritme yang jauh lebih baik adalah melakukan penelusuran hierarkis - jika tidak ada yang lain, dengan menggambar garis lurus di peta, dan mengambil 4-5 titik arah, kemudian menelusuri jalur dari satu titik jalan ke titik berikutnya, mengingat hanya bobot simpul yang jauh dikenal, dan mengatur semua bobot node lainnya untuk "acuh tak acuh". Sebagai alternatif, Anda dapat menjalankan A * pada grid kasar terlebih dahulu, dan kemudian pathfind dari satu node besar ke yang berikutnya (tapi saya menduga menggambar garis pada peta juga baik-baik saja).

Ini jauh lebih realistis (dan juga mengkonsumsi sebagian kecil dari kekuatan pemrosesan karena grafiknya jauh lebih kecil). Ya, itu bisa berarti bahwa unit bergerak ke arah tebing hanya untuk mengetahui bahwa itu tidak bisa menyeberang. Tidak apa-apa, itu juga terjadi pada musuh nyata. Lain kali, itu tidak akan terjadi lagi (karena sekarang biaya tak terbatas diketahui).