Geração de labirinto [fechada]

41

Eu sei que existe um segmento (antigo) semelhante a este ( aqui ), mas eu gostaria de reiniciá-lo com algumas modificações.

O objetivo: gerar um labirinto de aparência aleatória usando um algoritmo de sua escolha e depois imprimir o labirinto graficamente (contagens de impressão).

  • A largura e a altura são determinadas por você.
  • Deve haver pelo menos um caminho de pelo menos uma entrada para pelo menos uma saída.
  • O formato do labirinto (como você o exibe, marca entrada (s) ou saída (s)) também depende de você.
  • Quanto mais bonita, melhor.
  • Labirintos triviais (por exemplo, labirintos em branco, labirintos de treliça, labirintos de tamanho 1x1) são desencorajados.
  • Ciclos no labirinto são permitidos e, são incentivados, se o resultado for razoável.
  • Abuso de linguagem incentivado.
  • O labirinto deve parecer razoavelmente aleatório (mas um algoritmo completamente determinístico (por exemplo, caótico) que gera isso também é bom).

Edit: o foco principal aqui é fazer a menor implementação possível. No entanto, quero permitir uma margem de manobra dentro dessa restrição para incentivar o brilho. Eu deixei deliberadamente exatamente quais "características" o labirinto tem em aberto, mas como uma diretriz aproximada, você deve tentar colocar a maior quantidade de estrondo no dinheiro menos lexical.

imallett
fonte
4
Também "quanto mais bonito, melhor" parece dificilmente tangível (ou simplesmente irrelevante) a um desafio do código-golfe. Talvez um concurso de popularidade seja a melhor opção se você estiver interessado em obter bons resultados.
Martin Ender
5
Então, é realmente código-golfe ou é um concurso de popularidade?
L0b0
2
Como outra sugestão, se você deseja incentivar códigos curtos e labirintos elegantes, você pode desafiá-lo e declarar que o vencedor será selecionado por alguma pontuação que seja uma mistura de tamanho do código e votos positivos - embora isso depende de você determinar a pontuação total de cada resposta, porque incluir o número atual de upvotes na postagem é um pouco inútil.
Martin Ender
3
Eu acho que cada resposta deve explicar o que constitui entradas e saídas em cada labirinto (assim como, o que é um muro e o que é uma passagem), para que possamos avaliar a segunda bala.
Larsh
2
@ Geobits Eu não me importaria muito, mas daí a minha sugestão para torná-lo um desafio de código com pontuação combinada de tamanho e votos do código. Isso encorajaria exatamente o que o OP quer: código curto para labirintos interessantes.
Martin Ender

Respostas:

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]);}

(Requer terminal de 65 caracteres) Gera um labirinto 31x31 relativamente aleatório com um caminho garantido da entrada para a saída.

