Generowanie labiryntów obrazu

20

Wyzwanie

Napisz program / funkcję, która akceptuje „obraz” i generuje labirynt obrazkowy utworzony z tego obrazu.

Wejście

Twój program powinien zaakceptować dwa argumenty:

  • Ja, obraz, z którego tworzy się labirynt
  • S, boolean określający, czy wyświetlić rozwiązanie labiryntu

Otrzymuję w następującej formie:

.......
.#####.
.#####.
#######
.#####.
.#####.
.......

gdzie #są komórki, które mają zostać uwzględnione w ścieżce rozwiązania ., a komórki to komórki, które należy wykluczyć. Możesz zamienić się z .„s, #” s, a nowe linie z jakiegokolwiek charakteru swojego wyboru, o ile różnią się one od siebie. Alternatywnie możesz zaakceptować rzeczywistą bitmapę obrazu wejściowego.

Wynik

Powstały labirynt powinien mieć następującą formę:

###############
#             #
# ### ####### #
# #.........# #
# #.#######.# #
# #.#.......# #
###.#.#########
....#.#........
#####.#.#######
#  ...#.....  #
# #.#######.# #
# #.........# #
# ####### ### #
#   #       # #
###############

gdzie #„ściany .” oznaczają części ścieżki, które są częścią rozwiązania, a spacje są ścieżkami wykluczonymi z rozwiązania. Te .mogą być zastąpione spacjami, jeśli S jest fałszem. Znaki mogą zostać zamienione na inne wybrane przez ciebie postacie lub możesz wydrukować rzeczywistą mapę bitową labiryntu z podświetlonym rozwiązaniem.

Dodatkowe Szczegóły

  • Ścieżki muszą mieć szerokość jednej komórki (ścieżka nie może mieć gigantycznej puli pustej przestrzeni)
  • Labirynt nie może zawierać żadnych pętli
  • Labirynt musi być w pełni połączony (wszystkie komórki muszą być dostępne od wejścia / wyjścia)
  • Labirynt musi być otoczony murami (chyba że jest to wejście / wyjście)
  • Ścieżka rozwiązania nie może zawierać ślepych zaułków
  • Musi być dokładnie 1 wejście i 1 wyjście do labiryntu
  • Wejście i wyjście musi być wyrównane do krawędzi siatki i przylegać do komórki znajdującej się na ścieżce rozwiązania
  • Możesz wybrać miejsce wejścia i wyjścia
  • Możesz założyć, że z danego obrazu wejściowego można utworzyć prawidłową ścieżkę

(Dodano w celu wyjaśnienia) Poniższy schemat pokazuje, w jaki sposób ścieżka rozwiązania jest skorelowana z obrazem wejściowym:

Input (I): |    Output:            |    Corresponding Cells: 
           |                       |    (@'s denote #'s from I)
           |                       |
.......    |    ###############    |    ###############
.#####.    |    #             #    |    #             #
.#####.    |    # ### ####### #    |    # ### ####### #
#######    |    # #.........# #    |    # #@.@.@.@.@# #
.#####.    |    # #.#######.# #    |    # #.#######.# #
.#####.    |    # #.#.......# #    |    # #@#@.@.@.@# #
.......    |    ###.#.#########    |    ###.#.#########
           |    ....#.#........    |    .@.@#@#@.@.@.@.
           |    #####.#.#######    |    #####.#.#######
           |    #  ...#.....  #    |    #  @.@#@.@.@  #
           |    # #.#######.# #    |    # #.#######.# #
           |    # #.........# #    |    # #@.@.@.@.@# #
           |    # ####### ### #    |    # ####### ### #
           |    #   #       # #    |    #   #       # #
           |    ###############    |    ###############
           |                       |

Przypadki testowe

Przykład konewki z Wikipedii :

Wejście:

..................
..................
.......####.......
......##..##......
.....##....##....#
.....#......#...##
.#############.##.
##..############..
#...###########...
#...##########....
#...##########....
#...##########....
#...##########....
....##########....
....##########....
....##########....
..................
..................

Dane wyjściowe (S = fałsz):

#####################################
#   #     #   #   #     #           #
# ### ### ### # # ##### ### ### ### #
#     # #   # # #         # #   # # #
# ### # ##### # ########### # ### # #
# # #         #           # # #   # #
# # # ### ##### # ### ### # ### ### #
#   # # #   #   # # #   # #   # #   #
# ### # ##### ##### ### ##### # # ###
# #   #       #   #   #       # # #  
### ####### ### ### # ### ##### ### #
#   #     # #   #   #   # #   # #   #
# ### ##### # ### ####### # # # # # #
# #       #             #   # #   # #
# # ##### ############# ### ### ### #
#   #   #       #     #   # #   # # #
# ### # ####### # ### ### # # ### # #
# # # #         #   # #   #   #     #
# # # ### ######### # # ##### # #####
# #   # # #       # #   #   # # #   #
# ##### # # ##### # ##### # # ### # #
#       # #   #   # #     # #   # # #
# ### ### ### # ### # ##### ####### #
#   # # #     # #   # #       #     #
# # # # ####### # ### # ##### # ### #
  # # # #   #   #     #     # #   # #
