教你怎么用Python实现多路径迷宫
作者：明年十八岁 发布时间：2022-03-11 15:07:52
标签：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)
来源：https://blog.csdn.net/defaultbyzt/article/details/116238007
0
投稿猜你喜欢
本文用纯js代码手写一个瀑布流网页效果，初步实现一个基本的瀑布流布局，以及滚动到底部后模拟ajax数据加载新图片功能。缺点：1. 程序不是响- 图像增强算子几何变换算子图像的几何变换又称为图像空间变换， 它将一幅图像中的坐标位置映射到另一幅图像中的新坐标位置。图像缩放缩放只是调整图像
- 有的时候，为了对python文件进行加密，会把python模块编译成.pyd文件，供其他人调用。拿到一个.pyd文件，在没有文档说明的情况下
- 本文实例为大家分享了Python查询IP地址归属的具体代码，供大家参考，具体内容如下#!/usr/bin/env python# -*- c
- 这篇博客将介绍Canny边缘检测的概念，并利用cv2.Canny()实现边缘检测；Canny边缘检测是一种流行的边缘检测算法。它是由约翰F开
- 很多人在群里问，这个下拉框定位不到、那个弹出框定位不到…各种定位不到，其实大多数情况下就是两种问题：1 有frame，2 没有加等待。殊不知
- 在日常的测试工作中，我们的测试用例一般都是保存在Excel文件中，当然也有一些公司会使用Xmind来编写测试用例，那么为什么我们在这里只是讲
- python语言中的列表排序方法有三个：reverse反转/倒序排序、sort正序排序、sorted可以获取排序后的列表。在更高级列表排序中
- 切片：方便截取list、tuple、字符串部分索引的内容正序切片语法：dlist = doList[0:3]表示，从索引0开始取，直到索引3
- 在学习和使用各种数据库的过程中,我们常常会遇到聚族索引、非聚族索引、组合索引的概念,这些索引对我们使用数据库，特别是查询的速度的
- 本文实例讲述了Python使用cx_Oracle调用Oracle存储过程的方法。分享给大家供大家参考，具体如下：这里主要测试在Python中
- 如IP为192.168.1.111现要截取第二个.之前的值，得到结果192.168，很多网站都只显示前面2个值 &nb
- 理解新概念Python V2.2 中引入了迭代器的思想。唔，这并不十分正确；这种思想的“苗头”早已出现在较老的函数 xrange() 以及文
- 昨天在用用Pycharm读取一个200+M的CSV的过程中，竟然出现了Memory Error！简直让我怀疑自己买了个假电脑，毕竟是8G内存
- 代码如下: <％ '屏蔽主流的下载工具 Dimxurl,xtool '获取浏览器AGENT xurl=lcase(Re
- 前言因为工作中不怎么使用python，所以对python的了解不够，只是在使用的时候才去学，在之前的几个例子中几乎没使用什么python的特
- python解决循环依赖1.概述在使用python开发过程中在引入其他模块时可能都经历过一个异常就是循环引用most likely due
- 本文实例讲述了PHP中soap的用法，分享给大家供大家参考。具体用法分析如下：PHP 使用soap有两种方式。一、用wsdl文件服务器端：&
- 任何东西只要跟Google有关就总能给我们带来点儿惊喜，2008年9月2日发布的Google Chrome浏览器也不例外。Google Ch
- 说明1. 使用google翻译服务获得翻译和语音;2. 使用mplayer播放获得的声音文件，因此，如果要播放语音，请确保PATH中能够找到
