Generasi Labirin [ditutup]

41

Saya tahu ada utas (lama) yang mirip dengan ini (di sini ), tetapi saya ingin mem-boot-ulangnya dengan beberapa modifikasi.

Tujuannya: menghasilkan labirin yang tampak acak menggunakan algoritme pilihan Anda, lalu mengeluarkan labirin secara grafis (jumlah pencetakan).

  • Lebar dan tinggi ditentukan oleh Anda.
  • Harus ada setidaknya satu jalur dari setidaknya satu pintu masuk ke setidaknya satu pintu keluar.
  • Format labirin (cara Anda menampilkannya, tandai pintu masuk atau keluar) terserah Anda juga.
  • Lebih cantik, semakin baik.
  • Labirin sepele (mis. Labirin kosong, labirin kisi, labirin ukuran 1x1) tidak disarankan.
  • Siklus dalam labirin diizinkan dan, didorong, jika hasilnya masuk akal.
  • Penyalahgunaan bahasa didorong.
  • Labirin harus terlihat cukup acak (tetapi algoritma yang sepenuhnya deterministik (misalnya kacau) yang menghasilkan ini juga baik-baik saja).

Sunting: fokus utama di sini adalah membuat implementasi sekecil mungkin. Namun, saya ingin memberikan beberapa kelonggaran dalam batasan itu untuk mendorong shininess. Saya sengaja meninggalkan "fitur" apa yang telah dibuka oleh labirin, tetapi sebagai pedoman kasar Anda harus mencoba mengemas jumlah bang yang paling banyak ke dalam uang yang paling tidak leksikal.

Imallett
sumber
4
Juga "Semakin cantik, semakin baik" tampaknya hampir tidak nyata (atau hanya tidak relevan) dengan tantangan kode-golf. Mungkin kontes popularitas akan menjadi pilihan yang lebih baik jika Anda tertarik pada hasil yang cantik.
Martin Ender
5
Jadi, apakah ini benar-benar golf kode atau kontes-popularitas?
l0b0
2
Sebagai saran lain, jika Anda ingin memberikan insentif baik kode pendek dan labirin yang rapi, Anda bisa menjadikannya tantangan kode dan menyatakan bahwa pemenang akan dipilih oleh beberapa skor yang merupakan campuran dari panjang kode dan upvotes - meskipun itu akan terserah Anda untuk menentukan setiap jawaban skor total, karena termasuk jumlah upvotes saat ini di posting agak tidak berguna.
Martin Ender
3
Saya pikir setiap jawaban harus menjelaskan apa yang merupakan pintu masuk dan keluar di masing-masing labirin (dan juga, apa itu dinding dan apa itu bagian), sehingga kita dapat mengevaluasi peluru ke-2.
LarsH
2
@ Geobits Saya tidak akan terlalu keberatan, tapi karena itu saran saya untuk membuatnya menjadi tantangan kode dengan skor gabungan dari panjang kode dan suara. Itu persis akan mendorong apa yang diinginkan OP: kode pendek untuk labirin yang menarik.
Martin Ender

Jawaban:

10

C: 265 253 Bytes

#define f(v)for(v=0;v<k;++v)
#define d(q,n)case q:r(c+n,c+2*n);
z[4225],i,j,k=65;r(p,c){if(!z[c]){z[p]=z[c]=1;f(p)switch(rand()%4){d(0,-k)d(1,k)d(2,-1)d(3,1)}}}main(){f(i)z[i]=z[i+4160]=z[i*k]=z[i*k+64]=z[4157]=1;r(67,132);f(i)f(j)putchar(33-z[i*k+j]);}

(Membutuhkan terminal 65 karakter) Menghasilkan labirin 31x31 yang relatif acak dengan satu jalur terjamin dari pintu masuk ke pintu keluar.

