Merintis jalan dengan kunci dan kunci?

Saya mengerjakan game dengan peta yang menyerupai kunci dan teka-teki kunci . AI perlu menavigasi ke tujuan yang mungkin berada di belakang pintu merah yang terkunci, tetapi kunci merah mungkin di belakang pintu biru yang terkunci, dan seterusnya ...

Teka-teki ini mirip dengan penjara bawah tanah gaya Zelda, seperti gambar ini:

Untuk mencapai Goal, Anda harus mengalahkan Bos, yang mengharuskan Anda melewati pit, yang membutuhkan pengumpulan Bulu, yang membutuhkan pengumpulan Kunci

Penjara bawah tanah Zelda cenderung linier. Namun, saya perlu menyelesaikan masalah dalam kasus umum. Begitu:

• Tujuannya mungkin memerlukan salah satu dari serangkaian kunci. Jadi mungkin Anda perlu mendapatkan kunci merah atau biru. Atau mungkin ada pintu yang tidak terkunci sepanjang jalan!
• Mungkin ada beberapa pintu dan kunci sejenis. Misalnya mungkin ada beberapa kunci merah di peta, dan mengumpulkan satu akan memberikan akses ke semua pintu merah.
• Tujuannya mungkin tidak dapat diakses karena kunci yang tepat ada di balik pintu yang terkunci

Bagaimana saya melakukan penelusuran jalan di peta seperti itu? Seperti apa grafik pencarian?

Catatan: poin terakhir tentang mendeteksi tujuan yang tidak dapat diakses adalah penting; A *, misalnya, sangat tidak efisien jika tujuannya tidak dapat diakses. Saya ingin menangani ini secara efisien.

Asumsikan bahwa AI tahu di mana semuanya ada di peta.

Pathfinding standar adalah Cukup Baik - negara Anda adalah lokasi Anda saat ini + inventaris Anda saat ini. "Memindahkan" adalah mengubah kamar atau mengubah inventaris. Tidak tercakup dalam jawaban ini, tetapi tidak terlalu banyak upaya tambahan, menulis heuristik yang baik untuk A * - itu benar-benar dapat mempercepat pencarian dengan lebih memilih untuk mengambil barang-barang daripada bergerak menjauh dari itu, lebih memilih untuk membuka kunci pintu di dekat target mencari lebih jauh, dll.

Jawaban ini telah mendapatkan banyak peningkatan sejak datang pertama dan memiliki demo, tetapi untuk solusi yang jauh lebih dioptimalkan dan khusus, Anda juga harus membaca jawaban "Melakukannya mundur jauh lebih cepat" /gamedev/ / a / 150155/2624

Bukti Javascript yang sepenuhnya operasional konsep di bawah ini. Maaf untuk jawabannya sebagai dump kode - Saya telah benar-benar menerapkan ini sebelum saya yakin itu adalah jawaban yang baik, tetapi tampaknya cukup fleksibel bagi saya.

Untuk memulai ketika memikirkan pathfinding, ingatlah bahwa hirarki algoritma pathfinding sederhana adalah:

• Breadth First Search adalah sesederhana mungkin.
• Algoritma Djikstra seperti Breadth First Search tetapi dengan "jarak" yang bervariasi antar negara bagian
• A * adalah Djikstras di mana Anda memiliki 'pengertian umum tentang arah yang benar' yang tersedia sebagai heuristik.

Dalam kasus kami, hanya penyandian "keadaan" sebagai "lokasi + inventaris" dan "jarak" sebagai "perpindahan atau penggunaan item" memungkinkan kami untuk menggunakan Djikstra atau A * untuk menyelesaikan masalah kami.

Berikut adalah beberapa kode aktual yang menunjukkan level contoh Anda. Cuplikan pertama hanya untuk perbandingan - lompat ke bagian kedua jika Anda ingin melihat solusi akhir. Kami memulai dengan implementasi Djikstra yang menemukan jalan yang benar, tetapi kami mengabaikan semua hambatan dan kunci. (Cobalah, Anda bisa melihatnya hanya untuk garis finish, dari kamar 0 -> 2 -> 3-> 4-> 6-> 5)

