Maze Generation [geschlossen]

41

Ich weiß, dass es einen ähnlichen (alten) Thread gibt ( hier) ) , aber ich möchte ihn mit einigen Änderungen neu starten.

Das Ziel: Erstellen Sie ein zufällig aussehendes Labyrinth mit einem Algorithmus Ihrer Wahl und geben Sie das Labyrinth grafisch aus ( Anzahl der Ausdrucke).

  • Die Breite und Höhe bestimmen Sie.
  • Es sollte mindestens einen Weg von mindestens einem Eingang zu mindestens einem Ausgang geben.
  • Das Format des Labyrinths (wie Sie es anzeigen, Eingang (e) oder Ausgang (e) markieren) liegt ebenfalls bei Ihnen.
  • Je schöner, desto besser.
  • Trivial-Labyrinthe (z. B. leere Labyrinthe, Gitter-Labyrinthe, Labyrinthe der Größe 1x1) werden nicht empfohlen.
  • Zyklen im Labyrinth sind erlaubt und werden empfohlen, wenn das Ergebnis angemessen ist.
  • Sprachmissbrauch wird gefördert.
  • Das Labyrinth sollte einigermaßen zufällig aussehen (aber ein vollständig deterministischer (z. B. chaotischer) Algorithmus, der dies erzeugt, ist auch in Ordnung).

Bearbeiten: Der Hauptfokus liegt hier auf der kleinstmöglichen Implementierung. Ich möchte jedoch einen gewissen Spielraum innerhalb dieser Einschränkung einräumen, um den Glanz zu fördern. Ich habe absichtlich genau gelassen, welche "Merkmale" das Labyrinth offen hat, aber als grobe Richtlinie sollten Sie versuchen, die meiste Menge an Knall in das am wenigsten lexikalische Geld zu packen.

code-golf popularity-contest maze imallett
quelle
4
Auch "Je schöner, desto besser" scheint für eine Code-Golf-Herausforderung kaum greifbar (oder einfach irrelevant) zu sein. Vielleicht ist ein Beliebtheitswettbewerb die bessere Wahl, wenn Sie an schönen Ergebnissen interessiert sind.
Martin Ender
5
Also ist es wirklich Code-Golf oder eher ein Beliebtheitswettbewerb?
l0b0
2
Ein weiterer Vorschlag: Wenn Sie sowohl Kurzcodes als auch nette Labyrinthe anregen möchten, können Sie dies zu einer Code-Herausforderung machen und erklären, dass der Gewinner nach einer Punktzahl ausgewählt wird, die aus einer Mischung aus Codelänge und Aufwärtsstimmen besteht - obwohl dies der Fall ist Es liegt an Ihnen, die Gesamtpunktzahl für jede Antwort zu bestimmen, da die Angabe der aktuellen Anzahl der Stimmen im Beitrag ein wenig nutzlos ist.
Martin Ender
3
Ich denke, dass jede Antwort erklären sollte, was Eingänge und Ausgänge in jedem Labyrinth ausmacht (sowie, was eine Wand und was eine Passage ist), damit wir die 2. Kugel bewerten können.
LarsH
2
@Geobits Ich hätte nichts dagegen, aber daher mein Vorschlag, es tatsächlich zu einer Code-Herausforderung mit kombinierter Bewertung aus Codelänge und Stimmen zu machen. Das würde genau das fördern, was das OP will: Kurzcode für interessante Labyrinthe.
Martin Ender

Antworten:

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

(Erfordert ein Terminal mit 65 Zeichen) Erzeugt ein relativ zufälliges 31x31-Labyrinth mit einem garantierten Pfad vom Eingang zum Ausgang.