Contoh output (dengan terminal simulasi 65 karakter):

 ! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 
 !     !       !   !       !     !           !             !   ! 
 !!!!! !!! !!! ! !!! ! !!! ! !!! !!!!!!! !!! !!!!!!!!! !!! ! ! ! 
 !   !   !   ! !     ! ! ! ! ! ! !       !   !         !   ! ! ! 
 ! !!!!! !!! ! !!!!!!! ! ! ! ! ! ! !!!!!!! !!! ! !!!!!!! !!! ! ! 
 !     !     !         ! !   !   !     !   !   ! !     !   ! ! ! 
 ! !!! !!!!!!!!!!!!!!!!! !!!!! !!! !!! !!! ! ! !!! !!! !!! !!! ! 
 !   !         !     !   !     !     !   ! ! ! !     !   !   ! ! 
 !!!!!!!!!!! ! ! !!! !!! ! !!!!!!!!!!!!! ! !!! ! !!!!!!! !!! ! ! 
 !           !   !       ! !             !   !     !     !     ! 
 ! !!!!!!! !!!!!!! !!!!!!! ! !!!!!!!!!!!!!!! !!!!!!! !!!!!!!!!!! 
 ! !     ! !   !     !   ! !           !   !       ! !         ! 
 ! !!! ! ! ! ! !!!!!!! ! ! ! !!!!!!!!! ! ! !!!!!!! ! ! !!!!!!! ! 
 !   ! !   ! !       ! !   ! !         ! !       ! ! !   !   ! ! 
 !!! ! !!!!! !!!!!!! ! !!!!!!! !!!!!!!!! !!! !!!!! ! !!! ! !!! ! 
 !   !   ! ! !       !   !     !   !     ! !           ! !   ! ! 
 ! !!!!! ! ! ! !!!!!!!!! ! !!!!! !!! !!!!! !!!!!!!!!!! ! ! ! ! ! 
 ! !       ! !   !   !   ! !       ! !       !   !     ! ! ! ! ! 
 ! !!!!!!!!! !!! ! ! ! !!! !!!!!!! ! !!!!!!! ! ! !!!!!!! !!! ! ! 
 !             !   ! !   !       ! !     !   ! !             ! ! 
 !!!!!!!!!!!!!!!!!!! !!! !!!!!!! ! !!!!! ! !!! !!!!!!!!!!!!!!! ! 
 !               !   !   !       !         !   !     !   !     ! 
 ! !!!!!!!!!!!!! ! ! ! !!! !!!!!!! !!!!!!!!! !!! !!! !!! ! !!! ! 
 ! !   !       !   ! ! ! !     ! ! ! !     !     !   !   !   ! ! 
 ! ! ! !!!!! !!!!!!! ! ! ! !!! ! ! ! ! !!! !!!!!!! !!! !!!!! !!! 
 !   ! !   !       ! ! !     ! !     ! ! !     !   !       !   ! 
 !!!!! ! ! !!! !!! ! ! !!!!!!! !!!!!!! ! ! !!! ! !!!!!!!!! !!! ! 
 !     ! !   !   !   !       !       ! ! ! !   !   !         ! ! 
 ! !!!!! !!! !!! !!!!!!!!!!! !!!!!!! ! ! ! !!!!!!! ! !!!!!!! ! ! 
 !         ! !           !   !       ! ! !     !   ! !       ! ! 
 !!!!!!!!!!! !!!!!!!!!!! ! !!! !!!!!!! ! !!!!! ! !!! !!!!!!!!! ! 
 !         !     !     ! ! !       !   !     ! !     !         ! 
 ! !!!!!!! !!!!! ! !!! !!! !!!!!!! ! !!!!! ! ! !!!!! ! !!!!!!!!! 
 ! !     !     !   ! !   !       ! !       ! !       !         ! 
 ! ! !!! !!!!! ! !!! !!! !!!!!!! ! !!!!!!!!! !!!!!!!!!!!!!!!!! ! 
 !     !     ! !   !   ! !     ! !       !   ! !     !         ! 
 !!!!!!!!!!! ! !!! !!! ! ! ! !!! ! ! !!!!! !!! ! !!! ! !!!!!!! ! 
 !           ! !       !   ! !   ! !       !   ! ! ! !     !   ! 
 ! !!!!!!!!!!! !!!!!!!!!!!!! ! !!! !!!!!!!!!!! ! ! ! ! !!! ! !!! 
 !       !   !             ! ! ! !   !         ! !   !   ! ! ! ! 
 !!!!!!! !!! !!!!!!!!!!!!! ! ! ! !!! ! !!!!!!! ! !!! !!!!! ! ! ! 
 !       !         !     ! ! ! !   !   !     ! !   !       !   ! 
 ! !!!!!!! !!!!!!! ! !!!!! ! ! !!! !!!!!!! ! ! !!! !!!!!!!!!!!!! 
 !   !         ! !   !       ! !           ! !   !             ! 
 ! ! ! !!!!!!! ! ! !!! !!!!!!! ! !!!!!!!!!!! ! !!!!!!!!!!!!!!! ! 
 ! ! ! !     ! !   !   ! !     !   !   !     ! !               ! 
 ! ! !!! !!! ! !!!!! !!! ! !!!!! ! ! ! !!!!!!! ! !!!!!!!!!!!!! ! 
 ! !   !   ! !   !       !   !   !   !         ! !         !   ! 
 !!!!! !!! ! !!! ! !!!!!!!!! !!!!!!! !!!!!!!!!!! !!!!! !!!!! !!! 
 !     !   !   !   !       !       !       !   !     !       ! ! 
 ! !!!!! !!!!! !!!!! !!!!! !!!!!!! !!!!!!!!! ! !!!!! !!!!!!! ! ! 
 !           !     ! !   !   !   !           !   !   !     !   ! 
 ! !!!!!!!!! !!!!! ! !!! ! !!! ! !!!!!!!!!!!!!!! ! !!! !!! !!! ! 
 ! !     !       ! !     !     !     !         ! !       !   ! ! 
 !!! !!! !!!!!!!!! !!!!! !!!!!!!!! ! !!!!!!! !!! ! !!!!!!!!! ! ! 
 !   !     !   !   !   ! !       ! !         !   ! !         ! ! 
 ! !!!!!!! ! ! ! ! !!! ! !!!!!!! ! !!!!!!!!! ! !!!!! !!!!!!!!! ! 
 !       !   !   ! !   !         !   ! !   ! ! !     !       ! ! 
 ! !!!!! !!!!!!!!! ! !!!!!!!!!!! !!! ! ! ! ! ! ! !!!!! !!!!! ! ! 
 ! !     !           !         ! ! ! !   !   ! !   !   !     ! ! 
 ! ! !!!!!!!!!!!!!!!!! !!! !!!!! ! ! !!!!!!!!! !!! ! !!!!!!!!! ! 
 ! !                     !         !               !           ! 
 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ! 