function Transition(cost, state) { this.cost = cost, this.state = state; }
// given a current room, return a room of next rooms we can go to. it costs 
// 1 action to move to another room.
function next(n) {
    var moves = []
    // simulate moving to a room
    var move = room => new Transition(1, room)
    if (n == 0) moves.push(move(2))
    else if ( n == 1) moves.push(move(2))
    else if ( n == 2) moves.push(move(0), move(1), move(3))
    else if ( n == 3) moves.push(move(2), move(4), move(6))
    else if ( n == 4) moves.push(move(3))
    else if ( n == 5) moves.push(move(6))
    else if ( n == 6) moves.push(move(5), move(3))
    return moves
}

// Standard Djikstra's algorithm. keep a list of visited and unvisited nodes
// and iteratively find the "cheapest" next node to visit.
function calc_Djikstra(cost, goal, history, nextStates, visited) {

    if (!nextStates.length) return ['did not find goal', history]

    var action = nextStates.pop()
    cost += action.cost
    var cur = action.state

    if (cur == goal) return ['found!', history.concat([cur])]
    if (history.length > 15) return ['we got lost', history]

    var notVisited = (visit) => {
        return visited.filter(v => JSON.stringify(v) == JSON.stringify(visit.state)).length === 0;
    };
    nextStates = nextStates.concat(next(cur).filter(notVisited))
    nextStates.sort()

    visited.push(cur)
    return calc_Djikstra(cost, goal, history.concat([cur]), nextStates, visited)
}

console.log(calc_Djikstra(0, 5, [], [new Transition(0, 0)], []))

Jadi, bagaimana kita menambahkan item dan kunci ke kode ini? Sederhana! alih-alih setiap "keadaan" memulai hanya nomor kamar, sekarang menjadi tupel ruangan dan status inventaris kami:

 // Now, each state is a [room, haskey, hasfeather, killedboss] tuple
function State(room, k, f, b) { this.room = room; this.k = k; this.f = f; this.b = b }

Transisi sekarang berubah dari tuple (biaya, kamar) menjadi tupel (biaya, status), sehingga dapat menyandikan "pindah ke kamar lain" dan "mengambil item"

// move(3) keeps inventory but sets the room to 3
var move = room => new Transition(1, new State(room, cur.k, cur.f, cur.b))
// pickup("k") keeps room number but increments the key count
var pickup = (cost, item) => {
    var n = Object.assign({}, cur)
    n[item]++;
    return new Transition(cost, new State(cur.room, n.k, n.f, n.b));
};

akhirnya, kami membuat beberapa perubahan kecil yang berhubungan dengan tipe pada fungsi Djikstra (misalnya, masih cocok dengan nomor ruang tujuan alih-alih keadaan penuh), dan kami mendapatkan jawaban lengkap kami! Perhatikan hasil cetakan pertama pergi ke kamar 4 untuk mengambil kunci, kemudian pergi ke kamar 1 untuk mengambil bulu, kemudian pergi ke kamar 6, membunuh bos, lalu pergi ke kamar 5)

// Now, each state is a [room, haskey, hasfeather, killedboss] tuple
function State(room, k, f, b) { this.room = room; this.k = k; this.f = f; this.b = b }
function Transition(cost, state, msg) { this.cost = cost, this.state = state; this.msg = msg; }

