Python で迷路ジェネレーターを実装する方法

最初にレンダリングを表示します:

まず必要なライブラリを分析しましょう:

これはジェネレーターであるため、生成される迷路はまったく同じになります。毎回それは明らかに不当です。したがって、必然的に乱数（ランダムライブラリ）を使用する必要があります。迷路を描画する必要があるので、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()

これで、迷路が正式に生成されます。コードのこの部分を紹介する前に、アルゴリズムを理解する必要があります。

最初のステップは、迷路のセル (白いセル) と壁 (黒いセル) で構成されるグリッドを生成することです。行の迷路ユニットの数は迷路の列の数に等しく、列の迷路ユニットの数は迷路の行の数に等しい。左上隅の迷路ユニットを始点、右下隅の迷路ユニットを終点とし、図に示すように、始点の左側と終点の右側の壁を削除します。図:

2 番目のステップは、各迷路ユニットを訪問することです。開始点を現在の迷路ユニットとしてマークします。未訪問の迷路ユニットがある場合 (現在の迷路ユニットになった迷路ユニットは訪問済みとみなされます)、実行を繰り返します:

• 周囲の未訪問の迷路ユニットをテーブルに追加します;

• テーブルに迷路ユニットがある場合:

• 現在の迷路 ユニットをスタックにプッシュします (スタックと呼ばれるテーブルにユニットを追加すると理解できます);

• テーブルから迷路ユニットをランダムに選択します;

• 現在の迷路ユニットと選択した迷路ユニットの間の壁を壊します;

• 選択した迷路ユニットを現在の迷路ユニットとしてマークします;

• テーブルに迷路ユニットがない場合:

• 迷路ユニットをスタックの一番上にポップします (これは、取得すると理解できます)スタック内の最後の要素を削除します);

• ポップされた迷路ユニットを現在の迷路ユニットとして設定します;

サイクルが終了すると、記事の冒頭のものと同じレンダリング結果が表示されます。

次に、リテラル アルゴリズムを Python コードに変換します。

まず第一に、このプログラムは画像を認識するのではなく、データを認識します。現在の画像をデータの文字列として表すには、2 次元のリストを作成する必要があります。もちろん、最初のステップの設定を一緒に完了することもできます:

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

そしてこの内容が第2ステップです。アルゴリズムについては既に説明しましたが、唯一の違いは、ここでは隣接する迷路ユニットの座標をリストに追加するのではなく、対応する壊れた壁と、現在の迷路ユニットとしてマークされたコードを文字列として追加することです。形式は次のとおりです。をテーブルに保存し、特定の迷路ユニットに対応する文字列をランダムに選択した後、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 maze.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()

コードで使用されている画像「maze.png」(名前が正しくありません。ダウンロード後に名前を変更する必要があります):

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

以上がPython で迷路ジェネレーターを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。