Bagaimana saya bisa mengubah algoritma pencarian path * pencarian A * ini untuk menangani nilai pergerakan medan yang berbeda?

8

Saya membuat game aksi berbasis peta 2D dengan desain interaksi yang sama seperti Diablo II. Dengan kata lain, pemain mengklik di sekitar peta untuk memindahkan pemain mereka. Saya baru saja selesai bergerak pemain dan saya pindah ke pathfinding.

Dalam permainan, musuh harus mengisi karakter pemain. Ada juga lima jenis medan berbeda yang memberikan bonus gerakan berbeda. Saya ingin AI memanfaatkan bonus medan ini saat mereka mencoba menjangkau pemain.

Saya diberitahu untuk memeriksa algoritma pencarian A * (http://en.wikipedia.org/wiki/A*_search_algorithm). Saya melakukan permainan ini dalam HTML5 dan JavaScript, dan menemukan versi dalam JavaScript: http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript Saya mencoba mencari tahu cara men-tweak itu meskipun.

Di bawah ini adalah gagasan saya tentang apa yang perlu saya ubah. Apa lagi yang perlu saya khawatirkan?

  • Ketika saya membuat grafik, saya perlu menginisialisasi array 2D yang saya berikan dengan traversal peta yang sesuai dengan jenis medan yang berbeda.
  • di graph.js: definisi "GraphNodeType" perlu dimodifikasi untuk menangani 5 jenis medan. Tidak akan ada dinding.
  • di astar.js: Skor g dan h perlu dimodifikasi. Bagaimana saya harus melakukan ini?
  • di astar.js: isWall () mungkin harus dihapus. Gim saya tidak memiliki dinding.
  • di astar.js: Saya tidak yakin apa ini. Saya pikir ini menunjukkan simpul yang tidak valid untuk diproses. Namun, kapan ini akan terjadi?
  • Pada tingkat tinggi, bagaimana cara mengubah algoritme ini dari "oh, apakah ada tembok di sana?" untuk "akankah medan ini membawaku ke pemain lebih cepat daripada medan di sekitarku?"

Karena waktu, saya juga berdebat menggunakan kembali algoritma Bresenham saya untuk musuh. Sayangnya, bonus gerakan medan yang berbeda tidak akan digunakan oleh AI, yang akan membuat permainan menjadi membosankan. : / Saya benar-benar ingin memiliki ini untuk prototipe, tapi saya bukan pengembang dengan perdagangan atau saya seorang ilmuwan komputer. : D

Jika Anda mengetahui kode apa pun yang melakukan apa yang saya cari, silakan bagikan!

Kiat periksa kewarasan untuk ini juga dihargai.

javascript ai html5 user422318
sumber
Hei, penulis perpustakaan di sini. Apakah Anda menggunakan versi terbaru dari github? github.com/bgrins/javascript-astar/blob/master/astar.js . Ini jauh lebih cepat daripada implementasi berbasis daftar lama.
Brian Grinstead

Jawaban:

7

Anda perlu memperhatikan garis yang sangat spesifik dalam algoritma:

// g score is the shortest distance from start to current node, we need to check if
//   the path we have arrived at this neighbor is the shortest one we have seen yet
var gScore = currentNode.g + 1; // 1 is the distance from a node to it's neighbor

Ini adalah biaya simpul tertentu. Anda ingin memodifikasinya menjadi seperti

var gScore = currentNode.g + currentNode.cost

Ini akan menyebabkan jalur untuk menghindari medan mahal dan lebih memilih medan murah; itu adalah tanggung jawab Anda untuk membuat 'currentNode.cost' mengembalikan sesuatu yang sesuai untuk medan Anda. Adalah fakta bahwa tidak semua medan memiliki biaya 1 yang harus Anda perhatikan ... beberapa medan lebih murah daripada yang lain. Ada beberapa pertimbangan lain, tetapi poin spesifik dalam kode ini harus menjadi fokus perhatian Anda.

Myrddin Emrys
sumber
Terima kasih untuk ini. Saya telah memodifikasi kode saya sehingga setiap node mencari piksel pada koordinatnya dan menyimpannya sebagai biaya. Sayangnya, saya melakukan tes pathfind antara dua titik di grid 800x500 dan browser saya mogok. : / Ada beberapa faktor dalam hal ini: kode astar mungkin perlu dioptimalkan; ukuran kanvas saya sangat besar; mungkin inisialisasi grafik saya salah; dan mungkin warna pada avatar karakter mengacaukan semuanya. Apa yang harus saya lakukan? :(
user422318
Ketika Anda mengatakan 'menyimpan piksel', artinya Anda menyimpan biaya medan piksel, ya? Karena beberapa nilai RGB tidak mungkin cocok dengan biaya aktual medan itu. Anda mungkin harus menyimpan sesuatu antara 1 dan 10 (1 menjadi jalan, 10 menjadi rawa), meskipun nilai pastinya tentu saja tergantung pada gim Anda yang sebenarnya.
Myrddin Emrys
1
Hei, penulis perpustakaan di sini. Apakah Anda menggunakan versi terbaru dari github? github.com/bgrins/javascript-astar/blob/master/astar.js . Ini jauh lebih cepat daripada implementasi berbasis daftar lama.
Brian Grinstead
2
@Brian Anda harus meletakkan komentar ini pada pertanyaan, bukan pada jawaban saya, sehingga orang yang benar-benar menggunakan perpustakaan akan mendapatkan notifikasi di email mereka daripada saya.
Myrddin Emrys
2

Ini persis seperti apa A * adalah untuk. Yang perlu Anda lakukan hanyalah menetapkan simpul di antara biaya node berdasarkan jenis terain. (Sepertinya contoh Anda menggunakan grafik di mana semua simpul memiliki biaya 1.)

kekacauan
sumber
0

Implementasi ini sedikit spesifik untuk on / off sekarang. Seperti yang dikatakan Myrddin Emrys, Anda harus memodifikasi skor g berdasarkan biaya (bukan hanya dengan 1). Ada diskusi tentang ini di sini: https://github.com/bgrins/javascript-astar/issues/3 .

Saya ingin mendapatkan solusi ini porting kembali ke perpustakaan utama jika Anda membuatnya berfungsi!

Brian Grinstead
sumber