Maze Generation [cerrado]

41

Sé que hay un hilo (antiguo) similar a este ( aquí ), pero me gustaría reiniciarlo con algunas modificaciones.

El objetivo: generar un laberinto de aspecto aleatorio utilizando un algoritmo de su elección, luego generar el laberinto gráficamente (conteos de impresión).

  • El ancho y la altura los determina usted.
  • Debe haber al menos un camino desde al menos una entrada hasta al menos una salida.
  • El formato del laberinto (cómo lo muestra, marca las entradas o salidas) también depende de usted.
  • Cuanto más bonita, mejor.
  • Los laberintos triviales (por ejemplo, laberintos en blanco, laberintos enrejados, laberintos de tamaño 1x1) no se recomiendan.
  • Los ciclos en el laberinto están permitidos y, se recomienda, si el resultado es razonable.
  • Se alienta el abuso del lenguaje.
  • El laberinto debe verse razonablemente aleatorio (pero un algoritmo completamente determinista (por ejemplo, caótico) que genera esto también está bien).

Editar: el enfoque principal aquí es hacer la implementación más pequeña posible. Sin embargo, quiero permitir un margen de maniobra dentro de esa restricción para alentar el brillo. Deliberadamente he dejado exactamente qué "características" tiene el laberinto abierto, pero como guía aproximada, debes tratar de meter la mayor cantidad de explosión en el menor dinero léxico.

code-golf popularity-contest maze imallett
fuente
44
También "Cuanto más bonita, mejor" parece difícilmente tangible (o simplemente irrelevante) para un desafío de código de golf. Tal vez un concurso de popularidad sería la mejor opción si estás interesado en obtener buenos resultados.
Martin Ender
55
Entonces, ¿es realmente code-golf o es más bien un concurso de popularidad?
l0b0
2
Como otra sugerencia, si desea incentivar tanto los códigos cortos como los laberintos limpios, podría convertirlo en un desafío de código y declarar que el ganador será seleccionado por un puntaje que sea una mezcla de longitud de código y votos a favor, aunque será depende de usted determinar el puntaje total de cada respuesta, porque incluir el número actual de votos positivos en la publicación es un poco inútil.
Martin Ender
3
Creo que cada respuesta debe explicar qué constituyen entradas y salidas en cada laberinto (así como, qué es un muro y qué es un pasaje), para que podamos evaluar la segunda viñeta.
LarsH
2
@Geobits No me importaría demasiado, pero de ahí mi sugerencia de convertirlo en un desafío de código con una puntuación combinada de longitud de código y votos. Eso animaría exactamente lo que quiere el OP: código corto para laberintos interesantes.
Martin Ender

Respuestas:

10

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

(Requiere terminal de 65 caracteres) Genera un laberinto de 31x31 relativamente aleatorio con un camino garantizado desde la entrada hasta la salida.