### # # # # # ############# # ### # #
#   # # # #   #         #   # #   # #
##### # # ##### ####### # ### ##### #
#     # # #   #       # #   #       #
##### # # # # ####### # ### #########
#     #     #         #       #     #
# ### ######### ############# # #####
# # #   #     # #       #     #     #
# # ######### # ####### ####### ### #
#             #                 #   #
#####################################

Dane wyjściowe (S = prawda):

#####################################
#   #     #   #   #     #           #
# ### ### ### # # ##### ### ### ### #
#     # #   # # #         # #   # # #
# ### # ##### # ########### # ### # #
# # #         #.......    # # #   # #
# # # ### #####.# ###.### # ### ### #
#   # # #   #...# # #...# #   # #   #
# ### # #####.##### ###.##### # # ###
# #   #    ...#   #   #...    # # #..
### #######.### ### # ###.##### ###.#
#   #     #.#   #   #   #.#   # #...#
# ### #####.# ### #######.# # # #.# #
# #.......#.............#...# #...# #
# #.#####.#############.###.###.### #
#...#   #.......#.....#...#.#...# # #
#.### # #######.#.###.###.#.#.### # #
#.# # #  .......#...#.#...#...#     #
#.# # ###.#########.#.#.##### # #####
#.#   # #.#.......#.#...#...# # #   #
#.##### #.#.#####.#.#####.#.# ### # #
#.      #.#...#...#.#.....#.#   # # #
#.### ###.###.#.###.#.#####.####### #
#.  # # #.....#.#...#.#.....  #     #
#.# # # #######.#.###.#.##### # ### #
..# # # #...#...#.....#.....# #   # #
### # # #.#.#.#############.# ### # #
#   # # #.#...#.........#...# #   # #
##### # #.#####.#######.#.### ##### #
#     # #.#...#.......#.#...#       #
##### # #.#.#.#######.#.###.#########
#     #  ...#.........#.....  #     #
# ### ######### ############# # #####
# # #   #     # #       #     #     #
# # ######### # ####### ####### ### #
#             #                 #   #
#####################################

Przykład mapy bitowej (taki sam labirynt jak powyżej):

Dane wejściowe: Dane Wprowadź bitmapęwyjściowe (S = fałsz): Dane Wyjściowe rozwiązanie bitmapy nie jest podświetlonewyjściowe (S = prawda):Podświetlone rozwiązanie bitmapy wyjściowej

code-golf  ascii-art  graphical-output  path-finding  maze 
— Dendrobium
źródło
4
Może to tylko ja, ale nie widzę obrazu wejściowego w labiryncie wyjściowym.
— Mike Bufardeci
@ mike-bufardeci Dodano schemat pokazujący obraz wejściowy w labiryncie wyjściowym. Mam nadzieję, że to pomaga!
— Dendrobium
2
Wydaje się, że nie ma reguły wymagającej połączenia labiryntu. Czy byłoby to prawidłowe rozwiązanie? Wydaje się również, że nie ma zasady, że siatka musi być otoczona ścianami (chyba że każda nie-ściana jest uważana za wejście lub wyjście). Czy byłoby to prawidłowe rozwiązanie?
— Martin Ender
1
Dodaj także więcej przypadków testowych.
— flawr
@ MartinBüttner Labirynt powinien być w pełni połączony i otoczony murami, zredagował pytanie wyjaśniające te kwestie.
— Dendrobium

Odpowiedzi:

10

Python 3, 1599 bajtów

Uważam, że jest to fajny projekt i bardzo interesujący (i nieco długi). Kiedy to zobaczyłem, przypomniałem sobie lato, które spędziłem wyłącznie na pisaniu i ulepszaniu algorytmu generowania labiryntu i od razu zacząłem nad tym pracować.

Po chwili miałem początkowy szkic o długości około 6000 bajtów i następne kilka godzin spędziłem na kondensowaniu go w następujący program:

