Apakah ada algoritma pathfinding yang akan menangani jenis gerakan yang berbeda?

Saya sedang mengembangkan bot untuk simulator permainan papan BattleTech http://en.wikipedia.org/wiki/BattleTech , ini berbasis giliran.

Papan dibagi menjadi segi enam, masing-masing memiliki jenis medan dan ketinggian yang berbeda. Anda mengendarai robot yang bergerak di atasnya, untuk menghancurkan robot lain.

Saya hanya tahu algoritma Dijkstra dan A * pathfinding, tetapi masalahnya adalah ada 3 jenis gerakan: berjalan, berlari, dan lompat beberapa segi enam (masing-masing memiliki aturan sendiri). Berjalan dan berlari hampir sama.

Jalur terbaik bisa berupa kombinasi atau setiap jenis gerakan. Berikut adalah contoh peta http://megamek.info/sites/default/files/isometric_view.png

Apakah Anda tahu algoritma yang baik untuk penelusuran jalan yang rumit ini atau cara untuk menggabungkan hasil A * untuk setiap jenis gerakan?

ai movement path-finding alexvisio
sumber

Saya pikir ini sering ditangani oleh manipulasi pintar dari jalur tertimbang dengan A * (bobot menjadi biaya jalur / persegi itu). Misalnya, jika melompat lebih disukai, ia mendapat bobot yang lebih rendah (mis. 5) daripada berjalan (mis. 10).

ashes999

Bagaimana sebenarnya ketiga jenis gerakan itu berbeda? Bisakah mereka digabungkan (berjalan ke ubin A, lalu lari ke B dan kemudian melompat ke C pada giliran yang sama)? Bila ya, aturan apa yang mencegah pemain selalu menggunakan metode termurah untuk mendapatkan dari ubin A ke ubin B?

Philipp

@ Pilip Ya mereka bisa, saat menggunakan A *. Anda dapat menambahkan setiap ubin yang bisa Anda pindahkan dengan setiap jenis gerakan ke daftar terbuka, kemudian berdasarkan harga masing-masing + heuristik yang baik Anda dapat menentukan mana yang akan dikembangkan lebih lanjut.

akaltar

@ Pilip Tidak, Anda hanya dapat menggunakan satu jenis gerakan setiap belokan.

alexvisio

Berjalan: bergerak melalui segi enam dengan sedikit perbedaan ketinggian. Jalankan: sama tetapi Anda bisa melangkah jauh, meskipun Anda akan menghasilkan panas dan kehilangan akurasi pengambilan gambar (jadi itu tidak selalu yang terbaik). Lompat: Anda bisa melompati rintangan (dinding atau sungai) alih-alih berjalan di sekitarnya.

alexvisio

Jawaban:

Baik Dijkstra dan A * dapat menambahkan biaya yang berbeda ke tepi (= koneksi) dari satu ubin ke ubin lain. Mereka juga memungkinkan untuk menghubungkan dua node (= petak) dengan lebih dari satu sisi, masing-masing dengan biaya yang berbeda.

Mode lompatan alternatif berarti bahwa ada tepi langsung alternatif dari setiap ubin ke setiap ubin dalam jarak lompat. Tetapi karena suatu mekanisme dapat berjalan atau melompat pada gilirannya, biaya untuk menggunakan tepi ini akan menjadi titik bergerak dari seluruh belokan, ditambah poin yang tersisa dari belokan saat ini ketika sudah ada gerakan belokan ini.

Menurut uraian Anda, keputusan untuk berjalan vs berlari tidak membuat banyak perbedaan mengenai pilihan jalur, tetapi lebih merupakan keputusan strategis untuk dibuat. Aktor pasti bisa berjalan ketika tujuan dapat dicapai pada giliran saat ini tanpa menggunakan berlari. Tetapi sebaliknya ada banyak faktor yang menjadi faktor, seperti:

tingkat panas saat ini dan kemungkinan terlibat dalam pertempuran sebelum menjadi dingin
kesulitan setiap tembakan yang perlu ditembakkan babak ini
betapa pentingnya secara strategis untuk mencapai tujuan dengan cepat

Tidak ada aturan keras untuk membuat keputusan ini. Yang terbaik yang dapat Anda lakukan adalah menggunakan pendekatan heuristik. Tetapkan nilai poin positif atau negatif untuk semua keadaan, tambahkan, dan lihat apakah hasilnya positif atau negatif.

Ada juga faktor lain dalam pencarian jalan yang harus Anda pertanggungjawabkan: Dalam beberapa kondisi, masuk akal bagi mekanisme untuk menghindari mengakhiri gilirannya di lokasi tertentu. Saat berada di area berbahaya, menggunakan tiga belokan untuk beralih dari A ke B tetapi mengakhiri masing-masingnya dalam penutup mungkin lebih baik daripada hanya menggunakan dua, tetapi diekspos di akhir masing-masing. Atau mungkin tidak. Itu tergantung pada keadaan dan mekanisme permainan yang tepat. Sekali lagi, ini adalah keputusan strategis yang harus Anda buat berdasarkan heuristik. Anda bisa mewakili ini dengan menambahkan biaya tambahan ke tepi yang mengakhiri pergantian ubin berbahaya untuk mencegah AI membuat langkah ini.

Philipp
sumber