Saya membuat beberapa AI dasar untuk scroller samping saya dan saya perlu tahu apakah unit AI dapat mencapai titik B dari titik A hanya dengan mengambil lompatan.
Lintasan penerbangan karakter saya agak tidak biasa karena mereka dapat menerapkan gaya di udara (seperti dalam Jazz Jackrabbit 2 misalnya), jadi tidak seperti lintasan klasik proyektil yang sekitar ...
jalur yang dilemparkan atau diluncurkan proyektil akan mengambil (...) tanpa dorongan.
... Saya kira masalah saya lebih pada proyektil dengan propulsi (mis. Roket).
Untuk mengilustrasikannya, ini adalah bagaimana kurva penerbangan terlihat untuk karakter saya jika saya melompat dan terus menekan "tombol kiri" (terlihat berbeda di ujung kiri, ini adalah tempat saya membuat beberapa manuver di udara):
Gaya yang diterapkan selama penerbangan selalu sejajar dengan sumbu X, jadi itu adalah F = (-f, 0) jika saya menahan "kiri" dan itu adalah F = (f, 0) jika saya memegang "kanan".
Dia bisa bergerak sangat seperti pelompat ski:
Jadi sangat berbeda dari lintasan klasik yang hanya parabola (sumber: wikipedia ):
Untuk membuatnya lebih sulit, saya mensimulasikan hambatan udara sederhana sehingga karakter saya dapat mempercepat hanya hingga beberapa nilai kecepatan maksimum.
Ini dilakukan dengan menerapkan kekuatan kecil dalam arah perjalanan yang berlawanan :
b2Vec2 vel = body->GetLinearVelocity();
float speed = vel.Normalize(); //normalizes vector and returns length
body->ApplyForce( AIR_RESISTANCE_MULT * speed * speed * -vel, body->GetWorldCenter() );
AIR_RESISTANCE_MULT adalah konstanta yang dalam kasus saya sama dengan 0,1.
Mari kita asumsikan bahwa karakter saya adalah titik yang sangat kecil.
Dan saya TIDAK mempertimbangkan penghalang, jadi pertanyaan saya seperti ini ...
Cara menentukan (setidaknya dugaan andal), mengingat kecepatan awal V, impuls J = (0, -j) yang saya terapkan pada karakter saat melompat, gravitasi G = (0, g) , gaya F = (+ -f , 0) terus diterapkan selama penerbangan dan AIR_RESISTANCE_MULT jika kita benar-benar memutuskan untuk memperhitungkan hambatan udara (ini opsional) , apakah suatu titik terletak di bawah kurva yang ditarik oleh jalur yang akan diambil oleh karakter saya?
Saya benar-benar tidak tahu harus mulai dari mana dengan perhitungan dan pada kenyataannya, saya belum tentu tertarik dengan jawaban yang tepat; hack / pendekatan yang berfungsi dengan baik akan sangat bagus sebagai AI yang tidak perlu bertindak dengan sempurna.
sunting: Saya telah memutuskan untuk menyelesaikan ini menggunakan simulasi seperti yang disarankan Jason, tetapi bagaimana menangani kasus seperti itu?
Haruskah saya menggambar segmen dari C ke D dan memeriksa apakah titik yang diinginkan ada di bawah segmen ini?
Atau haruskah saya biner mencari timesteps antara C dan D untuk mencari titik yang cukup dekat dalam jarak horizontal ke titik yang diinginkan, dan hanya kemudian memeriksa perbedaan vertikal? (Sepertinya agak berlebihan bagiku)
sumber
Jawaban:
Saat Anda menyatakan, pilihan terbaik adalah perkiraan, dalam hal ini menggunakan skema numerik. Bagilah waktu menjadi timesteps besar (katakanlah 100-300ms), dan gunakan perkiraan parabola untuk setiap catatan waktu. Kekuatannya sama di seluruh kecuali hambatan udara. Lintasan parabola pada dasarnya untuk akselerasi konstan, tetapi dengan hambatan udara akselerasi berubah karena gaya bergantung pada kecepatan. Perkiraan yang masuk akal adalah memperlakukan hambatan udara sebagai konstan pada setiap catatan waktu. Tetapi menggunakan pendekatan kuadratik (yaitu parabola) ketika mengintegrasikan memungkinkan Anda untuk menangani langkah waktu yang jauh lebih besar. Kemudian Anda hanya menghitung sampai parabola melintasi titik yang diinginkan dalam arah horizontal, dan kemudian membandingkan ketinggian.
EDIT: Sedikit lebih detail tentang perbandingan. Anda tahu bahwa di atas timestep (yang mungkin banyak di frame game), bahwa pemain melewati target
<targetx,targety>
. Jalan mereka digambarkan oleh posisi di<ax*t^2 + bx*t + cx, ay*t^2 + by*t + cy>
mana:t
adalah waktu melalui timestep (0 <= t <= dt
) dan juga untuky
. Jadi ketikat=0
karakter berada di posisi sebelumnya, dan kapant=dt
, mereka berada di posisi berikutnya. Perhatikan bahwa ini pada dasarnya adalah pembaruan Euler yangdt
diganti oleht
sehingga kami dapat menghitung di mana saja di sepanjang lintasan. Sekarang kita tahu posisi-x adalah fungsi kuadratik, sehingga kita dapat menyelesaikanax*t^2 + bx*t + cx = targetx
dan mendapatkan (hingga) dua kali selama langkah di mana karakter langsung di atas atau di bawah target. Lalu kami membuang solusi yang tidak ada dalam jangkauan [0,dt
], karena ini tidak ada di timestep saat ini. (Untuk ketahanan, tambahkan konstanta kecil ke ujung rentang sehingga Anda tidak memiliki masalah pembulatan). Sekarang kami tidak dapat menemukan solusi (setelah pemfilteran), dalam hal ini kami tidak mencapai target waktu ini. Kalau tidak, kami mengevaluasiay*t^2 + by*t + cy
di solusi, dan membandingkan ini dengantargety
. Perhatikan bahwa Anda bisa berada di atas target pada satu titik di lintasan Anda, dan di bawahnya nanti (atau sebaliknya). Anda harus menafsirkan situasi seperti itu sesuai dengan apa yang ingin Anda lakukan.Mempertimbangkan banyak timesteps jauh lebih mudah daripada menemukan solusi analitik untuk masalah awal, dan jauh lebih fleksibel karena Anda dapat mengubah model gerak dan ini masih akan bekerja secara kasar.
Poin bonus untuk menggunakan langkah-langkah variabel, misalnya, 100 ms untuk detik pertama (sepuluh poin), 200 ms untuk dua berikutnya (sepuluh poin lebih), 400 ms lebih dari 4 detik, dll. Bahkan, ketika karakter Anda mendekati kecepatan terminal variasi dalam resistensi turun, dan Anda tidak perlu timesteps yang lebih besar pula. Dengan cara ini Anda dapat menangani lompatan yang sangat panjang tanpa terlalu banyak pemrosesan, karena kompleksitas untuk detik T adalah O (log T) daripada O (T).
Anda juga dapat mensimulasikan apa yang terjadi ketika karakter berhenti meningkatkan sebagian melalui lompatan mereka, atau mulai meningkatkan dengan cara lain. Dengan trik di atas kompleksitasnya adalah O ((log T) ^ 2), yang tidak terlalu buruk.
sumber
x'= x + v*dt
. Sebaliknya gunakanx' = x + v*dt + 1/2*a*dt*dt
. Ketikadt
kecil,dt^2
kecil, jadi umumnya ditinggalkan dalam integrasi Euler tradisional dalam permainan. Di sinidt
tidak kecil, jadi Anda perlu istilah akselerasi. Karenadt
dinaikkan ke kekuatan kedua, ini adalah integrasi kuadratik, dan jalurnya adalah parabola, karenanya perkiraan parabola. RK4 pada dasarnya menghitung turunan yang lebih tinggi, sehingga bisa memberikan perkiraan kubik, kuartik, kuintik, dll. RK4 berlebihan untuk hal ini, kemungkinan besar, karena stabilitas tidak penting.v' = v + a*dt
Yay! Saya melakukannya!
Saya menggunakan simulasi sederhana yang mengambil posisi pertama untuk mendarat di belakang sumbu vertikal dari titik target - dari sana, saya mengambil posisi simulasi sebelumnya dan membuat segmen. Sekarang saya memeriksa apakah titik target di bawah segmen ini. Jika ya - kita bisa melompat ke sana.
Ini adalah karakter yang dikendalikan pemain di gif. Merah muda adalah jalur yang diprediksi, segmen kuning diperkirakan posisi melangkah berikutnya, dan segmen terakhir berubah putih jika titik target terletak di bawahnya, merah sebaliknya. Kurva merah adalah jalur penerbangan yang sebenarnya. Ada beberapa ketidakakuratan sedikit karena interpolasi keadaan fisika dihidupkan.
Perhitungannya ternyata sangat mudah, namun membuat lingkungan saya bekerja dengan cara yang sama seperti perhitungan murni ini ... sangat menyebalkan. Setidaknya saya memecahkan beberapa bug serius di luar sana, jadi itu latihan yang bermanfaat.
Berikut ini adalah kode lengkap dalam Lua yang digunakan untuk menyelesaikan masalah asli (kode tersebut mengasumsikan Anda memiliki rutinitas "debug_draw" Anda sendiri dan kelas vektor Anda sendiri dengan metode dasar seperti "length_sq" (panjang kuadrat), "normalisasi" atau operator +, * :
Terima pergi ke Jason untuk mengatur saya ke arah yang benar! Terima kasih!
sumber
Anda mungkin ingin "hanya menghitung" jawabannya, tetapi saya yakin Anda akan merasa tidak cukup setelah mendapatkannya karena sifat fisika "jatuh bebas" yang sangat interaktif.
Pertimbangkan untuk menggunakan pendekatan yang berbeda: Mencari. Inilah cara melakukannya untuk Super Mario AI: http://aigamedev.com/open/interview/mario-ai/
Pencarian jalur yang mungkin untuk mendapatkan dari A ke B memungkinkan untuk interaktivitas tanpa batas di udara sambil tetap efisien secara komputasi.
sumber