教你怎么用Python實(shí)現(xiàn)多路徑迷宮
更新時(shí)間：2021年04月29日 15:36:07 作者：明年十八歲
這篇文章主要介紹了教你怎么用Python實(shí)現(xiàn)多路徑迷宮,文中有非常詳細(xì)的代碼示例,對(duì)正在學(xué)習(xí)python的小伙伴們有非常好的幫助,需要的朋友可以參考下
一、思路介紹
- 在已有的單路徑迷宮基礎(chǔ)上打開一塊合適的墻就可以構(gòu)成2路徑的迷宮。
- 打開的墻不能和已有的路徑過近。
- 1。從開始和終點(diǎn)開始進(jìn)行廣度優(yōu)先搜索，并為迷宮中的每個(gè)單元格記錄單元格遠(yuǎn)離開始和終點(diǎn)的步數(shù)。
- 2。通過將距離開頭較近的所有單元格放入 start 集合，并將更接近目標(biāo)的所有單元格放入end集合來將迷宮分成兩個(gè)部分。
- 3。 選擇分開兩個(gè)區(qū)域的任意一面墻拆開就可以形成2通路的迷宮。
- 如想生成最短的通路可以選擇相鄰格子距離差值最大的那面墻拆開，一般情況下這兩條路距離也比較遠(yuǎn)。
二、圖示
三、分區(qū)域演示代碼
#!/usr/bin/python3.7
# -*- coding: utf-8 -*-
import random
import pygame
#import depth_maze
import maze
#import aldous_broder_maze
pygame.init() # 初始化pygame
size = width, height = 800, 600 # 設(shè)置窗口大小
screen = pygame.display.set_mode(size) # 顯示窗口
# 顏色
diamond_color_size = 8
COLOR_RED, COLOR_BLUE, COLOR_GREEN, COLOR_YELLOW, COLOR_BLACK, COLOR_GREY, COLOR_GOLDEN, COLOR_NO_DIAMOND = list(range(
diamond_color_size))
COLOR = {
COLOR_RED: (255, 0, 0),
COLOR_BLUE: (0, 0, 255),
COLOR_GREEN: (0, 255, 0),
COLOR_YELLOW: (255, 255, 0),
COLOR_BLACK: (0, 0, 0),
COLOR_GREY: (250, 240, 230),
COLOR_GOLDEN : (255,215,0),
COLOR_NO_DIAMOND: (100, 100, 100),
}
# 格子大小
DIAMOND_LEN = 20
DIAMOND_SIZE = (DIAMOND_LEN, DIAMOND_LEN)
# 藍(lán)格子
DIAMOND=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND.fill(COLOR[COLOR_BLUE])
# 綠格子
DIAMOND_GREEN=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_GREEN.fill(COLOR[COLOR_GREEN])
# 紅格子
DIAMOND_RED=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_RED.fill(COLOR[COLOR_RED])
# 黃格子
DIAMOND_YELLOW=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_YELLOW.fill(COLOR[COLOR_YELLOW])
# 灰的格子
DIAMOND_GREY=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_GREY.fill(COLOR[COLOR_GREY])
# 字體
use_font = pygame.font.Font("FONT.TTF", 16)
use_font12 = pygame.font.Font("FONT.TTF", 12)
# 背景
background=pygame.surface.Surface(size).convert()
background.fill(COLOR[COLOR_BLACK])
# 文字
score_surface = use_font.render("找到終點(diǎn)", True, COLOR[COLOR_BLACK], COLOR[COLOR_GREY])
# 時(shí)間
clock = pygame.time.Clock()
##############################################
# 格子訪問標(biāo)記x,y,0，右墻x,y,1，下墻x,y,2
##############################################
#標(biāo)記
NOWALL=maze.NOWALL # 無墻
WALL=maze.WALL # 有墻
WALL2=maze.WALL2 # 有墻
VISIT=maze.VISIT # 到訪過
NOVISIT=maze.NOVISIT # 沒到過
VERTICAL = maze.VERTICAL # 垂直的
HORIZONTAL = maze.HORIZONTAL# 水平的
INFINITE = maze.INFINITE # 無窮遠(yuǎn)
INFINITE = maze.INFINITE # 無窮遠(yuǎn)
#
def FindNext(pathList, walls, grids, rows, cols):
nextList = [] # 下一步
for node in pathList:
r, c = node
l = grids[r][c]
nl=l+1
# 可以到達(dá)的位置
if r>0 and NOWALL == walls[r][c][1] and INFINITE == grids[r-1][c]:
# move = 'u'
nr=r-1
nc=c
if (nr,nc) not in nextList:
nextList.append((nr,nc))
grids[nr][nc] = l+1
if c>0 and NOWALL == walls[r][c][0] and INFINITE == grids[r][c-1]:
# move = 'l'
nr=r
nc=c-1
if (nr,nc) not in nextList:
nextList.append((nr,nc))
grids[nr][nc] = l+1
if c<cols-1 and NOWALL == walls[r][c+1][0] and INFINITE == grids[r][c+1] :
# move='r'
nr=r
nc=c+1
if (nr,nc) not in nextList:
nextList.append((nr,nc))
grids[nr][nc] = l+1
if r<rows-1 and NOWALL == walls[r+1][c][1] and INFINITE == grids[r+1][c] :
# move='d'
nr=r+1
nc=c
if (nr,nc) not in nextList:
nextList.append((nr,nc))
grids[nr][nc] = l+1
return nextList
def draw_diamond(r,c, screen, POSX, POSY, diamod):
px,py=POSX + 1 + (c) * DIAMOND_SIZE[0], POSY + 1 + (r) * DIAMOND_SIZE[1]
# 標(biāo)記訪問過的格子
screen.blit(diamod, (px, py))
return
def draw_diamond_and_str(r,c, screen, POSX, POSY, diamod, use_font, string, color, color_back):
px,py=POSX + 1 + (c) * DIAMOND_SIZE[0], POSY + 1 + (r) * DIAMOND_SIZE[1]
# 標(biāo)記訪問過的格子
screen.blit(diamod, (px, py))
distance_surface = use_font.render(string, True, color, color_back)
screen.blit(distance_surface, (px, py))
return
# Sample algorithm
def multipath_maze_demo(rows, cols):
#walls = maze.aldous_broder_maze(rows, cols)
#walls = maze.depth_maze(rows, cols)
#walls = maze.kruskal_maze(rows, cols)
#walls = maze.prim_maze(rows, cols)
#walls = maze.wilson_maze(rows, cols)
walls = maze.wilson_maze(rows, cols)
POSX=40
POSY=40
# 初始化未訪問
grids=[[ INFINITE for i in range(cols)]for j in range(rows)]
# 起點(diǎn)
# 標(biāo)記迷宮
r=0
c=0
findEndPoint=False
findPath=False
# 起點(diǎn)
startPoint=(r,c)
# 終點(diǎn)
stopPoint=(rows-1,cols-1)
#
mainList=[] # 主路徑
beginList=[startPoint]
endList=[stopPoint]
grids[r][c]=0 # 標(biāo)記已經(jīng)到過格子距離
grids[stopPoint[0]][stopPoint[1]]=0
# 沒有訪問過的格子
notUseGrids = []
for tr in range(rows):
for tc in range(cols):
notUseGrids.append((tr,tc))
beginMap=beginList
endMap=endList
while True:
for event in pygame.event.get():
if event.type == pygame.QUIT:
return
if notUseGrids:
beginNextList = [] # 下一步
for node in beginList:
r, c = node
l = grids[r][c]
# 可以到達(dá)的位置
if r>0 and NOWALL == walls[r][c][1] and INFINITE == grids[r-1][c]:
# move = 'u'
nr=r-1
nc=c
if (nr,nc) not in beginNextList:
beginNextList.append((nr,nc))
grids[nr][nc] = l+1
if c>0 and NOWALL == walls[r][c][0] and INFINITE == grids[r][c-1]:
# move = 'l'
nr=r
nc=c-1
if (nr,nc) not in beginNextList:
beginNextList.append((nr,nc))
grids[nr][nc] = l+1
if c<cols-1 and NOWALL == walls[r][c+1][0] and INFINITE == grids[r][c+1] :
# move='r'
nr=r
nc=c+1
if (nr,nc) not in beginNextList:
beginNextList.append((nr,nc))
grids[nr][nc] = l+1
if r<rows-1 and NOWALL == walls[r+1][c][1] and INFINITE == grids[r+1][c] :
# move='d'
nr=r+1
nc=c
if (nr,nc) not in beginNextList:
beginNextList.append((nr,nc))
grids[nr][nc] = l+1
# 下一圈
beginList = beginNextList
beginMap = beginMap + beginNextList
# end
endNextList = [] # 下一步
for node in endList:
r, c = node
l = grids[r][c]
# 可以到達(dá)的位置
if r>0 and NOWALL == walls[r][c][1] and INFINITE == grids[r-1][c]:
# move = 'u'
nr=r-1
nc=c
if (nr,nc) not in endNextList:
endNextList.append((nr,nc))
grids[nr][nc] = l+1
if c>0 and NOWALL == walls[r][c][0] and INFINITE == grids[r][c-1]:
# move = 'l'
nr=r
nc=c-1
if (nr,nc) not in endNextList:
endNextList.append((nr,nc))
grids[nr][nc] = l+1
if c<cols-1 and NOWALL == walls[r][c+1][0] and INFINITE == grids[r][c+1] :
# move='r'
nr=r
nc=c+1
if (nr,nc) not in endNextList:
endNextList.append((nr,nc))
grids[nr][nc] = l+1
if r<rows-1 and NOWALL == walls[r+1][c][1] and INFINITE == grids[r+1][c] :
# move='d'
nr=r+1
nc=c
if (nr,nc) not in endNextList:
endNextList.append((nr,nc))
grids[nr][nc] = l+1
# 下一圈
endList = endNextList
endMap = endMap + endNextList
elif findEndPoint and not findPath:
mainList.append((r,c))
l = grids[r][c]
nl=l-1
# 最近的
if r>0 and NOWALL == walls[r][c][1] and nl == grids[r-1][c]:
# move = 'u'
nr=r-1
nc=c
if c>0 and NOWALL == walls[r][c][0] and nl == grids[r][c-1]:
# move = 'l'
nr=r
nc=c-1
beginNextList.append((nr,nc))
if c<cols-1 and NOWALL == walls[r][c+1][0] and nl == grids[r][c+1] :
# move='r'
nr=r
nc=c+1
if r<rows-1 and NOWALL == walls[r+1][c][1] and nl == grids[r+1][c] :
# move='d'
nr=r+1
nc=c
# 找到起點(diǎn)
if 0 == nl:
mainList.append((nr,nc))
findPath = True
r,c=nr,nc
screen.blit(background, (0, 0))
# 格子
for cx in range(cols):
for ry in range(rows):
px,py=POSX + 1 + (cx) * DIAMOND_SIZE[0], POSY + 1 + (ry) * DIAMOND_SIZE[1]
# 標(biāo)記訪問過的格子
if maze.INFINITE == grids[ry][cx]:
draw_diamond(ry, cx, screen, POSX, POSY, DIAMOND)
else:
s = "{}".format(grids[ry][cx])
draw_diamond_and_str(ry, cx, screen, POSX,POSY, DIAMOND_GREY, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_GREY])
# 圈地
for pos in beginMap:
s = "{}".format(grids[pos[0]][pos[1]])
draw_diamond_and_str(pos[0], pos[1], screen, POSX,POSY, DIAMOND_GREEN, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_GREEN])
for pos in endMap:
s = "{}".format(grids[pos[0]][pos[1]])
draw_diamond_and_str(pos[0], pos[1], screen, POSX,POSY, DIAMOND_YELLOW, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_YELLOW])
# 循環(huán)外圈
if beginList and not mainList:
for pos in beginList:
s = "{}".format(grids[pos[0]][pos[1]])
draw_diamond_and_str(pos[0], pos[1], screen, POSX,POSY, DIAMOND_RED, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_RED])
for pos in endList:
s = "{}".format(grids[pos[0]][pos[1]])
draw_diamond_and_str(pos[0], pos[1], screen, POSX,POSY, DIAMOND_RED, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_RED])
# 路徑
if mainList:
for pos in mainList:
s = "{}".format(grids[pos[0]][pos[1]])
draw_diamond_and_str(pos[0], pos[1], screen, POSX,POSY, DIAMOND_YELLOW, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_YELLOW])
# r,c
px,py=POSX + 1 + (c) * DIAMOND_SIZE[0], POSY + 1 + (r) * DIAMOND_SIZE[1]
screen.blit(DIAMOND_GREEN, (px, py))
s = "{}".format(grids[r][c])
distance_surface = use_font12.render(s, True, COLOR[COLOR_BLACK], COLOR[COLOR_GREEN])
screen.blit(distance_surface, (px, py))
# 畫外墻
pygame.draw.rect(screen, COLOR[COLOR_RED], (POSX + 0, POSY + 0, DIAMOND_LEN*cols+1, DIAMOND_LEN*rows+1), 2)
# 畫沒打通的墻
for cx in range( cols):
for ry in range(rows):
px,py=POSX + 1 + (cx) * DIAMOND_SIZE[0], POSY + 1 + (ry) * DIAMOND_SIZE[1]
color = COLOR[COLOR_BLACK]
if maze.WALL == walls[ry][cx][0]:
pygame.draw.line(screen, color, (px, py), (px, py+DIAMOND_LEN), 2)
if maze.WALL == walls[ry][cx][1]:
pygame.draw.line(screen, color, (px, py), (px+DIAMOND_LEN, py), 2)
# 打印文字提示
if findEndPoint:
screen.blit(score_surface, (POSX+50, POSY+rows*22))
# 幀率
clock.tick(25)
pygame.display.update()
return
# main
if __name__ == "__main__":
'''main'''
multipath_maze_demo(20, 30)
到此這篇關(guān)于教你怎么用Python實(shí)現(xiàn)多路徑迷宮的文章就介紹到這了,更多相關(guān)Python實(shí)現(xiàn)多路徑迷宮內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
- 如何用 Python 制作一個(gè)迷宮游戲
- Python 實(shí)現(xiàn)遞歸法解決迷宮問題的示例代碼
- Python迷宮生成和迷宮破解算法實(shí)例
- 10分鐘教你用python動(dòng)畫演示深度優(yōu)先算法搜尋逃出迷宮的路徑
- Python解決走迷宮問題算法示例
- 一道python走迷宮算法題
- Python深度優(yōu)先算法生成迷宮
- Python使用Tkinter實(shí)現(xiàn)機(jī)器人走迷宮
- Python基于分水嶺算法解決走迷宮游戲示例
- Python使用回溯法子集樹模板解決迷宮問題示例
- Python基于遞歸算法實(shí)現(xiàn)的走迷宮問題
- 用Python代碼來解圖片迷宮的方法整理
- python實(shí)現(xiàn)的生成隨機(jī)迷宮算法核心代碼分享（含游戲完整代碼）
相關(guān)文章
python模塊簡(jiǎn)介之有序字典（OrderedDict）
字典是Python開發(fā)中很常用的一種數(shù)據(jù)結(jié)構(gòu)，但dict有個(gè)缺陷（其實(shí)也不算缺陷），迭代時(shí)并不是按照元素添加的順序進(jìn)行，可能在某些場(chǎng)景下，不能滿足我們的要求。2016-12-12
python實(shí)現(xiàn)word文檔批量轉(zhuǎn)成自定義格式的excel文檔的思路及實(shí)例代碼
這篇文章主要介紹了python實(shí)現(xiàn)word文檔批量轉(zhuǎn)成自定義格式的excel文檔的解決思路及實(shí)例代碼，代碼簡(jiǎn)單易懂，非常不錯(cuò)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-02-02
Python通過PIL獲取圖片主要顏色并和顏色庫(kù)進(jìn)行對(duì)比的方法
這篇文章主要介紹了Python通過PIL獲取圖片主要顏色并和顏色庫(kù)進(jìn)行對(duì)比的方法,實(shí)例分析了Python通過PIL模塊操作圖片的技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-03-03
這篇文章主要介紹了最基礎(chǔ)的Python的socket編程入門教程,包括最基本的發(fā)送和接受信息等內(nèi)容,需要的朋友可以參考下2015-04-04
requests是一個(gè)很實(shí)用的Python HTTP客戶端庫(kù)，爬蟲和測(cè)試服務(wù)器響應(yīng)數(shù)據(jù)時(shí)經(jīng)常會(huì)用到，requests是Python語言的第三方的庫(kù)，專門用于發(fā)送HTTP請(qǐng)求，使用起來比urllib簡(jiǎn)潔很多，這篇文章主要介紹requests的基礎(chǔ)用法2023-04-04
python 已知平行四邊形三個(gè)點(diǎn),求第四個(gè)點(diǎn)的案例
這篇文章主要介紹了python 已知平行四邊形三個(gè)點(diǎn),求第四個(gè)點(diǎn)的案例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-04-04
這篇文章主要介紹了python使用matplotlib顯示圖像失真的解決方案，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2021-04-04
這篇文章主要介紹了python校驗(yàn)SQL腳本命名規(guī)則，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-03-03
異步任務(wù)隊(duì)列Celery在Django中的使用方法
對(duì)于網(wǎng)站來說，給用戶一個(gè)較好的體驗(yàn)是很重要的事情，其中最重要的指標(biāo)就是網(wǎng)站的瀏覽速度。因此服務(wù)端要從各個(gè)方面對(duì)網(wǎng)站性能進(jìn)行優(yōu)化，這篇文章主要介紹了異步任務(wù)隊(duì)列Celery在Django中的使用方法，感興趣的小伙伴們可以參考一下2018-06-06
jupyter notebook是一個(gè)以網(wǎng)頁(yè)形式來使用的python編輯器,很多小伙伴在第一次安裝它的時(shí)候選擇的都是默認(rèn)安裝，那么jupyter默認(rèn)工作目錄如何更改，本文就來介紹一下2023-08-08