Kesadaran situasional dalam menemukan jalan

Asumsikan Anda harus menemukan jalur terpendek melalui ruang bawah tanah, di mana bagian-bagian tertentu hanya dibuka untuk Anda setelah barang-barang tertentu dikumpulkan, seperti pintu dan kunci yang terkunci, misalnya.

Reaksi usus normal terhadap kata-kata "jalan terpendek" jelas akan menjadi A *. Tapi A * akan gagal dalam lingkungan seperti itu, karena saya melihat banyak masalah mendefinisikan heuristik yang dapat diandalkan dan, juga, sangat mungkin, bahwa sebuah node harus dikunjungi beberapa kali, yang juga tidak mungkin dalam A * konvensional dan juga akan membuat heuristik lebih sulit.

Apa yang saya pikirkan hanyalah mencari jalan dari awal penjara bawah tanah sampai akhir, mengabaikan pintu yang diblokir. Setelah jalan ini ditemukan, untuk setiap pintu yang menghalangi jalan kami, jalan tambahan yang mencari kunci yang tepat dan kembali ke pintu akan dicari dan dilalui sebelum pintu itu bahkan tercapai. Sistem yang sama akan digunakan untuk menangani suatu situasi, di mana jalan menuju kunci yang diperlukan untuk membuka pintu kembali diblokir oleh pintu lain, yang perlu dibuka terlebih dahulu.

Masalah besar yang saya lihat dengan solusi saya adalah bahwa setelah semua jalur termasuk yang untuk akuisisi barang ditemukan, jarak total yang ditempuh oleh agen mungkin tidak sekecil mungkin, karena mungkin ada pintu diblokir lainnya yang lebih jauh dari tujuan tetapi memiliki kunci yang sesuai jauh lebih mudah tersedia. A * akan mengabaikan pintu-pintu ini pada lintasan pertama di mana pintu yang diblokir diabaikan begitu saja.

Saya yakin saya bukan orang pertama yang mencoba menyelesaikan ini dan saya akan sangat menghargai beberapa masukan tentang masalah ini.

Cara untuk menangani situasi seperti itu secara optimal menggunakan A * langsung adalah untuk memperluas ruang pencarian. Artinya, bayangkan ada salinan ruang bawah tanah yang terpisah untuk setiap kombinasi item yang mungkin dibawa karakter Anda.

Di setiap salinan ruang bawah tanah, pintu-pintu yang bisa dilewati adalah persis yang bisa dilewati menggunakan set item yang sesuai. Satu-satunya cara untuk berpindah dari satu salinan dungeon ke yang lain adalah dengan berdiri di lokasi item dan mengambilnya.

Anda dapat memperluas trik ini untuk memasukkan perubahan status lainnya, seperti sakelar yang dapat membuka dan / atau menutup pintu. Anda bahkan dapat mengizinkan pemain untuk menjatuhkan item, meskipun ini bisa menjadi rumit karena negara kemudian harus menyertakan lokasi setiap item yang dijatuhkan, meningkatkan ruang pencarian potensial sangat besar.

Optimalisasi yang sangat berguna adalah untuk menghitung ulang jalur terpendek dari setiap pintu (sebenarnya, setiap sisi dari setiap pintu) dan barang ke setiap pintu / barang lain yang dapat dijangkau, dengan asumsi bahwa semua pintu terkunci . Setelah Anda memiliki jalur tersebut, Anda bisa memperlakukan masing-masing jalur tersebut sebagai tepi tertimbang dalam grafik yang menghubungkan lokasi - lokasi penting ini satu sama lain, dan mengabaikan semua lokasi lainnya.

Sebagai contoh, asumsikan bahwa penjara bawah tanah Anda memiliki sepuluh pintu dan lima kunci. Maka akan ada 2 * 10 + 5 = 25 lokasi yang signifikan, dan 2 ^ 5 = 32 kemungkinan kombinasi item, dengan total 25 * 32 = 800 node di ruang pencarian penuh. Ini adalah angka yang sangat sederhana, terutama mengingat bahwa sebagian besar ruang pencarian cenderung tidak terjangkau.

Dari sudut pandang dunia nyata: Jika Anda menuju dari A ke B dan menemukan pintu D dengan cara yang terkunci, Anda akan menyadari bahwa Anda harus menemukan kunci D. Jadi, jika AI Anda sama tidak dikenalnya seperti manusia pada umumnya. , Itu akan melibatkan pengintaian untuk kunci, yang merupakan serangkaian langkah kecil dalam menemukan jalannya sendiri. Di sisi lain Anda mungkin ingin AI Anda tahu, bahkan sebelum mencoba jalan, bahwa ada pintu yang terkunci pada rute itu, dan dalam hal ini mungkin juga akan tahu di mana menemukan kunci.

