So implementieren Sie einen Labyrinthgenerator in Python

Zeigen Sie zunächst die Renderings:

Lassen Sie uns zunächst die erforderlichen Bibliotheken analysieren:

Da es generiert wird Es ist offensichtlich unvernünftig, dass das von der Maschine erzeugte Labyrinth jedes Mal genau das gleiche ist. Daher müssen wir zwangsläufig Zufallszahlen (Zufallsbibliothek) verwenden. Das Labyrinth muss gezeichnet werden, daher ist eine GUI-Bibliothek oder Zeichenbibliothek erforderlich. Hier verwende ich Pygame (Tkinter oder Turtle können das tatsächlich, aber Pygame ist schließlich bequemer). Sys (wird zum Beenden des Programms verwendet) scheint auch bei der Verwendung von Pygame erforderlich zu sein, aber selbst wenn es nicht verwendet wird, hat es keine großen Auswirkungen. Das Folgende ist eine Umformulierung des ursprünglichen Satzes: Als nächstes haben wir Tkinter.filedialog, das hauptsächlich zum Erfragen des Speicherpfads nach der Erstellung des Labyrinths verwendet wird. Schließlich muss das erzeugte Labyrinth erhalten bleiben. Natürlich scheint das Hinzufügen eines Timers mit Time das Tüpfelchen auf dem i zu sein.

Es gibt also:

#coding:utf-8
import contextlib
with contextlib.redirect_stdout(None):
    import pygame
import random
import sys
import time
from tkinter.filedialog import *

Was ich hier erklären möchte, ist, dass beim Importieren von Pygame viele Inhalte wie Versionsinformationen ausgegeben werden (was sich auf die Ästhetik auswirkt). ), müssen wir Contextlib verwenden, um die Ausgabe zu verhindern.

Als nächstes müssen wir nach einigen Parametern fragen:

a=int(input("列数："))
b=int(input("行数："))
l=int(input("大小："))
saveit=input("是否保存：")

Dann müssen wir das Programm ausführen, das das Labyrinth generiert. Gleichzeitig müssen wir die Zeit aufzeichnen (entspricht dem Starten eines Timers):

print("生成中...")
e = time.time()

Dann wird das Labyrinth offiziell generiert. Bevor wir diesen Teil des Codes einführen, müssen wir den Algorithmus verstehen:

Der erste Schritt besteht darin, ein Gitter zu generieren, das aus Labyrinthzellen (weißen Zellen) und Wänden (schwarzen Zellen) besteht. Die Anzahl der Labyrintheinheiten in Reihen entspricht der Anzahl der Spalten im Labyrinth und in Spalten entspricht der Anzahl der Zeilen im Labyrinth. Lassen Sie die Labyrintheinheit in der oberen linken Ecke den Startpunkt und die Labyrintheinheit in der unteren rechten Ecke den Endpunkt sein und entfernen Sie die Wände links vom Startpunkt und rechts vom Endpunkt, wie in gezeigt das Bild:

Der zweite Schritt besteht darin, jede Labyrintheinheit zu besuchen. Markieren Sie den Startpunkt als aktuelle Labyrintheinheit (jede Labyrintheinheit, die zur aktuellen Labyrintheinheit wurde, gilt als besucht), wiederholen Sie die Ausführung:

#🎜 🎜 #
• Fügen Sie die umliegenden, nicht besuchten Labyrintheinheiten zur Tabelle hinzu.

• Wenn die Tabelle Labyrintheinheiten enthält: 🎜 🎜#
  Schieben Sie die aktuelle Labyrintheinheit in den Stapel (kann als Hinzufügen zu einer Tabelle namens Stapel verstanden werden); Wählen Sie zufällig aus der Tabelle eine Labyrintheinheit aus.
• Brechen Sie die Wand zwischen der aktuellen Labyrintheinheit und der ausgewählten Labyrintheinheit ##🎜🎜 #Markieren Sie die ausgewählte Labyrintheinheit als aktuelle Labyrintheinheit;

  #🎜🎜 #