Exemplo de saída (com terminal simulado de 65 caracteres):

 ! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 
 !     !       !   !       !     !           !             !   ! 
 !!!!! !!! !!! ! !!! ! !!! ! !!! !!!!!!! !!! !!!!!!!!! !!! ! ! ! 
 !   !   !   ! !     ! ! ! ! ! ! !       !   !         !   ! ! ! 
 ! !!!!! !!! ! !!!!!!! ! ! ! ! ! ! !!!!!!! !!! ! !!!!!!! !!! ! ! 
 !     !     !         ! !   !   !     !   !   ! !     !   ! ! ! 
 ! !!! !!!!!!!!!!!!!!!!! !!!!! !!! !!! !!! ! ! !!! !!! !!! !!! ! 
 !   !         !     !   !     !     !   ! ! ! !     !   !   ! ! 
 !!!!!!!!!!! ! ! !!! !!! ! !!!!!!!!!!!!! ! !!! ! !!!!!!! !!! ! ! 
 !           !   !       ! !             !   !     !     !     ! 
 ! !!!!!!! !!!!!!! !!!!!!! ! !!!!!!!!!!!!!!! !!!!!!! !!!!!!!!!!! 
 ! !     ! !   !     !   ! !           !   !       ! !         ! 
 ! !!! ! ! ! ! !!!!!!! ! ! ! !!!!!!!!! ! ! !!!!!!! ! ! !!!!!!! ! 
 !   ! !   ! !       ! !   ! !         ! !       ! ! !   !   ! ! 
 !!! ! !!!!! !!!!!!! ! !!!!!!! !!!!!!!!! !!! !!!!! ! !!! ! !!! ! 
 !   !   ! ! !       !   !     !   !     ! !           ! !   ! ! 
 ! !!!!! ! ! ! !!!!!!!!! ! !!!!! !!! !!!!! !!!!!!!!!!! ! ! ! ! ! 
 ! !       ! !   !   !   ! !       ! !       !   !     ! ! ! ! ! 
 ! !!!!!!!!! !!! ! ! ! !!! !!!!!!! ! !!!!!!! ! ! !!!!!!! !!! ! ! 
 !             !   ! !   !       ! !     !   ! !             ! ! 
 !!!!!!!!!!!!!!!!!!! !!! !!!!!!! ! !!!!! ! !!! !!!!!!!!!!!!!!! ! 
 !               !   !   !       !         !   !     !   !     ! 
 ! !!!!!!!!!!!!! ! ! ! !!! !!!!!!! !!!!!!!!! !!! !!! !!! ! !!! ! 
 ! !   !       !   ! ! ! !     ! ! ! !     !     !   !   !   ! ! 
 ! ! ! !!!!! !!!!!!! ! ! ! !!! ! ! ! ! !!! !!!!!!! !!! !!!!! !!! 
 !   ! !   !       ! ! !     ! !     ! ! !     !   !       !   ! 
 !!!!! ! ! !!! !!! ! ! !!!!!!! !!!!!!! ! ! !!! ! !!!!!!!!! !!! ! 
 !     ! !   !   !   !       !       ! ! ! !   !   !         ! ! 
 ! !!!!! !!! !!! !!!!!!!!!!! !!!!!!! ! ! ! !!!!!!! ! !!!!!!! ! ! 
 !         ! !           !   !       ! ! !     !   ! !       ! ! 
 !!!!!!!!!!! !!!!!!!!!!! ! !!! !!!!!!! ! !!!!! ! !!! !!!!!!!!! ! 
 !         !     !     ! ! !       !   !     ! !     !         ! 
 ! !!!!!!! !!!!! ! !!! !!! !!!!!!! ! !!!!! ! ! !!!!! ! !!!!!!!!! 
 ! !     !     !   ! !   !       ! !       ! !       !         ! 
 ! ! !!! !!!!! ! !!! !!! !!!!!!! ! !!!!!!!!! !!!!!!!!!!!!!!!!! ! 
 !     !     ! !   !   ! !     ! !       !   ! !     !         ! 
 !!!!!!!!!!! ! !!! !!! ! ! ! !!! ! ! !!!!! !!! ! !!! ! !!!!!!! ! 
 !           ! !       !   ! !   ! !       !   ! ! ! !     !   ! 
 ! !!!!!!!!!!! !!!!!!!!!!!!! ! !!! !!!!!!!!!!! ! ! ! ! !!! ! !!! 
 !       !   !             ! ! ! !   !         ! !   !   ! ! ! ! 
 !!!!!!! !!! !!!!!!!!!!!!! ! ! ! !!! ! !!!!!!! ! !!! !!!!! ! ! ! 
 !       !         !     ! ! ! !   !   !     ! !   !       !   ! 
 ! !!!!!!! !!!!!!! ! !!!!! ! ! !!! !!!!!!! ! ! !!! !!!!!!!!!!!!! 
 !   !         ! !   !       ! !           ! !   !             ! 
 ! ! ! !!!!!!! ! ! !!! !!!!!!! ! !!!!!!!!!!! ! !!!!!!!!!!!!!!! ! 
 ! ! ! !     ! !   !   ! !     !   !   !     ! !               ! 
 ! ! !!! !!! ! !!!!! !!! ! !!!!! ! ! ! !!!!!!! ! !!!!!!!!!!!!! ! 
 ! !   !   ! !   !       !   !   !   !         ! !         !   ! 
 !!!!! !!! ! !!! ! !!!!!!!!! !!!!!!! !!!!!!!!!!! !!!!! !!!!! !!! 
 !     !   !   !   !       !       !       !   !     !       ! ! 
 ! !!!!! !!!!! !!!!! !!!!! !!!!!!! !!!!!!!!! ! !!!!! !!!!!!! ! ! 
 !           !     ! !   !   !   !           !   !   !     !   ! 
 ! !!!!!!!!! !!!!! ! !!! ! !!! ! !!!!!!!!!!!!!!! ! !!! !!! !!! ! 
 ! !     !       ! !     !     !     !         ! !       !   ! ! 
 !!! !!! !!!!!!!!! !!!!! !!!!!!!!! ! !!!!!!! !!! ! !!!!!!!!! ! ! 
 !   !     !   !   !   ! !       ! !         !   ! !         ! ! 
 ! !!!!!!! ! ! ! ! !!! ! !!!!!!! ! !!!!!!!!! ! !!!!! !!!!!!!!! ! 
 !       !   !   ! !   !         !   ! !   ! ! !     !       ! ! 
 ! !!!!! !!!!!!!!! ! !!!!!!!!!!! !!! ! ! ! ! ! ! !!!!! !!!!! ! ! 
 ! !     !           !         ! ! ! !   !   ! !   !   !     ! ! 
 ! ! !!!!!!!!!!!!!!!!! !!! !!!!! ! ! !!!!!!!!! !!! ! !!!!!!!!! ! 
 ! !                     !         !               !           ! 
 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ! 