Beispielausgabe (mit simuliertem Terminal mit 65 Zeichen):

 ! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 
 !     !       !   !       !     !           !             !   ! 
 !!!!! !!! !!! ! !!! ! !!! ! !!! !!!!!!! !!! !!!!!!!!! !!! ! ! ! 
 !   !   !   ! !     ! ! ! ! ! ! !       !   !         !   ! ! ! 
 ! !!!!! !!! ! !!!!!!! ! ! ! ! ! ! !!!!!!! !!! ! !!!!!!! !!! ! ! 
 !     !     !         ! !   !   !     !   !   ! !     !   ! ! ! 
 ! !!! !!!!!!!!!!!!!!!!! !!!!! !!! !!! !!! ! ! !!! !!! !!! !!! ! 
 !   !         !     !   !     !     !   ! ! ! !     !   !   ! ! 
 !!!!!!!!!!! ! ! !!! !!! ! !!!!!!!!!!!!! ! !!! ! !!!!!!! !!! ! ! 
 !           !   !       ! !             !   !     !     !     ! 
 ! !!!!!!! !!!!!!! !!!!!!! ! !!!!!!!!!!!!!!! !!!!!!! !!!!!!!!!!! 
 ! !     ! !   !     !   ! !           !   !       ! !         ! 
 ! !!! ! ! ! ! !!!!!!! ! ! ! !!!!!!!!! ! ! !!!!!!! ! ! !!!!!!! ! 
 !   ! !   ! !       ! !   ! !         ! !       ! ! !   !   ! ! 
 !!! ! !!!!! !!!!!!! ! !!!!!!! !!!!!!!!! !!! !!!!! ! !!! ! !!! ! 
 !   !   ! ! !       !   !     !   !     ! !           ! !   ! ! 
 ! !!!!! ! ! ! !!!!!!!!! ! !!!!! !!! !!!!! !!!!!!!!!!! ! ! ! ! ! 
 ! !       ! !   !   !   ! !       ! !       !   !     ! ! ! ! ! 
 ! !!!!!!!!! !!! ! ! ! !!! !!!!!!! ! !!!!!!! ! ! !!!!!!! !!! ! ! 
 !             !   ! !   !       ! !     !   ! !             ! ! 
 !!!!!!!!!!!!!!!!!!! !!! !!!!!!! ! !!!!! ! !!! !!!!!!!!!!!!!!! ! 
 !               !   !   !       !         !   !     !   !     ! 
 ! !!!!!!!!!!!!! ! ! ! !!! !!!!!!! !!!!!!!!! !!! !!! !!! ! !!! ! 
 ! !   !       !   ! ! ! !     ! ! ! !     !     !   !   !   ! ! 
 ! ! ! !!!!! !!!!!!! ! ! ! !!! ! ! ! ! !!! !!!!!!! !!! !!!!! !!! 
 !   ! !   !       ! ! !     ! !     ! ! !     !   !       !   ! 
 !!!!! ! ! !!! !!! ! ! !!!!!!! !!!!!!! ! ! !!! ! !!!!!!!!! !!! ! 
 !     ! !   !   !   !       !       ! ! ! !   !   !         ! ! 
 ! !!!!! !!! !!! !!!!!!!!!!! !!!!!!! ! ! ! !!!!!!! ! !!!!!!! ! ! 
 !         ! !           !   !       ! ! !     !   ! !       ! ! 
 !!!!!!!!!!! !!!!!!!!!!! ! !!! !!!!!!! ! !!!!! ! !!! !!!!!!!!! ! 
 !         !     !     ! ! !       !   !     ! !     !         ! 
 ! !!!!!!! !!!!! ! !!! !!! !!!!!!! ! !!!!! ! ! !!!!! ! !!!!!!!!! 
 ! !     !     !   ! !   !       ! !       ! !       !         ! 
 ! ! !!! !!!!! ! !!! !!! !!!!!!! ! !!!!!!!!! !!!!!!!!!!!!!!!!! ! 
 !     !     ! !   !   ! !     ! !       !   ! !     !         ! 
 !!!!!!!!!!! ! !!! !!! ! ! ! !!! ! ! !!!!! !!! ! !!! ! !!!!!!! ! 
 !           ! !       !   ! !   ! !       !   ! ! ! !     !   ! 
 ! !!!!!!!!!!! !!!!!!!!!!!!! ! !!! !!!!!!!!!!! ! ! ! ! !!! ! !!! 
 !       !   !             ! ! ! !   !         ! !   !   ! ! ! ! 
 !!!!!!! !!! !!!!!!!!!!!!! ! ! ! !!! ! !!!!!!! ! !!! !!!!! ! ! ! 
 !       !         !     ! ! ! !   !   !     ! !   !       !   ! 
 ! !!!!!!! !!!!!!! ! !!!!! ! ! !!! !!!!!!! ! ! !!! !!!!!!!!!!!!! 
 !   !         ! !   !       ! !           ! !   !             ! 
 ! ! ! !!!!!!! ! ! !!! !!!!!!! ! !!!!!!!!!!! ! !!!!!!!!!!!!!!! ! 
 ! ! ! !     ! !   !   ! !     !   !   !     ! !               ! 
 ! ! !!! !!! ! !!!!! !!! ! !!!!! ! ! ! !!!!!!! ! !!!!!!!!!!!!! ! 
 ! !   !   ! !   !       !   !   !   !         ! !         !   ! 
 !!!!! !!! ! !!! ! !!!!!!!!! !!!!!!! !!!!!!!!!!! !!!!! !!!!! !!! 
 !     !   !   !   !       !       !       !   !     !       ! ! 
 ! !!!!! !!!!! !!!!! !!!!! !!!!!!! !!!!!!!!! ! !!!!! !!!!!!! ! ! 
 !           !     ! !   !   !   !           !   !   !     !   ! 
 ! !!!!!!!!! !!!!! ! !!! ! !!! ! !!!!!!!!!!!!!!! ! !!! !!! !!! ! 
 ! !     !       ! !     !     !     !         ! !       !   ! ! 
 !!! !!! !!!!!!!!! !!!!! !!!!!!!!! ! !!!!!!! !!! ! !!!!!!!!! ! ! 
 !   !     !   !   !   ! !       ! !         !   ! !         ! ! 
 ! !!!!!!! ! ! ! ! !!! ! !!!!!!! ! !!!!!!!!! ! !!!!! !!!!!!!!! ! 
 !       !   !   ! !   !         !   ! !   ! ! !     !       ! ! 
 ! !!!!! !!!!!!!!! ! !!!!!!!!!!! !!! ! ! ! ! ! ! !!!!! !!!!! ! ! 
 ! !     !           !         ! ! ! !   !   ! !   !   !     ! ! 
 ! ! !!!!!!!!!!!!!!!!! !!! !!!!! ! ! !!!!!!!!! !!! ! !!!!!!!!! ! 
 ! !                     !         !               !           ! 
 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !
