Bagaimana cara menghasilkan Kotak Navigasi untuk dunia 3D?

11

Saya mencoba mencari solusi untuk masalah ini. Saya mencoba membangun mesh navigasi dalam format kisi-kisi simpul yang dikunci menjadi x, koordinat lantai dalam bentuk kotak untuk ruang 3D. Tetapi saya mengalami masalah dalam mencari cara untuk mengatasinya.

Saya mencoba melihat ke perpustakaan Recast. Ini adalah metode yang cukup kuat, tetapi tampaknya melambat dengan peta yang lebih besar dan ruang terbuka. Saya juga tidak tahu bagaimana mereka menghasilkan simpul dan tepi untuk ruang dunia dengan peta ketinggian.

Pikiran saya berikutnya adalah melakukan apa yang dulu dilakukan Unreal Engine 3.

https://udn.epicgames.com/Three/NavigationMeshReference.html

Yang menggunakan raycast untuk menghasilkan mesh. Saya tidak tahu bagaimana cara menghentikan raycast.

Jadi ... pilihan saya berikutnya adalah kotak, mungkin kotak. Buat volume terbagi dengan ukuran yang kekuatan 2. Sejajarkan kotak ke grid, dan menembak prisma persegi panjang ke bawah sebagai sinar. Jika itu mendarat di sepotong geometri yang merupakan bagian dari tanah dan persegi panjang tidak berpotongan, tinggalkan kotak di sana. Dan terus turun sampai batas volume tercapai. Untuk memeriksa apakah ujung-ujungnya perlu dikaitkan, saya kira saya bisa memeriksa untuk melihat apakah kemiringan antara dua pasang simpul berada dalam kemiringan walkable, gabungkan mereka jika ini benar.

Masalah utama saya adalah ... ini sepertinya tidak terlalu optimal. Tanpa memikirkannya, pada perkiraan prosesnya adalah O (N ^ 3) untuk tingkat berlapis-lapis. Yang bisa jadi sangat jahat.

Dan bit terakhir adalah untuk secara otomatis membuat kelompok persegi panjang dari kotak-kotak ini. Saya tidak sepenuhnya yakin bagaimana melakukan ini. Implementasi Unreal memisahkan mereka dengan lereng. Namun, saya mencoba mempertahankan format kisi. Jadi itu tidak sepenuhnya perlu. Masalahnya masih tetap pada pembuatan ubin persegi panjang besar untuk membagi proses pencarian jalan menjadi basis per ubin. Ubin tidak boleh terlalu besar, juga tidak terlalu kecil.

Jadi pertanyaannya adalah ...

Apa yang akan menjadi cara yang efisien untuk menghasilkan navmesh yang diikat ini? Dan apa cara yang baik untuk membuat ubin?

moonshineTheleocat
sumber
Kapan Anda berharap untuk menghasilkan mesh? Waktu kompilasi, Waktu muat, atau Waktu nyata? Kami berjuang dengan masalah yang sama ini dan akhirnya memutuskan itu adalah skenario kami yang berlebihan (generasi waktu muat dalam penembak top-down tanpa jalur yang tumpang tindih), kami memutuskan untuk menggunakan pendekatan berbasis quad-tree. Ini bekerja cukup baik untuk kita. Jadi saya kira apa yang saya tanyakan adalah, apakah Anda benar-benar membutuhkan ini, atau apa solusi termudah yang memenuhi persyaratan awal Anda karena ini dapat menjadi tenggang waktu. Jika Anda mengelola solusi yang baik, saya ingin mendengar bagaimana Anda memperbaikinya.
Niels
@Niels, saya berencana melakukan pra-bangunan, lalu memuatnya ke dalam game.
moonshineTheleocat
Maka konsumsi waktu tidak boleh terlalu banyak kelemahan awal, karena pemain tidak akan menunggu. Anda selalu dapat mengoptimalkan setelah Anda mengerjakan sesuatu.
Niels
Seberapa besar level Anda? Kami telah menggunakan penyusunan kembali pada game besar dan tidak punya masalah - Anda hanya perlu menyetel nilai tiie, dll.
Steven
Saya pikir Anda kehilangan sedikit "grid". Yang tidak persis sama dengan ubin yang digunakan kembali. Saya mencoba mencari cara untuk menyusun kembali perombakan untuk melakukan hal seperti itu. Tapi sebagian besar sudah mimpi buruk.
moonshineTheleocat