Dendrobium
fonte
2
Você nem precisa int p,int c. p,cé suficiente ...
chubakueno
Ah, obrigado por apontar isso
Dendrobium
34

Mathematica, 144 132 bytes

Desde o início, todos sabemos a maneira mais eficiente de desenhar um labirinto .

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}]

Saída ungolfed e exemplo:

insira a descrição da imagem aqui

Claro, as linhas são as paredes. Você é o minotauro que começa no centro e precisa sair.

Martin Ender
fonte
4
Isso é bonito, e o código é curto, mas eu diria que é no final do "labirinto trivial" do espectro.
precisa saber é
2
Você está certo que torná-lo maior não mudaria a trivialidade. A questão é que resolver esse labirinto é um processo linear: a cada momento, você pode descobrir rapidamente se tomou a direção errada, sem ter que "recuar" em ramos mais profundos. As respostas de Ian e Aleph, por outro lado, são labirintos "reais": não podem ser resolvidos dessa maneira linear. Como os labirintos triviais são desencorajados, eu ficaria tentado a votar contra este, mas não tenho representante suficiente.
precisa saber é
11
@ LarsH sim, concordamos com isso. Por isso eu disse que é a maneira mais "eficiente" de desenhar um labirinto, não a maneira mais "eficaz". ;) Ainda assim, pode ser simples, mas não acho que se enquadre em uma categoria com as excluídas, como "blank" ou "1x1". Obviamente, fica a critério do OP desqualificar esse envio por sua simplicidade, mas desde que ele não faça isso ou mude o tipo de desafio, não vejo um incentivo para torná-lo mais complicado / interessante.
Martin Ender
11
@LarsH, dito isso, não tenho certeza se é devido a seus algoritmos ou apenas a um recurso dos exemplos específicos que eles postaram, mas nenhuma de suas respostas exigiu retroceder além da profundidade "1" mais de uma vez. Portanto, embora eles contenham muita complexidade, é tudo em caminhos que são irrelevantes de qualquer maneira.
Martin Ender
11
Este labirinto não é trivial, na minha opinião, mesmo que seja fácil (e meu labirinto circular abaixo é ainda mais trivial). Eu realmente só queria evitar blank-canvas / size-1 / etc. "labirinto" s.
precisa saber é o seguinte
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);}

Nota: acima, adicionei novas linhas para ajustá-lo à página. Saída esperada (no terminal de 80 caracteres) (observe o início e o término no canto superior esquerdo): insira a descrição da imagem aqui

imallett
fonte
8
@bwoebi MSPaint ao resgate! IMAGE
Ceiling Gecko
6
Note que minha intenção era que o caminho estivesse dentro dos canos (como aqui) .
precisa saber é o seguinte
11
@IanMallett Acho que Ceeck Gecko sabia disso, mas encher a parede esquerda com uma cor dá a você um caminho (não ideal) seguindo ao longo da parede esquerda até encontrar a saída. ;)
Martin Ender
11
Eu estaria interessado em ver a versão un-golfed deste código, se você tiver tempo.
LarsH
4
Enquanto você escrevia isso, você era um codificador de labirinto.
totymedli
24

Mathematica, 134 130 caracteres

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]

Labirinto


De fato, podemos usar esse algoritmo para gerar um labirinto a partir de qualquer gráfico (não direcionado).

Por exemplo, gere um labirinto a partir do gráfico de excursão do cavaleiro 8 * 8 ( KnightTourGraph[8,8]):

gráfico da excursão do cavaleiro

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