Dendrobium
quelle
2
Du brauchst nicht mal int p,int c. p,cist genug ...
Chubakueno
Ah, danke für den Hinweis
Dendrobium
34

Mathematica, 144 132 Bytes

Seit Inception wissen wir alle, wie ein Labyrinth am effizientesten gezeichnet werden kann .

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 und Beispielausgabe:

Bildbeschreibung hier eingeben

Natürlich sind die Linien die Wände. Du bist der Minotaurus, der in der Mitte beginnt und aussteigen muss.

Martin Ender
quelle
4
Das ist hübsch und der Code ist kurz, aber ich würde sagen, es ist in Richtung des "trivialen Labyrinths" am Ende des Spektrums.
LarsH
2
Sie haben Recht, dass eine Vergrößerung die Trivialität nicht ändern würde. Der Punkt ist, dass das Lösen dieses Labyrinths ein linearer Prozess ist: An jedem Punkt können Sie schnell herausfinden, ob Sie die falsche Wendung eingeschlagen haben, ohne in tiefere Zweige "zurückkehren" zu müssen. Die Antworten von Ian und Aleph sind hingegen "echte" Labyrinthe: Sie können nicht auf diese lineare Weise gelöst werden. Da triviale Labyrinthe entmutigt sind, wäre ich versucht, diese abzustimmen, aber ich habe nicht genug Repräsentanten.
LarsH
1
@ LarsH Ja, da sind wir uns einig. Deshalb habe ich gesagt, es ist die "effizienteste" Art, ein Labyrinth zu zeichnen, nicht die "effektivste". ;) Trotzdem mag es einfach sein, aber ich glaube nicht, dass es in eine Kategorie mit ausgeschlossenen Kategorien wie "leer" oder "1x1" fällt. Natürlich liegt es im Ermessen des OP, diese Einreichung wegen ihrer Einfachheit zu disqualifizieren, aber solange er das nicht tut oder die Art der Herausforderung ändert, sehe ich keinen Anreiz, sie komplizierter / interessanter zu machen.
Martin Ender
1
@LarsH Abgesehen davon bin ich mir nicht sicher, ob es an ihren Algorithmen oder nur an einer Funktion der von ihnen geposteten Beispiele liegt, aber keine ihrer Antworten erforderte mehr als einmal ein Zurückverfolgen über die Tiefe "1" hinaus. Obwohl sie eine Menge Komplexität enthalten, ist alles in Pfaden, die sowieso irrelevant sind.
Martin Ender
1
Dieses Labyrinth ist meiner Meinung nach nicht trivial, auch wenn es einfach ist (und mein kreisförmiges Labyrinth darunter ist noch trivialer). Ich wollte eigentlich nur verhindern, dass Leinwand / Größe-1 / etc. "Labyrinth" 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);}

