Generowanie labiryntu [zamknięte]

41

Wiem, że istnieje (stary) wątek podobny do tego ( tutaj ), ale chciałbym go ponownie uruchomić z pewnymi modyfikacjami.

Cel: wygenerować losowo wyglądający labirynt przy użyciu wybranego algorytmu, a następnie wyprowadzić labirynt graficznie (liczba wydruków się liczy).

  • Szerokość i wysokość są określane przez Ciebie.
  • Powinna istnieć co najmniej jedna ścieżka od co najmniej jednego wejścia do co najmniej jednego wyjścia.
  • Format labiryntu (sposób jego wyświetlania, oznaczania wejść lub wyjść) zależy również od Ciebie.
  • Im ładniejsze, tym lepiej.
  • Trywialne labirynty (np. Labirynty puste, labirynty kratowe, labirynty wielkości 1x1) są odradzane.
  • Cykle w labiryncie są dozwolone i są zachęcane, jeśli wynik jest rozsądny.
  • Zachęcanie do nadużywania języka.
  • Labirynt powinien wyglądać na dość losowy (ale całkowicie deterministyczny (np. Chaotyczny) algorytm, który to generuje, też jest w porządku).

Edycja: główny nacisk kładziony jest tutaj na jak najmniejszą implementację. Chcę jednak pozwolić sobie na pewną swobodę w ramach tego ograniczenia, aby zachęcić do lśnienia. Celowo pozostawiłem dokładnie to, co „cechy” labiryntu mają otwarte, ale jako ogólną wytyczną powinieneś spróbować spakować jak najwięcej huku w najmniej leksykalne pieniądze.

code-golf popularity-contest maze imallett
źródło
4
Również „Im ładniejsze, tym lepsze” wydaje się mało namacalne (lub po prostu nieistotne) dla wyzwania golfowego. Może konkurs popularności byłby lepszym wyborem, jeśli interesują Cię ładne wyniki.
Martin Ender
5
Czy to naprawdę jest golf golfowy, czy raczej konkurs popularności?
l0b0
2
Jako kolejna sugestia, jeśli chcesz zachęcić zarówno krótkie kody, jak i czyste labirynty, możesz uczynić z niego wyzwanie kodowe i zadeklarować, że zwycięzca zostanie wybrany na podstawie wyniku, który jest kombinacją długości kodu i głosów pozytywnych - chociaż będzie od ciebie zależy ustalenie łącznej liczby odpowiedzi na wszystkie odpowiedzi, ponieważ uwzględnienie aktualnej liczby głosów pozytywnych w poście jest nieco bezużyteczne.
Martin Ender
3
Myślę, że każda odpowiedź powinna wyjaśniać, co stanowi wejścia i wyjścia w każdym labiryncie (a także czym jest ściana i co to jest przejście), abyśmy mogli ocenić drugą kulę.
LarsH
2
@Geobits Nie miałbym nic przeciwko, ale stąd moja sugestia, aby uczynić to wyzwanie kodowe z połączonym ocenianiem na podstawie długości kodu i głosów. To by dokładnie zachęciło do tego, czego chce OP: krótki kod dla interesujących labiryntów.
Martin Ender

Odpowiedzi:

10

C: 265 253 bajtów

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

(Wymagany terminal z 65 znakami) Generuje stosunkowo losowy labirynt 31x31 z jedną gwarantowaną ścieżką od wejścia do wyjścia.