Platzieren Sie die Labyrintheinheit oben im Stapel (was als Abrufen und Löschen des letzten Elements im Stapel verstanden werden kann); #

• wird vom Stapel entfernt. Die Labyrintheinheit wird als aktuelle Labyrintheinheit festgelegt; Es erscheint das gleiche Ergebnis wie bei der Darstellung am Anfang des Artikels.

Als nächstes konvertieren wir den Literalalgorithmus in Python-Code.

• Erstens erkennt das Programm keine Bilder, sondern Daten. Um das aktuelle Bild als Datenfolge darzustellen, müssen wir eine zweidimensionale Liste erstellen. Natürlich können wir die Einstellung des ersten Schritts übrigens auch gemeinsam abschließen:

  alist = []
  aa=0
  need=[]
  for j in range(2*a+1):
      if aa==0:
          aa = 1
          alistone = []
          for i in range(2*b+1):
              alistone.append(1)
          alist.append(alistone)
      else:
          aa=0
          alistone = []
          bb=0
          for i in range(2*b+1):
              if bb==0:
                  bb=1
                  alistone.append(1)
              else:
                  bb = 0
                  need.append((j,i))
                  alistone.append(0)
          alist.append(alistone)
  alist[0][1]=0
  alist[-1][-2]=0

Wir müssen nicht nur eine Liste erstellen, in der alle Labyrintheinheiten gespeichert sind, sondern wir können sie auch sehen. Seine Funktion besteht darin, festzustellen, ob die Labyrintheinheit besucht wurde. Bei jedem Besuch wird die Labyrintheinheit aus der Tabelle gelöscht.

• x=1
  y=1
  need.remove((1, 1))
  listing=[]
  while len(need)>0:
      aroundit=[]
      try:
          if x-2<0:
              print(1+"1")
          alist[x-2][y]=0
          if (x-2,y) in need:
              aroundit.append("alist[x-1][y],x=(0,x-2)")
      except:
          while False:
              print()
      try:
          alist[x+2][y]=0
          if (x+2,y) in need:
              aroundit.append("alist[x+1][y],x=(0,x+2)")
      except:
          while False:
              print()
      try:
          alist[x][y+2]=0
          if (x,y+2) in need:
              aroundit.append("alist[x][y+1],y=(0,y+2)")
      except:
          while False:
              print()
      try:
          if y-2<0:
              print(1+"1")
          alist[x][y-2]=0
          if (x,y-2) in need:
              aroundit.append("alist[x][y-1],y=(0,y-2)")
      except:
          while False:
              print()
      if len(aroundit)>0:
          listing.append((x,y))
          exec(random.choice(aroundit))
          need.remove((x, y))
      else:
          x,y=listing[-1]
          listing.pop()

  Und diese Inhalte sind der zweite Schritt. Ich habe den Algorithmus bereits erklärt. Der einzige kleine Unterschied besteht darin, dass wir hier nicht die Koordinaten benachbarter Labyrintheinheiten zur Liste hinzufügen, sondern stattdessen deren entsprechende unterbrochene Wände und die als aktuelle Labyrintheinheit markierten Codes In der Tabelle gespeichert und nach zufälliger Auswahl der Zeichenfolge, die einer bestimmten Labyrintheinheit entspricht, verwenden Sie exec, um sie in Code umzuwandeln und auszuführen (dies kann Code sparen).

  print("完成！用时{}秒".format(time.time()-e))

Nachdem wir die Zeit gedruckt haben, die zum Generieren des Labyrinths benötigt wird, müssen wir die Daten in der Tabelle in Bilder umwandeln. Bevor wir dies tun, müssen wir natürlich zunächst den Speicherort des Bildes bestimmen.