Bagaimanapun, masalahnya adalah salah satu konektivitas di dua tingkat. Pada level "di tanah", Anda tahu bahwa Anda selalu dapat bergerak dengan aman dalam satu zona yang tidak terbagi ... tidak terbagi oleh pintu yang terkunci, yaitu. Di sinilah Anda dapat menggunakan implementasi pathfinding A * saat ini dengan bebas. (Dalam contoh sederhana, Anda bisa melihat zona sebagai satu ruangan. Anda tidak bisa mencapai ruangan lain tanpa membuka kunci pintu. Pada kenyataannya, itu bisa menjadi seluruh wilayah ruang bawah tanah Anda.) Ini adalah fondasi dari Anda gerakan entitas, tapi ini agak seperti berjalan-jalan dengan mata tertunduk, alih-alih mengamati daerah di sekitar Anda terlebih dahulu - Anda cenderung berjalan ke tiang lampu. Atau dalam hal ini, pintu yang terkunci. Jadi peta level dasar tempat A * dijalankan harus membatasi pemain agar hanya bergerak di dalam zona saat ini.

Selanjutnya, ada peta tingkat yang lebih tinggi, yang lebih topologis daripada topografi di alam. Itu tidak benar-benar peduli tentang rincian hambatan di lapangan dan sebagainya, itu hanya peduli tentang konektivitas antara zona. Peta topologi ini mengandung koneksi antara zona genap yang saat ini memiliki pintu terkunci di antara mereka, karena ini menunjukkan konektivitas ideal semua zona di ruang bawah tanah Anda. Di tepinya - masing-masing mewakili pintu antara zona - ia menyimpan kunci apa yang diperlukan, jika ada, untuk membuka pintu itu, jika tidak maka dianggap terbuka. Jadi dalam mencari grafik ini untuk jalur terpendek, harus membatasi jalur yang ditemukan hanya untuk rute yang sudah terbuka , dengan memeriksa data di tepinya saat pencarian berjalan. Konektivitas di sini tidak menyiratkan keterbukaan, melainkan menyiratkan potensi keterbukaan.

Saat Anda ingin pindah ke titik yang berada dalam zona terpisah, pertama-tama Anda mencari peta tingkat yang lebih tinggi untuk menemukan jalur. (A * atau algoritma jalur terpendek lainnya dapat digunakan pada level ini.) Setelah Anda menemukan path, peta level yang lebih tinggi itu juga harus memberikan info pintu mana yang perlu Anda gunakan untuk mendapatkan dari zona Anda saat ini ke zona lain. Sekarang, di zona lokal, Anda dapat melakukan AI di permukaan tanah untuk menavigasi ke pintu itu. Setelah pintu tercapai, karakter Anda dapat melewati pintu / portal itu. Dia sekarang di zona B. Jika ini adalah zona target, dia dapat menggunakan navigasi dari permukaan tanah untuk menuju ke tombol. Jika tidak, maka Anda perlu mengulangi langkah pertama sampai Anda mencapai zona target.

Ada kemungkinan kunci yang dicari ada di balik pintu yang terkunci ... dan kunci pintu itu juga ... dan seterusnya ad nauseum. Ini pada dasarnya adalah masalah resolusi ketergantungan, dan ada beberapa cara untuk mengatasi ini, salah satunya adalah Petri Nets. Lihat kertas yang luar biasa ini .

PS. Jika Anda membuat ruang bawah tanah secara prosedural, maka saat melakukannya, Anda dapat menyimpan informasi tentang pemesanan ketergantungan, asalkan Anda sudah mengetahui posisi awal pemain.

Reaksi usus normal terhadap kata-kata "jalan terpendek" jelas akan menjadi A *. Tapi A * akan gagal dalam lingkungan seperti itu, karena saya melihat banyak masalah mendefinisikan heuristik yang dapat diandalkan dan, juga, sangat mungkin, bahwa sebuah node harus dikunjungi beberapa kali, yang juga tidak mungkin dalam A * konvensional dan juga akan membuat heuristik lebih sulit.

Pertama, heuristik yang diterima tidak harus sempurna. Itu hanya harus dianggap remeh dan harus lebih baik daripada tidak sama sekali. Mengingat bahwa Anda bekerja dengan jarak yang sebenarnya, sepertinya A * setidaknya akan sangat membantu, dan bahkan jika heuristik tidak meningkatkan banyak pencarian, itu mungkin masih akan lebih baik daripada pencarian pertama yang luasnya standar atau serupa.

Kedua, A * dapat mengunjungi simpul sebanyak yang Anda suka. Ingatlah bahwa A * bukan algoritma pencarian jalur tetapi algoritma pencarian. Itu mencari melalui negara. Dalam permainan, kita sering menyamakan keadaan dengan posisi, karena kami tidak peduli bagaimana Anda mencapai keadaan itu - betapa singkatnya jalan menuju ke sana. Namun dalam masalah seperti ini negara adalah kombinasi posisi plus keadaan relevan lainnya seperti kunci yang dipegang.