Przykładowe dane wyjściowe (z symulowanym terminalem o długości 65 znaków):

 ! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 
 !     !       !   !       !     !           !             !   ! 
 !!!!! !!! !!! ! !!! ! !!! ! !!! !!!!!!! !!! !!!!!!!!! !!! ! ! ! 
 !   !   !   ! !     ! ! ! ! ! ! !       !   !         !   ! ! ! 
 ! !!!!! !!! ! !!!!!!! ! ! ! ! ! ! !!!!!!! !!! ! !!!!!!! !!! ! ! 
 !     !     !         ! !   !   !     !   !   ! !     !   ! ! ! 
 ! !!! !!!!!!!!!!!!!!!!! !!!!! !!! !!! !!! ! ! !!! !!! !!! !!! ! 
 !   !         !     !   !     !     !   ! ! ! !     !   !   ! ! 
 !!!!!!!!!!! ! ! !!! !!! ! !!!!!!!!!!!!! ! !!! ! !!!!!!! !!! ! ! 
 !           !   !       ! !             !   !     !     !     ! 
 ! !!!!!!! !!!!!!! !!!!!!! ! !!!!!!!!!!!!!!! !!!!!!! !!!!!!!!!!! 
 ! !     ! !   !     !   ! !           !   !       ! !         ! 
 ! !!! ! ! ! ! !!!!!!! ! ! ! !!!!!!!!! ! ! !!!!!!! ! ! !!!!!!! ! 
 !   ! !   ! !       ! !   ! !         ! !       ! ! !   !   ! ! 
 !!! ! !!!!! !!!!!!! ! !!!!!!! !!!!!!!!! !!! !!!!! ! !!! ! !!! ! 
 !   !   ! ! !       !   !     !   !     ! !           ! !   ! ! 
 ! !!!!! ! ! ! !!!!!!!!! ! !!!!! !!! !!!!! !!!!!!!!!!! ! ! ! ! ! 
 ! !       ! !   !   !   ! !       ! !       !   !     ! ! ! ! ! 
 ! !!!!!!!!! !!! ! ! ! !!! !!!!!!! ! !!!!!!! ! ! !!!!!!! !!! ! ! 
 !             !   ! !   !       ! !     !   ! !             ! ! 
 !!!!!!!!!!!!!!!!!!! !!! !!!!!!! ! !!!!! ! !!! !!!!!!!!!!!!!!! ! 
 !               !   !   !       !         !   !     !   !     ! 
 ! !!!!!!!!!!!!! ! ! ! !!! !!!!!!! !!!!!!!!! !!! !!! !!! ! !!! ! 
 ! !   !       !   ! ! ! !     ! ! ! !     !     !   !   !   ! ! 
 ! ! ! !!!!! !!!!!!! ! ! ! !!! ! ! ! ! !!! !!!!!!! !!! !!!!! !!! 
 !   ! !   !       ! ! !     ! !     ! ! !     !   !       !   ! 
 !!!!! ! ! !!! !!! ! ! !!!!!!! !!!!!!! ! ! !!! ! !!!!!!!!! !!! ! 
 !     ! !   !   !   !       !       ! ! ! !   !   !         ! ! 
 ! !!!!! !!! !!! !!!!!!!!!!! !!!!!!! ! ! ! !!!!!!! ! !!!!!!! ! ! 
 !         ! !           !   !       ! ! !     !   ! !       ! ! 
 !!!!!!!!!!! !!!!!!!!!!! ! !!! !!!!!!! ! !!!!! ! !!! !!!!!!!!! ! 
 !         !     !     ! ! !       !   !     ! !     !         ! 
 ! !!!!!!! !!!!! ! !!! !!! !!!!!!! ! !!!!! ! ! !!!!! ! !!!!!!!!! 
 ! !     !     !   ! !   !       ! !       ! !       !         ! 
 ! ! !!! !!!!! ! !!! !!! !!!!!!! ! !!!!!!!!! !!!!!!!!!!!!!!!!! ! 
 !     !     ! !   !   ! !     ! !       !   ! !     !         ! 
 !!!!!!!!!!! ! !!! !!! ! ! ! !!! ! ! !!!!! !!! ! !!! ! !!!!!!! ! 
 !           ! !       !   ! !   ! !       !   ! ! ! !     !   ! 
 ! !!!!!!!!!!! !!!!!!!!!!!!! ! !!! !!!!!!!!!!! ! ! ! ! !!! ! !!! 
 !       !   !             ! ! ! !   !         ! !   !   ! ! ! ! 
 !!!!!!! !!! !!!!!!!!!!!!! ! ! ! !!! ! !!!!!!! ! !!! !!!!! ! ! ! 
 !       !         !     ! ! ! !   !   !     ! !   !       !   ! 
 ! !!!!!!! !!!!!!! ! !!!!! ! ! !!! !!!!!!! ! ! !!! !!!!!!!!!!!!! 
 !   !         ! !   !       ! !           ! !   !             ! 
 ! ! ! !!!!!!! ! ! !!! !!!!!!! ! !!!!!!!!!!! ! !!!!!!!!!!!!!!! ! 
 ! ! ! !     ! !   !   ! !     !   !   !     ! !               ! 
 ! ! !!! !!! ! !!!!! !!! ! !!!!! ! ! ! !!!!!!! ! !!!!!!!!!!!!! ! 
 ! !   !   ! !   !       !   !   !   !         ! !         !   ! 
 !!!!! !!! ! !!! ! !!!!!!!!! !!!!!!! !!!!!!!!!!! !!!!! !!!!! !!! 
 !     !   !   !   !       !       !       !   !     !       ! ! 
 ! !!!!! !!!!! !!!!! !!!!! !!!!!!! !!!!!!!!! ! !!!!! !!!!!!! ! ! 
 !           !     ! !   !   !   !           !   !   !     !   ! 
 ! !!!!!!!!! !!!!! ! !!! ! !!! ! !!!!!!!!!!!!!!! ! !!! !!! !!! ! 
 ! !     !       ! !     !     !     !         ! !       !   ! ! 
 !!! !!! !!!!!!!!! !!!!! !!!!!!!!! ! !!!!!!! !!! ! !!!!!!!!! ! ! 
 !   !     !   !   !   ! !       ! !         !   ! !         ! ! 
 ! !!!!!!! ! ! ! ! !!! ! !!!!!!! ! !!!!!!!!! ! !!!!! !!!!!!!!! ! 
 !       !   !   ! !   !         !   ! !   ! ! !     !       ! ! 
 ! !!!!! !!!!!!!!! ! !!!!!!!!!!! !!! ! ! ! ! ! ! !!!!! !!!!! ! ! 
 ! !     !           !         ! ! ! !   !   ! !   !   !     ! ! 
 ! ! !!!!!!!!!!!!!!!!! !!! !!!!! ! ! !!!!!!!!! !!! ! !!!!!!!!! ! 
 ! !                     !         !               !           ! 
 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !
Dendrobium
źródło
2
Nawet nie potrzebujesz int p,int c. p,cwystarczy ...
chubakueno
Ach, dzięki za zwrócenie na to uwagi
Dendrobium
34

Mathematica, 144 132 bajty

Od momentu powstania wszyscy znamy najskuteczniejszy sposób narysowania labiryntu .

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

Dane wyjściowe bez golfa i przykład:

wprowadź opis zdjęcia tutaj

Oczywiście linie to ściany. Jesteś minotaurem, który zaczyna się w centrum i musi się wydostać.

Martin Ender
źródło
4
To jest ładne, a kod jest krótki, ale powiedziałbym, że zmierza w kierunku końca „trywialnego labiryntu”.
LarsH
2
Masz rację, że powiększenie go nie zmieni trywialności. Chodzi o to, że rozwiązanie tego labiryntu jest procesem liniowym: w każdym momencie możesz szybko dowiedzieć się, czy skręciłeś w niewłaściwy sposób, bez konieczności „cofania się” w głębsze gałęzie. Z drugiej strony odpowiedzi Iana i Alepha są „prawdziwymi” labiryntami: nie można ich rozwiązać w taki liniowy sposób. Ponieważ trywialne labirynty są odradzane, skusiłbym się, aby zagłosować za tym, ale nie mam wystarczającej liczby przedstawicieli.
LarsH
1
@LarsH tak, zgadzamy się na to. Dlatego powiedziałem, że to najbardziej „efektywny” sposób narysowania labiryntu, a nie „najbardziej efektywny”. ;) Mimo wszystko może to być proste, ale nie sądzę, że należy do kategorii wykluczonych, takich jak „puste” lub „1x1”. Oczywiście OP jest w stanie zdyskwalifikować to zgłoszenie ze względu na jego prostotę, ale dopóki tego nie zrobi lub nie zmieni rodzaju wyzwania, nie widzę zachęty do uczynienia go bardziej skomplikowanym / interesującym.
Martin Ender
1
@LarsH to powiedziawszy, nie jestem pewien, czy jest to spowodowane ich algorytmami, czy tylko cechą poszczególnych opublikowanych przykładów, ale żadna z ich odpowiedzi nie wymagała cofania się poza głębokość „1” więcej niż jeden raz. Mimo że zawierają dużo złożoności, wszystko i tak jest nieistotne.
Martin Ender
1
Moim zdaniem ten labirynt nie jest trywialny, nawet jeśli jest łatwy (a mój okrągły labirynt poniżej jest jeszcze bardziej trywialny). Naprawdę chciałem po prostu zapobiec blank-canvas / size-1 / etc. „labirynt”.
imallett,
33