if saveit=="1":
    ccc = askdirectory()
    h=""
    bbbbb=1
    while True:
        try:
            open("{}/{}×{}迷宫{}.png".format(ccc,a,b,h),"r")
            h="({})".format(bbbbb)
        except:
            break
        bbbbb+=1

• Bevor Sie eine Auswahl treffen, müssen Sie festlegen, ob Sie das Bild speichern möchten oder nicht, da Sie sich möglicherweise dafür entscheiden, es nicht zu speichern. Das Zeichen „1“ bedeutet hier Speichern (wenn Sie etwas anderes eingeben, wird es natürlich nicht gespeichert). Als nächstes müssen Sie den Speicherpfad auswählen (verwenden Sie die Methode askdirectory(), um den Dateipfad auszuwählen, ohne einen Dateinamen auszuwählen). Als nächstes müssen wir bestätigen, dass der Dateiname „a×b maze.png“ ist. Wenn der Dateiname bereits im Pfad vorhanden ist, muss nach dem Dateinamen eine Seriennummer hinzugefügt werden. Alles in allem haben wir durch diese Codezeichenfolge den Pfad und den Dateinamen des Labyrinths ermittelt.

  pygame.init()
  icon=pygame.image.load("迷宫.png")
  pygame.display.set_icon(icon)
  screen=pygame.display.Info()
  screen = pygame.display.set_mode((l*(2*a+1),l*(2*b+1)))
  pygame.display.set_caption('迷宫')
  screen.fill("white")
  c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
  c.fill(color='white')
  d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
  d.fill(color='black')
  for i in range(2*a+1):
      for j in range(2*b+1):
          if alist[i][j]==0:
              screen.blit(c, (i*l, j*l))
          elif alist[i][j]==1:
              screen.blit(d, (i*l, j*l))
  pygame.display.flip()
  if saveit=="1":
      pygame.image.save(screen, "{}/{}×{}迷宫{}.png".format(ccc, a, b, h))
  while True:
      for event in pygame.event.get():
          if event.type == pygame.QUIT:
              pygame.quit()
              sys.exit()

  Das im Code verwendete Bild „maze.png“ (der Name ist nicht korrekt, Sie müssen ihn nach dem Herunterladen umbenennen):