Ejemplo de salida (con terminal simulada de 65 caracteres):

 ! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 
 !     !       !   !       !     !           !             !   ! 
 !!!!! !!! !!! ! !!! ! !!! ! !!! !!!!!!! !!! !!!!!!!!! !!! ! ! ! 
 !   !   !   ! !     ! ! ! ! ! ! !       !   !         !   ! ! ! 
 ! !!!!! !!! ! !!!!!!! ! ! ! ! ! ! !!!!!!! !!! ! !!!!!!! !!! ! ! 
 !     !     !         ! !   !   !     !   !   ! !     !   ! ! ! 
 ! !!! !!!!!!!!!!!!!!!!! !!!!! !!! !!! !!! ! ! !!! !!! !!! !!! ! 
 !   !         !     !   !     !     !   ! ! ! !     !   !   ! ! 
 !!!!!!!!!!! ! ! !!! !!! ! !!!!!!!!!!!!! ! !!! ! !!!!!!! !!! ! ! 
 !           !   !       ! !             !   !     !     !     ! 
 ! !!!!!!! !!!!!!! !!!!!!! ! !!!!!!!!!!!!!!! !!!!!!! !!!!!!!!!!! 
 ! !     ! !   !     !   ! !           !   !       ! !         ! 
 ! !!! ! ! ! ! !!!!!!! ! ! ! !!!!!!!!! ! ! !!!!!!! ! ! !!!!!!! ! 
 !   ! !   ! !       ! !   ! !         ! !       ! ! !   !   ! ! 
 !!! ! !!!!! !!!!!!! ! !!!!!!! !!!!!!!!! !!! !!!!! ! !!! ! !!! ! 
 !   !   ! ! !       !   !     !   !     ! !           ! !   ! ! 
 ! !!!!! ! ! ! !!!!!!!!! ! !!!!! !!! !!!!! !!!!!!!!!!! ! ! ! ! ! 
 ! !       ! !   !   !   ! !       ! !       !   !     ! ! ! ! ! 
 ! !!!!!!!!! !!! ! ! ! !!! !!!!!!! ! !!!!!!! ! ! !!!!!!! !!! ! ! 
 !             !   ! !   !       ! !     !   ! !             ! ! 
 !!!!!!!!!!!!!!!!!!! !!! !!!!!!! ! !!!!! ! !!! !!!!!!!!!!!!!!! ! 
 !               !   !   !       !         !   !     !   !     ! 
 ! !!!!!!!!!!!!! ! ! ! !!! !!!!!!! !!!!!!!!! !!! !!! !!! ! !!! ! 
 ! !   !       !   ! ! ! !     ! ! ! !     !     !   !   !   ! ! 
 ! ! ! !!!!! !!!!!!! ! ! ! !!! ! ! ! ! !!! !!!!!!! !!! !!!!! !!! 
 !   ! !   !       ! ! !     ! !     ! ! !     !   !       !   ! 
 !!!!! ! ! !!! !!! ! ! !!!!!!! !!!!!!! ! ! !!! ! !!!!!!!!! !!! ! 
 !     ! !   !   !   !       !       ! ! ! !   !   !         ! ! 
 ! !!!!! !!! !!! !!!!!!!!!!! !!!!!!! ! ! ! !!!!!!! ! !!!!!!! ! ! 
 !         ! !           !   !       ! ! !     !   ! !       ! ! 
 !!!!!!!!!!! !!!!!!!!!!! ! !!! !!!!!!! ! !!!!! ! !!! !!!!!!!!! ! 
 !         !     !     ! ! !       !   !     ! !     !         ! 
 ! !!!!!!! !!!!! ! !!! !!! !!!!!!! ! !!!!! ! ! !!!!! ! !!!!!!!!! 
 ! !     !     !   ! !   !       ! !       ! !       !         ! 
 ! ! !!! !!!!! ! !!! !!! !!!!!!! ! !!!!!!!!! !!!!!!!!!!!!!!!!! ! 
 !     !     ! !   !   ! !     ! !       !   ! !     !         ! 
 !!!!!!!!!!! ! !!! !!! ! ! ! !!! ! ! !!!!! !!! ! !!! ! !!!!!!! ! 
 !           ! !       !   ! !   ! !       !   ! ! ! !     !   ! 
 ! !!!!!!!!!!! !!!!!!!!!!!!! ! !!! !!!!!!!!!!! ! ! ! ! !!! ! !!! 
 !       !   !             ! ! ! !   !         ! !   !   ! ! ! ! 
 !!!!!!! !!! !!!!!!!!!!!!! ! ! ! !!! ! !!!!!!! ! !!! !!!!! ! ! ! 
 !       !         !     ! ! ! !   !   !     ! !   !       !   ! 
 ! !!!!!!! !!!!!!! ! !!!!! ! ! !!! !!!!!!! ! ! !!! !!!!!!!!!!!!! 
 !   !         ! !   !       ! !           ! !   !             ! 
 ! ! ! !!!!!!! ! ! !!! !!!!!!! ! !!!!!!!!!!! ! !!!!!!!!!!!!!!! ! 
 ! ! ! !     ! !   !   ! !     !   !   !     ! !               ! 
 ! ! !!! !!! ! !!!!! !!! ! !!!!! ! ! ! !!!!!!! ! !!!!!!!!!!!!! ! 
 ! !   !   ! !   !       !   !   !   !         ! !         !   ! 
 !!!!! !!! ! !!! ! !!!!!!!!! !!!!!!! !!!!!!!!!!! !!!!! !!!!! !!! 
 !     !   !   !   !       !       !       !   !     !       ! ! 
 ! !!!!! !!!!! !!!!! !!!!! !!!!!!! !!!!!!!!! ! !!!!! !!!!!!! ! ! 
 !           !     ! !   !   !   !           !   !   !     !   ! 
 ! !!!!!!!!! !!!!! ! !!! ! !!! ! !!!!!!!!!!!!!!! ! !!! !!! !!! ! 
 ! !     !       ! !     !     !     !         ! !       !   ! ! 
 !!! !!! !!!!!!!!! !!!!! !!!!!!!!! ! !!!!!!! !!! ! !!!!!!!!! ! ! 
 !   !     !   !   !   ! !       ! !         !   ! !         ! ! 
 ! !!!!!!! ! ! ! ! !!! ! !!!!!!! ! !!!!!!!!! ! !!!!! !!!!!!!!! ! 
 !       !   !   ! !   !         !   ! !   ! ! !     !       ! ! 
 ! !!!!! !!!!!!!!! ! !!!!!!!!!!! !!! ! ! ! ! ! ! !!!!! !!!!! ! ! 
 ! !     !           !         ! ! ! !   !   ! !   !   !     ! ! 
 ! ! !!!!!!!!!!!!!!!!! !!! !!!!! ! ! !!!!!!!!! !!! ! !!!!!!!!! ! 
 ! !                     !         !               !           ! 
 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !
Dendrobium
fuente
2
Ni siquiera lo necesitas int p,int c. p,ces suficiente ...
chubakueno
Ah, gracias por señalarlo
Dendrobium
34

Mathematica, 144 132 bytes

Desde el inicio, todos conocemos la forma más eficiente de dibujar un laberinto .

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

Ungolfed y salida de ejemplo:

ingrese la descripción de la imagen aquí

Por supuesto, las líneas son las paredes. Eres el minotauro que comienza en el centro y necesita salir.

Martin Ender
fuente
44
Esto es bonito, y el código es corto, pero diría que está hacia el final del "laberinto trivial" del espectro.
LarsH
2
Tienes razón en que hacerlo más grande no cambiaría la trivialidad. El punto es que resolver este laberinto es un proceso lineal: en cada coyuntura puedes descubrir rápidamente si has tomado el giro equivocado, sin tener que "recurrir" a ramas más profundas. Las respuestas de Ian y aleph, por otro lado, son laberintos "reales": no se pueden resolver de esta manera lineal. Como se desalientan los laberintos triviales, me vería tentado a rechazar este, pero no tengo suficiente reputación.
LarsH
1
@LarsH sí, estamos de acuerdo en eso. Por eso dije que es la forma más "eficiente" de dibujar un laberinto, no la más "efectiva". ;) Aún así, puede ser simple, pero no creo que caiga en una categoría con las descartadas como "en blanco" o "1x1". Por supuesto, queda a discreción del OP descalificar esta presentación por su simplicidad, pero mientras no lo haga o cambie el tipo de desafío, no veo un incentivo para hacerlo más complicado / interesante.
Martin Ender
1
Dicho esto, no estoy seguro si se debe a sus algoritmos o solo a una característica de los ejemplos particulares que publicaron, pero ninguna de sus respuestas requirió retroceder más allá del "1" más de una vez. Entonces, si bien contienen mucha complejidad, todo está en caminos que son irrelevantes de todos modos.
Martin Ender
1
Este laberinto no es trivial, en mi opinión, incluso si es fácil (y mi laberinto circular a continuación es aún más trivial). Realmente solo quería evitar blank-canvas / size-1 / etc. "laberinto" s.
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);}