C: 364 bajtów

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

Uwaga: powyżej, dodałem nowe wiersze, aby zmieściły się na stronie. Oczekiwany wynik (na 80-znakowym terminalu) (nuty zaczynają się i kończą w lewym górnym rogu): wprowadź opis zdjęcia tutaj

imallett
źródło
8
@bwoebi MSPaint na ratunek! OBRAZ
Gekon sufitowy
6
Zauważ, że moim zamiarem było umieszczenie ścieżki wewnątrz rur (jak tutaj) .
imallett
1
@IanMallett Myślę, że Ceiling Gecko był tego świadomy, ale wypełnienie zalewowe lewej ściany kolorem daje (nieoptymalną) ścieżkę wzdłuż lewej ściany, aż znajdziesz wyjście. ;)
Martin Ender
1
Chciałbym zobaczyć wersję tego kodu bez gry w golfa, jeśli masz czas.
LarsH
4
Pisząc to, byłeś programistą-labiryntem.
totymedli
24

Mathematica, 134 130 znaków

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]

Labirynt

W rzeczywistości możemy użyć tego algorytmu do wygenerowania labiryntu z dowolnego (niekierowanego) wykresu.

Na przykład wygeneruj labirynt z wykresu trasy rycerskiej 8 * 8 ( KnightTourGraph[8,8]):

wykres trasy rycerskiej

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
źródło
7
Fajny labirynt… ale nie widzę żadnego wejścia, które byłoby połączone z wyjściem…?
bwoebi
9
Uważam, że pomysł polega na wybraniu losowego węzła (powiedzmy, górny lewy) jako wejścia i kolejnego (dolny prawy) jako wyjścia. Mathematica upewnia się, że wszystkie węzły są połączone ze wszystkimi innymi węzłami, ale - szczególnie w drugim labiryncie - znalezienie sposobu ich połączenia jest trudniejsze.
EagleV_Attnam
Czy linie (krawędzie wykresu) powinny być ścianami labiryntu, czy przejściami? Myślałem, że wiem, ale teraz nie jestem pewien.
LarsH
@LarsH Są to fragmenty.
alephalpha
1
@LarsH Wykres jest połączony, więc możesz wziąć dwa dowolne węzły, jeden jako wejście, a drugi jako wyjście.
alephalpha
13

Bash, 53 bajty

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

Podobny pomysł do kodu C64. Używa znaków Unicode jako ukośników, ponieważ wyglądają znacznie ładniej w terminalu obsługującym Unicode. Przykładowe dane wyjściowe na terminalu OS X (czcionka Menlo):

Próbka wyjścia labiryntu

nneonneo
źródło
2
Kiedyś zdobione to: yes 'c=(╱ ╲);printf ${c[RANDOM%2]}'|bash. Zobacz ten post
gniourf_gniourf
5
Jest to oparte na algorytmie, który nie może zagwarantować, że da się go rozwiązać, który ma wiele lat.
Isiah Meadows,
9

JavaScript (ES6), 174

To budowniczy labiryntu, którego użyłem w tym innym wyzwaniu , właśnie grałem w golfa. Jest to funkcja z 2 parametrami: wierszami i kolumnami. Labirynt jest całkowicie połączony bez pętli, więc dowolna lokalizacja może być punktem początkowym lub końcowym.

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

Przykład

f(7,10)

Wydajność

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

Test

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>
Rozwiń fragment kodu

edc65
źródło
Nie jestem pewien ... czy światło czy ciemność to labirynt? Jeśli ciemność, to ma dużą pętlę i można po prostu pozostać na zewnątrz, wybierając dowolny punkt jako punkt wejścia / wyjścia. Jeśli światło, to należy dodać wyjście / wpis.
Paŭlo Ebermann
1
@ PaŭloEbermann to oczywiście światło, ciemny obszar to ściany. Powtarzam się: labirynt jest całkowicie połączony bez pętli, więc dowolna lokalizacja może być punktem początkowym lub końcowym
edc65
WOW, to jest niesamowite! Ogoliłem trochę bajtów i sprowadziłem do 133 bajtów: twitter.com/aemkei/status/889587308894326785 Ale wszystkie kredyty powinny iść do ciebie!
aemkei
@aemkei 8 zamiast '#', nie mogę uwierzyć, że tego dnia przegapiłem
edc65
8

