教你怎么用Python实现多路径迷宫
更新时间:2021年4月29日 20:01 点击:1993
一、思路介绍
- 在已有的单路径迷宫基础上打开一块合适的墙就可以构成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实现多路径迷宫内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
上一篇: Django一小时写出账号密码管理系统
相关文章
- 这篇文章主要介绍了python-opencv-画外接矩形框的实例代码,代码简单易懂,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-09-04
Python astype(np.float)函数使用方法解析
这篇文章主要介绍了Python astype(np.float)函数使用方法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-06-08- 2022虎年新年即将来临,小编为大家带来了一个利用Python编写的虎年烟花特效,堪称全网最绚烂,文中的示例代码简洁易懂,感兴趣的同学可以动手试一试...2022-02-14
- 在本篇文章里小编给大家分享的是一篇关于python中numpy.empty()函数实例讲解内容,对此有兴趣的朋友们可以学习下。...2021-02-06
python-for x in range的用法(注意要点、细节)
这篇文章主要介绍了python-for x in range的用法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-05-10- 这篇文章主要介绍了Python 图片转数组,二进制互转操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-09
- 这篇文章主要介绍了Python中的imread()函数用法说明,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-16
- 这篇文章主要介绍了python如何实现b站直播自动发送弹幕,帮助大家更好的理解和学习使用python,感兴趣的朋友可以了解下...2021-02-20
python Matplotlib基础--如何添加文本和标注
这篇文章主要介绍了python Matplotlib基础--如何添加文本和标注,帮助大家更好的利用Matplotlib绘制图表,感兴趣的朋友可以了解下...2021-01-26- 这篇文章主要介绍了解决python 使用openpyxl读写大文件的坑,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-13
- 今天小编就为大家分享一篇python 计算方位角实例(根据两点的坐标计算),具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-27
- 这篇文章主要介绍了使用Python的pencolor函数实现渐变色功能,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-09
- 在本篇文章里小编给大家整理的是一篇关于python中使用np.delete()的实例方法,对此有兴趣的朋友们可以学习参考下。...2021-02-01
- 这篇文章主要为大家详细介绍了python实现双色球随机选号,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-05-02
Python getsizeof()和getsize()区分详解
这篇文章主要介绍了Python getsizeof()和getsize()区分详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-20- 这篇文章主要介绍了python自动化办公操作PPT的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-05
- 这篇文章主要介绍了解决python 两个时间戳相减出现结果错误的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-12
- 这篇文章主要为大家详细介绍了python实现学生通讯录管理系统,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-25
- 这篇文章主要介绍了PyTorch一小时掌握之迁移学习篇,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-09-08
- 这篇文章主要介绍了python进行相关性分析并绘制散点图,具有一定借鉴价值,需要的朋友可以参考下,希望能够给你带来帮助...2021-09-18