Hinweis: Oben habe ich Zeilenumbrüche hinzugefügt, damit sie auf die Seite passen. Erwartete Ausgabe (auf einem Terminal mit 80 Zeichen) (Anfang und Ende oben links beachten): Bildbeschreibung hier eingeben

imallett
quelle
8
@bwoebi MSPaint zur Rettung! IMAGE
Ceiling Gecko
6
Beachten Sie, dass ich beabsichtigte, den Pfad innerhalb der Pipes zu haben (wie hier) .
Imallett
1
@ IanMallett Ich denke, Ceiling Gecko war sich dessen bewusst, aber wenn Sie die linke Wand mit einer Farbe überfluten, erhalten Sie einen (nicht optimalen) Pfad entlang der linken Wand, bis Sie den Ausgang finden. ;)
Martin Ender
1
Wenn Sie Zeit haben, würde es mich interessieren, die nicht golfene Version dieses Codes zu sehen.
LarsH
4
Während du das geschrieben hast, warst du ein verblüffender Programmierer.
Totymedli
24

Mathematica, 134.130 Zeichen

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]

Matze

Tatsächlich können wir diesen Algorithmus verwenden, um aus jedem (ungerichteten) Graphen ein Labyrinth zu generieren.

Erstellen Sie beispielsweise ein Labyrinth aus dem Tourdiagramm des 8 * 8- Ritters ( KnightTourGraph[8,8]):

Ritter-Tour-Grafik

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
quelle
7
Schönes Labyrinth ... aber ich sehe keinen Eingang, der mit einem Ausgang verbunden ist ...?
Bwoebi
9
Ich glaube, die Idee ist, einen zufälligen Knoten (etwa oben links) als Eingang und einen anderen (unten rechts) als Ausgang auszuwählen. Mathematica stellt sicher, dass alle Knoten mit allen anderen Knoten verbunden sind. Insbesondere im zweiten Labyrinth ist es jedoch schwieriger, festzustellen, wie sie verbunden sind.
EagleV_Attnam
Sollen die Linien (Graphenkanten) Labyrinthwände oder Passagen sein? Ich dachte, ich wüsste es, aber jetzt bin ich mir nicht sicher.
LarsH
@ LarsH Sie sind Passagen.
Alephalpha
1
@LarsH Der Graph ist verbunden, so dass Sie nur zwei beliebige Knoten als Eingang und den anderen als Ausgang nehmen können.
Alephalpha
13

Bash, 53 Bytes

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