ZX Basic - 54 znaki

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

Wydajność

Oto labirynt pokazujący trasę przez nią (odstępy między liniami)

ścieżka

i mały fragment z pierwszej chwili (kilka lat temu) i spędziłem trochę czasu na ulepszaniu grafiki.

lepsza grafika

Brian
źródło
2
Hm, bezczelny. ^^ Jaki jest początek i koniec? I czy przecięcie ścieżek czy ścian? A jaki jest minimalny rozmiar szczeliny, przez który mogę przejść?
Martin Ender
2
„Powinna istnieć co najmniej jedna ścieżka od co najmniej jednego wejścia do co najmniej jednego wyjścia”. Nie widzę żadnych oznak, że to kryterium jest spełnione. Losowe ściany niekoniecznie tworzą labirynt.
LarsH
1
@ m.buettner: Zgaduję, że ukośniki są ścianami i że powinniśmy to sobie wyobrazić, jak gdyby między wierszami i między kolumnami była zerowa przestrzeń. Tak więc lewe dolne znaki 2x2 tworzą całkowicie zamknięty kształt rombu (kwadratu).
LarsH
@ LarsH tak, tak myślałem. To tylko kolejny argument w sprawie OP dotyczącej tego, że ludzie powinni wskazać, jaki jest początek i koniec. Ponadto ten schemat nie pozwala nawet na skrzyżowania. Możesz mieć tylko te zamknięte kwadraty lub wijące się ścieżki (które mogą być również zamkniętymi pętlami).
Martin Ender
+1 za ulepszoną grafikę i wyświetlanie trasy. Wydaje mi się, że biorąc pod uwagę tyle potencjalnych wejść i wyjść, prawdopodobieństwo posiadania „co najmniej jednej ścieżki z co najmniej jednego wejścia do co najmniej jednego wyjścia” jest dość wysokie!
LarsH
8

BBC BASIC, 18 bajtów

Poprawiono długość 23-bajtowej wersji nieskończonej pętli C64 autorstwa @nneonneo. VDU wysyła pojedynczy znak do kontrolera VDU: albo 2 + 1 * 45 = ASCII 47, /albo 2 + 2 * 45 = ASCII 92\

  VDU2+RND(2)*45:RUN

BBC BASIC, 35 bajtów / 107 95 bajtów

35 bajtów jest tylko dla ostatniej linii, co daje labirynt o 25 rzędach w układzie 40 kolumn. MODE1 zapewnia, że ​​między wierszami nie pozostanie żadna dodatkowa przestrzeń. Pozostała część programu jest opcjonalna i poprawia formatowanie. Instrukcje VDU23 redefiniują czcionkę dla znaków 47 i 92 (8 bajtów tworzących bitmapę 8 x 8). Zawieram lekki piksel we wszystkich czterech rogach, aby nie dopuścić do zerwania prostych przebiegów. Efektem ubocznym jest to, że kropka pojawia się w pustych diamentach. Łącznie 107 bajtów, w tym 2 nowe znaki.

  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

Edytuj ten program można skrócić do 95 bajtów, kodując niektóre 8-bitowe kody VDU do 16-bitowych małych wartości endianowych (oznaczonych średnikiem po nich zamiast przecinkiem) i reprezentując instrukcję MODE jako parę kodów VDU, w następujący sposób .

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

Wydajność

Korzystanie z BBC Basic dla Windows z bbcbasic.co.uk

Tylko ostatni wiersz, 35 bajtów

wprowadź opis zdjęcia tutaj

Cały program, 107 95 bajtów

Jak skomentowałem odpowiedź @ Briana, ukośnik dzieli kwadrat na 2 ciemne trójkąty, z których każdy ma dokładnie 2 wejścia / wyjścia. To gwarantuje (trywialną, nierozgałęzioną) ścieżkę z dowolnego punktu na skraju labiryntu do innego punktu na krawędzi labiryntu. Wiele z nich jest bardzo krótkich, ale zawsze wydaje się, że jest kilka długich. Oczywiście na środku labiryntu są też pętle.

