Algoritma jalur terpanjang untuk generasi labirin roguelike

10

Saya memiliki peta sederhana berbasis grid yang terdiri dari kamar-kamar, seperti ini (A = pintu masuk, B = keluar):

   0 1 2 3
  ##########
0 # B # #####
  ##########
1 # ### #
  ##########
2 # # #
  # # #
3 # # #
  ##########
4 # ### #
  ##########
5 ### A #
  ### #
6 ### #
  ##########

Dan saya terjebak mencoba membuat algoritma yang cocok untuk membuat jalur pintu di antara kamar-kamar, sedemikian rupa sehingga pemain harus menjelajahi sebagian besar peta sebelum menemukan pintu keluar.

Dengan kata lain, saya sedang mencoba untuk menemukan jalan yang mungkin terpanjang dari A ke B .

(Saya sadar bahwa masalah ini dapat diselesaikan untuk grafik asiklik; namun, dalam hal ini mungkin ada siklus.)

SUNTING: Contoh lain di mana kamar terhubung menggunakan penampung banjir, dan pintu keluar dipilih sebagai kamar terjauh dari pintu masuk:

   0 1 2 3
  ##########
0 # B # #
  # # - #####
1 # | # #
  ### # #
2 ### # #
  ### - # - ###
3 # | ###
  # - ########
4 #A | #
  # # #
5 # # #
  # # #
6 # # #
  ##########

Perhatikan bahwa jalur ke jalan keluar sama sekali bukan jalur terpanjang yang mungkin.

Pengguna tidak ditemukan
sumber
Jika Anda memaksa pemain untuk mengambil jalur terpanjang yang mungkin, Anda sebenarnya membangun jalur lurus yang berpura-pura rumit. Ini buruk.
o0 '.
Ini tidak buruk (itu adalah dasar dari genre penembak rel, misalnya), tetapi Anda harus sadar bahwa Anda melakukannya dan merancang sisa permainan Anda untuk bekerja dengan baik dengannya.
Ini juga lebih mudah untuk mengontrol laju permainan ketika level sebagian besar linier. Itu memungkinkan untuk menambahkan, misalnya, ruang pemulihan setelah ruang monster yang sangat sulit. Jika tidak ada jalur utama, distribusi tantangan dan penghargaan akan dilakukan secara acak.
Pengguna tidak ditemukan

Jawaban:

11

Saya pikir Anda salah tentang hal ini. Jalur maksimal dalam grafik dengan siklus secara teknis tidak ditentukan karena tidak terbatas jika siklus terletak di antara awal dan akhir. Mungkin ada cara pintar Anda dapat memperluas / membatasi definisi jalur maksimal, tapi saya tidak berpikir itu pendekatan terbaik di sini.

Anda tidak mencoba memodelkan jalur panjang yang sebenarnya (mis. Robot yang mencoba menjelajahi area sebanyak mungkin di peta). Anda hanya mencoba membuat pemain menjelajahi banyak kamar.

Jadi, buat peluang pemain menemukan jalan keluar sebanding dengan persentase peta yang dieksplorasi sejauh ini . Katakanlah ada ruang X pada level, dan karakter pemain telah menjelajahi Y. Lain kali karakter memasuki ruangan, letakkan pintu keluar di sana dengan probabilitas f (Y, X). Contoh sepele dari f mungkin (Y * Y) / (X * X) - misalnya untuk 10 kamar, ada kemungkinan 100% keluar di kamar terakhir, 81% kemungkinan ada di sebelah kamar terakhir - dan hanya Kesempatan 1% ada di kamar pertama.

Anda dapat mengubah persamaannya namun Anda ingin membuat permainan terasa benar, dan mungkin bahkan memberi pemain beberapa kemampuan untuk membuatnya lebih mungkin dihasilkan. Kuncinya adalah, jangan menghasilkan jalan keluar sampai karakter benar-benar memasuki ruangan. Metode ini juga kebal terhadap pengetahuan pemain tentang algoritma generasi penjara bawah tanah; bahkan jika pemain memiliki pola gerakan aneh seperti lompatan ksatria di NetHack atau teleportasi, mereka harus menjelajahi lebih banyak kamar untuk menemukan jalan keluar.

Jika Anda harus membuat keluar secara statis, Anda dapat menggunakan ide yang sama dengan karakter virtual. Bayangkan isi banjir mulai dari posisi karakter, bergerak sekali sel setiap iterasi. Kamar terakhir yang akan diisi adalah kamar tempat pintu keluar berada (pada kenyataannya, sel terakhir yang harus diisi adalah sel tempat terjauh dari pemain). Namun, dalam hal ini pemain memiliki lebih banyak informasi tentang pintu keluar - jika mereka berada di sebelah kiri, kemungkinan besar di sebelah kanan - dan jika mereka bisa berteleportasi, mungkin sebenarnya bisa sampai di sana lebih cepat daripada berjalan secara normal.

Akhirnya, saya baru saja selesai seperti roguelike di mana pintu keluar muncul di sisi lain peta dari karakter pemain, dan kemudian mengembara secara acak. Beberapa item di ruang bawah tanah membuatnya terlihat di peta, dengan mengorbankan rasa lapar yang lebih cepat. Saya tidak melakukan analisis apa pun, tapi rasanya saya harus menjelajahi lebih banyak peta untuk menemukannya, dan itu memberi level perasaan yang unik.


