教你怎么用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实现多路径迷宫内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！