Cetak labirin acak

19

Tulis program yang menghasilkan dan mencetak labirin acak menggunakan algoritma pilihan Anda. Labirin harus berbeda untuk beberapa kali program dijalankan. Tinggi dan lebar diberikan sebagai argumen baris perintah. Gunakan |untuk dinding vertikal, -untuk dinding horizontal dan +untuk sudut. Labirin dibatasi oleh dinding dan pintu masuk ditandai oleh dinding yang hilang. Labirin berisi harta karun #yang harus bisa dijangkau dari setidaknya satu pintu masuk.

$ python2 random-maze.py 4 5
+-+-+
  |#|
|   |
+---+
Alexandru
sumber
+1 Pertanyaan Hebat. Beberapa poin. 1: Bagaimana jalan keluar ditandai? Apakah ini simbol seperti *atau ada dua pintu masuk yang terpisah? 2: Anda mungkin harus menentukan bahwa pintu keluar harus dapat dijangkau.
snmcdonald
1
@ snmcdonald: ayo bersenang-senang dan tambahkan harta :).
Alexandru
2
Saya bisa melihat tindak lanjut golf, tentang menyelesaikannya ... :)
st0le
@ st0le: Saya sudah punya beberapa ide. Kirimi saya email jika Anda ingin berdiskusi.
Alexandru
1
Jenis puzzle tidak ditentukan di sini. Saya melihat bahwa orang-orang menjawabnya seolah-olah [kode-golf]. Apakah itu maksudnya? Jika demikian, harap beri tag seperti itu?
dmckee

Jawaban:

5

Saya pikir ini secara teknis bukan generator labirin, tetapi menciptakan hasil seperti labirin: https://gist.github.com/803450 .

Beberapa kode mengerikan di sana saya tahu, dan itu hanya berfungsi kurang dari separuh waktu, dan hasilnya tidak terlihat tepat untuk dilakukan dengan dinding yang mencuat dari dinding lain. Tapi itu cukup dekat sehingga saya tidak bisa repot memperbaiki sisanya.

Beberapa contoh keluaran:

→ ruby random-maze.rb 30 30
+----+-+-----------++-+----+
|    + |           ++ |    |
++  +  | ++ ++   +    + ++ ++
|  ++ ++ |  |    +---+  +   |
| +      | +| +   +++  +  + |
|   +   +| +| +-+  |   + +  |
|        +  +    + + ++  |+ |
| + ++ +  ++   + |  +   ++| |
| |  | ++  + +----+ + +-+ | |
| +  |  +-+  |+        |  | |
|   +-+  +| ++  ++ + + |  | |
| ++   +  + |  ++|   + | ++ |
|  + + + +  +---++-+   +++  |
| +  |  +| +    |  ++   |   |
| | +++ +| + ++ +--+  + |---+
|#+ | |  |   +++     +  +   |
++  | ++ +-+  ++ +--+  +  + |
|  ++  |    +     ++| +  ++ |
| ++   +--------+  +| + +   |
| |     |      +++  |  +  +-+
| |     | +--+  |++ |+ | ++
| |     |  +--+ | | || |  |
| |     +-+     +-+ |+ |+ |
| | +---+   ++      +  |  |
| +-|     +    +      ++ ++
|   +       ++   +---+   |
|              ++   +  +-+
|                 +   ++
+-+ +-------------+---+
Nemo157
sumber
1
Ide bagus. Poin tambahan jika Anda memperbaikinya;)
Alexandru
Ini hanya rip cepat dan perubahan output untuk algoritma yang saya gunakan untuk menghasilkan labirin untuk salah satu tugas uni saya . Algoritma yang sebenarnya sebagian besar dicuri dari posting blog oleh CHEVYRAY . Saya mungkin akan memperbaikinya akhir pekan ini, saya tidak yakin apakah format output sepenuhnya akan bekerja karena itu bukan labirin yang benar, tapi saya akan mencoba dan sedekat mungkin sambil terlihat bagus.
Nemo157
Sepertinya labirin yang sangat baik bagi saya.
Alexandru
8

Python, 375 karakter

import random,sys
H,V=map(int,sys.argv[1:])
H-=1
V-=1
b,h,v,p=' -|+'
M=H/2*h
n=random.randint(1,(H/2)*(V/2-1))
for i in range(V/2):
 e=s=t='';N=v
 for j in range(H/2):
  if i and(random.randint(0,1)or j==0):s+=N+b;t+=v;N=v;M=M[1:]+p
  else:s+=M[0]+h;t+=b;N=p;M=M[1:]+h
  n-=1;t+=' #'[n==0]
 if H&1:s+=s[-1];t+=b;e=h
 print s+N+'\n'+t+v
if V&1:print t+v
print h.join(M)+e+h+p

Ini menghasilkan labirin dengan satu pintu masuk dan harta karun yang ditempatkan secara acak. Labirin adalah labirin pohon biner sederhana .