Nota: en lo anterior, agregué nuevas líneas para que se ajuste a la página. Salida esperada (en terminal de 80 caracteres) (nota de inicio y final en la parte superior izquierda): ingrese la descripción de la imagen aquí

imallett
fuente
8
@bwoebi MSPaint al rescate! IMAGEN
Gecko de techo
66
Tenga en cuenta que mi intención era que el camino estuviera dentro de las tuberías (como aquí) .
imallett
1
@IanMallett Creo que Ceiling Gecko estaba al tanto de eso, pero llenar la pared izquierda con un color te da un camino (no óptimo) siguiendo la pared izquierda hasta encontrar la salida. ;)
Martin Ender
1
Me interesaría ver la versión sin golf de este código, si tiene tiempo.
LarsH
44
Mientras escribías esto, eras un codificador asombroso.
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]

laberinto

De hecho, podemos usar este algoritmo para generar un laberinto a partir de cualquier gráfico (no dirigido).

Por ejemplo, genere un laberinto a partir del gráfico de recorrido del caballero 8 * 8 ( KnightTourGraph[8,8]):

gráfico del recorrido del caballero

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]

laberinto2

alephalpha
fuente
77
Bonito laberinto ... pero no veo ninguna entrada que esté conectada a una salida ...?
bwoebi
99
Creo que la idea es elegir un nodo aleatorio (digamos, arriba a la izquierda) como entrada y otro (abajo a la derecha) como salida. Mathematica se asegura de que todos los nodos estén conectados con todos los demás nodos, pero, especialmente en el segundo laberinto, descubrir cómo están conectados es la parte más difícil.
EagleV_Attnam
¿Se supone que las líneas (bordes del gráfico) son paredes de laberinto o pasajes? Pensé que lo sabía, pero ahora no estoy seguro.
LarsH
@LarsH Son pasajes.
alephalpha
1
@LarsH El gráfico está conectado, por lo que puede tomar dos nodos arbitrarios, uno como entrada y el otro como salida.
alephalpha
13

Bash, 53 bytes

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

Idea similar al código C64. Utiliza caracteres Unicode como barras oblicuas porque se ven mucho mejor en un terminal que admite Unicode. Salida de muestra en OS X Terminal (fuente Menlo):

Muestra de salida de laberinto

nneonneo
fuente
2
Una vez cuenta de esto: yes 'c=(╱ ╲);printf ${c[RANDOM%2]}'|bash. Ver esta publicación
gniourf_gniourf
55
Esto se basa en un algoritmo que no puede garantizarse solucionable, uno que tiene muchos años.
Isiah Meadows
9

JavaScript (ES6), 174

Este es el constructor de laberintos que utilicé en este otro desafío , solo golf. Es una función con 2 parámetros: filas y columnas. El laberinto está totalmente conectado sin bucles, por lo que cualquier ubicación puede ser el punto inicial o 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}

Ejemplo

f(7,10)

Salida

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

Prueba

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>
Expandir fragmento

edc65
fuente
No estoy seguro ... ¿es la luz o el área oscura el laberinto? Si está oscuro, tiene un gran bucle y uno puede quedarse en el exterior al elegir cualquier punto como punto de entrada / salida. Si la luz, entonces debe agregar la salida / entrada.
Paŭlo Ebermann
1
@ PaŭloEbermann es la luz, por supuesto, el área oscura es las paredes. Repitiéndome: el laberinto está totalmente conectado sin bucles, por lo que cualquier ubicación puede ser el punto de inicio o finalización
edc65
¡Wow esto es increíble! Afeité algunos bytes y lo reduje a 133 bytes: twitter.com/aemkei/status/889587308894326785 ¡ Pero todos los créditos deberían ir a usted!
aemkei
@aemkei 8 en lugar de '#', no puedo creer que me perdí eso en ese momento
edc65
8

