Pertanyaan Algoritma untuk generasi labirin tanpa jalan buntu?


Saya mencari algoritma generasi labirin yang dapat menghasilkan labirin tanpa jalan buntu tetapi hanya awal dan akhir. Seperti ini:

maze

Gambar dari http://www.astrolog.org/labyrnth/maze/unicursl.gif

Di mana saya menemukan atau pergi tentang membangun seperti algoritma generasi labirin?


32
2017-09-10 05:57


asal


Jawaban:


Sepertinya Anda menginginkan kurva pengisian ruang pseudo-acak (misalnya, lihat Kurva Pengisian Ruang Berbasis Konteks --EUROGRAPHICS '2000 (Format PDF, 1.1 MB))

Lihatlah a Kurva pengisian ruang.

Saya menduga Anda dapat menerapkan beberapa keacakan pada konstruksi salah satunya untuk mencapai apa yang Anda inginkan.


15
2017-09-10 07:16



Saya akan menyarankan untuk memulai dengan persegi yang benar-benar hitam (penuh) dan mencoba untuk menggali jalan. Selama penggalian Anda dengan mudah memastikan tidak ada jalan buntu, teruskan saja. Gunakan backtracking, kedalaman algoritma pencarian pertama. Lakukan "perjalanan acak" - di setiap langkah, tentukan secara acak apakah akan mempertahankan arah atau mengubahnya. Periksa kondisi buntu - jika Anda buntu, Anda bisa mengatakan "yah, saya sudah selesai, saya sudah selesai", atau, jika Anda menganggap labirin belum cukup digali, cukup mundur saja. Selalu ingat apa yang telah Anda lakukan sebelumnya dan coba secara acak beberapa tindakan lain. Mungkin menggunakan beberapa heuristik untuk memilih arah tertentu, seperti, katakanlah, selalu menjaga beberapa ruang kosong sebelum menghindari dinding, cobalah pertama untuk berjalan di sekitar dinding dll - cara ini Anda bisa menemukan solusi yang diinginkan yang mengisi semua kotak jauh lebih cepat.


5
2017-09-10 06:45



Dalam contoh yang Anda berikan hanya ada satu jalur yang sebenarnya dari awal hingga akhir. Jika itu yang Anda inginkan, saya pikir Anda bisa menggunakan jalan-jalan acak!

Konsepnya sederhana: mengingat batas luar labirin, titik awal, dan titik akhir, tulis sebuah fungsi untuk menghasilkan jalan acak dari titik awal yang akhirnya berakhir pada titik akhir. Syaratnya adalah "walker acak" kami hanya bisa bergerak ke atas, bawah, kanan, atau kiri dari kotak sebelumnya, dan tidak bisa masuk dalam satu kotak persegi yang dilalui sebelumnya (ini menciptakan dinding).

Seperti yang saya lihat, ada dua tantangan algoritmik di sini. Yang pertama adalah memastikan apakah kita berada dalam satu kotak persegi yang dilalui sebelumnya (tabrakan). Mungkin kita bisa mempertahankan daftar kuadrat yang dilalui (koordinatnya) dan batas-batas labirin, dan untuk setiap persegi baru mengevaluasi jarak dari setiap kotak dalam daftar. Ini tidak terdengar sangat efisien.

Tantangan lainnya adalah mencapai titik akhir dengan perjalanan acak kami. Jika tabrakan dengan kotak yang dilalui sebelumnya tidak menjadi masalah, kita pasti akan mencapai titik akhir kita, tetapi bersama mereka kita memiliki masalah bahwa kita dapat menutup diri dari titik akhir. Cara untuk menghindari ini adalah untuk memeriksa dan menghindari masuknya loop. Jika kita menghindari memasuki loop yang dibentuk oleh jalur yang dilalui dan / atau batas labirin, maka kita mempertahankan jalur yang mungkin menuju titik akhir. Sejauh yang sebenarnya jika kita berada dalam satu lingkaran ... Meh itu agak sulit.

Jika Anda sudah memiliki algoritma pemecahan labirin, Anda dapat menjalankannya kapan pun Anda memiliki kemungkinan tabrakan untuk melihat apakah ada jalur dari kotak Anda saat ini ke titik akhir. Saat Anda menjalankannya, pikirkan bahwa semua kotak yang dilalui sebelumnya adalah dinding, serta batas-batasnya.


2
2017-09-10 07:00



Saya belum memikirkan ini, hanya sebuah ide:

  • Berkonsentrasi tidak di jalan, tetapi di dinding
  • Mulai dengan hanya persegi luar hitam
  • Menambah blok dinding secara progresif di posisi arbitrer yang berdekatan dengan dinding blok yang ada, mempertahankan kondisi yang masih ada jalur dari awal hingga akhir
  • Ketika tidak ada sel jalur yang memiliki lebih dari dua jalur tetangga, Anda sudah selesai

Proses seleksi 'arbitrary' untuk potongan-potongan baru dinding dapat mulai mencoba untuk 'menumbuhkan' bagian-bagian lurus yang tegak lurus dengan dinding luar, kemudian pada tahap tertentu beralih untuk mengisi sedapat mungkin.

Mungkin perlu kemampuan untuk mundur jika itu macet.

Mungkin itu tidak terlalu efisien.


2
2017-09-10 06:29



Ahh - Saya telah menemukan cara yang lebih mudah untuk menghasilkan labirin unicursal.

Mulailah dengan grid kosong, dan isi dengan loop 2x2 kecil. Jika grid itu ganjil-ganjil, Anda harus mencampurkan beberapa loop 2x3, dan jika ganjil-ganjil, Anda harus meninggalkan satu persegi kosong - saya biasanya meninggalkan sudut kosong.

Selanjutnya, sewenang-wenang bergabung dengan loop bersama untuk membentuk loop yang lebih besar - jadi (misalnya) 2 2x2 loop menjadi loop 4x2 tunggal. Terus lakukan ini, pastikan Anda tidak bergabung kembali ke lingkaran itu sendiri.

Akhirnya Anda akan berakhir dengan satu loop yang menggunakan semua sel yang ditempati oleh pertanian asli loop. Pecahkan lingkaran ini di posisi mana pun, dan Anda punya labirin unicursal, di mana lokasi awal dan akhir bersebelahan.

Anda sekarang dapat memindahkan titik akhir di sekitar grid dengan membentuk dan memecah loop kecil - menghubungkan ujungnya ke titik lain di labirin, dan kemudian mematahkan T-junction di sisi berlawanan untuk membentuk kembali satu senar string Anda dengan yang baru. lokasi akhir.

Jika Anda bekerja pada labirin aneh-demi-aneh, gunakan teknik terakhir ini untuk membujuk salah satu ujung Anda ke pojok yang tak terisi untuk menyelesaikan labirin Anda.


2
2017-07-04 21:43



Saya pikir saya telah menemukan metode lain, namun saya belum mengujinya secara ekstensif.

Lihat https://twitter.com/tdhooper/status/340853820584230915/photo/1

Dari kiri ke kanan:

  • Hasilkan labirin non-unicursal seperti yang dijelaskan di sini https://en.wikipedia.org/wiki/File:Prim_Maze.svgSaya rasa ini adalah algoritma Prim

  • Tutup pintu keluar

  • Gambarlah jalur yang mengunjungi setiap titik di labirin (mis. Mencoba menyelesaikannya)

  • Jadikan jalan ini sebagai dinding


2
2018-06-01 15:35



Ketika 'berjalan' menjaga perubahan yang dibuat pada setiap langkah dalam tumpukan, sehingga dengan cara itu Anda dapat melihat langkah x ke depan dan kemudian pada setiap tahap sehingga Anda tidak dapat melakukan langkah lebih lanjut (berjalan ke sudut atau spiral seperti berjalan) pop tumpukan sampai Anda memiliki jalan berjalan yang layak dan terus berjalan dari sana sampai tumpukan kosong (yaitu Anda pop tumpukan semua jalan kembali karena pada setiap langkah sebelumnya tidak ada tetangga yang layak). Kemudian terapkan transformasi ke struktur data labirin.


1
2018-06-27 11:46



Saya sedang mengerjakan ini pada saat ini ... Mulai dari tepi, saya berjalan acak melintasi susunan persegi, menandai sel dengan panjang lintasan saat saya melewatinya.

Ketika Anda terjebak (dan Anda akan), buat T-junction membentuk loop dengan jalur paling baru yang berdekatan dengan Anda (tetapi lihat di bawah). Saya kemudian kembali melacak sepanjang jalan yang ada ke sisi lain dari pertigaan dan memutus loop di sana. Ekor menjuntai ini kemudian membentuk 'kepala' baru Anda dari jalan acak (ingat untuk menghitung ulang panjang jalur Anda dari sumber jalur), dan Anda dapat melanjutkan.

Eksperimen menunjukkan bahwa dengan melakukan hal ini tidak (atau belum - lihat di bawah) masuk ke dalam lingkaran menciptakan ekor baru, asalkan 'ekor' baru Anda terperangkap, Anda tidak hanya dengan sembarangan membentuk ulang tautan dengan sel yang baru saja Anda pisahkan dari yang paling baru - pilih yang paling baru kedua dalam kasus itu.

Kasus terminating adalah ketika Anda mendapatkan 'stuck' pada elemen edge, dan Anda telah mengisi array (panjang path Anda sama dengan luas array) - Anda selesai. Titik awal Anda mengarah ke titik akhir Anda.

Sepertinya ada dua kemungkinan ketidakefisienan dan potensi gangguan dengan ini (saya bermain dengan algoritme saat ini) - Terkadang Anda akan berjalan ke sudut dan satu-satunya cara untuk melanjutkan adalah dengan membentuk kembali tautan pengulangan dengan satu Anda baru saja rusak. Kemudian urutan kembali-trek melalui semua loop yang Anda buat sebelumnya ke titik di mana Anda awalnya terjebak. Jika bahwa tidak bisa pergi ke tempat lain (itu sudut lain) maka Anda hanya akan bangkit di antara keduanya. Ada beberapa cara di sekitar itu, tetapi itu berarti menyimpan semacam daftar sel yang dilingkarkan, hanya membersihkannya ketika Anda benar-benar meletakkan beberapa jalur baru.

Yang lain adalah bahwa tampaknya cenderung meninggalkan persegi aneh yang tidak terisi, terutama ketika array Anda aneh-dengan-aneh. Saya belum sepenuhnya menyelidiki mengapa hal ini terjadi, dan ketika ini terjadi bahwa masalah sudut sebelumnya tampaknya sangat umum. Pekerjaan berlanjut ...


1
2017-07-02 23:15