$ ./maze.py 15 15
--------------+
              |
| | ----------+
| |           |
| +-----+ | --+
|       | |   |
| --+ --+ +---+
|   |   |     |
| --+-+ +---+ |
|     |     | |
| --+ +-+ --+ |
|   |   |   |#|
| | | --+ --+-+
| | |   |     |
+-+-+---+-----+
Keith Randall
sumber
Mungkin memang dimaksudkan, tetapi baris atas (tepat di bawah dinding) selalu merupakan koridor yang panjang.
Alexandru
Ya, dan kolom paling kiri selalu merupakan koridor yang panjang juga. Ini adalah properti dari jenis labirin yang saya hasilkan.
Keith Randall
Oh Labirin sangat bagus :).
Alexandru
6

Ruby 1.9.2p136: 90

eval ARGV[0]
z=[l="+"+"-"*@w+"+"]
@h.times{z<<"|"+" "*@w+"|"}
z[rand(@h)+1]="|#"
puts z<<l

Keluaran

$> ruby maze.rb "@h=8;@w=8;"

+------+
|      |
|      |
|      |
|      |
|#
|      |
+------+

Hei, tidak ada yang mengatakan itu harus labirin yang bagus . OKE, OKE, aku akan membuat yang asli sekarang.


sumber
Bagus, tapi pastikan protokol itu menghormati (tinggi dan lebar dari baris perintah, maze dicetak ke stdout).
Alexandru
Sebenarnya ia tidak mengatakan apa-apa tentang stdout (itu juga bukan ketentuan yang masuk akal karena seseorang mungkin menggunakan bahasa yang tidak mencetak ke stdout) dan sudah umum diterima bahwa input adalah untuk fungsi / metode. Untuk orang yang memilih ini, itu memecahkan masalah seperti yang ditentukan jadi jangan membenci mazer membenci labirin.
Tidak terlalu lama seperti yang ditentukan dalam pertanyaan. Lihat meta.codegolf.stackexchange.com/questions/13/… . Selain itu, tidak seperti JavaScript Ruby mendukung pembacaan argumen dan penulisan ke output standar. Solusi Anda curang dibandingkan dengan orang lain yang memecahkan masalah dengan cara yang benar.
Alexandru
Tidak bisa mengedit Maksud saya 'tidak lengkap' bukan 'curang'. Saya suka ide labirin.
Alexandru
Kemudian bahasa lain harus menyertakan kode yang diperlukan untuk memanggil mereka atau memasukkan #!/usr/bin/env python, misalnya, dalam kode mereka. Seperti yang saya katakan saya akan menulis solusi nyata juga, ini hanya menunjukkan kualitas buruk dari pertanyaan itu sendiri (dan banyak lainnya) dan menunjukkan kita perlu memiliki pedoman yang lebih baik. Dan akhirnya menunjuk ke sebuah pertanyaan tidak membuat jawaban atas pertanyaan aturan sebenarnya untuk situs tersebut. Tapi baiklah, ini versi barumu ...
3

C 844

#include <stdlib.h>
#include <time.h>
h,w,*m,y,x,z;d(t,b,l,r){int i=b-t,j=r-l;if(i>1&&j>1){i=(rand()%--i)|1;j=(rand()%--j)|1;z=rand()%4;x=rand()%i+t;x|=1;for(y=t;y<i+t;y++)if(y!=x||!z)m[y*w+j+l]=124;x=rand()%(b-i-t)+i+t;x|=1;for(y=t+i;y<b+1;y++)if(y!=x||!(z-1))m[y*w+j+l]=124;y=rand()%j+l;y|=1;for(x=l;x<j+l;x++)if(y!=x||!(z-2))m[(i+t)*w+x]=45;y=rand()%(r-j-l)+j+l;y|=1;for(x=l+j;x<r+1;x++)if(y!=x||!(z-3))m[(i+t)*w+x]=45;m[(i+t)*w+j+l]=43;m[(t-1)*w+l+j]=43;m[(b+1)*w+j+l]=43;m[(i+t)*w+l-1]=43;m[(i+t)*w+r+1]=43;d(t,t+i-1,l,l+j-1);d(t+i+1,b,l,l+j-1);d(t,t+i-1,l+j+1,r);d(t+i+1,b,l+j+1,r);}}main(int c,char**v){h=atoi(v[1]),w=atoi(v[2]),m=calloc(h*w,4);srand(time(0));while(y<h){while(x<w){m[y*h+x]=(!y||y==h-1)?(!x||x==w-1)?43:45:(!x||x==w-1)?124:32;x++;}y++;x=0;}d(1,h-2,1,w-2);z=rand()%(w-2);z|=1;m[z]=32;z=rand()%(w-2);z|=1;m[h*(w-2)+z]=35;}

