Sample algorithm算法

本篇文章禁止转载

Sample algorithm

算法介绍

英文介绍

• This is a fairly simple and easy-to-understand pathfinding algorithm for tile-based maps. To start off, you have a map, a start coordinate and a destination coordinate. The map will look like this, X being walls, S being the start, O being the finish and _ being open spaces, the numbers along the top and right edges are the column and row numbers:

• First, create a list of coordinates, which we will use as a queue. The queue will be initialized with one coordinate, the end coordinate. Each coordinate will also have a counter variable attached (the purpose of this will soon become evident).

• Then, go through every element in the queue, including new elements added to the end over the course of the algorithm, and for each element, do the following:
• 1.Create a list of the four adjacent cells, with a counter variable of the current element’s counter variable + 1
• 2.Check all cells in each list for the following two conditions:
  • 1.If the cell is a wall, remove it from the list
  • 2.If there is an element in the main list with the same coordinate, remove it from the cells list
• 3.Add all remaining cells in the list to the end of the main list
• 4.Go to the next item in the list

  我的翻译

• 对于基于瓦片的地图来说，这是一个相当简单且易于理解的寻路算法。首先，你有一张地图，一个起始坐标和一个目的地坐标。地图是这样的，X是墙，S是开始，O是结束，_是开放空间，顶部和右边的数字是列号和行号:
• 首先，创建一个坐标列表，我们将其用作队列。队列将用一个坐标初始化，即end坐标。每个坐标还将附加一个计数器变量(其目的很快就会变得明显)。
• 然后，遍历队列中的每个元素，包括在算法过程中添加到队列末尾的新元素，并对每个元素执行以下操作:
• 1。创建一个包含四个相邻单元格的列表，使用当前元素的计数器变量+1做新格的计数器变量
• 2。检查每个列表中的所有单元格，满足以下两个条件:
  • 1。如果单元格是一堵墙，将其从列表中删除
  • 2。如果主列表中有一个具有相同坐标的元素，则将其从单元格列表中删除
• 3。将列表中所有剩余的单元格添加到主列表的末尾
• 4。转到列表中的下一项

寻路结果图

演示代码

#!/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_SIZE = (20, 20)
# 蓝格子
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 # 无穷远

# 抽样算法