Dendrobium
sumber
2
Anda bahkan tidak perlu int p,int c. p,csudah cukup ...
chubakueno
Ah, terima kasih sudah menunjukkannya
Dendrobium
34

Mathematica, 144 132 byte

Sejak awal, kita semua tahu cara paling efisien untuk menggambar labirin .

c=0;Graphics@Most[Join@@{Circle[{0,0},i,{a=c-(r=Random[](d=2Pi-1/i)&)[],a+d}],Line[{{i},{i+1}}.{{Cos[c=a+r[]],Sin@c}}]}~Table~{i,9}]

Output yang tidak digabungkan dan contoh:

masukkan deskripsi gambar di sini

Tentu saja, garis-garisnya adalah dinding. Anda adalah minotaur yang mulai di tengah dan harus keluar.

Martin Ender
sumber
4
Ini cantik, dan kodenya pendek, tetapi saya akan mengatakan itu menuju ujung "labirin sepele" dari spektrum.
LarsH
2
Anda benar bahwa membuatnya lebih besar tidak akan mengubah hal-hal sepele. Intinya adalah bahwa menyelesaikan labirin ini adalah proses linier: di setiap titik Anda dapat dengan cepat mengetahui apakah Anda telah mengambil jalan yang salah, tanpa harus "berulang" ke cabang yang lebih dalam. Sebaliknya, jawaban Ian dan aleph adalah labirin "nyata": mereka tidak dapat diselesaikan dengan cara linier ini. Karena labirin yang sepele tidak disarankan, saya akan tergoda untuk menurunkan suara yang satu ini, tetapi saya tidak memiliki cukup perwakilan.
LarsH
1
@ LarsH ya, kami sepakat tentang itu. Itu sebabnya saya mengatakan itu cara yang paling "efisien" untuk menggambar sebuah labirin, bukan yang paling "efektif". ;) Meski begitu, ini mungkin sederhana, tapi saya tidak berpikir itu termasuk dalam kategori dengan yang dikesampingkan seperti "kosong" atau "1x1". Tentu saja, atas kebijaksanaan OP untuk mendiskualifikasi pengajuan ini karena kesederhanaannya, tetapi selama dia tidak melakukan itu atau mengubah jenis tantangan, saya tidak melihat insentif untuk membuatnya lebih rumit / menarik.
Martin Ender
1
@ LarsH yang sedang berkata, saya tidak yakin apakah itu karena algoritma mereka atau hanya fitur dari contoh-contoh khusus yang mereka posting, tetapi tidak satu pun dari jawaban mereka yang diperlukan untuk mundur melampaui "1" lebih dari sekali. Jadi, meskipun mereka mengandung banyak kompleksitas, itu semua berada di jalur yang tidak relevan.
Martin Ender
1
Labirin ini tidak sepele, menurut saya, bahkan jika itu mudah (dan labirin melingkar saya di bawah ini bahkan lebih sepele). Saya benar-benar hanya ingin mencegah blank-canvas / size-1 / etc. "labirin".
imallett
33

C: 364 Bytes

#define I int
m[1600],i=0,r;f(I x,I y,I l){m[80*y+x]|=l;I d[]={x-1,y,2,1,x+1,y,1,2,x,y-1,8,4,x,y+1,4,8},
s[]={5,5,5,5},j=0;for(;j<4;){L:r=rand()%4;for(I k=0;k<4;)if(s[k++]==r)goto L;s[j]=r;I*p=d+
4*s[j++],X=p[0],Y=p[1];if(!(X<0|X>79|Y<0|Y>19|m[80*Y+X])){f(X,Y,p[2]);m[80*y+x]|=p[3];}}}
main(){f(0,0,4);m[9]|=4;for(;i<1600;)putchar("#5FMP<HJR;IK:9LN"[m[i++]]+128);}

Catatan: di atas, saya menambahkan baris baru agar pas di halaman. Output yang diharapkan (pada terminal 80 karakter) (mulai catatan dan berakhir di kiri atas): masukkan deskripsi gambar di sini

Imallett
sumber
8
@ bwoebi MSPaint untuk menyelamatkan! IMAGE
Ceiling Gecko
6
Perhatikan bahwa maksud saya adalah agar jalan berada di dalam pipa (seperti di sini) .
imallett
1
@IanMallett Saya pikir Ceiling Gecko menyadari hal itu, tetapi mengisi dinding kiri dengan warna memberi Anda jalan (tidak optimal) mengikuti sepanjang dinding kiri sampai Anda menemukan pintu keluar. ;)
Martin Ender
1
Saya akan tertarik melihat versi un-golfed dari kode ini, jika Anda punya waktu.
LarsH
4
Saat Anda menulis ini, Anda adalah pembuat kode-maze-ing.
totymedli
24