Ponieważ inne odpowiedzi o tym nie wspominały, chciałbym dobrze przyjrzeć się jasnym obszarom. Są one ograniczone ciemnymi obszarami, dlatego w następstwie powyższego stwierdzenia jasny obszar ograniczony zewnętrznie przez N ciemnych obszarów dotyka krawędzi pola w punktach N (dokładnie tyle). Dlatego pojawiają się dość duże jasne obszary, które tworzą interesujące, rozgałęzione labirynty.

W poniższym przykładzie możesz zobaczyć surowe wyjście (monochromatyczne) z mojego programu. Poniżej (używając Windows Paint) dwa najdłuższe ciemne obszary pokolorowałem na niebiesko. Następnie pokolorowałem największy jasny obszar na żółto, a dwa obszary ograniczone przez niebieski na czerwono i zielono. Żółte, zielone (a nawet czerwone) labirynty są dość interesujące i nietrywialne.

wprowadź opis zdjęcia tutaj

EDYCJA - Automatyczne wybieranie labiryntów i wybór początku / końca

Dla jeszcze jednej linii (59 znaków) program może automatycznie wybrać do 6 labiryntów, wybierając losowo kwadraty i zalewając kolory: czerwony, zielony, żółty, niebieski, magenta i cyjan. Nie zawsze znajduje pełne 6, ponieważ jeśli wybierze losowy kwadrat, który został już pokolorowany, nic nie robi.

Pozostała część kodu poniżej określa początek każdego koloru, skanując każdą kolumnę od góry do dołu oraz od lewej do prawej i wybierając pierwszy napotkany kwadrat. Wybiera koniec, skanując w przeciwnym kierunku.

To tworzy zestaw kolorowych, splecionych labiryntów. Czasami są tak splecione, że wygląda na to, że labirynty muszą gdzieś przejść. Ale oczywiście nie!

Dodatkowy kod i wynik 59 + 187 = 246 dodatkowych znaków, które należy dodać na końcu oryginalnego programu (w celu rozszerzenia poza specyfikację pytań)

  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)

wprowadź opis zdjęcia tutaj

Level River St
źródło
7

C: 235 bajtów

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

Uwaga: powyżej, dodałem nowe wiersze, aby zmieściły się na stronie. Oczekiwany wynik (na terminalu 80-znakowym):wprowadź opis zdjęcia tutaj

Żałuję, że nie jest to zbyt trudny labirynt (w rzeczywistości nie jest wymagane cofanie się do pierścieni wewnętrznych (i powinieneś być w stanie znaleźć ścieżkę od obwodu do centrum w sposób trywialny). Jednak ma fajną implementację koła Bresenhama algorytm rysowania w jego rdzeniu.

imallett
źródło
Trochę trudno zobaczyć, gdzie można przejść, a gdzie nie. Muszę powiedzieć, że wolałem rury;) (zarówno od tego, jak i od mojego okólnika).
Martin Ender
@ m.buettner: Zgadzam się. Jeśli zmienisz i+=2się i+=3, może to być bardziej jasne, co się dzieje.
imallett
6

Pomogłem mojemu dziecku to zrobić, nauczyć się programowania: http://jsfiddle.net/fs2000/4KLUC/34/ jak ci się podoba?

Giuseppe Strafforello
źródło
17
Jeśli możesz zmieścić kod w poście, zrób to. Dołącz także nagłówek taki jak #Language (s) - Bytecount. Jeśli używałeś tylko znaków ASCII w swoim kodzie, możesz uzyskać ładny bajt tutaj . Podsumowanie tego, co robi Twój kod, wszelkie spostrzeżenia, które posiadasz, lub wszelkie sprytne rzeczy, które zrobiłeś, mogą być miłym dodatkiem do twojego postu. Nawiasem mówiąc, Darth Vader bardzo utrudnia dostrzeżenie niektórych linii. Wreszcie, Witamy w Code Golf!
Rainbolt
Nauczyłeś się trochę programowania z dziećmi, a ja nauczyłem się grać w golfa. To jest mój pierwszy golf i wynik jest wciąż dość długi. Liczba bajtów: Oryginalny: 55 + 6822 = 6877. Trochę zreorganizowany : 39 + 3131 = 3170 Gra w golfa : 39 + 1593 = 1632
BartekChom
6

Commodore 64 BASIC - 38 bajtów

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

To nie jest mój wynalazek, po prostu powtarzam bardzo piękny i krótki program z minionych dni. W rzeczywistości istnieje cała książka o nazwie 10 PRINT CHR$(205.5+RND(1)); : GOTO 10świętująca ten fragment kodu!

