小编给大家分享一下如何使用Python实现多路径迷宫,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!
python的数据类型:1. 数字类型,包括int(整型)、long(长整型)和float(浮点型)。2.字符串,分别是str类型和unicode类型。3.布尔型,Python布尔类型也是用于逻辑运算,有两个值:True(真)和False(假)。4.列表,列表是Python中使用最频繁的数据类型,集合中可以放任何数据类型。5. 元组,元组用”()”标识,内部元素用逗号隔开。6. 字典,字典是一种键值对的集合。7. 集合,集合是一个无序的、不重复的数据组合。
在已有的单路径迷宫基础上打开一块合适的墙就可以构成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实现多路径迷宫”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。