Mathematica, 134 130 karakter

Graph[Range@273,Reap[Do[c@n/._c:>#0[Sow[#<->n];n],{n,RandomSample@AdjacencyList[g=GridGraph@{13,21},c@#=#]}]&@1][[2,1]],Options@g]

labirin


Faktanya, kita dapat menggunakan algoritma ini untuk menghasilkan labirin dari grafik apa pun (tidak terarah).

Misalnya, hasilkan labirin dari grafik tur ksatria 8 * 8 ( KnightTourGraph[8,8]):

grafik tur knight

Graph[Range@64,Reap[Do[c@n/._c:>#0[Sow[#<->n];n],{n,RandomSample@AdjacencyList[g=KnightTourGraph[8,8],c@#=#]}]&@1][[2,1]],Options@g]

maze2

alephalpha
sumber
7
Labirin yang bagus ... tapi saya tidak melihat pintu masuk yang terhubung ke pintu keluar ...?
bwoebi
9
Saya percaya idenya adalah untuk memilih simpul acak (katakanlah, kiri atas) sebagai pintu masuk dan yang lain (kanan bawah) sebagai pintu keluar. Mathematica memastikan semua node terhubung dengan semua node lain, tetapi - terutama di labirin kedua - menemukan bagaimana mereka terhubung adalah bagian yang lebih sulit.
EagleV_Attnam
Apakah garis-garis (tepi grafik) seharusnya adalah dinding labirin, atau lorong? Saya pikir saya tahu, tetapi sekarang saya tidak yakin.
LarsH
@ LarsH Mereka adalah bagian.
alephalpha
1
@ LarsH Grafik terhubung, sehingga Anda hanya dapat mengambil dua node sembarang, satu sebagai pintu masuk, yang lain sebagai keluar.
alephalpha
13

Bash, 53 byte

w=(╱ ╲);while true;do echo -n ${w[RANDOM%2]};done

Ide yang mirip dengan kode C64. Menggunakan karakter Unicode sebagai garis miring karena terlihat jauh lebih bagus di terminal yang mendukung Unicode. Contoh keluaran pada Terminal OS X (font Menlo):

Contoh hasil labirin

nneonneo
sumber
2
Saya pernah tahu ini: yes 'c=(╱ ╲);printf ${c[RANDOM%2]}'|bash. Lihat posting ini
gniourf_gniourf
5
Ini didasarkan pada algoritma yang tidak dapat menjamin dirinya dapat dipecahkan, yang sudah berumur bertahun-tahun.
Isiah Meadows
9

JavaScript (ES6), 174

Ini adalah pembangun labirin yang saya gunakan dalam tantangan lain ini , hanya bermain golf. Ini adalah fungsi dengan 2 parameter: baris dan kolom. Labirin benar-benar terhubung tanpa loop, sehingga lokasi mana pun bisa menjadi titik awal atau akhir.

(r,c,o=2*c+2,i=2*r*o+o,z=[],F=(p,i=Math.random()*4)=>[o,1,-o,-1].map((s,j,d)=>z[s=p+2*d[j+i&3]]>0&&(z[s]=z[(p+s)/2]=' ',F(s))))=>{for(;i--;)z[i]=i%o?8:`\n`;F(o+2);return''+z}

Contoh

f(7,10)

Keluaran

,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
,8, , , ,8, , , , , ,8, , , , , , , , , ,8,
,8, ,8, ,8,8,8, ,8, ,8,8,8,8,8,8,8, ,8, ,8,
,8, , , ,8, , , ,8, , , ,8, , , , , ,8, ,8,
,8, ,8,8,8, ,8,8,8,8,8, ,8, ,8,8,8,8,8, ,8,
,8, ,8, , , , , ,8, ,8, ,8, ,8, , , , , ,8,
,8, ,8, ,8,8,8, ,8, ,8, ,8, ,8, ,8,8,8,8,8,
,8, ,8, ,8, , , ,8, , , , , ,8, ,8, , , ,8,
,8, ,8, ,8, ,8,8,8,8,8,8,8,8,8, ,8, ,8,8,8,
,8, ,8, ,8, , , , , , , ,8, , , ,8, , , ,8,
,8, ,8, ,8,8,8,8,8,8,8, ,8,8,8, ,8,8,8, ,8,
,8, ,8, , , , , , , ,8, , , ,8, , , , , ,8,
,8, ,8,8,8,8,8,8,8,8,8,8,8, ,8,8,8,8,8, ,8,
,8, , , , , , , , , , , , , ,8, , , , , ,8,
,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8

Uji

f=
(r,c,o=2*c+2,i=2*r*o+o,z=[],F=(p,i=Math.random()*4)=>[o,1,-o,-1].map((s,j,d)=>z[s=p+2*d[j+i&3]]>0&&(z[s]=z[(p+s)/2]=' ',F(s))))=>{for(;i--;)z[i]=i%o?8:`\n`;F(o+2);return''+z}
    
function update() {    
  O.textContent='';
  [r,c]=I.value.match(/\d+/g)
  O.textContent=f(r,c)
}  

update()
pre { line-height: 0.8em }
Rows,Columns <input id=I oninput='update()' value='8,12'>
<pre id=O></pre>

edc65
sumber
Saya tidak yakin ... apakah daerah terang atau gelap adalah labirin? Jika gelap, maka ia memiliki lingkaran besar dan satu hanya bisa tetap di luar ketika memilih titik sebagai titik masuk / keluar. Jika menyala, maka Anda harus menambahkan pintu keluar / masuk.
Paŭlo Ebermann
1
@ PaŭloEbermann itu adalah terang tentu saja, area gelap adalah dinding. Mengulangi diri saya: Labirin benar-benar terhubung tanpa loop, sehingga lokasi mana pun bisa menjadi titik awal atau akhir
edc65
Wow, ini membingungkan! Mencukur beberapa byte dan menurunkannya menjadi 133 byte: twitter.com/aemkei/status/889587308894326785 Tetapi semua kredit harus diberikan kepada Anda!
aemkei
@aemkei 8 bukannya '#', saya tidak percaya saya melewatkannya tepat waktu
edc65
8

ZX Basic - 54 karakter

a$="/\":for i=1 to 24*32:print a$(1+int(rnd*2));:next

Keluaran

Inilah labirin yang menunjukkan rute melaluinya (spasi antar garis)

jalan

dan potongan kecil dari saat saya pertama kali melakukan ini (beberapa tahun yang lalu), dan menghabiskan sedikit waktu melakukan grafis yang lebih baik.

grafis yang lebih baik

Brian
sumber
2
Hm, kurang ajar. ^^ Apa awal dan akhir apa di sana? Dan apakah garis miring jalan atau dinding? Dan berapa ukuran celah minimum yang bisa saya lewati?
Martin Ender
2
"Seharusnya ada setidaknya satu jalur dari setidaknya satu pintu masuk ke setidaknya satu pintu keluar." Saya tidak melihat indikasi bahwa kriteria ini dipenuhi. Dinding acak tidak harus membuat labirin.
LarsH
1
@ m.buettner: Saya menduga bahwa garis miring adalah dinding, dan kita seharusnya memvisualisasikannya seolah-olah tidak ada spasi di antara baris, dan di antara kolom. Jadi karakter 2x2 kiri bawah membentuk bentuk berlian (persegi) yang benar-benar tertutup.
LarsH
@ LarsH ya saya pikir begitu. Itu hanya membuat poin lain untuk kasus Anda pada pertanyaan OP bahwa orang harus menunjukkan apa yang memulai dan menyelesaikan. Juga, skema ini bahkan tidak memungkinkan untuk persimpangan. Anda hanya dapat memiliki kuadrat tertutup atau jalur berkelok-kelok (yang mungkin juga merupakan loop tertutup).
Martin Ender
+1 untuk grafik yang ditingkatkan dan menunjukkan rute. Saya kira mengingat begitu banyak pintu masuk dan keluar potensial, kemungkinan memiliki "setidaknya satu jalur dari setidaknya satu pintu masuk ke setidaknya satu pintu keluar" cukup tinggi!
LarsH
8

BBC BASIC, 18 Bytes

Peningkatan panjang pada 23-byte versi C64 infinite loop oleh @nneonneo. VDU mengirimkan satu karakter ke pengontrol VDU: baik 2 + 1 * 45 = ASCII 47 /atau 2 + 2 * 45 = ASCII 92\

  VDU2+RND(2)*45:RUN

BBC BASIC, 35 Bytes / 107 95 Bytes

35 byte hanya untuk baris terakhir, yang memberikan labirin 25 baris dalam tata letak 40 kolom. MODE1 memastikan bahwa tidak ada ruang ekstra yang tersisa di antara garis. Sisa dari program ini adalah opsional dan meningkatkan format. Pernyataan VDU23 mendefinisikan kembali font untuk karakter 47 dan 92 (8 byte yang membentuk bitmap 8x8). Saya menyertakan pixel cahaya di keempat sudut untuk menghentikan lari lurus agar tidak terjepit. Efek sampingnya adalah titik muncul di berlian kosong. Total 107 byte termasuk 2 baris baru.

  VDU23,47,131,7,14,28,56,112,224,193
  VDU23,92,193,224,112,56,28,14,7,131
  MODE9FORa=0TO999VDU2+RND(2)*45:NEXT

Edit program ini dapat disingkat menjadi 95 byte dengan menyandikan beberapa kode VDU 8 bit menjadi 16 bit nilai endian kecil (dilambangkan dengan tanda titik koma alih-alih koma) dan mewakili pernyataan MODE sebagai pasangan kode VDU, sebagai berikut .

VDU23,47,1923;7182;28728;49632;23,92,57537;14448;3612;33543;22,9:FORa=0TO999VDU2+RND(2)*45:NEXT

Keluaran

Menggunakan BBC Basic untuk Windows dari bbcbasic.co.uk

Baris terakhir saja, 35 byte

masukkan deskripsi gambar di sini

Seluruh program, 107 95 byte

Saat saya mengomentari jawaban @ Brian, garis miring membagi persegi menjadi 2 segitiga gelap, yang masing-masing memiliki tepat 2 pintu masuk / keluar. Ini menjamin jalur (sepele, tidak bercabang) dari titik mana pun di tepi labirin ke titik lain di tepi labirin. Banyak dari ini sangat pendek, tetapi selalu ada beberapa yang panjang. Tentu saja, di tengah-tengah labirin ada juga beberapa loop.

Karena jawaban lain belum menyebutkannya, saya ingin memperhatikan dengan baik area terang. Ini dibatasi oleh area gelap, oleh karena itu sebagai akibat wajar dari pernyataan yang dibuat di atas, area terang yang dibatasi secara eksternal oleh N area gelap menyentuh tepi bidang pada titik N (persis sama banyak). Oleh karena itu beberapa daerah cahaya yang cukup besar terjadi, dan ini membentuk labirin yang menarik dan bercabang.

Pada contoh di bawah ini, Anda dapat melihat output mentah (monokrom) dari program saya. Di bawah itu (menggunakan Windows Paint) saya telah mewarnai dua area gelap terpanjang dengan warna biru. Lalu aku mewarnai area cahaya terbesar dengan warna kuning, dan dua area yang dibatasi oleh warna biru merah dan hijau. Labirin kuning, hijau (dan bahkan merah) cukup menarik dan tidak suram.

masukkan deskripsi gambar di sini

EDIT - Memilih labirin secara otomatis dan pemilihan awal / akhir

Untuk satu baris lagi (59 karakter) program dapat secara otomatis memilih hingga 6 labirin dengan memilih kotak secara acak dan mengisi warna merah, hijau, kuning, biru, magenta, dan cyan. Itu tidak selalu menemukan 6 penuh, karena jika mengambil kuadrat acak yang sudah diwarnai tidak melakukan apa-apa.

Sisa kode di bawah ini memilih awal untuk setiap warna dengan memindai setiap kolom dari atas ke bawah dan kiri ke kanan, dan memilih kotak pertama yang ditemui. Ini mengambil akhir dengan memindai ke arah yang berlawanan.

Ini menghasilkan satu set labirin berwarna-warni yang saling terkait. Kadang-kadang mereka begitu terjalin sehingga labirin harus menyeberang di suatu tempat. Tapi tentu saja, mereka tidak melakukannya!

Kode dan hasil tambahan 59 + 187 = 246 karakter tambahan yang akan ditambahkan ke akhir program asli (untuk peningkatan di luar spesifikasi pertanyaan.)

  GCOL135FORa=1TO6GCOLa FILLRND(40)*32-16,RND(25)*32+208:NEXT   :REM set background to grey so fill can identify. For each colour 1 to 6, pick a point in the centre of a character and flood fill (characters are logically 32x32 although they are physically only 8x8 pixels.)
  f=126:g=126                                                   :REM flags 1111110 to indicate which starts and ends have not been allocated yet
  FORx=0TO39FORy=0TO24                                          :REM maze is 40x25. There is some blank space at the bottom of the screen (32 rows total)
  p=POINT(x*32+16,1008-y*32)                                    :REM check start point. Text origin is at top of screen, Graphics origin is at bottom, 1280x1024 logical. therefore y offset is 1024-32/2=1008.
  IFf AND2^p f=f-2^p:VDU31,x,y,17,p,79                          :REM if start for colour P has not been allocated yet, allocate it now. VDU31,X,Y go to that square. VDU 17,p select text colour. VDU 79 print an "O"                 
  p=POINT(1264-x*32,240+y*32)                                   :REM check end point
  IFg AND2^p g=g-2^p:VDU31,39-x,24-y,17,p,79                    :REM if end for colour P has not been allocated yet, allocate it now.
  NEXT:NEXT
  VDU31;26                                                      :REM get the cursor off the board. Move to (0,26). Semicolon used instead of comma here indicating that 31 is a 16 bit small endian value, equivalent to VDU31,0,26 or PRINTTAB(0,26)

masukkan deskripsi gambar di sini

Level River St
sumber
7

C: 235 Bytes

#define P(X,Y)M[(Y+40)*80+X+40]=rand()%49/6;
#define B(X,Y)P(X,Y)P(Y,X)
M[6400],r,i;main(){for(i=0;i<40;i+=2){int x=i,y=0,e=1-x;while(x>=y)
{B(x,y)B(-x,y)B(-x,-y)B(x,-y)++y;e+=e<0?2*y+1:2*(y-x--);}}for(i=0;
i<6400;)putchar(64>>!M[i++]);}

Catatan: di atas, saya menambahkan baris baru agar pas di halaman. Output yang diharapkan (pada terminal 80 karakter):masukkan deskripsi gambar di sini

Saya menyesal ini bukan labirin yang sangat sulit (pada kenyataannya, tidak diperlukan backtracking ke cincin bagian dalam (dan Anda harus dapat menemukan jalur dari perimeter ke pusat secara sepele). Namun, ia memiliki implementasi lingkaran Bresenham yang bagus. algoritma menggambar pada intinya.

Imallett
sumber
Agak sulit untuk melihat di mana Anda bisa melewati dan di mana Anda tidak bisa. Saya harus mengatakan, saya lebih suka pipa;) (untuk ini dan pengiriman melingkar saya).
Martin Ender
@ m.buettner: Saya sebenarnya setuju. Jika Anda mengubah i+=2ke i+=3, mungkin lebih jelas apa yang terjadi.
imallett
6

Saya membantu anak saya untuk melakukan ini, untuk belajar sedikit pemrograman: http://jsfiddle.net/fs2000/4KLUC/34/ bagaimana Anda menyukainya?

Giuseppe Strafforello
sumber
17
Jika Anda dapat memasukkan kode Anda ke dalam pos, lakukan itu. Juga, sertakan tajuk seperti #Language (s) - Bytecount. Jika Anda hanya menggunakan karakter ASCII dalam kode Anda, Anda bisa mendapatkan bytecount yang bagus di sini . Ringkasan tentang apa yang kode Anda lakukan, wawasan apa pun yang Anda miliki, atau hal-hal cerdas yang Anda lakukan mungkin merupakan tambahan yang bagus untuk posting Anda. Ngomong-ngomong, Darth Vader membuatnya sangat sulit untuk melihat beberapa garis. Akhirnya, Selamat Datang di Golf Code!
Rainbolt
Anda belajar sedikit pemrograman dengan anak-anak Anda dan saya belajar sedikit bermain golf. Ini golf pertama saya dan hasilnya masih agak lama. Jumlah byte: Asli: 55 + 6822 = 6877. Agak direorganisasi : 39 + 3131 = 3170 Golf : 39 + 1593 = 1632
BartekChom
6

Commodore 64 BASIC - 38 byte

10 PRINT CHR$(205.5+RND(1)); : GOTO 10

Ini bukan penemuan saya, saya hanya mengulangi program yang sangat indah dan singkat dari masa lalu. Bahkan, ada seluruh buku yang dinamai 10 PRINT CHR$(205.5+RND(1)); : GOTO 10merayakan potongan kode ini!

Anda dapat melihat output di video YouTube ini ; inilah screencap:

Screencap YouTube

Di sini, di pertanyaan StackOverflow ini adalah implementasi lebih lanjut dari program maze-generator ini. Implementasi terpendek dari program ini adalah program BASIC C64 23-byte berikut yang diposting oleh penulis pertanyaan itu:

1?cH(109.5+rN(1));:gO1

di mana huruf kecil dimasukkan apa adanya, dan huruf besar dimasukkan menggunakan tombol Shift (ini memiliki penampilan yang berbeda pada layar C64 yang sebenarnya).

nneonneo
sumber
Bukankah ini persis sama dengan pengajuan Brian? (hanya sedikit lebih pendek) Dan begitu juga jawaban Bash Anda? Maka pertanyaannya di sini adalah, apakah labirin tanpa persimpangan masih merupakan labirin?
Martin Ender
nneonneo, +1 untuk atribusi yang tepat dan jujur ​​dari ide hebat ini. @ m.buettner Area yang belum dicetak menghasilkan labirin yang tidak bercabang seperti yang Anda tunjukkan. Namun (dan saya terkejut belum ada orang yang menunjukkan ini) area cetak membentuk beberapa labirin yang menarik, non-sepele, bercabang (lihat jawaban saya.) Saya juga memperbaiki labirin Anda karena memiliki awal dan akhir yang ditentukan terbaik . Menentukan awal dan akhir pada labirin diagonal ini tidak mudah.
Level River St
@ m.buettner 1. Biner x86 hanya berukuran 10 byte. 2. Ini adalah algoritma yang diasah dengan baik, dan sama sekali tidak asli, juga tidak dimaksudkan untuk membuat labirin yang dapat dipecahkan.
Isiah Meadows
5

Jawa: 700

Inilah penambah dinding rekursif. Algoritme diuraikan di situs ini :

public class Z{int i,j,u=20,v=u,g[][]=new int[v][u];public static void main(String[]a){new Z().d(0,0,20,20,0).p();}int q(int m){return(int)(Math.random()*m);}<T>void z(T m){System.out.print(m);}void p(){for(i=0;i++<u*2;z("_"));for(i=0;i<v;i++){z("\n|");for(j=0;j<u;j++){boolean b=i+2>v,s=g[i][j]%2>0||b;z(s?"_":" ");z(g[i][j]>1||j+2>u?"|":s&(j+1<u&&g[i][j+1]%2>0||b)?"_":" ");}}}Z d(int x,int y,int w,int h,int o){int a=x,b=y,c=a,d=b,e,f;boolean t=o<1;if(t){b+=q(h-2);c+=q(w);}else{a+=q(w-2);d+=q(h);}for(i=t?w:h;i-->0;j=t?a++:b++)if(a!=c&&b!=d)g[b][a]|=t?1:2;e=t?w:a-x+1;f=t?b-y+1:h;if(e>2&&f>2)d(x,y,e,f,e<f?0:1);e=t?w:x+w-a-1;f=t?y+h-b-1:h;if(e>2&&f>2)d(t?x:a+1,t?b+1:y,e,f,e<f?0:1);return this;}}

Pada dasarnya, ia membagi masing-masing persegi panjang menjadi dua dengan dinding (dan bagian), kemudian membelah mereka menjadi dua, dll. Ini menghasilkan labirin yang "sempurna" - satu tanpa siklus - yang memiliki jalur dari setiap titik ke setiap titik lainnya. Banyak jalan buntu, jadi itu bukan "sepele" dalam arti untuk labirin yang lebih besar.

Jadi, pintu masuk dan keluar bisa diputuskan dengan sewenang-wenang. Jika saya harus memilih satu, itu hanya akan mengatakan atas / kiri dan bawah / kanan.

Ini digambar dalam ascii lebar-ganda, jadi ide yang bagus untuk menyalurkan output ke file jika Anda melakukan salah satu dari ukuran apa pun. Inilah konsol 20x20:

20x20

Dan 100x100 di notepad ++ (saya harus memperkecil untuk mendapatkan semua, jadi agak ... kecil ):

100x100

Kode dengan jeda baris:

public class Z{
    int i,j,u=20,v=u,g[][]=new int[v][u];
    public static void main(String[]a){
        new Z().d(0,0,20,20,0).p();
    }

    int q(int m){return(int)(Math.random()*m);}
    <T>void z(T m){System.out.print(m);}

    void p(){
        for(i=0;i++<u*2;z("_"));
        for(i=0;i<v;i++){
            z("\n|");
            for(j=0;j<u;j++){
                boolean b=i+2>v,s=g[i][j]%2>0||b;
                z(s?"_":" ");
                z(g[i][j]>1||j+2>u?"|":s&(j+1<u&&g[i][j+1]%2>0||b)?"_":" ");
            }
        }
    }

    Z d(int x,int y,int w,int h,int o){
        int a=x,b=y,c=a,d=b,e,f;
        boolean t=o<1;
        if(t){
            b+=q(h-2);
            c+=q(w);
            }
        else{
            a+=q(w-2);
            d+=q(h);
        }

        for(i=t?w:h;i-->0;j=t?a++:b++)
            if(a!=c&&b!=d)
                g[b][a]|=t?1:2;

        e=t?w:a-x+1;f=t?b-y+1:h;
        if(e>2&&f>2)d(x,y,e,f,e<f?0:1);
        e=t?w:x+w-a-1;f=t?y+h-b-1:h;
        if(e>2&&f>2)d(t?x:a+1,t?b+1:y,e,f,e<f?0:1);
        return this;
    }
}
Geobit
sumber
2

ZX Basic - 281 karakter

Ini lebih merupakan labirin yang "tepat", lebih sedikit golf, tetapi lebih simpang siur. Algoritma Binary maze disebut, setiap sel dapat memiliki jalan keluar turun atau kanan, tetapi tidak keduanya. (Sekarang termasuk Mulai ditandai "S" dan Akhir "E", untuk mencegah hanya lurus di satu sisi).

"::" adalah cara ZXB memasukkan karakter grafik Spectrum ke file teks, sama dengan karakter blok yang dijual.

randomize:border 1:paper 1:ink 6:cls
for x=0 to 30 step 2
 for y=0 to 20 step 2
  r=1+int(rnd*2)
  if x=30 and r=1 then 
   r=2
  end if
  if y=20 and r=2 then
   r=1
  end if
  print at y,x;"\::"
  print at y+(r=2),x+(r=1);"\::"
 next
next
print inverse 1;at 0,0;"S";at 20,31;"E"

Labirin

Brian
sumber
2
Tidak, sebenarnya saya maksudkan bahwa Anda harus menukar awal dan akhir (mulai kanan bawah, ujung kiri atas). Seperti itu berdiri sepele, karena karena aturan Anda hanya harus turun dan benar sepanjang waktu untuk mencapai akhir.
Martin Ender
1
Bahkan jika awal dan akhir dibalik, labirin memiliki properti (mungkin menarik) bahwa jalan yang benar hanya akan bergerak ke atas dan ke kiri. Labirin tidak sepele lagi, karena ada banyak titik di mana Anda bisa pergi salah satu dari dua cara.
Kevin - mengembalikan Monica
1

C- 244

#include <unistd.h>
#include <windows.h>
int main(i,j,rv,rs){srand( time(0));for (i = 0; i < 80; i++)for (j = 0; j <50 ; j++){rv = rand() %10;rs = rand() %100;if(rs < 10 || rs  > 90)continue;if(rv<4){gotoxy(i,j);printf("%c", '#');}}return 0;}

Berikut ini tampilannya:

Labirin

Catatan: solusi ini terinspirasi oleh level game 8 yang tidak dipercaya : ke dalam hutan.

Mhmd
sumber