教你怎麼用Python實現多路徑迷宮
一、思路介紹
- 在已有的單路徑迷宮基礎上打開一塊合適的墻就可以構成2路徑的迷宮。
- 打開的墻不能和已有的路徑過近。
- 1。從開始和終點開始進行廣度優先搜索,並為迷宮中的每個單元格記錄單元格遠離開始和終點的步數。
- 2。通過將距離開頭較近的所有單元格放入 start 集合,並將更接近目標的所有單元格放入end集合來將迷宮分成兩個部分。
- 3。 選擇分開兩個區域的任意一面墻拆開就可以形成2通路的迷宮。
- 如想生成最短的通路可以選擇相鄰格子距離差值最大的那面墻拆開,一般情況下這兩條路距離也比較遠。
二、圖示
三、分區域演示代碼
#!/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 # 設置窗口大小 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) # 藍格子 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("找到終點", True, COLOR[COLOR_BLACK], COLOR[COLOR_GREY]) # 時間 clock = pygame.time.Clock() ############################################## # 格子訪問標記x,y,0,右墻x,y,1,下墻x,y,2 ############################################## #標記 NOWALL=maze.NOWALL # 無墻 WALL=maze.WALL # 有墻 WALL2=maze.WALL2 # 有墻 VISIT=maze.VISIT # 到訪過 NOVISIT=maze.NOVISIT # 沒到過 VERTICAL = maze.VERTICAL # 垂直的 HORIZONTAL = maze.HORIZONTAL# 水平的 INFINITE = maze.INFINITE # 無窮遠 INFINITE = maze.INFINITE # 無窮遠 # def FindNext(pathList, walls, grids, rows, cols): nextList = [] # 下一步 for node in pathList: r, c = node l = grids[r][c] nl=l+1 # 可以到達的位置 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] # 標記訪問過的格子 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] # 標記訪問過的格子 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)] # 起點 # 標記迷宮 r=0 c=0 findEndPoint=False findPath=False # 起點 startPoint=(r,c) # 終點 stopPoint=(rows-1,cols-1) # mainList=[] # 主路徑 beginList=[startPoint] endList=[stopPoint] grids[r][c]=0 # 標記已經到過格子距離 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] # 可以到達的位置 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] # 可以到達的位置 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 # 找到起點 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] # 標記訪問過的格子 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]) # 循環外圈 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)
到此這篇關於教你怎麼用Python實現多路徑迷宮的文章就介紹到這瞭,更多相關Python實現多路徑迷宮內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!