资讯专栏INFORMATION COLUMN

Python怎么实现迷宫?生成代码是什么

89542767 / 493人阅读


  小编写这篇文章的主要目的,是给大家去做一个相关的介绍,介绍一下关于其怎么才能够实现python迷宫,那么,我们要使用的话,就要去生成代码了,那么,具体的代码有吗?下面就给大家做一个解答。


  作为一项古老的智力游戏,千百年来迷宫都散发着迷人的魅力。但是,手工设计迷宫费时又耗(脑)力,于是,我们有必要制作一个程序:迷宫生成器……


  好吧,我编不下去了。但是,从上面的文字中,我们可以看出,我们此次的主题是:用Python实现一个迷宫生成器。


  首先展示一下效果图:

01.png

  我们先分析一下所需的库:


  既然是生成器,每次生成的迷宫一模一样显然是说不过去的。因此,我们不可避免地要使用随机数(Random库)。迷宫一定是要绘制的,所以需要有一个GUI库或绘图库,这里我使用Pygame(Tkinter或Turtle其实都可以做到,但毕竟Pygame比较顺手)。与Pygame搭配,Sys似乎也是需要的(用于退出程序,但其实不使用似乎也无伤大雅)。然后是Tkinter.filedialog,主要用于询问保存路径(生成的迷宫总得保存吧)。当然,用Time加一个计时器似乎是锦上添花。


  于是,就有:


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


  这里要说明的是,由于导入Pygame时会输出版本信息等很多内容(这很影响美感),我们需要使用Contextlib阻止它输出。


  接下来,我们需要询问一些参数:


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


  然后,就要运行生成迷宫的程序了。同时,我们有必要计录一下时间(相当于开启计时器):


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


  然后就是正式生成迷宫。在介绍这部分代码之前,我们需要了解一下算法:


  第一步,生成一个由迷宫单元(白格)和墙(黑格)组成的网格。一行中迷宫单元的数量为迷宫的列数,一列找迷宫单元的数量为迷宫的行数。令左上角的迷宫单元为起点,右下角的迷宫单元为终点,打破起点左边与终点右边的墙,如图所示:

02.png

  第二步,访问各迷宫单元。将起点标记为当前迷宫单元,当存在未被访问的迷宫单元(凡是曾经成为过当前迷宫单元的迷宫单元,都视为已访问)时,重复执行:


  将周围的未被访问的迷宫单元加入表格;


  如果表格中有迷宫单元:


  将当前迷宫单元入栈(可以理解为将其加入一个叫做栈的表格);


  从表格中随机选择一个迷宫单元;


  打破当前迷宫单元与选择的迷宫单元之间的墙;


  将选择的迷宫单元标记为当前迷宫单元;


  如果表格中没有迷宫单元:


  栈顶迷宫单元出栈(可以理解为将栈中的最后一个元素获取并删除);


  将出栈的迷宫单元设为当前迷宫单元;


  在循环结束以后,就会出现像文章开头效果图一样的结果。


  接下来,我们就要将文字化的算法转化为Python的代码。


  首先,程序是不认识图片的,它认识的是数据。所以我们需要设置一个二维列表,以此来用一串数据表示当前的图像。当然,我们可以顺便将第一步的设置一起完成:


  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


  可以看到,除此以外我们还建立了一个列表need,里面存储了所有的迷宫单元。它的作用就是判断迷宫单元是否被访问,每次访问都会将迷宫单元从表格中删除,当表格中没有迷宫单元时,就说明所有迷宫单元都被访问了。


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


  而这些内容,就是第二步。其算法我已经解释过,唯一一个微小的不同是,在此处我们并没有在列表中加入相邻迷宫单元的坐标,而是将其对应的破墙和标记为当前迷宫单元的代码以字符串的形式存储在表格中,并在随机选择出某个迷宫单元所对应的字符串后,使用exec将其转换为代码并运行(这可以节省一些代码)。

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


  打印完生成迷宫的用时后,我们需要将表格中的数据转化为图像了。当然,在此之前,我们要先确定图片保存的位置。


  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

  由于使用时有可能选择不保存图片,因此要先判断你的选择是保存还是不保存。这里字符“1”表示保存(输入其他,自然就是不保存了)。然后我们需要让你选择保存路径(askdirectory()询问的是文件路径,不需要选择文件名)。然后,我们要确定文件名称:“a×b迷宫.png”。这里需要判断指定路径是否存在此名称的文件,如果存在,则我们需要在后面加上序号。总而言之,通过这串代码,我们已经将迷宫的路径+文件名确定了。


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


  代码中使用的图片“迷宫.png”(名称不太对,下载以后要重新命名一下):