Ähnliche Idee zum C64-Code. Verwendet Unicode-Zeichen als Schrägstriche, da sie in einem Terminal, das Unicode unterstützt, viel besser aussehen. Beispielausgabe auf dem OS X-Terminal (Menlo-Schriftart):

Beispiel für eine Labyrinth-Ausgabe

nneonneo
quelle
2
Ich habe einmal diese herausgefunden : yes 'c=(╱ ╲);printf ${c[RANDOM%2]}'|bash. Sehen Sie diesen Beitrag
gniourf_gniourf
5
Dies basiert auf einem Algorithmus , der nicht garantiert, dass er lösbar ist, und der viele Jahre alt ist.
Isiah Meadows
9

JavaScript (ES6), 174

Dies ist der Labyrinthbauer, den ich in dieser anderen Herausforderung verwendet habe , nur Golf. Es ist eine Funktion mit 2 Parametern: Zeilen und Spalten. Das Labyrinth ist vollständig ohne Schleifen verbunden, sodass jeder Ort der Start- oder Endpunkt sein kann.

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

Beispiel

f(7,10)

Ausgabe

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

Prüfung

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>
Erweitern Sie das Snippet

edc65
quelle
Ich bin mir nicht sicher ... ist das Licht oder der dunkle Bereich das Labyrinth? Wenn es dunkel ist, hat es eine große Schleife und man kann einfach draußen bleiben, wenn man einen beliebigen Punkt als Ein- / Ausstiegspunkt wählt. Wenn das Licht, dann sollten Sie den Ausgang / Eingang hinzufügen.
Paŭlo Ebermann
1
@PaŭloEbermann es ist das licht natürlich, dunkle fläche sind die wände. Ich wiederhole mich: Das Labyrinth ist völlig ohne Schleifen verbunden, sodass jeder Ort der Start- oder Endpunkt sein kann
edc65 11.10.15
Wow das ist beeindruckend! Einige Bytes wurden rasiert und auf 133 Bytes reduziert : twitter.com/aemkei/status/889587308894326785 Aber alle Credits sollten an Sie gehen!
Aemkei
@aemkei 8 anstelle von '#', ich kann nicht glauben, dass ich das zur Zeit verpasst habe
edc65
8

ZX Basic - 54 Zeichen

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

Ausgabe

Hier ist das Labyrinth, das eine Route durch das Labyrinth zeigt (Leerzeichen zwischen den Linien)

Pfad

und ein kleiner Ausschnitt aus der Zeit, als ich dies zum ersten Mal tat (vor einigen Jahren) und ein bisschen Zeit damit verbrachte, bessere Grafiken zu machen.

bessere Grafik

Brian
quelle
2
Hm, frech. ^^ Was ist der Anfang und was ist das Ende dort? Und sind die Schrägstriche die Wege oder die Mauern? Und was ist die minimale Lückengröße, die ich passieren kann?
Martin Ender
2
"Es sollte mindestens einen Weg von mindestens einem Eingang zu mindestens einem Ausgang geben." Ich sehe keinen Hinweis darauf, dass dieses Kriterium erfüllt ist. Zufällige Wände erzeugen nicht unbedingt ein Labyrinth.
LarsH
1
@ m.buettner: Ich vermute, dass die Schrägstriche Wände sind und dass wir sie so darstellen sollen, als ob zwischen Zeilen und zwischen Spalten kein Abstand wäre. Die 2x2 Zeichen unten links bilden also eine vollständig geschlossene quadratische Form.
LarsH
@ LarsH Ja, das dachte ich mir. Das macht nur einen weiteren Punkt für Ihren Fall in der Frage des OP aus, dass die Leute angeben sollten, was Anfang und Ende sind. Dieses Schema erlaubt auch nicht einmal Kreuzungen. Sie können nur diese geschlossenen Quadrate oder Mäanderpfade haben (die auch geschlossene Schleifen sein können).
Martin Ender
+1 für die verbesserte Grafik und die Darstellung der Route. Bei so vielen möglichen Ein- und Ausgängen ist die Wahrscheinlichkeit, dass "mindestens ein Pfad von mindestens einem Eingang zu mindestens einem Ausgang führt", ziemlich hoch!
LarsH
8