• #🎜 🎜#

  这里主要是Pygame的基本设置，并将表格内容图像化。方格中每个数字代表一个方块，数字的大小则决定了方块的颜色，数值在表格中的位置决定了方块放置的位置。就这样，我们呢将表格完全转化成了图像。当然，我们还需要使用pygame.image.save()函数将图像另存为图片文件。

  这样，这个生成器似乎完成了。

  它运行良好，但当迷宫比较复杂时，暴露出一个问题（下图是100×100的迷宫）：

  

  由于正确路径过于曲折，在复杂度较高时，这个迷宫的难度会变得极高！

  难度高，在某方面上讲，的确是好事。如果你自己无法找到正确的路线，那么当你展示这个迷宫给朋友看时，感觉会很失落吧？

  因此，一个寻路算法变得非常有必要。

  寻路算法的大体思路：

  在生成的迷宫中，白格为路，黑格为墙。将起点设置为当前位置，重复执行直到终点成为当前位置：

  • 将当前位置标记为正确路径；

  • 将周围未标记的路加入一个表格；

  • 如果表格不空：

  • 将当前位置入栈；

  • 从表格中随机选择一条路，并将其设为当前位置；

  • 如果表格是空的：

  • 栈顶的路出栈；

  • 将其设为当前位置；

  通过这个算法，我们可以试出正确的路径（如图）：

  

  代码的实现：

  x2=0
  y2=1
  listing2=[]
  while not(alist[-1][-2]==2):
      alist[x2][y2]=3
      around2=[]
      try:
          if x2-1<0:
              print(1+"1")
          if alist[x2-1][y2]==0:
              around2.append("x2=x2-1")
      except:
          while False:
              print()
      try:
          if alist[x2+1][y2]==0:
              around2.append("x2=x2+1")
      except:
          while False:
              print()
      try:
          if alist[x2][y2+1]==0:
              around2.append("y2=y2+1")
      except:
          while False:
              print()
      try:
          if y2-1<0:
              print(1+"1")
          if alist[x2][y2-1]==0:
              around2.append("y2=y2-1")
      except:
          while False:
              print()
      if len(around2)>0:
          listing2.append((x2,y2))
          exec(random.choice(around2))
      else:
          alist[x2][y2]=2
          x2,y2=listing2[-1]
          listing2.pop()
  alist[-1][-2]=3
  for i in range(len(alist)):
      for j in range(len(alist[0])):
          if alist[i][j]==2:
              alist[i][j]=0

  同时，图像绘制的过程也要作出一些改动，以显示正确路径：

  if saveit=="1":
      ccc = askdirectory()
      h=""
      bbbbb=1
      while True:
          try:
              open("{}/{}×{}迷宫{}.png".format(ccc,a,b,h),"r")
              open("{}/{}×{}迷宫（正确线路）{}.png".format(ccc,a,b,h),"r")
              h="({})".format(bbbbb)
          except:
              break
          bbbbb+=1
  pygame.init()
  icon=pygame.image.load("迷宫.png")
  pygame.display.set_icon(icon)
  screen=pygame.display.Info()
  screen = pygame.display.set_mode((l*(2*a+1),l*(2*b+1)))
  pygame.display.set_caption('迷宫')
  screen.fill("white")
  if saveit=="1":
      c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
      c.fill(color='white')
      d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
      d.fill(color='black')
      f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
      f.fill(color='white')
      for i in range(2 * a + 1):
          for j in range(2 * b + 1):
              if alist[i][j] == 0:
                  screen.blit(c, (i * l, j * l))
              elif alist[i][j] == 1:
                  screen.blit(d, (i * l, j * l))
              else:
                  screen.blit(f, (i * l, j * l))
      pygame.image.save(screen, "{}/{}×{}迷宫{}.png".format(ccc, a, b, h))
      c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
      c.fill(color='white')
      d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
      d.fill(color='black')
      f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
      f.fill(color='red')
      for i in range(2 * a + 1):
          for j in range(2 * b + 1):
              if alist[i][j] == 0:
                  screen.blit(c, (i * l, j * l))
              elif alist[i][j] == 1:
                  screen.blit(d, (i * l, j * l))
              else:
                  screen.blit(f, (i * l, j * l))
      pygame.image.save(screen, "{}/{}×{}迷宫（正确线路）{}.png".format(ccc, a, b, h))
  c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
  c.fill(color='white')
  d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
  d.fill(color='black')
  f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
  f.fill(color='white')
  for i in range(2*a+1):
      for j in range(2*b+1):
          if alist[i][j]==0:
              screen.blit(c, (i*l, j*l))
          elif alist[i][j]==1:
              screen.blit(d, (i*l, j*l))
          else:
              screen.blit(f,(i*l, j*l))
  pygame.display.flip()
  aaaaaaa = 0
  while True:
      for event in pygame.event.get():
          if event.type == pygame.QUIT:
              pygame.quit()
              sys.exit()
          if event.type == pygame.MOUSEBUTTONDOWN:
              if aaaaaaa == 1:
                  aaaaaaa = 0
                  c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                  c.fill(color='white')
                  d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                  d.fill(color='black')
                  f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                  f.fill(color='white')
                  for i in range(2 * a + 1):
                      for j in range(2 * b + 1):
                          if alist[i][j] == 0:
                              screen.blit(c, (i * l, j * l))
                          elif alist[i][j] == 1:
                              screen.blit(d, (i * l, j * l))
                          else:
                              screen.blit(f, (i * l, j * l))
                  pygame.display.flip()
              else:
                  aaaaaaa = 1
                  c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                  c.fill(color='white')
                  d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                  d.fill(color='black')
                  f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                  f.fill(color='red')
                  for i in range(2 * a + 1):
                      for j in range(2 * b + 1):
                          if alist[i][j] == 0:
                              screen.blit(c, (i * l, j * l))
                          elif alist[i][j] == 1:
                              screen.blit(d, (i * l, j * l))
                          else:
                              screen.blit(f, (i * l, j * l))
                  pygame.display.flip()

  通过这些改动，显示正确路径的效果就实现了。当生成迷宫完成后，窗口显示的是没有正确路径的迷宫。但是，当单击窗口时，正确的路径便会显示出来，再次单击即可隐藏。

  刚刚那张100×100的迷宫，其正确路径是：

  

  完整的代码：

  #coding:utf-8
  import contextlib
  with contextlib.redirect_stdout(None):
      import pygame
  import random
  import sys
  import time
  from tkinter.filedialog import *
  a=int(input("列数："))
  b=int(input("行数："))
  l=int(input("大小："))
  saveit=input("是否保存：")
  print("生成中...")
  e = time.time()
  alist = []
  aa=0
  need=[]
  for j in range(2*a+1):
      if aa==0:
          aa = 1
          alistone = []
          for i in range(2*b+1):
              alistone.append(1)
          alist.append(alistone)
      else:
          aa=0
          alistone = []
          bb=0
          for i in range(2*b+1):
              if bb==0:
                  bb=1
                  alistone.append(1)
              else:
                  bb = 0
                  need.append((j,i))
                  alistone.append(0)
          alist.append(alistone)
  alist[0][1]=0
  alist[-1][-2]=0
  x=1
  y=1
  need.remove((1, 1))
  listing=[]
  while len(need)>0:
      aroundit=[]
      try:
          if x-2<0:
              print(1+"1")
          alist[x-2][y]=0
          if (x-2,y) in need:
              aroundit.append("alist[x-1][y],x=(0,x-2)")
      except:
          while False:
              print()
      try:
          alist[x+2][y]=0
          if (x+2,y) in need:
              aroundit.append("alist[x+1][y],x=(0,x+2)")
      except:
          while False:
              print()
      try:
          alist[x][y+2]=0
          if (x,y+2) in need:
              aroundit.append("alist[x][y+1],y=(0,y+2)")
      except:
          while False:
              print()
      try:
          if y-2<0:
              print(1+"1")
          alist[x][y-2]=0
          if (x,y-2) in need:
              aroundit.append("alist[x][y-1],y=(0,y-2)")
      except:
          while False:
              print()
      if len(aroundit)>0:
          listing.append((x,y))
          exec(random.choice(aroundit))
          need.remove((x, y))
      else:
          x,y=listing[-1]
          listing.pop()
  x2=0
  y2=1
  listing2=[]
  while not(alist[-1][-2]==2):
      alist[x2][y2]=3
      around2=[]
      try:
          if x2-1<0:
              print(1+"1")
  
          if alist[x2-1][y2]==0:
              around2.append("x2=x2-1")
      except:
          while False:
              print()
      try:
  
          if alist[x2+1][y2]==0:
              around2.append("x2=x2+1")
      except:
          while False:
              print()
      try:
  
          if alist[x2][y2+1]==0:
              around2.append("y2=y2+1")
      except:
          while False:
              print()
      try:
          if y2-1<0:
              print(1+"1")
          if alist[x2][y2-1]==0:
              around2.append("y2=y2-1")
      except:
          while False:
              print()
      if len(around2)>0:
          listing2.append((x2,y2))
          exec(random.choice(around2))
      else:
          alist[x2][y2]=2
          x2,y2=listing2[-1]
          listing2.pop()
  alist[-1][-2]=3
  for i in range(len(alist)):
      for j in range(len(alist[0])):
          if alist[i][j]==2:
              alist[i][j]=0
  print("完成！用时{}秒".format(time.time()-e))
  if saveit=="1":
      ccc = askdirectory()
      h=""
      bbbbb=1
      while True:
          try:
              open("{}/{}×{}迷宫{}.png".format(ccc,a,b,h),"r")
              open("{}/{}×{}迷宫（正确线路）{}.png".format(ccc,a,b,h),"r")
              h="({})".format(bbbbb)
          except:
              break
          bbbbb+=1
  pygame.init()
  icon=pygame.image.load("迷宫.png")
  pygame.display.set_icon(icon)
  screen=pygame.display.Info()
  screen = pygame.display.set_mode((l*(2*a+1),l*(2*b+1)))
  pygame.display.set_caption(&#39;迷宫&#39;)
  screen.fill("white")
  if saveit=="1":
      c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
      c.fill(color=&#39;white&#39;)
      d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
      d.fill(color=&#39;black&#39;)
      f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
      f.fill(color=&#39;white&#39;)
      for i in range(2 * a + 1):
          for j in range(2 * b + 1):
              if alist[i][j] == 0:
                  screen.blit(c, (i * l, j * l))
              elif alist[i][j] == 1:
                  screen.blit(d, (i * l, j * l))
              else:
                  screen.blit(f, (i * l, j * l))
      pygame.image.save(screen, "{}/{}×{}迷宫{}.png".format(ccc, a, b, h))
      c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
      c.fill(color=&#39;white&#39;)
      d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
      d.fill(color=&#39;black&#39;)
      f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
      f.fill(color=&#39;red&#39;)
      for i in range(2 * a + 1):
          for j in range(2 * b + 1):
              if alist[i][j] == 0:
                  screen.blit(c, (i * l, j * l))
              elif alist[i][j] == 1:
                  screen.blit(d, (i * l, j * l))
              else:
                  screen.blit(f, (i * l, j * l))
      pygame.image.save(screen, "{}/{}×{}迷宫（正确线路）{}.png".format(ccc, a, b, h))
  c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
  c.fill(color=&#39;white&#39;)
  d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
  d.fill(color=&#39;black&#39;)
  f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
  f.fill(color=&#39;white&#39;)
  for i in range(2*a+1):
      for j in range(2*b+1):
          if alist[i][j]==0:
              screen.blit(c, (i*l, j*l))
          elif alist[i][j]==1:
              screen.blit(d, (i*l, j*l))
          else:
              screen.blit(f,(i*l, j*l))
  pygame.display.flip()
  aaaaaaa = 0
  while True:
      for event in pygame.event.get():
          if event.type == pygame.QUIT:
              pygame.quit()
              sys.exit()
          if event.type == pygame.MOUSEBUTTONDOWN:
              if aaaaaaa == 1:
                  aaaaaaa = 0
                  c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                  c.fill(color=&#39;white&#39;)
                  d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                  d.fill(color=&#39;black&#39;)
                  f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                  f.fill(color=&#39;white&#39;)
                  for i in range(2 * a + 1):
                      for j in range(2 * b + 1):
                          if alist[i][j] == 0:
                              screen.blit(c, (i * l, j * l))
                          elif alist[i][j] == 1:
                              screen.blit(d, (i * l, j * l))
                          else:
                              screen.blit(f, (i * l, j * l))
                  pygame.display.flip()
              else:
                  aaaaaaa = 1
                  c = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                  c.fill(color=&#39;white&#39;)
                  d = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                  d.fill(color=&#39;black&#39;)
                  f = pygame.Surface((l, l), flags=pygame.HWSURFACE)
                  f.fill(color=&#39;red&#39;)
                  for i in range(2 * a + 1):
                      for j in range(2 * b + 1):
                          if alist[i][j] == 0:
                              screen.blit(c, (i * l, j * l))
                          elif alist[i][j] == 1:
                              screen.blit(d, (i * l, j * l))
                          else:
                              screen.blit(f, (i * l, j * l))
                  pygame.display.flip()

  Das obige ist der detaillierte Inhalt vonSo implementieren Sie einen Labyrinthgenerator in Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!