Bagaimana cara menemukan rintangan?

Bagaimana cara mewakili situasi berikut ini - agen ( @) perlu mencapai tujuan ( $). Path diblokir oleh parit ( ~~~). Tersedia penggaruk (atau perangkat lain, seperti sepatu berjalan air) yang memungkinkan untuk melewati rintangan.

.....~~~...   . ground
...=.~~~...   = rake
.....~~~.$.   ~ water
.@...~~~...   @ agent
.....~~~...   $ goal

Bagaimana benar pathfind dari @ke $asalkan tidak ada segera tersedia jalan? Haruskah jalan saya tidak hanya memiliki biaya tetapi juga prasyarat?

UPD : Masalahnya adalah tujuannya tidak dapat diakses dan menyapu hanya salah satu dari banyak objek yang mungkin di peta. Pertanyaannya kemudian adalah "bagaimana membuat agen mengerti bahwa ia membutuhkan penggaruk?"

ai path-finding zandy
sumber

Saya pikir Anda harus mengklarifikasi kasus penggunaan Anda karena itu akan mempengaruhi pendekatan yang diperlukan untuk menyelesaikan masalah ini. Misalnya, jika use case adalah untuk menghitung jalur untuk musuh maka Anda mungkin harus terlebih dahulu melihat apakah tujuan dapat dicapai saat ini, jika tidak ada musuh yang mendapatkan rake (mis. Rake IS the goal) dan kemudian pathfind ke yang pertama tujuan lagi.

jhocking

Jawaban:

Saya sedang memikirkan setumpuk tujuan, merintis jalan harus dianotasi :

Mulailah dengan tujuan get $
Coba temukan jalur ke $- jalur yang ada dengan kemampuan jalan air diperlukan.
Dorong tujuan get waterwalking.
Tumpukan sasaran sekarang get waterwalking, get $
Entah bagaimana menemukan bahwa menyapu memberi jalan air, mari kita ganti namanya menjadi perahu.
Jalan menuju menyapu. Tujuan teratas tercapai, keluarkan dari tumpukan, tujuannya adalah get $.
Path to $- sekarang kami memiliki kemampuan dan dapat mencapai tujuan.

zandy
sumber

+1 Saya melakukan sesuatu yang mirip dengan permainan saya, dan menulis sedikit posting tentang hal itu beberapa waktu lalu di bawah Unit Tasks dan merintis jalan .

MichaelHouse

@ byte66 tidak menangani case khusus ketika ada path tanpa menggunakan rake tetapi, menggunakan rake menghasilkan path yang lebih pendek

Ali1S232

@ Dapatkan Anda benar. Tebak akan membutuhkan pendekatan yang berbeda untuk itu.

zzandy

Itu hanya masalah menambahkan biaya tambahan. Ketika Anda menjumpai air, tambahkan biaya untuk mengantar barang air ke jalan setapak. A * akan melewati jalan air hingga menjadi jalur termurah.

MichaelHouse

Seluruh hal yang menemukan jalur hanyalah pencarian jalur terpendek di atas grafik. untuk menyelesaikan masalah Anda, satu-satunya perubahan yang perlu Anda terapkan adalah dengan menambahkan beberapa tepi tambahan (mewakili jalur yang dapat diambil perahu), dan lakukan algoritma pencarian jalur sederhana. tidak masalah apakah Anda menggunakan BFS, Dijkstra atau A *, hanya menerapkan algoritma pencarian jalur normal dengan beberapa tepi tambahan. untuk informasi lebih lanjut tentang pencarian jalur di halaman wiki periksa grafik

Ali1S232
sumber

+1 Buat penggaruk Anda sebagai tautan satu arah ke air, dengan tautan satu arah air ke darat juga.

Laurent Couvidou

Saya tidak memiliki pemahaman yang jelas tentang cara mengikat bersama pencarian geometris dan pencarian fitur. Bagaimana cara beralih dari no path from @ to $ke goto rake, bring it to water, place it, goto $.

zzandy

@zzandy sambil mencari jalan, untuk setiap ubin Anda pergi ke ubin terdekat jika memungkinkan. Anda hanya perlu menambahkan kondisi bahwa jika simpul saat ini adalah rake, Anda dapat langsung menambahkan node dari sisi lain sungai untuk membuka daftar.

Ali1S232

Tetapi bagaimana jika Anda dapat membawa perangkat? Saya pikir itu yang dia maksud (dan karenanya jawaban saya.)

kaoD

Ya, maksud saya perangkat dapat (dan harus) dicari. @ kaoD, jawaban Anda tidak termasuk langkah ketika agen mendapatkan ide yang dibutuhkan penggaruk.

zzandy

Saya akan melakukan ini dengan semacam solusi pohon perilaku - Anda jalan ke tujuan, dan perhatikan semua hambatan yang telah menghalangi A * Anda. Jika Anda gagal, Anda memeriksa apakah ada objek yang dapat membantu mengatasi hambatan itu, dalam hal ini, jalur ke objek itu. Ulang. Ini berarti bahwa agen perlu mencoba untuk mencapai tujuan dan gagal sebelum mendapatkan ide menggunakan alat, yang mungkin membutuhkan waktu, terutama jika ada dunia ubin besar yang semuanya perlu diperiksa. Mungkin tidak terlihat terlalu aneh sehingga agen membutuhkan waktu untuk merenungkan bagaimana menyelesaikan masalah.

Saya dapat membayangkan solusi nyata yang keras. Tambahkan dimensi lain ke grid jalur pencarian Anda. Jadi dalam kasus peta 2D, Anda membuat grid pathfinding 3D. Dalam contoh sederhana ini, dimensi baru ini hanya akan memiliki kedalaman dua, tetapi dalam game nyata akan menjadi besar dengan cepat.

Pada z = 0 Anda memetakan medan selama keadaan normal, artinya ubin air dianggap tidak bisa dilewati.

Pada z = 1 Anda memetakan medan seperti saat menyapu, yang berarti bahwa ubin air dianggap walkable (tetapi jika Anda memiliki misalnya ubin dinding, itu mungkin tetap solid).

Temuan path adalah A * biasa dalam dimensi x dan y, yang berarti bahwa setiap sel grid dianggap memiliki akses ke tetangganya. Namun dalam dimensi z, A * TIDAK diizinkan untuk menyebar.

Kecuali di mana penyapu. Objek menyapu bertindak sebagai celah antara z = 0 dan z = 1 di jalur pencarian path.

Ini berarti bahwa A * akan banjir mengisi ke luar di z = 0, menabrak air, dan kehabisan pilihan - maka itu akan menyebar ke z = 1 melalui rake tile, dan pada z = 1 (di mana air bisa dilalui dengan berjalan kaki) temukan jalannya ke tujuan. Efeknya adalah bahwa NPC tanpa keraguan bergerak ke rake, dan kemudian memindahkan jalur terpendek ke gawang.

Joar Jakobsson
sumber

Saya telah memperlakukan rake lebih seperti "water walking boots" dalam contoh saya, yang berarti sebuah objek yang jika Anda miliki membuat Anda dapat melakukan perjalanan di atas ubin air. Jika rake perlu benar-benar "dibangun" sebagai bagian dari medan, dan mencakup sejumlah kecil ubin yang mungkin atau mungkin tidak cukup untuk menjangkau melintasi air, masalahnya lebih sulit. Solusi saya memungkinkan untuk item sekali pakai, jika Anda bergerak di z = 1 secara otomatis drop down ke z = 0 lagi.

Joar Jakobsson