BBC BASIC, 18 Bytes

Eine Längenverbesserung gegenüber der 23-Byte-C64-Endlosschleifenversion von @nneonneo. VDU sendet ein einzelnes Zeichen an den VDU-Controller: entweder 2 + 1 * 45 = ASCII 47 /oder 2 + 2 * 45 = ASCII 92\

  VDU2+RND(2)*45:RUN

BBC BASIC, 35 Bytes / 107 95 Bytes

35 Bytes sind nur für die letzte Zeile, was ein 25-Zeilen-Labyrinth in 40-Spalten-Layout ergibt. MODE1 stellt sicher, dass kein zusätzlicher Abstand zwischen den Zeilen verbleibt. Der Rest des Programms ist optional und verbessert die Formatierung. Die VDU23-Anweisungen definieren die Schriftart für die Zeichen 47 und 92 neu (8 Bytes bilden eine 8x8-Bitmap). Ich füge in allen vier Ecken ein helles Pixel ein, um zu verhindern, dass gerade Abläufe eingeklemmt werden. Der Nebeneffekt davon ist, dass ein Punkt in den leeren Diamanten erscheint. Insgesamt 107 Byte, einschließlich 2 Zeilenumbrüche.

  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

Das Editieren dieses Programms kann auf 95 Byte verkürzt werden, indem einige der 8-Bit-VDU-Codes in 16-Bit-Small-Endian-Werte (durch ein Semikolon nach ihnen anstelle eines Kommas gekennzeichnet) codiert und die MODE-Anweisung wie folgt als Paar von VDU-Codes dargestellt werden .

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

Ausgabe

Verwenden von BBC Basic für Windows von bbcbasic.co.uk

Letzte Zeile nur 35 Bytes

Bildbeschreibung hier eingeben

Gesamtes Programm, 107 95 Bytes

Wie ich @ Brians Antwort kommentierte, teilt der Schrägstrich das Quadrat in zwei dunkle Dreiecke, von denen jedes genau zwei Ein- / Ausgänge hat. Dies garantiert einen (trivialen, unverzweigten) Pfad von einem beliebigen Punkt am Rand des Labyrinths zu einem anderen Punkt am Rand des Labyrinths. Viele davon sind sehr kurz, aber es scheinen immer ein paar lange zu sein. Natürlich gibt es in der Mitte des Labyrinths auch einige Schleifen.

Da andere Antworten dies nicht erwähnt haben, möchte ich mir die hellen Bereiche genauer ansehen. Diese sind durch dunkle Bereiche begrenzt, daher berührt ein heller Bereich, der außen von N dunklen Bereichen begrenzt ist, den Rand des Feldes an N (genau so vielen) Punkten. Daher treten einige ziemlich große helle Bereiche auf, und diese bilden interessante, verzweigte Irrgärten.

Im folgenden Beispiel können Sie die Rohausgabe (Monochrom) aus meinem Programm sehen. Darunter habe ich (mit Windows Paint) die beiden längsten dunklen Bereiche blau eingefärbt. Dann habe ich den größten hellen Bereich gelb und die beiden blau umrandeten Bereiche rot und grün eingefärbt. Die gelben, grünen (und sogar die roten) Labyrinthe sind sehr interessant und nicht trivial.

Bildbeschreibung hier eingeben

EDIT - Automatische Auswahl von Labyrinthen und Starts / Ends

Für eine weitere Zeile (59 Zeichen) kann das Programm automatisch bis zu 6 Labyrinthe auswählen, indem Sie nach dem Zufallsprinzip Quadrate auswählen und die Farben Rot, Grün, Gelb, Blau, Magenta und Cyan füllen. Es wird nicht immer eine volle 6 gefunden, da es nichts tut, wenn es ein zufälliges Quadrat auswählt, das bereits gefärbt wurde.

