Comment implémenter un générateur de labyrinthe en Python

Affichez d'abord les rendus :

Analysons d'abord les bibliothèques requises :

Puisqu'il est généré Il est évidemment déraisonnable que le labyrinthe généré par la machine soit exactement le même à chaque fois. Nous devons donc inévitablement utiliser des nombres aléatoires (Random library). Le labyrinthe doit être dessiné, donc une bibliothèque d'interface graphique ou une bibliothèque de dessins est requise. Ici, j'utilise Pygame (Tkinter ou Turtle peuvent effectivement le faire, mais après tout, Pygame est plus pratique). Sys (utilisé pour quitter le programme) semble également être requis lors de l'utilisation de Pygame, mais même s'il n'est pas utilisé, cela n'aura pas beaucoup d'impact. Ce qui suit est une réécriture de la phrase originale : Nous avons ensuite Tkinter.filedialog, qui est principalement utilisé pour demander le chemin de sauvegarde après la génération du labyrinthe. Après tout, le labyrinthe généré doit être préservé. Bien sûr, ajouter une minuterie avec Time semble être la cerise sur le gâteau.

Donc, il y a :

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

Ce que je veux expliquer ici, c'est que puisque beaucoup de contenu tel que les informations de version seront affichés lors de l'importation de Pygame (ce qui affecte l'esthétique ), nous devons utiliser Contextlib pour empêcher sa sortie.

Ensuite, nous devons demander quelques paramètres :

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

Ensuite, nous devons exécuter le programme qui génère le labyrinthe. En même temps, nous devons enregistrer le temps (équivalent à démarrer un chronomètre) :

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

Ensuite, le labyrinthe est officiellement généré. Avant d'introduire cette partie du code, nous devons comprendre l'algorithme :

La première étape consiste à générer une grille composée de cellules de labyrinthe (cellules blanches) et de murs (cellules noires). Le nombre d'unités du labyrinthe en lignes est égal au nombre de colonnes dans le labyrinthe, et en colonnes est égal au nombre de lignes dans le labyrinthe. Laissez l'unité de labyrinthe dans le coin supérieur gauche être le point de départ et l'unité de labyrinthe dans le coin inférieur droit le point final, et supprimez les murs à gauche du point de départ et à droite du point final, comme indiqué dans la photo :

La deuxième étape consiste à visiter chaque unité du labyrinthe. Marquez le point de départ comme l'unité de labyrinthe actuelle. Lorsqu'il y a une unité de labyrinthe non visitée (toute unité de labyrinthe qui est devenue l'unité de labyrinthe actuelle est considérée comme ayant été visitée), répétez l'exécution :

#🎜. 🎜 #
• Ajoutez les unités de labyrinthe environnantes non visitées au tableau

• S'il y a des unités de labyrinthe dans le tableau :
  # 🎜 🎜#
Poussez l'unité de labyrinthe actuelle dans la pile (peut être comprise comme l'ajoutant à une table appelée la pile) ; Au hasard dans le tableau, sélectionnez une unité de labyrinthe
Brisez le mur entre l'unité de labyrinthe actuelle et l'unité de labyrinthe sélectionnée ; ##🎜🎜 #Marquer l'unité de labyrinthe sélectionnée comme unité de labyrinthe actuelle
• S'il n'y a pas d'unité de labyrinthe dans le tableau :
  #🎜🎜 #
• Pop l'unité du labyrinthe en haut de la pile (ce qui peut être compris comme l'obtention et la suppression du dernier élément de la pile)

  #🎜🎜 ; #

sortira de la pile. L'unité du labyrinthe est définie comme l'unité du labyrinthe actuelle
Après la fin du cycle ; , le même résultat que le rendu au début de l'article apparaîtra.
• Ensuite, nous convertirons l'algorithme littéral en code Python.
  Tout d'abord, le programme ne reconnaît pas les images, il reconnaît les données. Afin de représenter l'image actuelle sous forme de chaîne de données, nous devons créer une liste bidimensionnelle. Bien sûr, nous pouvons d'ailleurs compléter ensemble le paramétrage de la première étape :

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

• Non seulement nous créons une liste de besoins qui stocke toutes les unités du labyrinthe, mais nous pouvons également la voir. Sa fonction est de déterminer si l'unité du labyrinthe a été visitée. Chaque visite supprimera l'unité du labyrinthe du tableau. Lorsqu'il n'y a aucune unité du labyrinthe dans le tableau, cela signifie que toutes les unités du labyrinthe ont été visitées.

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

  Et ces contenus sont la deuxième étape. J'ai déjà expliqué l'algorithme. La seule légère différence est qu'ici nous n'ajoutons pas les coordonnées des unités de labyrinthe adjacentes à la liste, mais ajoutons plutôt leurs murs brisés correspondants et les codes marqués comme unité de labyrinthe actuelle sous forme de chaînes. stocké dans la table, et après avoir sélectionné au hasard la chaîne correspondant à une certaine unité du labyrinthe, utilisez exec pour la convertir en code et l'exécuter (cela peut enregistrer du code).

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

Après avoir imprimé le temps nécessaire pour générer le labyrinthe, nous devons convertir les données du tableau en images. Bien entendu, avant de faire cela, nous devons d’abord déterminer l’emplacement où l’image est enregistré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

Avant de faire une sélection, vous devez déterminer si vous souhaitez enregistrer ou non l'image, car vous pouvez choisir de ne pas l'enregistrer. Le caractère "1" signifie ici une sauvegarde (si vous saisissez autre chose, elle ne sera naturellement pas enregistrée). Ensuite, vous devez sélectionner le chemin de sauvegarde (utilisez la méthode Askdirectory() pour sélectionner le chemin du fichier sans sélectionner de nom de fichier). Ensuite, nous devons confirmer que le nom du fichier est "a×b maze.png". Si le nom du fichier existe déjà dans le chemin, un numéro de série doit être ajouté après le nom du fichier. Au total, grâce à cette chaîne de code, nous avons déterminé le chemin + le nom du fichier du labyrinthe.

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

L'image "maze.png" utilisée dans le code (le nom n'est pas correct, vous devez la renommer après le téléchargement) :

#🎜 🎜#

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!