Bagaimana melakukan pathfinding starcraft?

Saya sudah mencoba mencari cara untuk mengimplementasikan sesuatu seperti pathfinding di Starcraft 2. Saya tidak mencari semua fitur canggih seperti berkelompok, mengantri, dll. Sebenarnya saya suka bagaimana di Starcraft 1 unit akan saling mengganggu. lain. Tapi saya ingin pencari jalan lebih baik daripada yang digunakan di Starcraft 1.

Dari pencarian Google saya telah melakukan berbagai jawaban ada hubungannya dengan A * lebih dari mesh navigasi dan / atau berurusan dengan semacam "grafik visibilitas". Tetapi saya mendapatkan jawaban yang agak bertentangan atau tidak jelas tentang apa yang harus saya lakukan.

Satu hal yang saya baca ada hubungannya dengan melakukan A * di atas simpul segitiga mesh (navigasi mesh). Dan kemudian entah bagaimana "meluruskan jalan" yang saya tidak tahu harus bagaimana. Tapi itu tidak menjamin optimalitas bukan?

Pertanyaan lain yang saya miliki adalah bagaimana starcraft 2 pathfinding berurusan dengan fakta bahwa unit adalah cakram dengan jari-jari terbatas dan bukan titik ketika berhadapan dengan sudut? Dan bagaimana menghadapi hambatan dinamis seperti unit idle atau bahkan unit bergerak lainnya.

Saya mencari beberapa penjelasan terperinci yang mendetail dan bukan gambaran umum tingkat tinggi yang umum dalam hasil pencarian.

Jika itu penting, saya sudah melihat Catatan Amit tentang Path-Finding . Saya pernah mendengar tetapi tidak membaca Computational Geometry: Algorithms and Applications . Dan sebuah posting blog tentang presentasi navigasi AI di GDC 2011 menyebutkan bahwa Starcraft 2 menggunakan triangulasi delaunay terbatas untuk navmesh. Meskipun posting blog menyebutkan Boids steering dan "horizon analysis", itu tidak menyebutkan secara tepat bagaimana inti pathfinding dilakukan di navmesh.

Jika Anda sudah menginstal Starcraft 2, buka editor peta dan matikan pathfinding . Anda akan dapat melihat bagaimana nav mesh dibangun saat Anda menempatkan bangunan dan hambatan lain di sekitarnya.

Sebenarnya saya suka bagaimana di Starcraft 1 unit akan saling mengganggu. Tapi saya ingin pencari jalan lebih baik daripada yang digunakan di Starcraft 1.

Seharusnya tidak menjadi masalah - merintis jalan Starcraft 1 konyol. Posting blog ini oleh salah satu programmer membicarakannya.

Satu hal yang saya baca ada hubungannya dengan melakukan A * di atas simpul segitiga mesh (navigasi mesh). Dan kemudian entah bagaimana "meluruskan jalan" yang saya tidak tahu harus bagaimana. Tapi itu tidak menjamin optimalitas bukan?

Ini tentang membuat AI tidak bodoh lebih dari optimal. Unit Anda berakhir dengan gerakan zig-zag antara node jika Anda tidak menerapkan sedikit smoothing.

Saat melakukan perencanaan jalur, Anda akan memiliki tahap penyempurnaan di mana Anda melihat node apa yang harus dilalui unit Anda untuk mencapai tujuannya, dan kemudian Anda mulai mengambil kelebihan node di tengah jalan yang tidak perlu kita lakukan. ikuti, yaitu kita dapat langsung pergi dari simpul A ke simpul C hingga B tanpa tumbukan statis, jadi abaikan B seluruhnya.

Ini akhirnya meluruskan jalan.

Saya mencari beberapa penjelasan terperinci yang mendetail dan bukan gambaran umum tingkat tinggi yang umum dalam hasil pencarian.

Jika Anda ingin penjelasan yang solid, ini sudah tercakup dengan baik di buku-buku (bahkan dengan kode game yang berfungsi). Jadi, jika Anda memiliki uang untuk dibakar, lihat Programming Game AI Dengan Contoh dan / atau Kecerdasan Buatan untuk Game . Keduanya membahas topik ini secara mendalam.