Jadi saya sudah memahami cara menggunakan A * untuk mencari jalan, dan saya bisa menggunakannya di grid. Namun, dunia gim saya sangat besar dan saya memiliki banyak musuh yang bergerak ke arah pemain, yang merupakan target yang bergerak, sehingga sistem grid terlalu lambat untuk pencarian jalur. Saya perlu menyederhanakan grafik simpul saya dengan menggunakan mesh navigasi.
Saya memahami konsep "bagaimana" mesh bekerja (menemukan jalur melalui node pada simpul dan / atau pusat-pusat tepi poligon).
Game saya menggunakan rintangan dinamis yang dihasilkan secara prosedural saat run-time.
Saya tidak bisa membungkus kepala saya di sekitar cara mengambil pesawat yang memiliki banyak hambatan di dalamnya dan secara sistematis membagi area walkable menjadi poligon untuk navigasi mesh, seperti gambar berikut.
Di mana saya memulai? Bagaimana saya tahu kapan segmen area yang bisa berjalan sudah ditentukan, atau lebih buruk, ketika saya menyadari saya perlu membagi area yang bisa didefinisikan sebelumnya sebagai algoritma "berjalan" melalui peta?
Saya menggunakan javascript di nodejs, jika itu penting.
sumber
Jawaban:
@Stephen - Komentar Panjang - Makalah itu sepertinya layak dibaca ketika saya punya waktu. Pada dasarnya apa yang saya sarankan adalah sesuatu di sepanjang garis Algoritma Hertel-Mehlhorn yang disebutkan dalam makalah (referensi untuk algoritma spesifik ini dapat ditemukan di sini http://www.bringyou.to/compgeom/ ) dengan tambahan membagi lagi sisi-sisi peta (di luar batas area bermain) beberapa waktu untuk mengurangi kemunculan beberapa segitiga kecil yang terbentuk di sudut-sudut. Segitiga-segitiga kecil itu bisa bermasalah karena ujung-ujungnya bisa lebih kecil dari yang Anda cari sebelumnya. The Hertel-Mehlhorn adalah untuk pengurangan poligon yang dihasilkan oleh partisi segitiga jika Anda tertarik di sini lebih lanjut tentang triangulasi:http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/PolyPart/polyPartition.htm .
Juga, jika Anda lebih suka tidak menemukan kembali roda, saya pikir perpustakaan ini benar-benar akan melakukan semua yang Anda butuhkan: http://code.google.com/p/polypartition/ . Ini membentuk triangulasi dan reduksi dengan salah satu dari sejumlah opsi yang berbeda termasuk Hertel-Mehlhorn. Ini adalah Lisensi MIT yang artinya dapat digunakan untuk proyek sumber tertutup dan komersial jika itu merupakan masalah.
Jika Anda memutuskan untuk terus bekerja pada implementasi Anda sendiri, saya ingin melihat apa yang Anda hasilkan.
sumber
Daripada mesh, Anda mungkin hanya mempertimbangkan pendekatan A * hirarkis. Keuntungan terbesar mesh adalah dalam berhadapan dengan dunia game yang tidak selaras grid, daripada mengurangi kompleksitas dari grid.
Dengan pendekatan hierarkis, Anda membagi dunia Anda berulang kali (seperti pohon quad), dan menghasilkan informasi konektivitas antara node. Anda kemudian dapat dengan cepat membuat jalur antara bongkahan besar dunia, dan hanya menggunakan kisi resolusi tinggi untuk menemukan lintasan dalam bongkahan yang lebih besar.
Pendekatan hierarkis akan memberikan urutan kinerja yang lebih baik, sementara mesh terbaik hanya akan memberi Anda peningkatan linier kecil.
Pendekatan naif adalah dengan hanya membagi dunia Anda ke dalam X oleh X potongan grid yang lebih besar, menghasilkan info konektivitas di antara mereka (misalnya, apakah ada jalur antara melalui potongan 2x1 dari 3x1 ke 2x2, dan berapa jarak jalur rata-rata) .
Perhatikan bahwa Anda mungkin tidak selalu mendapatkan jalur yang ideal dengan pendekatan ini dalam beberapa keadaan tertentu. Menghasilkan potongan-potongan berukuran variabel mengurangi masalah, tapi jujur itu biasanya hanya cara yang lebih mudah untuk menghindari membuat dengan jalur masalah dan mengandalkan kenyataan bahwa pemain sangat tidak mungkin untuk melihat musuh mengambil jalur suboptimal kecuali di sebagian besar kasus merosot.
sumber
Saya pikir Anda mungkin terlalu rumit ini. Anda mungkin tidak perlu membuat jaring navigasi dengan cepat. Alih-alih memiliki jaring navigasi statis untuk dunia basis Anda.
Melintasi rintangan dapat diselesaikan dengan menggunakan perilaku kemudi (gunakan penghindaran rintangan). Jika hambatan Anda begitu besar sehingga memenuhi atau benar-benar memblokir perjalanan dari satu nav-poli ke yang berikutnya, maka miliki beberapa cara untuk memeriksa kasing tepi ini dan menghitung ulang jalur antara poli yang saat ini Anda masuki dan yang Anda blokir dari.
sumber