Możesz zobaczyć wynik na tym filmie na YouTube ; oto zrzut ekranu:

Screencap YouTube

Tutaj, w tym pytaniu StackOverflow, znajduje się więcej implementacji tego programu do generowania labiryntów. Najkrótszą implementacją programu jest następujący 23-bajtowy program C64 BASIC opublikowany przez autora tego pytania:

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

gdzie małe litery są wprowadzane bez zmian, a wielkie litery są wprowadzane za pomocą klawisza Shift (mają one inny wygląd na rzeczywistym ekranie C64).

nneonneo
źródło
Czy to nie jest dokładnie to samo oświadczenie Briana? (tylko trochę krócej). A więc twoja odpowiedź na Bash? Zatem pytanie również brzmi: czy labirynt bez skrzyżowań jest nadal labiryntem?
Martin Ender
nneonneo, +1 za prawidłowe i uczciwe przypisanie tego wspaniałego pomysłu. @ m.buettner Niezadrukowany obszar wytwarza nierozgałęzione labirynty, jak wskazałeś. Jednak (i ​​jestem zaskoczony, że nikt jeszcze tego nie pokazał) drukowany obszar tworzy ciekawe, nietrywialne, rozgałęzione labirynty (patrz moja odpowiedź). Poprawiam również twój labirynt, ponieważ ma najlepiej zdefiniowany początek i koniec . Zdefiniowanie początku i końca tych ukośnych labiryntów nie jest łatwe.
Level River St
@ m.buettner 1. Plik binarny x86 ma tylko 10 bajtów w najmniejszym rozmiarze. 2. Jest to dobrze dopracowany algorytm i wcale nie jest oryginalny, ani nie miał na celu stworzenia rozwiązanego labiryntu.
Isiah Meadows,
5

Java: 700

Oto rekursywny dodatek do ściany. Algorytm jest opisany na tej stronie :

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

Zasadniczo dzieli każdy prostokąt na pół ścianą (i przejściem), a następnie dzieli je na dwie części itp. Generuje „idealny” labirynt - jeden bez cykli - który ma ścieżkę z każdego punktu do każdego innego punktu. Mnóstwo ślepych zaułków, więc nie jest w żadnym sensie „trywialna” dla większych labiryntów.

Tak więc wejście i wyjście można ustalić dowolnie. Jeśli będę musiał wybrać jeden, powie tylko górny / lewy i dolny / prawy.

Jest rysowany w ascii o podwójnej szerokości, więc dobrym pomysłem jest przesyłanie danych wyjściowych do pliku, jeśli wykonujesz dowolną dowolną wielkość. Oto konsola 20x20:

20x20

I 100x100 w notatniku ++ (musiałem pomniejszyć, aby dostać wszystko, więc jest trochę ... mały ):

100 x 100

Kod z podziałem wiersza:

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;
    }
}
Geobity
źródło
2

ZX Basic - 281 znaków

To bardziej „właściwy” labirynt, mniej golfisty, ale bardziej mazera. Tak zwany algorytm Binary labirynt, każda komórka może mieć wyjście schodzące lub w prawo, ale nie jedno i drugie. (Teraz zawiera oznaczony Początek „S” i Koniec „E”, aby zapobiec prostemu poruszaniu się po jednej stronie).

„::” to sposób wprowadzania znaków graficznych Spectrum do pliku tekstowego przez ZXB, co odpowiada sprzedanemu znakowi blokowemu.

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"

Labirynt

Brian
źródło
2
Nie, właściwie to znaczyłem, że powinieneś zamienić początek i koniec (początek dolny prawy, koniec górny lewy). Ponieważ jest to trywialne, ponieważ z powodu zasad musisz po prostu zejść cały czas w prawo, aby dojść do końca.
Martin Ender
1
Nawet jeśli początek i koniec są odwrócone, labirynt ma (być może interesującą) właściwość polegającą na tym, że poprawna ścieżka przesunie się tylko w górę i w lewo. Labirynt nie jest już trywialny, ponieważ istnieje wiele punktów, w których można przejść na dwa sposoby.
Kevin - Przywróć Monikę
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;}

Oto jak to wygląda:

Labirynt

Uwaga: to rozwiązanie jest inspirowane niezaufanym poziomem gry 8: w lesie.

Mhm
źródło