# Sample algorithm
def sample_pathfinding(rows, cols, walls, startPoint=(0,0), endPoint=None):
    # walls = depth_maze.depth_maze(rows, cols)
    # 初始化未访问
    grids=[[ INFINITE for i in range(cols)]for j in range(rows)]
    # 起点
    r=startPoint[0]
    c=startPoint[1]
    findEndPoint=False
    findPath=False
    # 终点
    if endPoint:
        stopPoint=endPoint
    else:
        stopPoint=(rows-1,cols-1)

    # 
    mainList=[] # 主路径
    pathList=[(r,c,0)] # 路径
    grids[r][c]=0 # 标记已经到过格子距离
    while not findPath:
        # 当存在未访问细胞时:
        if  pathList and not findEndPoint:        
            nextList = [] # 下一步
            for node in pathList:
                r, c, l = node
                if (r,c) == stopPoint:
                    # 找到终点
                    grids[r][c] = l
                    findEndPoint=True
                    break
                # 可以到达的位置
                if r>0 and NOWALL == walls[r][c][1] and INFINITE == grids[r-1][c]:
                    # move = 'u'
                    nr=r-1
                    nc=c
                    nextList.append((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
                    nextList.append((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
                    nextList.append((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
                    nextList.append((nr,nc,l+1))
                #if nextList:
                #    # 后面有可到达的路径，记录当前点与起点的距离
                #    grids[r][c] = l
                if  INFINITE == grids[r][c]:
                    grids[r][c] = l
            # 下一圈
            pathList = nextList
        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
                nextList.append((nr,nc,l+1))
            if c>0 and NOWALL == walls[r][c][0] and nl == grids[r][c-1]:
                # move = 'l'
                nr=r
                nc=c-1
                nextList.append((nr,nc,l+1))
            if c<cols-1 and NOWALL == walls[r][c+1][0] and nl == grids[r][c+1] :
                # move='r'
                nr=r
                nc=c+1
                nextList.append((nr,nc,l+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
                nextList.append((nr,nc,l+1))
            if 0 == nl:
                mainList.append((nr,nc))
                findPath = True
                break
            r,c=nr,nc

    return mainList, grids


# Sample algorithm
def sample_pathfinding_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)
    
    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=[] # 主路径
    pathList=[(r,c,0)] # 路径
    grids[r][c]=0 # 标记已经到过格子距离

    #fpath, grids = sample_pathfinding(rows,cols,walls)
    #mainList = fpath
    #findEndPoint = True
    #findPath = True

    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                return
        # 当存在未访问细胞时:
        if  pathList and not findEndPoint:        
            nextList = [] # 下一步
            for node in pathList:
                r, c, l = node
                if (r,c) == stopPoint:
                    # 找到终点
                    grids[r][c] = l
                    pathList=[]
                    findEndPoint=True
                    break
                # 可以到达的位置
                if r>0 and NOWALL == walls[r][c][1] and INFINITE == grids[r-1][c]:
                    # move = 'u'
                    nr=r-1
                    nc=c
                    nextList.append((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
                    nextList.append((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
                    nextList.append((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
                    nextList.append((nr,nc,l+1))
                #if nextList:
                #    # 后面有可到达的路径，记录当前点与起点的距离
                #    grids[r][c] = l
                if  INFINITE == grids[r][c]:
                    grids[r][c] = l
            # 下一圈
            pathList = nextList
        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
                nextList.append((nr,nc,l+1))
            if c>0 and NOWALL == walls[r][c][0] and nl == grids[r][c-1]:
                # move = 'l'
                nr=r
                nc=c-1
                nextList.append((nr,nc,l+1))
            if c<cols-1 and NOWALL == walls[r][c+1][0] and nl == grids[r][c+1] :
                # move='r'
                nr=r
                nc=c+1
                nextList.append((nr,nc,l+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
                nextList.append((nr,nc,l+1))
            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]:
                    screen.blit(DIAMOND, (px, py))
                else:
                    screen.blit(DIAMOND_GREY, (px, py))
                    s = "{}".format(grids[ry][cx])
                    distance_surface = use_font12.render(s, True, COLOR[COLOR_BLACK], COLOR[COLOR_GREY])
                    screen.blit(distance_surface, (px, py))
        
        if pathList and not mainList:
            # 当前圈
            for pos in pathList:
                px,py=POSX + 1 + (pos[1]) * DIAMOND_SIZE[0], POSY + 1 + (pos[0]) * DIAMOND_SIZE[1]
                screen.blit(DIAMOND_GREEN, (px, py))
                s = "{}".format(grids[pos[0]][pos[1]])
                distance_surface = use_font12.render(s, True, COLOR[COLOR_BLACK], COLOR[COLOR_GREEN])
                screen.blit(distance_surface, (px, py))
        if mainList:
            # 路径
            for pos in mainList:
                px,py=POSX + 1 + (pos[1]) * DIAMOND_SIZE[0], POSY + 1 + (pos[0]) * DIAMOND_SIZE[1]
                screen.blit(DIAMOND_YELLOW, (px, py))
                s = "{}".format(grids[pos[0]][pos[1]])
                distance_surface = use_font12.render(s, True, COLOR[COLOR_BLACK], COLOR[COLOR_YELLOW])
                screen.blit(distance_surface, (px, py))
            # 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, 20*cols+1, 20*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]
                color2 = COLOR[COLOR_RED]
                if maze.WALL == walls[ry][cx][0]:
                    pygame.draw.line(screen, color, (px, py), (px, py+20), 2)
                if maze.WALL == walls[ry][cx][1]:
                    pygame.draw.line(screen, color, (px, py), (px+20, py), 2)
        # 
        if findEndPoint:
            screen.blit(score_surface, (POSX+50, POSY+rows*22))
        time_passed = clock.tick(25)

        pygame.display.update()
    return 



# main
if __name__ == "__main__":
    '''main'''
    sample_pathfinding_demo(20, 30)

GIF动画演示

maze.py

#!/usr/bin/python3.7
# -*- coding: utf-8 -*-
import random

#标记 
NOWALL=0 # 无墙
WALL=1  # 有墙
WALL2=2  # 有墙

VISIT=1 # 到访过
NOVISIT=0 # 没到过
VERTICAL = 0 # 垂直的
HORIZONTAL = 1# 水平的
INFINITE = -1 # infinite distance 无穷远

#Aldous-Broder algorithm
#The Aldous-Broder algorithm also produces uniform spanning trees.

# 1.Pick a random cell as the current cell and mark it as visited.
# 2.While there are unvisited cells:
#   1.Pick a random neighbour.
#   2.If the chosen neighbour has not been visited:
#       1.Remove the wall between the current cell and the chosen neighbour.
#       2.Mark the chosen neighbour as visited.
#   3.Make the chosen neighbour the current cell.

# Aldous-Broder算法
# Aldous-Broder算法也生成统一的生成树。
# 1。选择一个随机的单元格作为当前单元格，并将其标记为已访问的。
# 2。当存在未访问细胞时:
#   1。随机选择一个邻居。
#   2。如果选中的邻居没有被访问:
#       1。移除当前单元格和所选邻居之间的墙。
#       2。标记被选中的邻居已被拜访过。
#   3。使选择的邻居成为当前单元格。

def aldous_broder_maze(rows, cols):
    # 墙 [0]表示格子访问标记，左[1]竖墙，上[2]横墙，最右边竖墙和最下边横墙没有记录。
    # (最左和最上墙不能打通，r,c右和r,c+1左共用墙。r,c和r+1,c共用横墙)
    # 初始化未访问，墙未打通
    grids=[[ NOVISIT for i in range(cols)]for j in range(rows)]
    # 一个格子有四堵墙，其中有两面共有，用2个标记就够用。
    # 墙0通路1。x,y是墙的坐标。
    # wall[x][y][0]竖墙wall[x][y][1]横墙
    # 墙 [0]表示格子访问标记，左[1]竖墙，上[2]横墙，最右边竖墙和最下边横墙没有记录。
    # (最左和最上墙不能打通，r,c右和r,c+1左共用墙。r,c和r+1,c共用横墙)
    # 初始化全为墙
    wall=[[ [WALL,WALL] for i in range(cols)]for i in range(rows)]
    notusegrids = [] # 没有访问过的格子
    for tr in range(rows):
        for tc in range(cols):
            notusegrids.append((tr,tc))
    # 选择一个随机的单元格作为当前单元格，并将其标记为已访问的。
    r,c = random.choice(notusegrids)
    # 标记迷宫
    grids[r][c]=VISIT
    notusegrids.remove((r,c))
    # 当存在未访问细胞时:
    while notusegrids:
        directions = []
        # 可随机方向
        if r > 0:
            directions.append('u')
        if c > 0:
            directions.append('l')
        if r < rows-1:
            directions.append('d')
        if c < cols-1:
            directions.append('r')
        if len(directions):
            # 随机一个方向
            move = random.choice(directions)
            if move == 'u':
                newr = r-1
                newc = c
                opwall=(r, c, HORIZONTAL)
            if move == 'l':
                newr = r
                newc = c-1
                opwall=(r, c, VERTICAL)
            if move == 'd':
                newr = r+1
                newc = c
                opwall=(newr, newc, HORIZONTAL)
            if move == 'r':
                newr = r
                newc = c+1
                opwall=(newr, newc, VERTICAL)
            # 如果选中的邻居没有被访问:
            if grids[newr][newc] == NOVISIT:
                #   1。移除当前单元格和所选邻居之间的墙。
                #   2。标记被选中的邻居已被拜访过。
                #   3。使选择的邻居成为当前单元格。
                grids[newr][newc]=VISIT
                notusegrids.remove((newr,newc))
                wall[opwall[0]][opwall[1]][opwall[2]] = NOWALL
                r=newr
                c=newc   
            else:
                # 使选择的邻居成为当前单元格。
                r=newr
                c=newc 
    return wall


# Randomized depth-first search
# Recursive implementation
#1。Choose the initial cell, mark it as visited and push it to the stack
#2。While the stack is not empty
#   1。Pop a cell from the stack and make it a current cell
#   2。If the current cell has any neighbours which have not been visited
#       1。Push the current cell to the stack
#       2。Choose one of the unvisited neighbours
#       3。Remove the wall between the current cell and the chosen cell
#       4。Mark the chosen cell as visited and push it to the stack
#随机深度优先搜索
#递归实现
#1。选择初始单元格，将其标记为已访问，并将其压入堆栈
#2。而堆栈不是空的
#   1。从堆栈中弹出一个单元格并使其成为当前单元格
#   2。如果当前单元有任何未被访问的邻居
#       1。将当前单元格压入堆栈
#       2。选择一个未被拜访的邻居
#       3。移除当前单元格和所选单元格之间的墙
#       4。将选中的单元格标记为已访问的，并将其压入堆栈
# 墙不占用单元格
# 可以保证所有的格都是相通的
# 深度优先算法可以遍历所有的单元格。
# Randomized depth-first search
# Recursive backtracker
# 递归回溯算法
def depth_maze(rows, cols):
    history = [(0,0)]
    # 一个格子有四堵墙，其中有两面共有，用2个标记就够用。
    # 墙0通路1。x,y是墙的坐标。
    # wall[x][y][0]竖墙wall[x][y][0][1]横墙
    # 左[0]竖墙，上[1]横墙，最右边竖墙和最下边横墙没有记录。
    # (最左和最上墙不能打通，r,c右和r,c+1左共用墙。r,c和r+1,c共用横墙)
    # 初始化全为墙
    wall=[[ [WALL,WALL] for i in range(cols)]for i in range(rows)]
    # way用来标记已经访问过的格子
    # 初始化全未访问
    way=[[ NOVISIT for i in range(cols)]for i in range(rows)]
    # 设置起点
    r=0
    c=0
    # 起点加入记录
    history = [(r,c)]
    # 1。选择初始单元格，将其标记为已访问，并将其压入堆栈
    # 2。堆栈不是空的
    while history:
        way[r][c] = VISIT #
        check = []
        # 可以移动到的位置
        if c > 0 and way[r][c-1] == NOVISIT:
            check.append('L')  
        if r > 0 and way[r-1][c] == NOVISIT:
            check.append('U')
        if c < cols-1 and way[r][c+1] == NOVISIT:
            check.append('R')
        if r < rows-1 and way[r+1][c] == NOVISIT:
            check.append('D')    
        # 如果当前单元有任何未被访问的邻居
        if len(check): 
            # 选择一个未被拜访的邻居
            # 移除当前单元格和所选单元格之间的墙
            # 将选中的单元格标记为已访问的，并将其压入堆栈
            history.append((r, c))
            # 随机移动
            move_direction = random.choice(check)
            # 打通墙壁
            if move_direction == 'L':
                wall[r][c][0] = NOWALL
                c=c-1
            if move_direction == 'U':
                wall[r][c][1] = NOWALL
                r=r-1
            if move_direction == 'R':
                c=c+1
                wall[r][c][0] = NOWALL
            if move_direction == 'D':
                r=r+1
                wall[r][c][1] = NOWALL
        else: 
            #从堆栈中弹出一个单元格并使其成为当前单元格
            r, c = history.pop()
    return wall

# Randomized Kruskal's algorithm
# This algorithm is a randomized version of Kruskal's algorithm.
# 1.Create a list of all walls, and create a set for each cell, each containing just that one cell.
# 2.For each wall, in some random order:
#    1.If the cells divided by this wall belong to distinct sets:
#        1.Remove the current wall.
#        2.Join the sets of the formerly divided cells.
# 随机的Kruskal算法
# 这个算法是Kruskal算法的随机化版本。
# 1。创建所有墙壁的列表，并为每个单元格创建一个集合，每个单元格只包含一个单元格。
# 2。对于每一面墙，以一些随机的顺序:
#   1。如果由这个壁分隔的细胞属于不同的集合:
#       1。移除当前的墙。
#       2。加入以前分裂的细胞组。

def kruskal_maze(rows, cols):
    # [0]表示格子访问标记
    grids=[[ NOVISIT for i in range(cols)]for i in range(rows)]
    # 一个格子有四堵墙，其中有两面共有，用2个标记就够用。
    # 墙0通路1。x,y是墙的坐标。
    # wall[x][y][0]竖墙wall[x][y][1]横墙
    # 墙 [0]表示格子访问标记，左[1]竖墙，上[2]横墙，最右边竖墙和最下边横墙没有记录。
    # (最左和最上墙不能打通，r,c右和r,c+1左共用墙。r,c和r+1,c共用横墙)
    # 初始化全为墙
    wall=[[ [WALL,WALL] for i in range(cols)]for i in range(rows)]
    # 设置起点
    r=0
    c=0
    # 格子列表
    gridlist=[]
    gridlist.append((r,c))
    # 单元格集合
    collection =[]
    # 墙壁的列表
    wallList=[]
    for r in range(rows):
        for c in range(cols):
            collection.append([(r,c)])
            for x in (HORIZONTAL, VERTICAL):
                # 最左和上的墙不能打通
                if r == 0 and x == HORIZONTAL:
                    continue
                if c == 0 and x == VERTICAL:
                    continue
                wallList.append((r,c,x))
    while wallList:
        # 随机选一个墙
        r,c,x = random.choice(wallList)
        # 每个墙随机到一次
        wallList.remove((r,c,x))
        # a,b相邻的集合
        if x == VERTICAL: # 竖墙
            a = (r,c-1)
            b = (r,c)
        else :  # 横墙
            a = (r,c)
            b = (r-1,c)
        coll1 = []
        coll2 = []
        for coll in collection:
            if a in coll:
                coll1 = coll
            if b in coll:
                coll2 = coll
        # 设置访问过
        grids[a[0]][a[1]] = VISIT
        grids[b[0]][b[1]] = VISIT
        # 
        if coll1 != coll2:
            # 打通墙
            wall[r][c][x] = NOWALL
            # 合并集合
            coll = coll1+coll2
            collection.remove(coll1)
            collection.remove(coll2)
            collection.append(coll)
    return wall


# Randomized Prim's algorithm
#1.Start with a grid full of walls.
#2.Pick a cell, mark it as part of the maze. Add the walls of the cell to the wall list.
#3.While there are walls in the list:
#	1.Pick a random wall from the list. If only one of the two cells that the wall divides is visited, then:
#		1.Make the wall a passage and mark the unvisited cell as part of the maze.
#		2.Add the neighboring walls of the cell to the wall list.
#	2.Remove the wall from the list.
# 随机普里姆算法
# 1。从布满墙壁的网格开始。
# 2。选一个细胞，把它标记为迷宫的一部分。将单元格的墙添加到墙列表中。
# 3。名单上有墙:
#   1。从列表中随机选择一面墙。如果细胞壁分裂的两个细胞中只有一个被访问，那么:
#       1。将墙壁做成通道，并将未造访的牢房标记为迷宫的一部分。
#       2。将单元格相邻的墙添加到墙列表中。
# 2。把墙从列表中移除。

# 随机墙
# prim算法
def prim_maze(rows, cols):
     # 一个格子有四堵墙，其中有两面共有，用2个标记就够用。
    # 墙0通路1。x,y是墙的坐标。
    # wall[x][y][0]竖墙wall[x][y][1]横墙
    # 墙 [0]表示格子访问标记，左[1]竖墙，上[2]横墙，最右边竖墙和最下边横墙没有记录。
    # (最左和最上墙不能打通，r,c右和r,c+1左共用墙。r,c和r+1,c共用横墙)
    # 初始化全为墙
    wall=[[ [WALL,WALL] for i in range(cols+1)]for i in range(rows+1)]
    # 已访问标记
    way=[[ NOVISIT for i in range(cols)]for i in range(rows)]
    # 设置起点
    r=0
    c=0
    # 起点加入记录
    # 标记为迷宫的一部分
    way[r][c]=VISIT
    # 墙列表
    walllist=[]
    walllist.append((r+1,c, HORIZONTAL))
    walllist.append((r,c+1, VERTICAL))
    # 
    while walllist:
        # 随机选一个墙
        r, c, d = random.choice(walllist)
        # 移除墙
        walllist.remove((r,c,d))
        if d == VERTICAL:
            # 如果这面墙分隔的两个单元格只有一个单元格被访问过，那么：
            if c > 0 and (not way[r][c-1] == way[r][c] ):
                #1.把墙打通，将未访问的单元格标记成为迷宫的一部分
                wall[r][c][0]=NOWALL
                if way[r][c] == VISIT:
                    nc=c-1
                else:
                    nc=c
                c=nc
                way[r][c]=VISIT
                #2.将单元格相邻的墙加入到墙列表中
                # 上
                if r > 0 and wall[r][c][1] == WALL:
                    walllist.append((r,c,1))
                # 下
                if r+1 < rows and wall[r+1][c][1] == WALL:
                    walllist.append((r+1,c,1))
                # 左
                if c > 0 and wall[r][c][0] == WALL:
                    walllist.append((r,c,0))
                # 右
                if c+1 < cols and wall[r][c+1][0] == WALL:
                    walllist.append((r,c+1,0))
        elif d == HORIZONTAL:
            # 如果这面墙分隔的两个单元格只有一个单元格被访问过，那么：
            if r > 0 and ( (not way[r-1][c]) == way[r][c] ):
                #1.把墙打通，将未访问的单元格标记成为迷宫的一部分
                wall[r][c][1]=NOWALL
                if way[r][c] == VISIT:
                    nr=r-1
                else:
                    nr=r
                r=nr
                way[r][c]=VISIT
                #2.将单元格相邻的墙加入到墙列表中
                # 上
                if r > 0 and wall[r][c][1] == WALL:
                    walllist.append((r,c,1))
                # 下
                if r + 1 < rows and wall[r+1][c][1] == WALL:
                    walllist.append((r+1,c,1))
                # 左
                if c > 0 and wall[r][c][0] == WALL:
                    walllist.append((r,c,0))
                # 右
                if c + 1 < cols and wall[r][c+1][0] == WALL:
                    walllist.append((r,c+1,0))
        #2.如果墙两面的单元格都已经被访问过，那就从列表里移除这面墙
        for rrr1, ccc1, ddd1 in walllist:
            if ddd1 == VERTICAL:
                if ccc1 > 0 and way[rrr1][ccc1-1] == VISIT and way[rrr1][ccc1] == VISIT:
                    walllist.remove((rrr1,ccc1,ddd1))
            elif ddd1 == HORIZONTAL:
                if rrr1 > 0 and way[rrr1-1][ccc1] == VISIT and way[rrr1][ccc1] == VISIT:
                    walllist.remove((rrr1,ccc1,ddd1))

    return wall



# 随机格子
def wilson_maze(rows, cols):
    # 一个格子有四堵墙，其中有两面共有，用2个标记就够用。
    # 墙0通路1。x,y是墙的坐标。
    # wall[x][y][0]竖墙wall[x][y][1]横墙
    # 墙 [0]表示格子访问标记，左[1]竖墙，上[2]横墙，最右边竖墙和最下边横墙没有记录。
    # (最左和最上墙不能打通，r,c右和r,c+1左共用墙。r,c和r+1,c共用横墙)
    # 初始化全为墙
    wall=[[ [WALL,WALL] for i in range(cols+1)]for i in range(rows+1)]
    # 已访问标记
    grids=[[ NOVISIT for i in range(cols)]for j in range(rows)]
    # 我们任意选择一个单元格开始初始化迷宫算法。
    # 然后我们随机选择一个新单元格，开始执行随机漫步，直到我们到达迷宫中已经存在的单元格，然而，
    # 如果在任意一点随机漫步到达自己的路径，形成一个循环，在继续之前从路径中删除循环。
    # 当路径到达迷宫时，我们将其添加到迷宫中。
    # 然后我们从另一个任意的起始单元执行另一个循环擦除的随机漫步，
    # 重复，直到填充完所有单元格。

    # 无论我们使用哪种方法来选择开始单元格，这个过程都是无偏的。
    # 因此，为了简单起见，我们可以按照从左到右、从上到下的顺序选择第一个未填充的单元格。
    tmpgrids = [] # 临时路径
    tmpwalls = [] # 临时路径中的墙
    notusegrids = [] # 没有访问过的格子
    for tr in range(rows):
        for tc in range(cols):
            notusegrids.append((tr,tc))
    r,c = random.choice(notusegrids)
    notusegrids.remove((r,c))
    # 标记迷宫
    grids[r][c]=VISIT
    # 
    r,c = notusegrids[0]
    tmpgrids.append((r,c))

    while  notusegrids:
        #r,c = notusegrids[0]
        directions = []
        # 可随机方向
        if r > 0:
            directions.append('u')
        if c > 0:
            directions.append('l')
        if r < rows-1:
            directions.append('d')
        if c < cols-1:
            directions.append('r')
        if len(directions):
            # 随机一个方向
            move = random.choice(directions)
            if move == 'u':
                newr = r-1
                newc = c
                nextgrid=(newr, newc)
                opwall=(r, c, HORIZONTAL)
            if move == 'l':
                newr = r
                newc = c-1
                nextgrid=(newr, newc)
                opwall=(r, c, VERTICAL)
            if move == 'd':
                newr = r+1
                newc = c
                nextgrid=(newr, newc)
                opwall=(newr, newc, HORIZONTAL)
            if move == 'r':
                newr = r
                newc = c+1
                nextgrid=(newr, newc)
                opwall=(newr, newc, VERTICAL)
            # 
            if (newr, newc) in tmpgrids:
                # 随机到环路
                i = tmpgrids.index((newr, newc))
                tmpgrids=tmpgrids[:i+1]
                tmpwalls=tmpwalls[:i]
                r=newr
                c=newc
            elif grids[newr][newc] == VISIT:
                # 遇到到迷宫
                tmpwalls.append(opwall)
                # 加入迷宫
                for (r,c) in tmpgrids:
                    notusegrids.remove((r,c))
                    grids[r][c]=VISIT
                for (r,c,x) in tmpwalls:
                    wall[r][c][x]=NOWALL
                    
                tmpgrids=[]
                tmpwalls=[]
                if notusegrids:
                    r,c = notusegrids[0]   
                    tmpgrids.append((r, c))
            else:    
                tmpgrids.append(nextgrid)
                tmpwalls.append(opwall)
                r=newr 
                c=newc

    return wall


# main
if __name__ == "__main__":
    '''main'''
    aldous_broder_maze(20, 30)

参考

https://en.wikipedia.org/wiki/Pathfinding