alefalpha
fonte
7
Belo labirinto… mas não vejo nenhuma entrada conectada a uma saída…?
bwoebi
9
Acredito que a idéia é escolher um nó aleatório (digamos, superior esquerdo) como entrada e outro (inferior direito) como saída. O Mathematica garante que todos os nós estejam conectados com todos os outros nós, mas - especialmente no segundo labirinto - descobrir como eles estão conectados é a parte mais difícil.
EagleV_Attnam
As linhas (bordas do gráfico) deveriam ser paredes de labirinto ou passagens? Eu pensei que sabia, mas agora não tenho certeza.
precisa saber é
@LarsH São passagens.
alephalpha
11
@LarsH O gráfico está conectado, então você pode usar apenas dois nós arbitrários, um como entrada e outro como saída.
alephalpha
13

Bash, 53 bytes

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

Idéia semelhante ao código C64. Usa caracteres Unicode como barras, porque eles são muito mais agradáveis ​​em um terminal que suporta Unicode. Exemplo de saída no OS X Terminal (fonte Menlo):

Saída de labirinto de amostra

nneonneo
fonte
2
Uma vez que eu descobri isso: yes 'c=(╱ ╲);printf ${c[RANDOM%2]}'|bash. Veja esta publicação
gniourf_gniourf
5
Isso se baseia em um algoritmo que não pode garantir sua capacidade de solução, um algoritmo com muitos anos de idade.
Isiah Meadows
9

JavaScript (ES6), 174

Este é o labirinto que usei nesse outro desafio , apenas jogando golfe. É uma função com 2 parâmetros: linhas e colunas. O labirinto é totalmente conectado sem loops, então qualquer local pode ser o ponto inicial ou final.

(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}

Exemplo

f(7,10)

Saída

,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

Teste

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
fonte
Não tenho certeza ... a área clara ou escura é o labirinto? Se estiver escuro, ele tem um loop grande e pode-se ficar do lado de fora ao escolher qualquer ponto como ponto de entrada / saída. Se a luz, então você deve adicionar a saída / entrada.
Paŭlo Ebermann
11
@ PaŭloEbermann é a luz, claro, a área escura são as paredes. Me repetir: O labirinto é totalmente conectado sem loops, então qualquer local pode ser a começar ou terminar ponto
edc65
Uau isso é incrível! Raspou alguns bytes e reduziu para 133 bytes: twitter.com/aemkei/status/889587308894326785 Mas todos os créditos devem ir para você!
aemkei
@aemkei 8 em vez de '#', eu não posso acreditar que eu perdi no momento
edc65
8

ZX Basic - 54 caracteres

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

Saída

Aqui está o labirinto mostrando uma rota através dele (espaços entre linhas)

caminho

e um pequeno trecho de quando eu fiz isso pela primeira vez (há vários anos) e passei um pouco de tempo fazendo gráficos melhores.

melhores gráficos

Brian
fonte
2
Hum, atrevido. ^^ Qual é o começo e o fim aí? E as barras são os caminhos ou as paredes? E qual é o tamanho mínimo do espaço pelo qual posso passar?
Martin Ender
2
"Deve haver pelo menos um caminho de pelo menos uma entrada para pelo menos uma saída". Não vejo nenhuma indicação de que este critério seja atendido. Paredes aleatórias não criam necessariamente um labirinto.
precisa saber é o seguinte
11
@ m.buettner: Suponho que as barras sejam paredes e que devemos visualizá-las como se houvesse espaço zero entre as linhas e as colunas. Assim, os caracteres 2x2 no canto inferior esquerdo formam uma forma de diamante (quadrado) totalmente fechada.
Larsh
@ LarsH sim, eu pensei que sim. Isso apenas faz outro argumento para o seu caso sobre a pergunta do OP de que as pessoas devem indicar o que é o começo e o fim. Além disso, esse esquema nem permite junções. Você só pode ter quadrados fechados ou caminhos sinuosos (que também podem ser loops fechados).
Martin Ender
+1 para os gráficos aprimorados e mostrando a rota. Eu acho que, dadas tantas entradas e saídas em potencial, a probabilidade de ter "pelo menos um caminho de pelo menos uma entrada para pelo menos uma saída" é bastante alta!
Larsh
8

BBC BASIC, 18 bytes

Uma melhoria no comprimento da versão de loop infinito C64 de 23 bytes da @nneonneo. O VDU envia um único caractere para o controlador VDU: 2 + 1 * 45 = ASCII 47 /ou 2 + 2 * 45 = ASCII 92\

  VDU2+RND(2)*45:RUN

BBC BASIC, 35 bytes / 107 95 bytes