function next(cur) {
var moves = []
// simulate moving to a room
var n = cur.room
var move = room => new Transition(1, new State(room, cur.k, cur.f, cur.b), "move to " + room)
var pickup = (cost, item) => {
	var n = Object.assign({}, cur)
	n[item]++;
	return new Transition(cost, new State(cur.room, n.k, n.f, n.b), {
		"k": "pick up key",
		"f": "pick up feather",
		"b": "SLAY BOSS!!!!"}[item]);
};

if (n == 0) moves.push(move(2))
else if ( n == 1) { }
else if ( n == 2) moves.push(move(0), move(3))
else if ( n == 3) moves.push(move(2), move(4))
else if ( n == 4) moves.push(move(3))
else if ( n == 5) { }
else if ( n == 6) { }

// if we have a key, then we can move between rooms 1 and 2
if (cur.k && n == 1) moves.push(move(2));
if (cur.k && n == 2) moves.push(move(1));

// if we have a feather, then we can move between rooms 3 and 6
if (cur.f && n == 3) moves.push(move(6));
if (cur.f && n == 6) moves.push(move(3));

// if killed the boss, then we can move between rooms 5 and 6
if (cur.b && n == 5) moves.push(move(6));
if (cur.b && n == 6) moves.push(move(5));

if (n == 4 && !cur.k) moves.push(pickup(0, 'k'))
if (n == 1 && !cur.f) moves.push(pickup(0, 'f'))
if (n == 6 && !cur.b) moves.push(pickup(100, 'b'))	
return moves
}

var notVisited = (visitedList) => (visit) => {
return visitedList.filter(v => JSON.stringify(v) == JSON.stringify(visit.state)).length === 0;
};

// Standard Djikstra's algorithm. keep a list of visited and unvisited nodes
// and iteratively find the "cheapest" next node to visit.
function calc_Djikstra(cost, goal, history, nextStates, visited) {

if (!nextStates.length) return ['No path exists', history]

var action = nextStates.pop()
cost += action.cost
var cur = action.state

if (cur.room == goal) return history.concat([action.msg])
if (history.length > 15) return ['we got lost', history]

nextStates = nextStates.concat(next(cur).filter(notVisited(visited)))
nextStates.sort()

visited.push(cur)
return calc_Djikstra(cost, goal, history.concat([action.msg]), nextStates, visited)
o}

console.log(calc_Djikstra(0, 5, [], [new Transition(0, new State(0, 0, 0, 0), 'start')], []))

Secara teori, ini bekerja bahkan dengan BFS dan kami tidak memerlukan fungsi biaya untuk Djikstra, tetapi memiliki biaya memungkinkan kami untuk mengatakan "mengambil kunci itu mudah, tetapi melawan bos sangat sulit, dan kami lebih memilih mundur 100 langkah daripada melawan bos, jika kita punya pilihan ":

if (n == 4 && !cur.k) moves.push(pickup(0, 'k'))
if (n == 1 && !cur.f) moves.push(pickup(0, 'f'))
if (n == 6 && !cur.b) moves.push(pickup(100, 'b'))

Mundur A * akan melakukan trik

Seperti dibahas dalam jawaban ini untuk pertanyaan tentang maju dan mundur pathfinding , merintis jalan mundur adalah solusi yang relatif sederhana untuk masalah ini. Ini bekerja sangat mirip dengan GOAP (Goal Oriented Action Planning), perencanaan solusi yang efisien sambil meminimalkan bertanya-tanya tanpa tujuan.

Di bagian bawah jawaban ini saya memiliki rincian tentang bagaimana menangani contoh yang Anda berikan.

Secara terperinci

Temukan dari tujuan ke awal. Jika, di pathfinding Anda, Anda menemukan pintu yang terkunci, Anda memiliki cabang baru ke pathfinding Anda yang berlanjut melalui pintu seolah-olah tidak terkunci, dengan cabang utama terus mencari jalan lain. Cabang yang terus melewati pintu seolah-olah tidak dikunci tidak lagi mencari agen AI - sekarang mencari kunci yang dapat digunakan untuk melewati pintu. Dengan A *, heuristik barunya adalah jarak ke kunci + jarak ke agen AI, bukan hanya jarak ke agen AI.

Jika cabang pintu terbuka menemukan kunci, maka terus mencari agen AI.

