Jalur "Line of sight" melintasi jala navigasi

Saya ingin menghitung garis pandang di jala navigasi.

Perhatikan gambar di bawah ini, garis kuning adalah hasil dari hanya A * dan garis merah adalah hasil dari garis pandang "algoritma yang menggunakan garis kuning sebagai input. Sekarang unit dapat bergerak langsung tanpa" zig-zagging ".

Apa yang dimaksud dengan algoritma untuk menghitung "garis pandang" itu?

Anda mencari algoritma saluran.

Di sini Anda sederhana

http://digestingduck.blogspot.com.es/2010/03/simple-stupid-funnel-algorithm.html

Pada dasarnya, algoritma mengidentifikasi tepi sebagai portal, dan membangun corong yang diuji terhadap simpul tepi untuk memeriksa apakah mereka berada di dalam corong atau tidak.

Pada langkah A corong dibangun dengan posisi awal dan portal dilintasi garis kuning.

Pada langkah B portal berikutnya dicentang, puncak atas berada di dalam corong, sehingga saluran atas corong sekarang lewat begitu saja. Tetapi simpul bawah keluar dari corong karena garis merah di bawah garis hijau, sehingga garis bawah tidak akan melewatinya, akan terus melewati simpul bawah portal sebelumnya.

Karena Anda dapat memeriksa corong akan lebih kecil, dan lebih kecil, hingga langkah F, di mana corong tidak mungkin dibangun, karena garis merah membuat corong yang buruk, sehingga simpul atas dipilih sebagai titik awal baru dan corong baru akan dibangun jika titik akhirnya tidak berada di jala itu.

Sadarilah bahwa algoritma semacam ini memungkinkan solusi sederhana untuk masalah ukuran model juga, karena Anda dapat mempertimbangkan bahwa portal lebih kecil oleh 2xradius model Anda.

Ada teknik sederhana yang dapat digunakan dengan jalur yang dihasilkan menggunakan ide garis pandang ini. Pada dasarnya, Anda ingin berjalan di jalur, dan pada setiap node, "lihat kembali" dua node sebelum yang terakhir untuk melihat apakah itu terlihat. Jika node sebelum terakhir terlihat, Anda dapat menghapus node terakhir (karena Anda memiliki garis pandang antara node Anda saat ini dan node sebelum yang terakhir, node terakhir, yang merupakan node perantara, tidak diperlukan).

Artikel Gamasutra memiliki contoh kode pseudo berikut:

checkPoint = starting point of path
currentPoint = next point in path
while (currentPoint->next != NULL)
if Walkable(checkPoint, currentPoint->next)
// Make a straight path between those points:
temp = currentPoint
currentPoint = currentPoint->next
delete temp from the path
else
checkPoint = currentPoint
currentPoint = currentPoint->next

Algoritme ini Walkableberfungsi seperti yang Anda inginkan, di mana fungsinya pada dasarnya adalah fungsi line-of-sight, tetapi sedikit ditingkatkan untuk memasukkan juga situasi di mana jalan terlihat, tetapi tidak dapat dilalui (yaitu lubang, jebakan, zona terbatas).