欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python?Prim算法通過遍歷墻實(shí)現(xiàn)迷宮的生成

 更新時(shí)間：2023年01月06日 09:13:06   作者：Leleprogrammer  
之前，我們在另外一篇文章中使用Prim算法生成了一個(gè)完美迷宮，利用的是遍歷網(wǎng)格的方法，這一次，我們要教教大家用遍歷墻的方法生成，感興趣的可以收藏一下

之前，我們在另外一篇文章中使用Prim算法生成了一個(gè)完美迷宮，利用的是遍歷網(wǎng)格的方法，這一次，我們要教教大家用遍歷墻的方法生成，上一篇文章鏈接：Python利用Prim算法生成迷宮

我們需要用到隨機(jī)庫random，以及用來計(jì)算算法使用時(shí)間的time模塊

導(dǎo)入這些模塊

import random as rd
import time

我們定義一個(gè)函數(shù)

def createMaze(a,b): # a:width b:height

添加一個(gè)變量儲(chǔ)存算法開始的時(shí)間

startTime=time.time()

定義maze

maze={}

maze用來儲(chǔ)存迷宮地圖，格式如下：

{(n,"u"):0}

n表示第n個(gè)塊，u d l r分別表示上下左右的墻壁，0表示沒有墻壁，1表示有墻壁，初始是全部為1，生成的代碼如下：

    for n in range(a*b):
        for face in ["u","d","l","r"]:
            maze[(n,face)]=1

創(chuàng)建兩個(gè)變量

    history=[]
    walls=[]

先初始隨機(jī)選一個(gè)塊并添加到遍歷過的方塊之中

block=rd.choice(list(maze.keys()))[0]
history.append(block)

將這個(gè)方塊的四個(gè)面的對應(yīng)的墻都添加到候選墻的列表之中

    for face in ["u","d","l","r"]:
        walls.append((block,face))

只要候選墻不為空就一直循環(huán)

while len(walls)!=0:

選擇一面墻，獲取這個(gè)墻壁分割開來的兩個(gè)塊，如果已經(jīng)到達(dá)邊界外，則為None。注意，在最后一個(gè)elif之中，獲取len(maze)要除以4，因?yàn)槲覀兠總€(gè)塊有4個(gè)不同方向的墻壁，這個(gè)也是很容易疏忽的一點(diǎn)。

        wall=rd.choice(walls)
        twoBlocks=[wall[0]]
        faces=[wall[1]]
        if wall[1]=="u":
            if wall[0]-a<0:
                twoBlocks.append(None)
            else:
                twoBlocks.append(wall[0]-a)
                faces.append("d")
        elif wall[1]=="r":
            if (wall[0]+1)%a!=0:
                twoBlocks.append(wall[0]+1)
                faces.append("l")
            else:
                twoBlocks.append(None)
        elif wall[1]=="l":
            if wall[0]%a!=0:
                twoBlocks.append(wall[0]-1)
                faces.append("r")
            else:
                twoBlocks.append(None)
        elif wall[1]=="d":
            if wall[0]+a>len(maze)/4-1:
                twoBlocks.append(None)
            else:
                twoBlocks.append(wall[0]+a)
                faces.append("u")

再定義兩個(gè)列表

        ins=[]
        infaces=[]

獲取這兩個(gè)方塊中有被添加到history的

        for i,oneBlock in enumerate(twoBlocks):
            if oneBlock in history:
                ins.append(oneBlock)
                infaces.append(faces[i])

因?yàn)橹挥幸粋€(gè)被遍歷過，所以我們就需要把這兩個(gè)塊中間的墻刪掉，其實(shí)這里有兩面，一面是第一個(gè)塊的，另一個(gè)是第二個(gè)塊相反方向的，只是重疊了，我們需要把這兩面墻對應(yīng)的值都設(shè)置為0，首先獲取mirrorFace，也就是相反的方向，如果None在這兩個(gè)方塊的列表之中，那么就說明其中一個(gè)塊在邊上，所以就不需要再把這面墻刪掉，保留這面墻，直接從候選墻之中刪掉這面墻并開始新的循環(huán)，使用continue；如果他不是邊上的塊，也就是說twoBlocks里面沒有None，就先把第一個(gè)塊的那面墻去掉（改為0），然后獲取另一個(gè)塊放在other變量中，再把這第二個(gè)塊的墻改為0，然后把這第二個(gè)塊添加到history中，然后將這第二個(gè)塊的四面墻都添加到候選墻中，注意，這里要添加的墻的值必須是1，也就是沒有被檢查遍歷過的墻，如果候選墻已經(jīng)有這面墻，就無需再添加，用for循環(huán)和if語句搭配，就可以簡簡單單寫出這段代碼，邏輯理清楚就不難寫啦！代碼如下：

        if len(ins)==1:
            mirrorFace=None
            if infaces[0]=="u":
                mirrorFace="d"
            elif infaces[0]=="d":
                mirrorFace="u"
            elif infaces[0]=="r":
                mirrorFace="l"
            elif infaces[0]=="l":
                mirrorFace="r"
            if not (None in twoBlocks):
                maze[(ins[0],infaces[0])]=0
                other=None
                if ins[0]==twoBlocks[0]:
                    other=twoBlocks[1]
                else:
                    other=twoBlocks[0]
                maze[(other,mirrorFace)]=0
                walls.remove(wall)
                history.append(other)
                for face in ["u","l","r","d"]:
                    if maze.get((other,face))==1 and not ((other,face) in walls):
                        walls.append((other,face))
            else:
                walls.remove(wall)
                continue
        elif len(ins)==2:
            walls.remove(wall)

寫到這兒，我們的算法就差不多結(jié)束了，最后添加endTime獲取算法結(jié)束時(shí)間

endTime=time.time()

并將它輸出到控制臺

print(f"生成迷宮使用時(shí)間：{endTime-startTime}秒")

返回迷宮

return maze

這個(gè)算法速度挺快的，99x99的迷宮只用了三秒多，一般三十多乘三十多的也只生成了30毫秒，效率很高！

到此這篇關(guān)于Python Prim算法通過遍歷墻實(shí)現(xiàn)迷宮的生成的文章就介紹到這了,更多相關(guān)Python Prim生成迷宮內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

最新評論