Algoritma jalur terpanjang untuk generasi labirin roguelike

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.

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.

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 # | #
  ##########

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.

2 Tumpukan Overflow mirip dengan yang ini: grafik jalur terpanjang , referensi dari posting yang sama .

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.