Saya memikirkan pathfinding acak untuk game Tower Defense saya. A * tidak akan berfungsi untuk puposis saya, karena saya secara spesifik memerlukan penelusuran jalur acak .
Bayangkan sebuah peta dengan rute, titik awal dan tujuan. Saya memiliki beberapa rute, yang semuanya mengarah dari titik awal ke tujuan, dengan satu atau lain cara. Itu bisa terlihat seperti ini:
Deskripsi warna: merah - titik awal; tujuan hitam; rute abu-abu; white - free space
(Angka-angka tersebut digunakan dalam teks sebagai referensi untuk beberapa ubin)
Saya pertama kali berpikir tentang hanya menghitung titik jalan berikutnya secara acak, ketika suatu entitas melewati ubin. Tetapi itu tidak akan berhasil. Ketika suatu entitas melewati ubin 1 itu bisa naik atau turun. Ketika datang ke 2 itu bisa turun / naik (relatif terhadap posisi itu) atau kanan.
Jika ia pergi ke bawah / atas itu akan pergi untuk ubin 1, yang berarti bahwa ia pergi ke belakang. Buruk...
Saya benar-benar ingin membuatnya dinamis , tetapi saya tidak tahu apa yang bisa saya lakukan sekarang. Adakah yang punya ide atau pengalaman dalam hal ini?
Jawaban:
Instead of having all adjacent squares as possible next waypoints, only include squares that do not lead back to the beginning and randomly pick from those. If you did this, it would be impossible to go backwards because going back is not an option.
This is a directed graph problem with each waypoint as a vertex, and each path an edge. You just need to limit the number of cycles, perhaps removing them entirely.
sumber
Anda mengatakan acak, tetapi seberapa banyak keacakan yang Anda inginkan? Apakah boleh jika musuh memilih jalur 10 kali lebih lama dari yang terpendek? Apakah boleh jika musuh memasuki jalan buntu dan harus mundur? Yaitu, acak atas set path apa, dan dengan distribusi probabilitas apa?
Dengan anggapan Anda menginginkan musuh lebih memilih jalur pendek, Anda bisa menggunakan A *, tetapi secara acak memvariasikan bobot tepi yang diberikan padanya. Kemudian, musuh akan selalu memilih jalur acak yang mengunjungi setiap simpul paling banyak sekali, dengan bias menuju jalur yang lebih pendek. Secara khusus, jika tanpa pengacakan akan ada beberapa jalur dengan panjang yang sama, masing-masing jalur ini akan dipilih dengan probabilitas yang sama.
Atau, dalam A *, Anda bisa beralih di atas tetangga secara acak. Dalam eaxmple Anda, ketika pencarian jalur mencapai simpul 1, itu akan secara acak terlebih dahulu menentukan bagian atas tetangga bawah, menyebabkan jalur atas atau bawah dipertimbangkan terlebih dahulu. Solusi ini akan menyebabkan musuh memilih di antara semua jalur terpendek secara acak. Dalam contoh sederhana Anda, kedua jalur terpendek akan sama-sama memungkinkan, tetapi dalam situasi seperti:
jalan teratas akan dipilih pada probabilitas 1/2, sedangkan yang bawah akan dipilih pada probabilitas 1/4 masing-masing.
sumber
Hanya bukti konsep:
sumber