Untuk mengetes:

#include <stdio.h>//beginning
for(y=0;y<h;y++){for(x=0;x<w;x++){putchar(m[y*h+x]);}putchar('\n');}getchar();//end

3x3

+ +
| # |
+ - +

7x8

+ - + - - +
| |
+ + - + - +
| |
| + - + - +
| | # |
+ - + - + - +

18x20

+ - + - + + --- + --- + - + - +
| | | | |
| + + + - + --- + + - +
| | | |
+ + + - + --- + - + - + - +
| | | |
+ - + + - + - + - + --- + - + - +
| | | | | |
| + + + + - + - - + |
| | | | |
| | | + - + - + ---- + |
| | | | |
+ + + - + - + - + - - + - +
| | | | |
| + + - + - + - - + |
| | | | |
| | | | # | | |
+ - + - + - + --- + ----- + - +
snmcdonald
sumber
Ini adalah tantangan kode , bukan golf kode . Mengapa kodenya sulit dibaca?
Braden Best
-1. Tidak hanya kode ini dikaburkan, tetapi tidak ada instruksi yang jelas tentang bagaimana ini harus dikompilasi, dan bagaimana dua blok kode harus diimplementasikan. Instruksi penggunaan jarang, jika tidak sepenuhnya hilang. Jelas bahwa jawaban Anda adalah kode-golf. Tapi pertanyaannya bukan . Jadi kodenya harus dapat dibaca, dan mandiri untuk memudahkan penyalinan / tempel / kompilasi, sehingga orang lain dapat memverifikasi bahwa itu memang berfungsi tanpa harus menguraikan bagaimana Anda membuat kode bekerja di tempat pertama.
Braden Best
0

Inilah solusi java sederhana:

import java.util.*;

public class MazeGen {
    public static void main(String[]a){
        int w,l;
        Random rand=new Random(System.currentTimeMillis()%1000+System.nanoTime());
        if(a.length==2){
            w=Integer.parseInt(a[0]);
            l=Integer.parseInt(a[1]);
        }else{
            System.out.println("No command line arguments, taking from STDIN.");
            Scanner input=new Scanner(System.in);
            w=input.nextInt();
            l=input.nextInt();
            input.close();
        }
        char[][]maze=new char[w][l];
        for(int x=0;x<w;x++){
            for(int y=0;y<l;y++){
                maze[x][y]=' ';
            }
        }
        for(int x=0;x<w;x++){
            maze[x][0]=maze[x][l-1]='|';
        }
        for(int y=0;y<l;y++){
            maze[0][y]=maze[w-1][y]='-';
        }
        maze[0][0]=maze[w-1][0]=maze[w-1][l-1]=maze[0][l-1]='+';
        int dor=1+rand.nextInt(l-2);
        maze[0][dor]=' ';
        int tx=2+rand.nextInt(w-3),ty=1+rand.nextInt(l-2);
        maze[tx][ty]='#';
        if(ty<dor-1){
            maze[tx][ty+1]='|';
            if(tx==w-2){
                maze[tx+1][ty+1]='+';
            }
            if(tx==1){
                maze[0][ty+1]='+';
            }
        }
        if(ty>dor+1){
            maze[tx][ty-1]='|';
            if(tx==w-2){
                maze[tx+1][ty-1]='+';
            }
            if(tx==1){
                maze[0][ty-1]='+';
            }
        }
        if(ty==dor&&tx>3&&(maze[tx][ty+1]==' '||maze[tx][ty-1]==' ')){
            maze[tx-1][ty]='-';
        }
        if(dor>5){
            int z=2+rand.nextInt(dor-3);
            int q=1+rand.nextInt(w-3);
            for(int i=0;i<w;i++){
                if(i==0||i==w-1){
                    maze[i][z]='+';
                }else if(i!=q&&maze[i][z]==' '){
                    maze[i][z]='|';
                }
            }

        }
        if(l-dor>5){
            int z=dor+2+rand.nextInt(l-dor-3);
            int q=1+rand.nextInt(w-3);
            for(int i=0;i<w;i++){
                if(i==0||i==w-1){
                    maze[i][z]='+';
                }else if(i!=q&&maze[i][z]==' '){
                    maze[i][z]='|';
                }
            }

        }
        for(char[]row:maze){
            System.out.println(row);
        }
    }
}

Beberapa hasil sampel:

3x3:

+ +
|#|
+-+

4x4:

+ -+
| #|
|  |
+--+

4x5:

+-+ +
|#| |
|   |
+---+

5x5:

+ --+
|   |
|   |
| |#|
+-+-+

5x8:

+ --+--+
|   |  |
|      |
| # |  |
+---+--+

8x15:

+---- ----+---+
|         |   |
|         |   |
|         |   |
|             |
| #|      |   |
|         |   |
+---------+---+
SuperJedi224
sumber