Der Rest des Codes unten zeigt einen Anfang für jede Farbe, indem jede Spalte von oben nach unten und von links nach rechts gescannt wird und das erste Quadrat ausgewählt wird, auf das sie trifft. Es nimmt ein Ende, indem es in die entgegengesetzte Richtung scannt.

Dies erzeugt eine Reihe von farbenfrohen, ineinander verschlungenen Irrgärten. Manchmal sind sie so miteinander verflochten, als müssten sich die Irrgärten irgendwo kreuzen. Aber natürlich nicht!

Zusätzlicher Code und Ausgabe 59 + 187 = 246 zusätzliche Zeichen, die am Ende des ursprünglichen Programms hinzugefügt werden sollen (zur Verbesserung über die Frage-Spezifikation hinaus)

  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)

Bildbeschreibung hier eingeben

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

Hinweis: Oben habe ich Zeilenumbrüche hinzugefügt, damit sie auf die Seite passen. Erwartete Ausgabe (auf einem Terminal mit 80 Zeichen):Bildbeschreibung hier eingeben

Ich bedaure, dass dies kein sehr hartes Labyrinth ist (in der Tat ist kein Zurückverfolgen zu inneren Ringen erforderlich (und Sie sollten in der Lage sein, einen Pfad vom Umfang zum Zentrum zu finden). Es hat jedoch eine schöne Implementierung von Bresenhams Kreis Zeichnungsalgorithmus im Kern.

imallett
quelle
Es ist ein bisschen schwer zu erkennen, wo man hindurch kann und wo nicht. Ich muss sagen, ich habe die Pfeifen vorgezogen;) (sowohl diesem als auch meinem Rundschreiben vorgezogen).
Martin Ender
@m.buettner: da stimme ich eigentlich zu. Wenn Sie die Änderung i+=2an i+=3, könnte es klar sein , was passiert.
Imallett
6

Ich habe meinem Kind dabei geholfen, ein bisschen Programmieren zu lernen: http://jsfiddle.net/fs2000/4KLUC/34/ Wie gefällt es dir?

Giuseppe Strafforello
quelle
17
Wenn Sie Ihren Code in den Beitrag einpassen können, tun Sie das. Fügen Sie auch einen Header wie #Language (s) - Bytecount ein. Wenn Sie nur ASCII - Zeichen in Ihrem Code verwendet wird , kann man einen schönen bytecount bekommen hier . Eine Zusammenfassung der Funktionen Ihres Codes, etwaige Erkenntnisse oder clevere Dinge, die Sie getan haben, sind möglicherweise eine nette Ergänzung für Ihren Beitrag. Übrigens macht es Darth Vader sehr schwer, einige der Zeilen zu sehen. Endlich Willkommen bei Code Golf!
Rainbolt
Du hast mit deinen Kindern ein bisschen Programmieren gelernt und ich habe ein bisschen Golfen gelernt. Dies ist mein erstes Golfen und das Ergebnis ist noch ziemlich lang. Byteanzahl: Original: 55 + 6822 = 6877. Ein bisschen reorganisiert : 39 + 3131 = 3170 Golf : 39 + 1593 = 1632
BartekChom
6

Commodore 64 BASIC - 38 Bytes

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

Dies ist nicht meine Erfindung, ich wiederhole einfach ein sehr schönes und kurzes Programm vergangener Tage. Tatsächlich gibt es ein ganzes Buch, das 10 PRINT CHR$(205.5+RND(1)); : GOTO 10diesen Code feiert!

Sie können die Ausgabe auf diesem YouTube-Video sehen . Hier ist eine Screencap:

YouTube Screencap

Hier bei dieser StackOverflow-Frage sind weitere Implementierungen dieses Labyrinth-Generator-Programms. Die kürzeste Implementierung des Programms ist das folgende 23-Byte-C64-BASIC-Programm, das vom Autor dieser Frage veröffentlicht wurde:

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

Hier werden Kleinbuchstaben unverändert und Großbuchstaben mit der Umschalttaste eingegeben (diese werden auf einem tatsächlichen C64-Bildschirm unterschiedlich dargestellt).