ZX Basic - 54 caracteres

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

Salida

Aquí está el laberinto que muestra una ruta a través de él (espacios entre líneas)

camino

y un pequeño fragmento de cuando hice esto por primera vez (hace varios años), y pasé un poco de tiempo haciendo mejores gráficos.

mejores gráficos

Brian
fuente
2
Hm, descarado. ^^ ¿Cuál es el comienzo y el final allí? ¿Y son los cortes los caminos o las paredes? ¿Y cuál es el tamaño mínimo de espacio por el que puedo pasar?
Martin Ender
2
"Debe haber al menos un camino desde al menos una entrada a al menos una salida". No veo ninguna indicación de que se cumpla este criterio. Los muros al azar no necesariamente crean un laberinto.
LarsH
1
@ m.buettner: supongo que las barras son paredes, y que se supone que debemos visualizarlo como si hubiera cero espacio entre filas y entre columnas. Por lo tanto, los caracteres 2x2 de la parte inferior izquierda forman una forma de diamante (cuadrado) totalmente cerrada.
LarsH
@LarsH, sí, eso creo. Eso solo hace otro punto para su caso sobre la pregunta del OP de que las personas deben indicar qué son el comienzo y el final. Además, este esquema ni siquiera permite uniones. Solo puede tener esos cuadrados cerrados o caminos serpenteantes (que también pueden ser bucles cerrados).
Martin Ender
+1 para los gráficos mejorados y mostrar la ruta. ¡Supongo que dadas tantas entradas y salidas potenciales, la probabilidad de tener "al menos un camino desde al menos una entrada a al menos una salida" es bastante alta!
LarsH
8

BBC BASIC, 18 Bytes

Una mejora en la longitud de la versión de bucle infinito C64 de 23 bytes de @nneonneo. VDU envía un solo carácter al controlador de VDU: 2 + 1 * 45 = ASCII 47 /o 2 + 2 * 45 = ASCII 92\

  VDU2+RND(2)*45:RUN

BBC BASIC, 35 Bytes / 107 95 Bytes

35 bytes es solo para la última línea, que da un laberinto de 25 filas en un diseño de 40 columnas. MODE1 asegura que no quede espacio adicional entre líneas. El resto del programa es opcional y mejora el formato. Las instrucciones VDU23 redefinen la fuente para los caracteres 47 y 92 (8 bytes que forman un mapa de bits de 8x8). Incluyo un píxel claro en las cuatro esquinas para evitar que las corridas se pinchen. El efecto secundario de esto es que aparece un punto en los diamantes vacíos. 107 bytes en total, incluidas 2 líneas nuevas.

  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 se puede acortar a 95 bytes codificando algunos de los códigos VDU de 8 bits en valores endian pequeños de 16 bits (indicados con un punto y coma después de ellos en lugar de una coma) y representando la declaración MODE como un par de códigos VDU, de la siguiente manera .

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

Salida

Usando BBC Basic para Windows desde bbcbasic.co.uk

Última línea solamente, 35 bytes

ingrese la descripción de la imagen aquí

Programa completo, 107 95 bytes

Como comenté sobre la respuesta de @ Brian, la barra divide el cuadrado en 2 triángulos oscuros, cada uno de los cuales tiene exactamente 2 entradas / salidas. Esto garantiza un camino (trivial, no ramificado) desde cualquier punto en el borde del laberinto a algún otro punto en el borde del laberinto. Muchos de estos son muy cortos, pero siempre parece haber algunos largos. Por supuesto, en el medio del laberinto también hay algunos bucles.