Solusi ini dibuat sedikit lebih rumit ketika ada beberapa kunci yang layak tersedia, tetapi Anda dapat melakukan percabangan yang sesuai. Karena cabang memiliki tujuan tetap, itu masih memungkinkan Anda menggunakan heuristik untuk mengoptimalkan pencarian jalan (A *), dan jalur yang mustahil semoga akan terpotong dengan cepat - jika tidak ada jalan di sekitar pintu yang terkunci, cabang yang tidak bisa melewati pintu kehabisan pilihan dengan cepat dan cabang yang melewati pintu dan mencari kunci terus sendiri.

Tentu saja, di mana ada berbagai pilihan yang tersedia (beberapa kunci, item lain untuk menghindari pintu, jalan panjang di sekitar pintu), banyak cabang akan dipertahankan, yang mempengaruhi kinerja. Tetapi Anda juga akan menemukan opsi tercepat, dan dapat menggunakannya.

Beraksi

Dalam contoh spesifik Anda, merintis jalan dari Sasaran ke Mulai:

1. Kami dengan cepat menemukan pintu bos. Cabang A berlanjut melalui pintu, sekarang mencari bos untuk bertarung. Cabang B tetap tersangkut di ruangan, dan akan segera kedaluwarsa ketika menemukan tidak ada jalan keluar.

2. Cabang A menemukan bos dan sekarang sedang mencari Start, tetapi bertemu lubang.

3. Cabang A berlanjut di atas lubang, tetapi sekarang mencari bulu, dan akan membuat garis lebah ke arah bulu yang sesuai. Cabang C dibuat yang mencoba menemukan jalan di sekitar lubang, tetapi segera kedaluwarsa karena tidak bisa. Itu, atau akan diabaikan untuk sementara waktu, jika heuristik A * Anda menemukan bahwa Cabang A masih terlihat paling menjanjikan.

4. Cabang A menjumpai pintu yang terkunci, dan terus melalui pintu yang terkunci seolah-olah tidak dikunci, tetapi sekarang sedang mencari kuncinya. Cabang D terus melalui pintu yang terkunci juga, masih mencari bulu, tetapi kemudian akan mencari kuncinya. Ini karena kita tidak tahu apakah kita perlu menemukan kunci atau bulu terlebih dahulu, dan sejauh menyangkut pathfinding, Start bisa berada di sisi lain dari pintu ini. Cabang E mencoba menemukan jalan di sekitar pintu yang terkunci, dan gagal.

5. Cabang D dengan cepat menemukan bulu dan terus mencari kuncinya. Diperbolehkan melewati pintu yang terkunci lagi, karena masih mencari kuncinya (dan itu bekerja dengan cara mundur dalam waktu). Tetapi begitu ia memiliki kunci, ia tidak akan dapat melewati pintu yang terkunci (karena ia tidak dapat melewati pintu yang terkunci sebelum ia menemukan kunci itu).

6. Cabang A dan D terus bersaing, tetapi ketika Cabang A mencapai kunci, ia mencari bulu, dan ia akan gagal mencapai bulu karena harus melewati pintu yang terkunci lagi. Cabang D, di sisi lain, setelah mencapai kunci, mengalihkan perhatiannya ke Start, dan menemukannya tanpa kerumitan.

7. Cabang D menang. Ia telah menemukan jalan sebaliknya. Jalur terakhir adalah: Mulai -> Kunci -> Bulu -> Bos -> Sasaran.

Sunting : Ini ditulis dari sudut pandang AI yang keluar untuk menjelajahi dan menemukan tujuan, dan tidak tahu lokasi kunci, kunci, atau tujuan sebelumnya.

Pertama, anggaplah bahwa AI memiliki semacam tujuan keseluruhan. Misalnya ,, "Temukan bos" dalam contoh Anda. Ya, Anda ingin mengalahkannya, tetapi sebenarnya ini tentang menemukannya. Anggaplah ia tidak tahu bagaimana mencapai tujuan, hanya saja itu ada. Dan itu akan mengetahuinya ketika menemukannya. Begitu tujuan tercapai, AI dapat berhenti bekerja untuk menyelesaikan masalah.