import math,random;R=range;L=len;T=sorted;P=print;N=random.randint
def M(I,S):
 I=I.rsplit('\n');s=[0]*(1+L(I[0])*2);G=[s]
 for i in R(L(I)):
  r=[0]
  for x in I[i]:r+=x,0
  G+=[r];s=[0]*(1+L(I[0])*2);G+=[s]
 c=E(G,L(G[0])-2,-2);G[c][L(G[0])-1]=1;e=[c,L(G[0])-2];c=E(G,1,2);G[c][0]=1;G[c][1]=1;s=[c,1]
 while s!=e:
  o=[];Q(G,s,e,-2,0,o,0);Q(G,s,e,0,2,o,1);Q(G,s,e,2,0,o,2);Q(G,s,e,0,-2,o,3);o=T(o,key=lambda x:(x[2],-x[1]))[0][0]
  if o==0:G[s[0]-1][s[1]]=1;s[0]-=2
  elif o==1:G[s[0]][s[1]+1]=1;s[1]+=2
  elif o==2:G[s[0]+1][s[1]]=1;s[0]+=2
  else:G[s[0]][s[1]-1]=1;s[1]-=2
  G[s[0]][s[1]]=1
 s=0
 while not s:
  r=N(1,(L(G)-1)/2)*2-1;c=N(1,(L(G[0])-1)/2)*2-1
  if G[r][c]in[1,2]:
   o=[];F(G,r-2,c,o,0);F(G,r,c+2,o,1);F(G,r+2,c,o,2);F(G,r,c-2,o,3)
   try:
    if o[0]==0:G[r-1][c]=2;G[r-2][c]=2
    elif o[0]==1:G[r][c+1]=2;G[r][c+2]=2
    elif o[0]==2:G[r+1][c]=2;G[r+2][c]=2
    else:G[r][c-1]=2;G[r][c-2]=2
   except:0
  s=1
  for x in G:
   if'.'in x:s=0;break
 *s,='#  '
 if S:s[1]='.'
 for x in G:
  for y in x:P(s[y],end='')
  P()
def Q(G,s,e,x,y,o,a,n=0):
 c=lambda x,y:G[s[0]+x][s[1]+y]is'#'
 try:
  if c(x,y):
   try:n+=c(2*x,2*y)
   except:0
   try:n+=c(x+abs(x)-2,y+abs(y)-2)
   except:0
   try:n+=c(x-abs(x)+2,y-abs(y)+2)
   except:0
   o+=[[a,math.sqrt((s[0]+x-e[0])**2+(s[1]+y-e[1])**2),n]]
 except:0
def F(G,r,c,o,a):
 try:
  if G[r][c] is'.':o+=[a]
 except:0
def E(G,y,z,d='#'):
 c=[]
 for x in R(1,L(G)-1,2):
  n=0
  try:n+=G[x-2][y]==d
  except:0
  try:n+=G[x+2][y]==d
  except:0
  n+=G[x][y+z]==d
  if G[x][y]==d:c+=[[x,n]]
 if L(c)>1:c=T(c,key=lambda x:x[1])
 return c[0][0]

To, co jest równie niesensowne, jak labirynt ascii-art, to ...

Warto zauważyć, że ponieważ funkcja losowa nie jest używana, dopóki nie zostanie znaleziona poprawna ścieżka, bez względu na to, ile razy podano takie same dane wejściowe, trasa od początku do końca będzie taka sama i, podczas gdy ten program robi pracując nad powyższymi przykładami, czasami nie będzie w stanie znaleźć rozwiązania, jeśli „wpędzi się w ścianę”, że tak powiem.

Podczas uruchamiania powyższych przykładów daje to:

>>> M('''.......
.#####.
.#####.
#######
.#####.
.#####.
.......''',True)
###############
# # #   # #   #
# # # ### # # #
# #...#.....# #
# #.#.#.###.###
#  .#.#.#...# #
###.#.#.#.### #
....#.#.#.#....
# ###.#.#.#.###
# #...#.#.#.  #
# #.###.#.#.# #
# #.....#...# #
### ####### # #
#         # # #
###############
>>>

to:

>>> M('''..................
..................
.......####.......
......##..##......
.....##....##....#
.....#......#...##
.#############.##.
##..############..
#...###########...
#...##########....
#...##########....
#...##########....
#...##########....
....##########....
....##########....
....##########....
..................
..................''',False)
#####################################
# #     #   # # #   # #   # # # # # #
# ### ##### # # # ### # ### # # # # #
#   # # #   #   # # # #   # # #   # #
### # # ### # ### # # # ### # ### # #
# #     #   # #         # # # # # # #
# ### ##### # # ##### ### # # # # # #
# # #   #   #     # #   # # # # # # #
# # # ##### # ##### ### # # # # # # #
# # # #         # # #         #      
# # # # # # ##### # ### # ######### #
# #   # # # #   # # # # # # # # #   #
# # ####### # ### # # ### # # # # # #
#         # #           #   #     # #
### ##### # # ######### ### ### ### #
#     #   # # #   #   #     #   # # #
# ### ### # # # # # # ####### ### # #
#   # #   # # # # # # #   #       # #
# ##### # # # # # # # # # # # ##### #
#   #   # # # # # # # # #   #     # #
# ####### # # # # # # # #############
#   #     # # # # # # #         #   #
# ####### # # # # # # ##### ##### # #
#   #     # # # # # #           # # #
# ### ### # # # # # ######### ### ###
    # #   # # # # #         #   #   #