Jawaban:

1

Dunia 3D dasar dapat diwakili oleh jaring navigasi yang dapat dibangun dengan nyaman di sebagian besar mesin game. Aktor dapat melakukan perjalanan di sepanjang tepi poligon.

Itu akan menjadi solusi sederhana. Ada banyak algoritma untuk pencarian jalur dan menghasilkan navmesh.

Saya ingin membagikan sesuatu yang saya baca beberapa waktu lalu.

Contoh01

Ini menjelaskan solusi yang memungkinkan di mana kita dapat memecah dunia game kita menjadi ubin persegi. setiap kali ubin kotak ditambahkan ke dalam game (saat pemain mendekati area / medan prosedural), ubin kotak ditambahkan. Namun, kita tidak perlu menghitung seluruh navmesh lagi. kami hanya menghitungnya untuk ubin itu dan menambahkannya ke grafik yang ada. Keuntungan kinerja yang signifikan di sana.

Contoh02

Masalah selanjutnya yang ditangani adalah gerakan bergerigi dari contoh sebelumnya. Saya bisa mengerti bahwa dengan mempertimbangkan belokan di masa depan dan menggeneralisasi arah akan mengurangi gerakan zigzag banyak dan membuat gerakan fluida. Gim dengan animasi terperinci tidak memberikannya, tetapi Anda dapat melihat ini di beberapa gim dunia terbuka di mana saya akan menganggap navigasi sebagian besar dipanggang.

Adapun pertanyaan, saya akan merekomendasikan Anda untuk pergi memeriksa jawaban Kromster pada daftar algoritma penghasil navmesh.

Lihat juga The AI ​​Systems of Left 4 Dead yang contohnya merupakan bagiannya. Banyak lagi topik menarik yang dibahas

Semoga berhasil.

suvam0451
sumber
0

ada banyak cara, mengapa tidak membuatnya lokal untuk pemain, membuat kotak kecil yang mengikuti pemain dan memeriksa di bawah setiap persimpangan apakah itu transversable, seperti apakah ada lantai di sana dan melakukan pemeran sinar untuk melihat apakah ada dinding / bangunan di sisi yang akan datang ..

joe shmoe
sumber
Ide yang bagus, tetapi bukan ide yang bagus untuk tujuan akhir. Saya perlu mendukung dunia yang besar, dan memungkinkan AI untuk menavigasi dari satu sisi benua ke sisi lain benua. Banyak yang bisa dilakukan tetapi saya harus memiliki grid nav tetap di tempat untuk menghasilkan node yang lebih tinggi.
moonshineTheleocat
0

Ini adalah masalah yang pernah saya lihat di mana-mana. Caranya adalah "pemisahan keprihatinan". "Katakan apa?", Kudengar kamu berpikir. Apa yang ditampilkan di layar BUKAN apa "struktur data" itu. Menjaga visual terpisah dari data untuk membangun visual adalah penting. Melakukan hal itu akan selalu "bukti masa depan" permainan Anda ketika versi perangkat lunak mendasar yang baru dirilis.

Bangun struktur data (alias: model) yang akan mewakili dunia game Anda. Kemudian buat "tampilan" model struktur data. Jika Anda ingin mengubah dunia dari kisi papan kotak ke kisi heksagonal, struktur data (model) tetap sama, tetapi tampilan akan "melukis" (merender) tampilan yang berbeda.

PBMCube
sumber
4
Sementara memisahkan kekhawatiran memang merupakan praktik yang baik secara umum, jawaban ini saat ini kurang jelas pada detail khusus untuk menjawab pertanyaan (mis. Bagaimana cara menghasilkan model pathfinding berbasis grid yang cocok dari sekumpulan geometri dunia tertentu). Anda benar bahwa apa pun model ini, kemungkinan harus terpisah dari data yang digunakan untuk menggambar level, tetapi untuk menjawab pertanyaan kita masih memerlukan metode untuk menghasilkan model pathfinding ini.
DMGregory
-2

Buat array ganda. Dan kemudian jika suatu objek / objek tidak dapat dilewati, memiliki metode untuk memberi tahu array bahwa posisi tidak bisa dilewati. Ketika AI mencoba untuk bergerak, mereka akan melihat array ganda dan melihat apakah itu lumayan.

Peter J
sumber
4
Metode untuk mengisi array ini adalah bagian yang sulit. ;)
DMGregory