Memang benar, bagaimanapun, bahwa komplikasi ini akan memindahkan A * dari dunia 'sangat efisien' ke 'akan berhasil, tetapi mungkin tidak dalam skala waktu yang saya butuhkan'. Berapa skala waktu yang Anda butuhkan? Sebenarnya, mengapa Anda perlu melakukan ini - apakah Anda benar-benar membutuhkan jalur terpendek, atau cukupkah jalan yang masuk akal?

Apa yang saya pikirkan hanyalah mencari jalan dari awal penjara bawah tanah sampai akhir, mengabaikan pintu yang diblokir. Setelah jalan ini ditemukan, untuk setiap pintu yang menghalangi jalan kami, jalan tambahan yang mencari kunci yang tepat dan kembali ke pintu akan dicari dan dilalui sebelum pintu itu bahkan tercapai.

Sangat mudah untuk membuktikan bahwa sistem seperti itu akan menjadi suboptimal. Dari mana Anda akan memulai jalur tambahan? Jika sejak awal, maka Anda sudah membuang-buang waktu merencanakan jalan asli ke pintu. Jika dari ujung, maka menempatkan kunci di dekat awal berarti jalan melintasi peta dua kali ketika satu kali sudah cukup. Jika Anda mencoba dan menghitung titik gabungan optimal untuk jalur ke dan dari pintu dan jalur asli, itu akan menghasilkan hasil yang optimal tetapi akan menjadi sumber daya intensif karena jumlah permutasi dan kesulitan membentuk heuristik untuk menyederhanakan pencarian. Jika Anda menambahkan beberapa kunci ke dalam masalah, maka Anda memiliki masalah Travelling Salesman yang tidak mudah dipecahkan secara efisien.

Apa yang akan saya coba, jika mungkin untuk bersantai dengan kriteria 'jalur terpendek', adalah ini:

• Buat grafik tingkat tinggi yang hanya berisi lokasi penting - posisi kunci, posisi pintu, posisi di dalam area yang terkunci, dan catat jarak garis lurus di antara mereka. Jika peta Anda sudah dibagi menjadi beberapa ruangan atau lokasi terpisah lainnya, itu bagus.
• Gunakan A * untuk menemukan jalur melalui grafik ini, dari awal hingga akhir. Heuristik jarak Cartesian normal harus cukup untuk membuatnya dapat dikelola.
• Sekarang, dengan jalur yang disederhanakan ini di antara titik-titik jalan ini, gunakan A * lagi untuk memplot jalur tingkat rendah dari satu titik jalan ke titik berikutnya.
• Gabungkan jalur tingkat rendah ini bersama untuk membentuk seluruh jalur Anda.

Setelah saya berhasil, saya akan mempertimbangkan beberapa optimasi kecil - misalnya. membobot area dengan kunci lebih leniently sehingga jalur tingkat rendah akan lebih mungkin untuk membuat jalan memutar kecil untuk mengumpulkan kunci.

dengan informasi yang Anda berikan, saya pikir Anda dapat menggunakan A * hanya dengan sedikit modifikasi. dalam algoritma A * normal, Anda menandai setiap node saat Anda melewati mereka untuk memastikan Anda tidak akan pernah lulus lagi. Itu adalah bagian persis yang membuat masalah dengan Item. Perubahan kuncinya adalah mengingat item apa yang Anda miliki ketika sebelumnya Anda lewati dari sebuah node. di sini adalah kode sudo yang menjelaskan apa yang saya maksud:

if (nodestoCheck.notempty())
    newNode = nodeToCheck.first;
    if (notpassed(newNode.pos, newNode.items))
        if (room(newNode).containItem)
            add NewNode + room(NewNode).items 
        else
            do normal A* algorithm for new Node

dengan algoritma ini, Anda pertama kali mulai memeriksa semua node tanpa item. ada kemungkinan besar bahwa grup pencarian pertama Anda akhirnya diblokir oleh beberapa pintu. tetapi akan menemukan kunci ke pintu itu sebelum mencari semua kamar. dari kunci itu Anda memulai pencarian baru dengan kunci spesifik itu. saat ini ketika Anda mencapai pintu Anda dapat melewatinya. rutinitas yang sama berlanjut sampai Anda menemukan jalan keluar dari penjara bawah tanah. satu-satunya masalah adalah konsumsi memori setiap kali ada banyak pintu dan kunci. meskipun tidak akan menjadi masalah untuk setidaknya 10 atau 15 kunci.

Mengapa Anda tidak menggunakan A * biasa saja, dan memodelkan pintu terkunci sebagai wilayah yang tidak bisa dilewati; setelah Anda mengambil kunci (berjalan di ubin kunci?), yang mengubah pintu terkunci tertentu menjadi wilayah yang lumayan.

Ini berarti bahwa pencari jalan Anda akan pergi untuk rute tanpa kunci terpendek , dan jika menemukan kunci di sepanjang jalan, itu akan memasukkan itu ke dalam jalurnya jika itu membantu.

Bagi saya itu masuk akal. Ini tidak sempurna, tetapi ini adalah solusi sederhana untuk masalah ini.