apa solusi standar untuk merintis jalan menuju target yang bergerak?

Saya mengerjakan game 2D RTS seperti, dasar A * bekerja dengan sempurna untuk memindahkan unit dari titik A ke titik B.

Tapi sekarang saya menghadapi masalah pencarian jalur terus menerus, seperti serangan pada objek bergerak B, panggil A * di setiap frame begitu posisi Objek B berubah tampaknya tidak efisien.

jadi apa metode standar untuk masalah ini?

Dari apa yang saya tahu, Anda bisa melihat pada algoritma D * yang merupakan singkatan dari "Dynamic A *". Algoritma ini digunakan untuk menghitung pathfinding untuk lingkungan yang dinamis, di sini dengan target bergerak.

Berikut ini makalah yang menggunakan D * untuk memindahkan pencarian jalur target: Memindahkan Target D * Lite

Salah satu opsi adalah dengan hanya membuat jalur baru setiap beberapa frame. Jika Anda melakukannya sekali atau dua kali per detik daripada 60+ kali per detik, maka pengguna tidak akan melihat kecuali mereka berdua adalah dua objek yang bergerak sangat cepat

Anda dapat menggunakan pendekatan "kurva anjing" yang tampaknya digunakan anjing saat memburu seseorang. Mereka menghitung di mana titik impak akan berada "di masa depan" dan set langsung ke posisi itu.

Cara perkiraan sederhana bisa berupa sesuatu:

A = NPC

B = Target

T = waktu untuk sampai ke posisi B: s (B: posisi awal)

Hitung di mana B akan berada dalam waktu 'T' (jika B terus pada kecepatan / sudut yang sama) dan pergi ke sana.

Ini bukan cara yang sempurna karena jarak berubah tetapi jauh lebih sederhana daripada membuat solusi yang sempurna dan jauh lebih baik daripada hanya mencoba untuk mendapatkan 'B'.

Setuju dengan Kylotan bahwa tidak ada metode standar .

Salah satu metode yang saya lihat berhasil adalah dengan mengasumsikan target terus bergerak ke arah yang sama dan mengubah posisi tujuan saat Anda menjalankan algoritma pencarian jalur Anda. Ini berarti Anda harus memegang dua metrik di simpul A * Anda (biaya dan waktu sebagai lawan dari biaya yang adil).

Melakukan yang lebih baik dari itu sangat sulit. Kecuali jika Anda benar-benar memiliki pengetahuan tentang jalan yang tidak tergoyahkan dari target, Anda menuju ke tanah AI yang cukup sulit karena Anda akan memiliki tebakan kedua AI atau mensimulasikan perilaku target untuk menebak di mana mereka akan berada dan jalan menuju itu. AI semacam ini adalah game AB real-time dari teori game, sebuah area yang tidak standar dalam toolkit AI game 3D mana pun.

Salah satu cara untuk melakukan pencarian jalur dinamis adalah membuat entitas memprediksi ke mana target pergi dan pergi ke sana.

Salah satu cara untuk melakukan ini adalah menggunakan seri Taylor.

Saya akan memanggil lintasan target dari waktu ke waktu fungsi S (t) di mana S adalah posisi dan t adalah waktu saat ini dan perkiraan untuk lintasan adalah A (f) dan f adalah tanggal di masa depan yang mendekati .

Maka pendekatan yang paling sederhana dan paling bodoh adalah A (f) = 0.

Yang paling sederhana berikutnya adalah A (f) = S (t) di mana t adalah waktu saat ini dan f adalah masa depan. Ini memprediksi target hanya berhenti di tempatnya.

Yang paling sederhana ketiga adalah A (f) = S '(t) * f + S (t) di mana S' adalah turunan dari S sehubungan dengan waktu. Ini memprediksi target berlanjut pada kecepatan konstan tanpa akselerasi.

Yang paling sederhana adalah A (f) = S '' (t) * f ^ 2/2 + S '(t) * f + S (t). Ini memprediksi targetnya melaju dengan kecepatan konstan seperti bola yang jatuh.

Saya tahu ini bisa diulang dalam hal perubahan waktu yang mungkin lebih nyaman untuk permainan. Sekarang S bisa apa saja. Bisa jadi koordinat X, bisa koordinat Y, bisa jarak antara objek, bisa juga sudut. Juga ada kemungkinan metode yang lebih baik untuk memprediksi jalur masa depan suatu objek jadi saya akan melihat-lihat sedikit.

Jika medan cukup terbuka dan target tidak terlalu jauh dari pengejar, maka Anda dapat menggunakan perilaku kemudi intersep. Pada dasarnya, Anda mengambil posisi dan kecepatan target untuk menghitung posisi di depan target yang tidak terlalu jauh, dan tidak terlalu dekat, dan Anda mengarahkan pengejar menuju titik itu (dihitung masing-masing secara berkala).