Apa kerugian dan / atau batasan jerat navigasi? [Tutup]

8

Saya memiliki banyak materi tentang jerat navigasi, apa itu, kelebihannya dibandingkan grafik yang terdiri dari titik arah, dll. Namun, saya belum melihat banyak informasi mengenai batasan dan kerugian menggunakan jerat navigasi, selain waktu yang jelas. mereka harus dibuat secara manual (yang relatif dipecahkan oleh Recast).

Tentunya ini bukan teknik yang sepenuhnya "ajaib" yang menghadirkan dirinya sendiri tanpa kekurangan? Bisakah seseorang tolong jelaskan apa batasan dan kekurangan menggunakan navigasi mesh, katakanlah, grafik yang terdiri dari titik arah? Atau arahkan saya ke arah yang benar?

path-finding navmesh Ray Dey
sumber

Jawaban:

8

Nav mesh adalah peningkatan kualitatif atas grafik waypoint, dengan cara yang sama bahwa A * adalah perkembangan alami dari algoritma Dijkstra. Dalam setiap kasus, yang pertama telah berevolusi karena kekurangan yang terakhir, dan merupakan algoritma yang sepenuhnya lebih berguna untuk sebagian besar aplikasi. Kekurangannya, tentu saja, kompleksitas (waktu dan / atau ruang). Tapi saya harus mengatakan tradeoffnya kecil untuk nav meshs vs waypoint grafik (yaitu kompleksitas komputasi dapat meningkat, tetapi tidak dengan urutan besarnya).

Satu-satunya manfaat praktis untuk menggunakan grafik waypoint adalah di mana Anda memang ingin membatasi pergerakan ke garis yang tepat daripada area. Grafik waypoint = titik dan garis yang sangat kecil, sedangkan nav mesh adalah hal yang sama persis dengan bidang poligon (cembung) yang dilampirkan yang menggambarkan ruang valid yang dianggap sebagai "wilayah sel ini". Apa pun cara Anda menginterpolasi posisi entitas AI dari satu node ke node lainnya; satu-satunya perbedaan dengan navmeshes adalah Anda melakukannya dari satu titik ke titik yang lain, sedangkan dengan grafik titik Anda melakukannya dari satu titik ke titik lainnya, dan berpotensi memberikan pertimbangan pada ujung yang memisahkan simpul A dan B. Dan tentu saja dari perspektif kompleksitas, mudah untuk melihat bahwa grafik waypoint lebih murah untuk dioperasikan.

Seiring berjalannya waktu, perbaikan memang tampak "gratis" (dari perspektif individu). Itu sebabnya komputer yang Anda beli hari ini seharga $ X jauh lebih cepat daripada komputer yang bisa Anda beli sepuluh tahun yang lalu dengan harga yang sama. Intinya, itu tidak benar-benar gratis - seseorang, di suatu tempat, telah menempatkan upaya R&D ke dalamnya. Sama dengan algoritma. Dan itu sebabnya teknologi yang lebih tua sebagian besar jatuh di pinggir jalan.

Insinyur
sumber
3
Jawaban Anda sebagian besar baik, tetapi saya benar-benar ingin melihat kutipan untuk "bahkan pada tingkat neuron hewan, [pathfinding] direpresentasikan sebagai semacam grafik yang menghubungkan ide dari satu tempat ke ide lain melalui asosiasi, dan seterusnya. " Ini klaim yang sangat kuat yang belum pernah saya dengar sebelumnya.
1
"Dapat diwakili" dan "diwakili" sama sekali tidak sama. Hubungan antara pemikiran dan struktur neuron bukanlah pemetaan langsung (jelas - neuron yang memberi sinyal merah tidak sendiri merah). Bagaimanapun, edit Anda adalah klaim yang jauh lebih mudah.
Terima kasih atas jawaban yang informatif. Saya menyadari bahwa semua contoh pathfinding praktis menggunakan grafik dan menebak bahwa mungkin ada masalah kompleksitas waktu / memori. Namun, saya bertanya-tanya apakah ada kasus tepi di mana Anda tidak dapat menggunakan navmesh secara efektif - di belakang, saya pikir saya mungkin telah memikirkan hal ini. Menanyakan batasan jerat navigasi kemungkinan besar menanyakan batasan grafik sebagai bentuk representasi dunia. Hanya satu hal lagi, jika Anda bisa menautkan ke contoh Difusi Kolaboratif, saya akan sangat menghargainya! Terima kasih lagi.
Ray Dey
-1, karena Anda tidak benar-benar menjawab pertanyaan. Anda bilang navmeshes adalah peningkatan kualitatif, tetapi poster asli ingin tahu apa kualitas itu.
Kylotan
@Kylotan: Tidak, sebenarnya, pertanyaannya adalah "Saya punya banyak materi tentang navigasi mesh [dan] kelebihannya".
0

Jaring navigasi dibatasi untuk permukaan, sedangkan titik arah dapat ditempatkan di mana saja dan dapat melakukan sejumlah koneksi (tepi) ke arah mana pun. Dengan demikian, waypoint dapat memberikan solusi yang lebih umum dan fleksibel untuk, misalnya game dengan unit atau lingkungan abstrak atau luar biasa.

Acey
sumber