nneonneo
quelle
Ist das nicht genau das gleiche Ergebnis von Brian? (nur ein bisschen kürzer) Und ist deine Bash-Antwort auch so? Dann ist auch hier die Frage, ob ein Labyrinth ohne Abzweigungen noch ein Labyrinth ist.
Martin Ender
nneonneo, +1 für die korrekte und ehrliche Zuschreibung dieser großartigen Idee. @ m.buettner Der unbedruckte Bereich erzeugt unverzweigte Labyrinthe, wie Sie betonen. Allerdings (und ich bin überrascht, dass noch niemand dies gezeigt hat) bildet der gedruckte Bereich einige interessante, nicht triviale, verzweigte Labyrinthe (siehe meine Antwort). Ich stimme auch Ihrem Labyrinth zu, da es den besten definierten Anfang und das beste Ende hat . Es ist nicht einfach, Start und Ende für diese diagonalen Irrgärten zu definieren.
Level River St
@ m.buettner 1. Die x86-Binärdatei ist nur 10 Byte klein. 2. Dies ist ein ausgereifter Algorithmus, der keineswegs originell ist und auch kein lösbares Labyrinth erzeugen soll.
Isiah Meadows
5

Java: 700

Hier ist ein rekursiver Wandaddierer. Der Algorithmus wird auf dieser Site beschrieben :

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

Grundsätzlich wird jedes Rechteck mit einer Wand (und einem Durchgang) in zwei Teile geteilt, dann werden die Rechtecke in zwei Teile geteilt usw. Es wird ein "perfektes" Labyrinth erzeugt - eines ohne Zyklen - das einen Pfad von jedem Punkt zu jedem anderen Punkt hat. Viele Sackgassen, daher ist es für größere Labyrinthe in keiner Weise "trivial".

So kann der Ein- und Ausgang beliebig entschieden werden. Wenn ich eine auswählen muss, heißt es einfach oben / links und unten / rechts.

Es wird in Ascii mit doppelter Breite gezeichnet, daher ist es eine gute Idee, die Ausgabe an eine Datei weiterzuleiten, wenn Sie eine Datei beliebiger Größe erstellen. Hier ist eine 20x20 in Konsole:

20x20

Und eine 100x100 in Notepad ++ (ich musste herauszoomen, um alles zu bekommen, also ist es etwas ... klein ):

100x100

Code mit Zeilenumbrüchen:

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

ZX Basic - 281 Zeichen

Dies ist eher ein "richtiges" Labyrinth, weniger golferisch, aber mehr fusselig. Sogenannter binärer Labyrinthalgorithmus, jede Zelle kann einen Ausgang haben, der nach unten oder rechts geht, aber nicht beides. (Enthält jetzt markierte Anfangsbuchstaben "S" und Endbuchstaben "E", um zu verhindern, dass man nur eine Seite entlang fährt).

Das "::" ist die Art und Weise, wie ZXB Spectrum-Grafikzeichen in eine Textdatei eingibt. Dies entspricht einem verkauften Blockzeichen.

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"

Matze

Brian
quelle
2
Nein, ich meinte eigentlich, dass Sie den Anfang und das Ende tauschen sollten (Anfang unten rechts, Ende oben links). Wie es aussieht, ist es trivial, denn aufgrund der Regeln muss man die ganze Zeit nach unten und nach rechts gehen, um das Ende zu erreichen.
Martin Ender
1
Selbst wenn Anfang und Ende vertauscht sind, hat das Labyrinth die (möglicherweise interessante) Eigenschaft, dass sich der richtige Pfad nur nach oben und links bewegt. Das Labyrinth ist jedoch nicht mehr trivial, da es viele Punkte gibt, an denen Sie einen von zwei Wegen gehen können.
Kevin - Reinstate 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;}

So sieht es aus:

Matze

Hinweis: Diese Lösung ist inspiriert vom nicht vertrauenswürdigen Spiellevel 8: in den Wald.

Mhmd
quelle