35 bytes é apenas para a última linha, que fornece um labirinto de 25 linhas no layout de 40 colunas. MODE1 garante que não haja espaço extra entre as linhas. O restante do programa é opcional e melhora a formatação. As instruções VDU23 redefinem a fonte dos caracteres 47 e 92 (8 bytes formando um bitmap de 8x8). Incluo um pixel claro nos quatro cantos para impedir que execuções retas sejam cortadas. O efeito colateral disso é que um ponto aparece nos diamantes vazios. Total de 107 bytes, incluindo 2 novas linhas.

  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

Editar este programa pode ser reduzido para 95 bytes, codificando alguns dos códigos VDU de 8 bits em pequenos valores endianos de 16 bits (indicados por um ponto-e-vírgula depois deles em vez de vírgula) e representando a instrução MODE como um par de códigos VDU, da seguinte maneira .

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

Saída

Usando o BBC Basic para Windows em bbcbasic.co.uk

Somente última linha, 35 bytes

insira a descrição da imagem aqui

Programa inteiro, 107 95 bytes

Como comentei na resposta de @ Brian, a barra divide o quadrado em 2 triângulos escuros, cada um com exatamente 2 entradas / saídas. Isso garante um caminho (trivial, não ramificado) de qualquer ponto na borda do labirinto até algum outro ponto na borda do labirinto. Muitos deles são muito curtos, mas sempre parecem existir alguns longos. Claro, no meio do labirinto também existem alguns loops.

Como outras respostas não mencionaram isso, eu gostaria de dar uma boa olhada nas áreas claras. Elas são delimitadas por áreas escuras; portanto, como corolário da afirmação acima, uma área clara delimitada externamente por N áreas escuras toca a borda do campo em N (exatamente quantos) pontos. Portanto, algumas áreas de luz razoavelmente grandes ocorrem e elas formam labirintos interessantes e ramificados.

No exemplo abaixo, você pode ver a saída bruta (monocromática) do meu programa. Abaixo disso (usando o Windows Paint), pintei as duas áreas escuras mais longas em azul. Depois pintei a maior área clara em amarelo e as duas áreas delimitadas por azul em vermelho e verde. Os labirintos amarelos, verdes (e até vermelhos) são bastante interessantes e não triviais.

insira a descrição da imagem aqui

EDIT - Seleção automática de labirintos e seleção de partidas / finais

Para mais uma linha (59 caracteres), o programa pode selecionar automaticamente até 6 labirintos escolhendo quadrados aleatoriamente e preenchendo cores nas cores vermelho, verde, amarelo, azul, magenta e ciano. Nem sempre encontra um 6 completo, porque se ele escolhe um quadrado aleatório que já foi colorido, não faz nada.

O restante do código abaixo seleciona o início de cada cor, digitalizando cada coluna de cima para baixo e da esquerda para a direita e escolhendo o primeiro quadrado encontrado. Ele escolhe um fim, digitalizando na direção oposta.

Isso produz um conjunto de labirintos coloridos e entrelaçados. Às vezes, eles estão tão entrelaçados que parece que os labirintos devem atravessar algum lugar. Mas é claro que não!

Código e saída adicionais 59 + 187 = 246 caracteres adicionais a serem adicionados ao final do programa original (para aprimoramento além das especificações das perguntas)

  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)

insira a descrição da imagem aqui

Level River St
fonte
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++]);}

Nota: acima, adicionei novas linhas para ajustá-lo à página. Saída esperada (no terminal de 80 caracteres):insira a descrição da imagem aqui

Lamento que este não seja um labirinto muito difícil (na verdade, não é necessário voltar atrás aos anéis internos (e você deve encontrar um caminho do perímetro para o centro trivialmente) .No entanto, ele tem uma boa implementação do círculo de Bresenham algoritmo de desenho em sua essência.

imallett
fonte
É um pouco difícil ver por onde você pode passar e onde não pode. Devo dizer que preferi os canos;) (tanto para isso quanto para a minha apresentação circular).
Martin Ender
@ m.buettner: Na verdade, eu concordo. Se você mudar i+=2para i+=3, pode ficar mais claro o que está acontecendo.
precisa saber é o seguinte
6

Ajudei meu filho a fazer isso, a aprender um pouco de programação: http://jsfiddle.net/fs2000/4KLUC/34/ como você gosta?