Como otras respuestas no lo han mencionado, me gustaría echar un vistazo a las áreas claras. Estos están delimitados por áreas oscuras, por lo tanto, como corolario de la declaración anterior, un área clara delimitada externamente por N áreas oscuras toca el borde del campo en N (exactamente tantos) puntos. Por lo tanto, se producen algunas áreas de luz bastante grandes, que forman laberintos interesantes y ramificados.

En el siguiente ejemplo, puede ver la salida sin formato (monocromo) de mi programa. Debajo de eso (usando Windows Paint) he coloreado las dos áreas oscuras más largas en azul. Luego coloreé el área de luz más grande en amarillo, y las dos áreas delimitadas por azul en rojo y verde. Los laberintos amarillo, verde (e incluso el rojo) son bastante interesantes y no triviales.

ingrese la descripción de la imagen aquí

EDITAR: selección automática de laberintos y selección de comienzos / finales

Para una línea más (59 caracteres), el programa puede seleccionar automáticamente hasta 6 laberintos eligiendo cuadrados al azar e inundando los colores rojo, verde, amarillo, azul, magenta y cian. No siempre encuentra un 6 completo, porque si elige un cuadrado aleatorio que ya ha sido coloreado, no hace nada.

El resto del código a continuación selecciona un comienzo para cada color al escanear cada columna de arriba a abajo y de izquierda a derecha, y elegir el primer cuadrado que encuentra. Elige un final escaneando en la dirección opuesta.

Esto produce un conjunto de laberintos coloridos y entrelazados. A veces están tan entrelazados que parece que los laberintos deben cruzarse en alguna parte. ¡Pero por supuesto que no!

Código adicional y salida 59 + 187 = 246 caracteres adicionales que se agregarán al final del programa original (para una mejora más allá de las especificaciones de la pregunta)

  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)

ingrese la descripción de la imagen aquí

Level River St
fuente
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: en lo anterior, agregué nuevas líneas para que se ajuste a la página. Salida esperada (en terminal de 80 caracteres):ingrese la descripción de la imagen aquí

Lamento que este no sea un laberinto muy difícil (de hecho, no es necesario retroceder a los anillos internos (y debería ser capaz de encontrar un camino desde el perímetro al centro trivialmente). Sin embargo, tiene una buena implementación del círculo de Bresenham algoritmo de dibujo en su núcleo.

imallett
fuente
Es un poco difícil ver por dónde puedes pasar y dónde no. Tengo que decir que preferí las tuberías;) (tanto a esto como a mi presentación circular).
Martin Ender
@ m.buettner: de hecho estoy de acuerdo. Si cambia el i+=2a i+=3, podría quedar más claro lo que está sucediendo.
imallett
6

Ayudé a mi hijo a hacer esto, a aprender un poco de programación: http://jsfiddle.net/fs2000/4KLUC/34/ ¿cómo te gusta?

Giuseppe Strafforello
fuente
17
Si puedes incluir tu código en la publicación, hazlo. Además, incluya un encabezado como #Language (s) - Bytecount. Si solo usó caracteres ASCII en su código, puede obtener un buen bytecount aquí . Un resumen de lo que hace su código, cualquier información que haya tenido o cualquier cosa inteligente que haya hecho podría ser una buena adición a su publicación. Por cierto, Darth Vader hace que sea muy difícil ver algunas de las líneas. Finalmente, ¡Bienvenido a Code Golf!
Rainbolt
Aprendiste un poco de programación con tus hijos y yo aprendí un poco de golf. Este es mi primer juego de golf y el resultado aún es bastante largo. Recuento de bytes: Original: 55 + 6822 = 6877. Un poco reorganizado : 39 + 3131 = 3170 Golfizado : 39 + 1593 = 1632
BartekChom
6

Commodore 64 BASIC - 38 bytes

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

