Bagaimana untuk melaksanakan penjana maze dalam Python

Mula-mula tunjukkan pemaparan:

Mari kita analisis dahulu perpustakaan yang diperlukan:

Memandangkan ia adalah penjana, labirin yang dijana akan sama persis setiap masa Ia jelas tidak wajar. Oleh itu, kita tidak dapat tidak perlu menggunakan nombor rawak (Random library). Maze mesti dilukis, jadi perpustakaan GUI atau perpustakaan lukisan diperlukan Di sini saya menggunakan Pygame (Tkinter atau Turtle sebenarnya boleh melakukannya, tetapi selepas semua, Pygame lebih mudah). Sys (digunakan untuk keluar dari program) juga nampaknya diperlukan apabila menggunakan Pygame, tetapi walaupun ia tidak digunakan, ia tidak akan memberi banyak kesan. Berikut ialah penulisan semula ayat asal: Seterusnya kita mempunyai Tkinter.filedialog, yang digunakan terutamanya untuk menanyakan laluan penjimatan selepas maze dijana. Lagipun, labirin yang dihasilkan perlu dipelihara. Sudah tentu, menambah pemasa dengan Masa kelihatan seperti aising pada kek.

Jadi, terdapat:

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

Apa yang perlu dijelaskan di sini ialah memandangkan banyak kandungan seperti maklumat versi akan dikeluarkan apabila mengimport Pygame (yang menjejaskan estetika), kita perlu untuk menggunakan Contextlib untuk menghalangnya daripada menjadi output.

Seterusnya, kita perlu meminta beberapa parameter:

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

Kemudian, kita perlu menjalankan program yang menjana maze. Pada masa yang sama, kita perlu merekodkan masa (bersamaan dengan memulakan pemasa):

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

Kemudian maze dijana secara rasmi. Sebelum memperkenalkan bahagian kod ini, kita perlu memahami algoritma:

Langkah pertama ialah menjana grid yang terdiri daripada sel maze (sel putih) dan dinding (sel hitam). Bilangan unit maze dalam baris adalah sama dengan bilangan lajur dalam maze, dan dalam lajur adalah sama dengan bilangan baris dalam maze. Biarkan unit maze di sudut kiri atas menjadi titik permulaan dan unit maze di sudut kanan bawah menjadi titik akhir, dan alih keluar dinding di sebelah kiri titik permulaan dan di sebelah kanan titik akhir, seperti yang ditunjukkan dalam rajah:

Bab Langkah kedua ialah melawat setiap unit labirin. Tandakan titik permulaan sebagai unit labirin semasa Apabila terdapat unit labirin yang belum dilawati (mana-mana unit labirin yang telah menjadi unit labirin semasa dianggap telah dilawati), ulangi pelaksanaan:

• Tambahkan unit maze yang tidak dilawati di sekeliling ke meja; maze Tolak unit ke dalam tindanan (boleh difahami sebagai menambahkannya pada jadual yang dipanggil tindanan); 🎜>

  Pecahkan dinding antara unit labirin semasa dan unit labirin yang dipilih;

• Tandakan unit labirin yang dipilih sebagai unit labirin semasa; >
Jika tiada unit labirin dalam jadual:
• Letakkan unit labirin di bahagian atas tindanan (yang boleh difahami sebagai mendapatkan dan memadamkan elemen terakhir dalam timbunan); tamat, rendering seperti pada permulaan artikel akan muncul hasil.
  Seterusnya, kami akan menukar algoritma literal kepada kod Python.
• Pertama sekali, program ini tidak mengenali gambar, ia mengecam data. Untuk mewakili imej semasa sebagai rentetan data, kita perlu membuat senarai dua dimensi. Sudah tentu, kita boleh melengkapkan tetapan langkah pertama bersama-sama dengan cara:

  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

  Bukan sahaja kami membuat senarai keperluan yang menyimpan semua unit labirin, tetapi kami juga dapat melihatnya. Fungsinya adalah untuk menentukan sama ada unit maze telah dilawati Setiap lawatan akan memadam unit maze daripada jadual Apabila tiada unit maze dalam jadual, ini bermakna semua unit maze telah dilawati.

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

• Dan kandungan ini adalah langkah kedua. Saya telah menjelaskan algoritma Satu-satunya perbezaan kecil ialah di sini kita tidak menambah koordinat unit maze bersebelahan ke senarai, sebaliknya menambah dinding pecah yang sepadan dan kod yang ditandakan sebagai unit maze semasa sebagai rentetan disimpan dalam jadual, dan selepas secara rawak memilih rentetan yang sepadan dengan unit maze tertentu, gunakan exec untuk menukarnya menjadi kod dan jalankannya (ini boleh menyimpan beberapa kod).

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

  Selepas mencetak masa yang diperlukan untuk menjana maze, kita perlu menukar data dalam jadual kepada imej. Sudah tentu, sebelum melakukan ini, kita mesti terlebih dahulu menentukan lokasi di mana imej itu disimpan.

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

Sebelum membuat pilihan, anda perlu menentukan sama ada anda mahu menyimpan atau tidak menyimpan imej, kerana anda mungkin memilih untuk tidak menyimpannya. Aksara "1" di sini bermaksud menyimpan (jika anda memasukkan apa-apa lagi, ia secara semula jadi tidak akan disimpan). Seterusnya, anda perlu memilih laluan simpan (gunakan kaedah askdirectory() untuk memilih laluan fail, tanpa memilih nama fail). Seterusnya, kita perlu mengesahkan bahawa nama fail ialah "a×b maze.png". Jika nama fail sudah wujud dalam laluan, nombor siri perlu ditambah selepas nama fail. Secara keseluruhannya, melalui rentetan kod ini, kami telah menentukan laluan + nama fail labirin.

• 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()

  Imej "maze.png" yang digunakan dalam kod (nama tidak betul, anda perlu menamakan semula selepas memuat turun):

• 这里主要是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()

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan penjana maze dalam Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!