# ### # # # # # # ######### ##### ###
#   # # # # # # #                 # #
# # # ### # # # ################### #
# # # # # # # #               #     #
# ### # # # # ############# ### ### #
# # # #     #                     # #
# # ##### # # # ##### # # ##### ### #
# # #     # # #     # # #     #   # #
### ##### # ### # # # ##### # ### # #
#         #   # # # #     # #   # # #
#####################################
>>>

i to:

>>> M('''..................
..................
.......####.......
......##..##......
.....##....##....#
.....#......#...##
.#############.##.
##..############..
#...###########...
#...##########....
#...##########....
#...##########....
#...##########....
....##########....
....##########....
....##########....
..................
..................''',True)
#####################################
#     #     # #   # # # # # # #     #
##### # # ### ### # # # # # # ### # #
# # # # # # # #     # # # # # # # # #
# # # ### # # ##### # # # # # # # ###
#   # #   # # #.......# #     #   # #
### # ### # # #.#####.# # ####### # #
#   # #   # #...#   #...#   # #   # #
### # ### # #.# # ### #.# ### ### # #
# # # # # #...# #   # #...  # #   #..
# # # # # #.# ### #######.### ### #.#
# #     #  .# #   # # #  .    # #...#
# # #######.##### # # ###.##### #.# #
#  .......#.#...........#...# #...# #
###.# ###.#.#.#########.###.# #.### #
#...# #  .#.#.#...#...#.....#...  # #
#.#######.#.#.#.#.#.#.#######.#######
#.    #  .#.#.#.#.#.#.#...#...#     #
#.#######.#.#.#.#.#.#.#.#.#.### #####
#.    #  .#.#.#.#.#.#.#.#...        #
#.#######.#.#.#.#.#.#.#.#############
#.    # #.#.#.#.#.#.#.#.....        #
#.##### #.#.#.#.#.#.#.#####.#########
#.  #    .#.#.#.#.#.#.......  # #   #
#.# # ###.#.#.#.#.#.########### # ###
..# # #  .#.#.#.#.#.........#   # # #
# # #####.#.#.#.#.#########.# ### # #
# # #    .#.#.#.#...........        #
#########.#.#.#.############### #####
#   #    .#.#.#.............# #     #
### # ###.#.#.#############.# ##### #
#     #  ...#...............      # #
##### # # ### # # # # ### # # ##### #
#     # #   # # # # #   # # #   #   #
####### # ### # # # ##### # ####### #
#       # #   # # #     # #       # #
#####################################
>>>

Dla każdego, kto chciałby spróbować uruchomić ten program samodzielnie, użyj polecenia M(Image, Show solution). Polecam użycie potrójnych cudzysłowów do wprowadzenia obrazu, ponieważ w przeciwnym razie będzie wiele znaków odwrotnego ukośnika lub znaków nowej linii.

— Anonimowy No Lifer
źródło
1
Dokładny pseudonim: p
— Fatalize
1
Dobra robota! Kilka porad: Użyj 0zamiast pass, l.append(a);l.append(b)-> l+=a,b, l.append(a)-> l+=[a], warto przypisać '#'do zmiennej, i def E(G,y,z):\n c=[]->def E(G,y,z,c=[]):
— Loovjo,
1
Ponadto, if G[r][c]==1 or G[r][c]==2:-> if 0<G[r][c]<3:, s=[0]\n for x in R(L(I[0])*2):s+=[0]-> s=[0]*(1+L(I[0])*2)i (myślę, że jeszcze tego nie przetestowałem) G=[s]-> *G=s.
— Loovjo,
@Loovjo Dzięki za opinię, except:0, l+=a,bi s=[0]*(1+L(I[0])*2)naprawdę pomogło. Niestety, z jakiegokolwiek powodu przypisanie c w wywołaniu funkcji nie resetuje go przez wiele wywołań, co oznaczało, że przestał działać, G [r] [c] może być ciągiem, więc nie mogę użyć <lub> na nim i * G = s dał mi błąd składniowy. Mimo to świetna rada.
— Anonimowy No Lifer
1
@AnonymousNoLifer Brak problemów. Ponadto, jeśli G[r][c]może być łańcuchem, G[r][c]in[1,2]powinno działać.
— Loovjo
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.