Este no es mi invento, simplemente estoy repitiendo un programa muy hermoso y corto de días pasados. De hecho, ¡hay un libro completo llamado 10 PRINT CHR$(205.5+RND(1)); : GOTO 10celebrando este código!

Puedes ver la salida en este video de YouTube ; Aquí hay una captura de pantalla:

Captura de pantalla de YouTube

Aquí en esta pregunta de StackOverflow hay más implementaciones de este programa generador de laberintos. La implementación más corta del programa es el siguiente programa BASIC C64 de 23 bytes publicado por el autor de esa pregunta:

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

donde las letras minúsculas se ingresan tal cual y las mayúsculas se ingresan con la tecla Mayús (tienen diferentes apariencias en una pantalla C64 real).

nneonneo
fuente
¿No es exactamente la misma sumisión de Brian? (solo un poco más corto) ¿Y tu respuesta Bash también? Entonces la pregunta aquí también es, ¿un laberinto sin cruces sigue siendo un laberinto?
Martin Ender
nneonneo, +1 por la atribución adecuada y honesta de esta gran idea. @ m.buettner El área no impresa produce laberintos no ramificados como usted señala. Sin embargo (y me sorprende que nadie más lo haya mostrado aún) el área impresa forma algunos laberintos ramificados interesantes, no triviales (vea mi respuesta). También estoy votando su laberinto ya que tiene el comienzo y el final mejor definidos . Definir inicio y fin en estos laberintos diagonales no es fácil.
Level River St
@ m.buettner 1. El binario x86 tiene solo 10 bytes como mínimo. 2. Este es un algoritmo bien perfeccionado, y no es en absoluto original, ni tenía la intención de crear un laberinto solucionable.
Isiah Meadows
5

Java: 700

Aquí hay un sumador de pared recursivo. El algoritmo se describe en este sitio :

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

Básicamente, divide cada rectángulo en dos con una pared (y pasaje), luego divide aquellos en dos, etc. Genera un laberinto "perfecto", uno sin ciclos, que tiene una ruta desde cada punto a cualquier otro punto. Muchos callejones sin salida, por lo que no es "trivial" en ningún sentido para laberintos más grandes.

Entonces, la entrada y la salida se pueden decidir arbitrariamente. Si tengo que elegir uno, solo dirá arriba / izquierda e inferior / derecha.

Está dibujado en ascii de doble ancho, por lo que es una buena idea canalizar la salida a un archivo si está haciendo uno de cualquier tamaño. Aquí hay una consola 20x20:

20x20

Y un 100x100 en el bloc de notas ++ (tuve que alejarme para obtener todo, así que es algo ... pequeño ):

100x100

Código con saltos de línea:

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
fuente
2

ZX Basic - 281 caracteres

Este es más un laberinto "apropiado", menos golfista, pero más mazier. Llamado algoritmo de laberinto binario, cada celda puede tener una salida hacia abajo o hacia la derecha, pero no ambas. (Ahora incluye el inicio marcado "S" y el final "E", para evitar ir directamente a un lado).

El "::" es la forma en que ZXB ingresa los caracteres gráficos de Spectrum en un archivo de texto, equivale a un carácter de bloque 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"

Laberinto

Brian
fuente
2
No, en realidad quise decir que debería intercambiar el inicio y el final (inicio inferior derecha, final superior izquierda). Tal como es, es trivial, porque debido a las reglas solo tienes que bajar y corregir todo el tiempo para llegar al final.
Martin Ender
1
Incluso si el inicio y el final se invierten, el laberinto tiene la propiedad (quizás interesante) de que la ruta correcta solo se moverá hacia arriba y hacia la izquierda. Sin embargo, el laberinto ya no es trivial, porque hay muchos puntos en los que puede ir de dos maneras.
Kevin - Restablece a Mónica el
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;}

Así es como se ve:

Laberinto

Nota: esta solución está inspirada en el juego no confiable de nivel 8: en el bosque.

Mhmd
fuente