Giuseppe Strafforello
fonte
17
Se você pode ajustar seu código na postagem, faça isso. Além disso, inclua um cabeçalho como #Language (s) - Bytecount. Se você usou apenas caracteres ASCII no seu código, pode obter um bom bytecount aqui . Um resumo do que o seu código faz, quaisquer informações que você possa ter ou quaisquer coisas inteligentes que você fez podem ser uma boa adição à sua postagem. A propósito, Darth Vader torna muito difícil ver algumas das linhas. Finalmente, bem-vindo ao Code Golf!
Rainbolt
Você aprendeu um pouco de programação com seus filhos e eu aprendi um pouco de golfe. Este é o meu primeiro jogo de golfe e o resultado ainda é bastante longo. Contagem de bytes: Original: 55 + 6822 = 6877. Um pouco reorganizada : 39 + 3131 = 3170 Golfed : 39 + 1593 = 1632
BartekChom
6

Commodore 64 BASIC - 38 bytes

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

Esta não é minha invenção, estou simplesmente repetindo um programa muito bonito e curto dos dias passados. De fato, há um livro inteiro chamado 10 PRINT CHR$(205.5+RND(1)); : GOTO 10celebrando esse pedaço de código!

Você pode ver a saída deste vídeo do YouTube ; Aqui está um screencap:

Screencap do YouTube

Aqui nesta questão do StackOverflow, há mais implementações deste programa gerador de labirinto. A implementação mais curta do programa é o seguinte programa C64 BASIC de 23 bytes publicado pelo autor da pergunta:

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

onde as letras minúsculas são inseridas como estão e as letras maiúsculas são inseridas usando a tecla Shift (elas têm aparências diferentes na tela C64 real).

nneonneo
fonte
Não é exatamente a mesma afirmação de Brian? (um pouco mais curto) E sua resposta é a Bash? Então a questão aqui também é: um labirinto sem junções ainda é um labirinto?
Martin Ender
nneonneo, +1 pela atribuição correta e honesta dessa ótima idéia. @ m.buettner A área não impressa produz labirintos não ramificados como você aponta. No entanto (e estou surpreso que ninguém mais tenha mostrado isso ainda), a área impressa forma alguns labirintos interessantes, não triviais e ramificados (veja minha resposta). . Definir início e fim nesses labirintos diagonais não é fácil.
Level River St
@ m.buettner 1. O binário x86 tem apenas 10 bytes no menor. 2. Este é um algoritmo bem aperfeiçoado, e não é de todo original, nem pretendia criar um labirinto solucionável.
Isiah Meadows
5

Java: 700

Aqui está um adicionador de parede recursivo. O algoritmo está descrito neste site :

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;}}

Basicamente, ele divide cada retângulo em dois com uma parede (e passagem), depois os divide em dois, etc. Gera um labirinto "perfeito" - um sem ciclos - que tem um caminho de todos os pontos para todos os outros pontos. Muitos becos sem saída, por isso não é "trivial" em nenhum sentido para labirintos maiores.

Assim, a entrada e saída podem ser decididas arbitrariamente. Se eu tiver que escolher um, será apenas superior / esquerda e inferior / direita.

Ele é desenhado em ascii de largura dupla, por isso é uma boa idéia canalizar a saída para um arquivo se você estiver usando um tamanho qualquer. Aqui está um console 20x20:

20x20

E um 100x100 no bloco de notas ++ (eu tive que diminuir o zoom para obter tudo, então é um pouco ... pequeno ):

100x100

Código com quebras de linha:

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;
    }
}
Geobits
fonte
2

ZX Basic - 281 caracteres

Este é mais um labirinto "adequado", menos golfista, mas mais labirinto. O chamado algoritmo de labirinto binário, cada célula pode ter uma saída descendente ou direita, mas não as duas. (Agora inclui as marcadas Start "S" e End "E", para evitar apenas seguir em frente).

O "::" é a maneira do ZXB de inserir caracteres gráficos do Spectrum em um arquivo de texto, igual a um caractere de bloco vendido.

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"

Labirinto

Brian
fonte
2
Não, na verdade, eu quis dizer que você deveria trocar o início e o fim (começo inferior direito, final superior esquerdo). Como é trivial, porque, devido às regras, você só precisa descer e acertar o tempo todo para chegar ao fim.
Martin Ender
11
Mesmo que o início e o fim sejam invertidos, o labirinto possui a propriedade (talvez interessante) de que o caminho correto só será movido para cima e para a esquerda. O labirinto não é mais trivial, porém, porque há muitos pontos nos quais você pode seguir uma de duas maneiras.
Kevin - Restabelece 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;}

Aqui está como ele se parece:

Labirinto

Nota: esta solução é inspirada no jogo não confiável nível 8: na floresta.

Mhmd
fonte