Juga, saya akan menggunakan istilah umum "kunci" dan "kunci" di sini, bahkan jika itu mungkin jurang dan bulu. Yaitu, bulu "membuka" jurang "kunci".

Pendekatan Solusi

Sepertinya Anda akan mulai pertama hanya dengan AI yang pada dasarnya adalah penjelajah labirin (jika Anda menganggap peta Anda sebagai labirin). Menjelajahi dan memetakan semua tempat yang bisa dituju akan menjadi fokus utama AI. Itu bisa didasarkan murni pada sesuatu yang sederhana seperti, "Selalu pergi ke jalan terdekat yang pernah saya lihat tetapi belum dikunjungi."

Namun, beberapa aturan akan muncul saat menjelajah yang mungkin mengubah prioritas ...

• Itu akan mengambil kunci apa pun yang ditemukannya, kecuali jika sudah memiliki kunci yang sama
• Jika ia menemukan kunci yang belum pernah dilihatnya, itu akan mencoba setiap kunci yang ditemukan pada kunci itu
• Jika kunci bekerja pada jenis kunci baru, itu akan mengingat jenis kunci dan jenis kunci
• Jika menemukan kunci yang telah dilihat sebelumnya dan memiliki kunci, itu akan menggunakan jenis kunci yang diingat (misalnya, kunci merah kedua ditemukan, kunci merah bekerja sebelumnya pada kunci merah, jadi gunakan saja kunci merah)
• Ia akan mengingat lokasi kunci apa pun yang tidak dapat dibuka kuncinya
• Tidak perlu mengingat lokasi kunci yang telah dibuka kuncinya
• Setiap kali ia menemukan kunci dan mengetahui adanya kunci yang tidak dapat dibuka sebelumnya, ia akan segera mengunjungi masing-masing kunci yang terkunci itu, dan mencoba untuk membuka kunci itu dengan kunci yang baru ditemukan.
• Ketika pernah membuka jalan, itu hanya akan kembali ke tujuan eksplorasi dan pemetaan, memprioritaskan melangkah ke daerah baru

Catatan tentang poin terakhir itu. Jika harus memilih antara akan memeriksa area yang belum dijelajahi yang terlihat sebelumnya (tetapi tidak dikunjungi) versus area yang belum dijelajahi di belakang jalur yang baru dibuka, itu harus menjadikan jalur yang baru dibuka menjadi prioritas. Itu mungkin di mana ada kunci baru (atau kunci) yang akan berguna. Ini mengasumsikan jalan yang terkunci mungkin tidak akan menjadi jalan buntu yang sia-sia.

Memperluas Ide dengan Kunci "Dapat Dikunci"

Anda dapat berpotensi memiliki kunci yang tidak dapat diambil tanpa kunci lain. Atau kunci yang terkunci. Jika Anda tahu Gua Kolosal lama Anda, Anda perlu memiliki sangkar burung untuk menangkap burung - yang Anda butuhkan nanti untuk seekor ular. Jadi Anda "membuka" burung dengan kandang (yang tidak menghalangi jalan tetapi tidak dapat diambil tanpa kandang), dan kemudian "membuka" ular (yang menghalangi jalan Anda) dengan burung.

Jadi menambahkan beberapa aturan ...

• Jika kunci tidak dapat diambil (dikunci), coba setiap kunci yang sudah Anda miliki
• Jika Anda menemukan kunci yang tidak dapat dibuka kuncinya, ingat untuk nanti
• Jika Anda menemukan kunci baru, coba di setiap kunci yang dikenal terkunci serta jalur terkunci

Saya bahkan tidak akan membahas semuanya tentang bagaimana membawa kunci tertentu dapat meniadakan efek kunci lain (Gua Colossal, batang menakut-nakuti burung dan harus dijatuhkan sebelum burung dapat diambil, tetapi diperlukan kemudian untuk membuat jembatan ajaib) .