04.png

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


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


  它运行良好,但当迷宫比较复杂时,暴露出一个问题(下图是100×100的迷宫):

05.png

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


  难度高,在某方面上讲,的确是好事。但当你向你的朋友们展示这个迷宫时,如果你自己也无法得出正确的路径,这不是很扫兴吗?


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


  寻路算法的大体思路:


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


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


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


  如果表格不空:


  将当前位置入栈;


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


  如果表格是空的:


  栈顶的路出栈;


  将其设为当前位置;


  通过这个算法,我们可以试出正确的路径(如图):

06.png

  代码的实现:


  x2=0
  y2=1
  listing2=[]
  while not(alist[-1][-2]==2):
  alist[x2][y2]=3
  around2=[]
  try:
  if x2-1&lt;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&lt;0:
  print(1+"1")
  if alist[x2][y2-1]==0:
  around2.append("y2=y2-1")
  except:
  while False:
  print()
  if len(around2)&gt;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的迷宫,其正确路径是:

07.png

  可以看出,本文中所用的算法生成的迷宫,其正确路径还是非常曲折的(难度很高)。你何不将其发给你的朋友,让其破解一下呢?


  完整的代码:


  #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)&gt;0:
  aroundit=[]
  try:
  if x-2&lt;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&lt;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)&gt;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&lt;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&lt;0:
  print(1+"1")
  if alist[x2][y2-1]==0:
  around2.append("y2=y2-1")
  except:
  while False:
  print()
  if len(around2)&gt;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('迷宫')
  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()


  代码的结束,对于程序也许仅仅只是开始;学习的暂时告一段落,从不影响生活的继续。生命无止境,贵在一颗永远向上的心。


  至此,小编就给大家介绍完毕了,希望可以给大家带来更多的帮助。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/128009.html

相关文章

  • 用并查集(find-union)实现迷宫算法以及最短路径求解

    摘要:本人邮箱欢迎转载转载请注明网址代码已经全部托管有需要的同学自行下载引言迷宫对于大家都不会陌生那么迷宫是怎么生成已经迷宫要如何找到正确的路径呢用代码又怎么实现带着这些问题我们继续往下看并查集朋友圈有一种算法就做并查集什么意思呢比如现在有零 本人邮箱: 欢迎转载,转载请注明网址 http://blog.csdn.net/tianshi_kcogithub: https://github.c...

    xiangchaobin 评论0 收藏0
  • 一篇文章把本该属于你的源码天赋还给你

    摘要:一些方法不应该这样不应该漫无目的地随手拿起一分源码,试图去通读。应该这样精心挑选要阅读的源码项目。这最好是与你的编程语言你的工作内容你的兴趣所在相关的,这样才能更切实地感受到阅读源码给你带来的益处,更有动力继续。 showImg(https://segmentfault.com/img/bVbcvmm?w=785&h=525); 怎么阅读源码 没有经验的技术差底子薄的初级程序员,如何阅...

    chanjarster 评论0 收藏0
  • 快速实现一个简单的canvas迷宫游戏

    摘要:所以我先写了一个样例扔在服务器上,大家可以先体验一下效果用成就感作为驱动力哈哈哈点我体验地址正文实现这个小游戏也不难,让我们想想,一个迷宫游戏有哪些基本要素。迷宫地图的生成,可以借助谷歌的一个迷宫在线生成器来获得。 前言 (最近设计模式看的有点头大,一直面对纯js实在是有些枯燥-_-。所以写一点有趣的东西调剂一下)现在canvas已经不算新鲜了,不过由于日常业务中并不常用,所以实践并不...

    wangdai 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<