sumber
Generasi dinamis memang tampak seperti ide yang bagus, asalkan pemain tidak menyadarinya. Kalau tidak, saya pikir mereka akan merasa sangat ditipu. Saya suka ide penimbunan banjir.
Pengguna tidak ditemukan
2
Ya, seluruh proposal Anda dalam beberapa hal menipu pemain. Jangan salahkan saya karena memperbaiki matematika untuk tidak membutuhkan model dunia. ;) Tetapi Anda dapat menggunakan trik desain untuk membuatnya lebih enak - misalnya, pintu keluar ditempatkan secara apriori, tetapi kunci yang diperlukan untuk menggunakannya dihasilkan dalam metode yang saya jelaskan, atau ditempatkan pada monster yang hanya memunculkan setelah menjelajahi X kamar / membunuh monster X, atau membuka pintu membutuhkan membalik X switch, satu di setiap kamar, dll ...
Saya mencoba pendekatan penimbunan. Itu melakukan pekerjaan yang baik untuk menghubungkan setiap kamar dan menghasilkan cabang pendek, tetapi sebenarnya tidak menghasilkan jalur terpanjang yang mungkin untuk keluar bahkan jika keluar adalah simpul terakhir yang dikunjungi (atau, dalam implementasi saya, yang terjauh). (contoh ditambahkan ke pertanyaan saya)
Pengguna tidak ditemukan
Saya semua untuk labirin berbasis key / switch. Tampaknya lebih mudah untuk menerapkan hal semacam itu dengan pohon, karena jika Anda memiliki dua cabang, Anda dapat mendeteksi cabang mana yang mengarah ke pintu keluar, memblokirnya, dan meletakkan kunci di cabang lainnya.
Pengguna tidak ditemukan
Tetapi saya akui bahwa saya salah dalam berpikir bahwa itu adalah masalah pencarian jalan "A to B". Saya menyadari lebih masuk akal untuk menemukan jalan keluar sebagai hasil dari algoritma daripada sebagai tujuan.
Pengguna tidak ditemukan
6

Alternatif yang mungkin adalah membuat pohon spanning (maksimum?) Menggunakan Prim / Kruskal (untuk menghilangkan siklus) dan menerapkan algoritma jalur terpanjang tradisional pada pohon spanning.

Namun, saya khawatir bahwa algoritma spanning tree akan cenderung membuat cabang jalan buntu, memaksa pemain untuk mundur terus-menerus.

EDIT: Hasil menggunakan algoritma berbasis Kruskal dan menempatkan pintu keluar di ujung cabang terpanjang:

   0 1 2 3
  ##########
0 #A | #
  # ##### - #
1 # # #
  ### #
2 ### #
  ### #
3 ### #
  ### - #####
4 # | #
  # - ##### - #
5 # ### #
  # - ########
6 # # B #
  # # - #
7 # | #
  ##########
Pengguna tidak ditemukan
sumber
1
Saya juga akan menyarankan Primm :-), +1, saya pikir backtrack adalah bagian penting dari banyak permainan juga ... periksa diablo 2.
Mr.Gando
2

Berikut ini sesuatu yang bisa Anda gunakan:

Connect each room with a door to another room.
N = 0.75*TotalNumberOfRooms
Until (pathSize > N) {
  Use A* pathing to get a path from A to B. (G being size of room, or # of monsters)
  if (pathSize < N) remove a connection/door
  if (noPath) choose a different door/connection
  if (room.doors < 1) choose a different door/connection
}

Saya akan menghapus pintu secara acak di sepanjang jalan, jika tidak Anda berakhir dengan 1 pintu di pintu keluar, dan banyak pintu di awal.

Saya pikir ini O(n^2)sangat tidak bagus untuk peta besar.

Stephen Furlani
sumber
Solusi yang sangat elegan secara prinsip. Lain kali saya harus mencoba memikirkan sesuatu seperti ini sebelum pergi untuk teknik yang berbelit-belit.
Pengguna tidak ditemukan
Yah, elegan mungkin tapi itu akan menjadi babi prosesor. O (n ^ 2) tidak akan skala dengan peta besar.
Stephen Furlani
1

Saya yakin Anda sudah memiliki jawaban yang bagus, tetapi inilah solusi teoretis saya sebesar $ 0,02 untuk masalah ini.

Yang Anda inginkan BUKAN jalan terpanjang, tetapi jalan terpanjang terpanjang. Anda ingin ruangan yang paling jauh, mengingat Anda mempertimbangkan jalur terpendek ke kamar. Ini mungkin terdengar membingungkan, tetapi sangat mudah untuk dihitung.

  1. Mulai dari ruang awal Anda. Tandai setiap tetangganya 1. Jarak 1 dari ruang awal.
  2. Untuk setiap kamar bertanda 1, kunjungi masing-masing tetangganya yang tidak ditandai dan tandai mereka 2. Mereka berjarak 2 jarak dari awal.
  3. Lanjutkan sampai Anda telah menutupi semua kamar. Kamar dengan jumlah maksimum adalah yang terjauh dari awal.

Menghitung jalur terpanjang yang sebenarnya (tidak akan memakan waktu terlalu lama untuk mengatakan 10 kamar) tidak akan berfungsi karena Anda tidak dapat membuat pemain mengambil jalur terpanjang itu. Jadi menempatkan pintu masuk dan keluar di dua kamar yang paling jauh satu sama lain adalah pilihan terbaik Anda. Untuk menemukan ini, hitung ruang terjauh dari ruang acak. Kemudian, dari ruangan itu, temukan ruangan terjauh. Ini disebut menemukan diameter Grafik, silakan Google itu.

Sid Datta
sumber