多通路迷宫生成

本篇文章禁止转载

思路介绍

• 在已有的单路径迷宫基础上打开一块合适的墙就可以构成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)

  多路径迷宫图

  
  绿色是随拆除，青色是可拆墙中拆出的路最短。

随机拆墙演示代码

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

pygame.init()  # 初始化pygame
size = width, height = 800, 600  # 设置窗口大小
screen = pygame.display.set_mode(size)  # 显示窗口
# 颜色
diamond_color_size = 12
COLOR_RED, COLOR_BLUE, COLOR_GREEN, COLOR_YELLOW, COLOR_BLACK, COLOR_FLAXEN, COLOR_GOLD, COLOR_GRAY, COLOR_PINK, COLOR_ORANGE, COLOR_WHEAT, COLOR_CYAN = 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_FLAXEN: (250, 240, 230), # 亚麻
    COLOR_GOLD : (255,215,0), # 金
    COLOR_GRAY: (128,128,128), # 灰
    COLOR_PINK:(255,192,203), # 粉
    COLOR_ORANGE: (255,165,0),# 橙
    COLOR_WHEAT: (245,222,179),# 小麦
    COLOR_CYAN : (0,255,255), # 青
}
# 格子大小
DIAMOND_LEN = 20
DIAMOND_SIZE = (DIAMOND_LEN, DIAMOND_LEN)
# 蓝格子
DIAMOND_BULE=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_BULE.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_GRAY=pygame.surface.Surface(DIAMOND_SIZE).convert()
DIAMOND_GRAY.fill(COLOR[COLOR_FLAXEN])

# 各色的格子
DIAMONDS=[]
for x in range(diamond_color_size):
    diamoand=pygame.surface.Surface(DIAMOND_SIZE).convert()
    diamoand.fill(COLOR[x])
    DIAMONDS.append(diamoand)

# 字体
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_FLAXEN])
# 时间
clock = pygame.time.Clock()

#标记 
NOWALL=maze.NOWALL # 无墙
WALL=maze.WALL  # 有墙
WALL2=maze.WALL2  # 有墙
VISIT=maze.VISIT # 到访过
NOVISIT=maze.NOVISIT # 没到过
VERTICAL = maze.VERTICAL # 垂直的
HORIZONTAL = maze.HORIZONTAL# 水平的
INFINITE = maze.INFINITE # 无穷远


# 下一圈
def FindNextCircle(startList, walls, grids, rows, cols):
    startNextList = [] # 下一步
    for node in startList:
        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 startNextList:
                startNextList.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 startNextList:
                startNextList.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 startNextList:
                startNextList.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 startNextList:
                startNextList.append((nr,nc))
                grids[nr][nc] = l+1
    # 下一圈
    startList.clear()
    startList.extend(startNextList)
    return startList


# 画方块
def draw_diamond(r, c, screen, diamod):
    px,py= 1 + (c) * DIAMOND_SIZE[0], 1 + (r) * DIAMOND_SIZE[1]
    screen.blit(diamod, (px, py))
    return 


# 画方块和字符串string
def draw_diamond_and_str(r, c, screen, diamod, use_font, string, color, color_back):
    px,py= 1 + (c) * DIAMOND_SIZE[0], 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 


# 拆分迷宫
def split_maze(walls, grids, startPoint, endPoint, startMap, endMap, rows, cols):
    startList = [startPoint]
    endList = [endPoint]
    startMap.append(startPoint)
    endMap.append(endPoint)
    while startList or endList:
        split_maze_step(walls, grids, startList, endList, startMap, endMap, rows, cols)
    return startMap, endMap


# 一步一步执行
def split_maze_step(walls, grids, startList, endList, startMap, endMap, rows, cols):
    # 起点
    FindNextCircle(startList, walls, grids, rows, cols)
    startMap+=startList
    # 终点
    FindNextCircle(endList, walls, grids, rows, cols)
    endMap+=endList
    return startList, endList



def find_partition_walls(walls, grids, startMap, endMap, rows, cols):
    tmp_grids=[[ 'e' for i in range(cols)]for j in range(rows)]
    for s in startMap:
        tmp_grids[s[0]][s[1]] = 's'
    part = []
    # 找到分隔两部分的墙
    for r in range(rows):
        for c in range(cols):
            if WALL == walls[r][c][0] and c > 0:
                if tmp_grids[r][c-1] != tmp_grids[r][c]:
                    part.append((r,c,0))
            if WALL == walls[r][c][1] and r > 0:
                if tmp_grids[r-1][c] != tmp_grids[r][c]:
                    part.append((r,c,1))
    return part


# 随机拆一个合适的墙
def random_down_wall(walls, grids, startMap, endMap, rows, cols):
    # 找到墙
    parts = find_partition_walls(walls, grids, startMap, endMap, rows, cols)
    swr, swc, swd = random.choice(parts)
    walls[swr][swc][swd] = NOWALL
    parts.remove((swr, swc, swd))
    return walls


# 差值最大的墙
def find_diff_partition_wall(walls, grids, startMap, endMap, rows, cols):
    tmp_grids=[[ 'e' for i in range(cols)]for j in range(rows)]
    for s in startMap:
        tmp_grids[s[0]][s[1]] = 's'
    wall = None
    l = 0
    # 找到分隔两部分的墙
    for r in range(rows):
        for c in range(cols):
            if WALL == walls[r][c][0] and c > 0:
                if tmp_grids[r][c-1] != tmp_grids[r][c]:
                    if l < abs(grids[r][c-1] - grids[r][c]):
                        wall = (r,c,0)
                        l = abs(grids[r][c-1] - grids[r][c])
            if WALL == walls[r][c][1] and r > 0:
                if tmp_grids[r-1][c] != tmp_grids[r][c]:
                    if l < abs(grids[r-1][c] - grids[r][c]):
                        wall = (r,c,1)
                        l = abs(grids[r-1][c] - grids[r][c])
    return wall

# 拆两边差值最大的墙
def diff_down_wall(walls, grids, startMap, endMap, rows, cols):
    # 找到墙
    wall = find_diff_partition_wall(walls, grids, startMap, endMap, rows, cols)
    swr, swc, swd = wall
    walls[swr][swc][swd] = NOWALL
    return walls



# Sample algorithm
def multipath_maze_demo(rows, cols):
    maze_h = rows * DIAMOND_SIZE[0] + 1
    maze_w = cols * DIAMOND_SIZE[0] + 1
    size = (maze_w, maze_h)
    maze_surface=pygame.surface.Surface(size).convert()
    #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
    secondWay=False
    # 起点
    startPoint=(r,c)
    # 终点
    endPoint=(rows-1,cols-1)
    mainList=[] # 主路径
    # 
    startList=[startPoint]
    endList=[endPoint]
    grids[startPoint[0]][startPoint[1]]=0 # 标记已经到过格子距离
    grids[endPoint[0]][endPoint[1]]=0
    # 没有访问过的格子
    notUseGrids = [] 
    for tr in range(rows):
        for tc in range(cols):
            notUseGrids.append((tr,tc))
    # 
    startMap=[]
    endMap=[]
    startMap += startList
    endMap += endList
    # 
    parts = []
    rand_wall = None
    diff_wall = None
    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                return
        if startList or endList:    
            # 分区
            # python 传参是引用传递 （不可改变参数指向，可改变参数的内部值。）
            # 可变对象：列表，字典（当参数时，函数内部的修改可以带出外部；但是赋值操作不能带出，此时的赋值操作相当于不可变对象的赋值）
            # 不可变的对象：数字，元组，字符串（当参数时，函数内部的修改不能带出；不可变对象修改值时相当于修改指向地址。）
            split_maze_step(walls, grids, startList, endList, startMap, endMap, rows, cols)
            # 
            # split_maze(walls, grids, startPoint, endPoint, startMap, endMap, rows, cols)
        elif not secondWay:
            parts = find_partition_walls(walls, grids, startMap, endMap, rows, cols)
            # 拆近路
            # diff_down_wall(walls, grids, startMap, endMap, rows, cols)
            diff_wall = find_diff_partition_wall(walls, grids, startMap, endMap, rows, cols)
            swr, swc, swd = diff_wall
            parts.remove((swr, swc, swd))
            # walls[swr][swc][swd] = NOWALL

            # 随机拆
            # random_down_wall(walls, grids, startMap, endMap, rows, cols)
            # parts = find_partition_walls(walls, grids, startMap, endMap, rows, cols)
            rand_wall = random.choice(parts)
            swr, swc, swd = rand_wall
            parts.remove((swr, swc, swd))
            # walls[swr][swc][swd] = NOWALL
            secondWay = True
        else:
            findPath
        # 背景
        screen.blit(background, (0, 0))
        # maze_surface
        # 格子
        for cx in range(cols):
            for ry in range(rows):
                # 标记访问过的格子
                if maze.INFINITE == grids[ry][cx]:
                    draw_diamond(ry, cx, maze_surface, DIAMONDS[COLOR_GRAY])
                else:
                    s = "{}".format(grids[ry][cx])
                    draw_diamond_and_str(ry, cx, maze_surface, DIAMOND_GRAY, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_FLAXEN]) 
        # 圈地
        for pos in startMap:
            s = "{}".format(grids[pos[0]][pos[1]])
            draw_diamond_and_str(pos[0], pos[1], maze_surface, DIAMONDS[COLOR_WHEAT], use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_WHEAT])
        for pos in endMap:
            s = "{}".format(grids[pos[0]][pos[1]])
            draw_diamond_and_str(pos[0], pos[1], maze_surface, DIAMONDS[COLOR_FLAXEN], use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_FLAXEN])
        # 循环外圈
        if startList and not mainList:
            for pos in startList:
                s = "{}".format(grids[pos[0]][pos[1]])
                draw_diamond_and_str(pos[0], pos[1], maze_surface, 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], maze_surface, 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], maze_surface, DIAMOND_YELLOW, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_YELLOW])
            # r,c
            s = "{}".format(grids[pos[0]][pos[1]])
            draw_diamond_and_str(r, c, maze_surface, DIAMOND_GREEN, use_font12, s, COLOR[COLOR_BLACK], COLOR[COLOR_GREEN])
        # 画外墙
        pygame.draw.rect(maze_surface, COLOR[COLOR_RED], (0, 0, DIAMOND_LEN*cols+1, DIAMOND_LEN*rows+1), 2)
        # 画没打通的墙
        DrawWalls(maze_surface, DIAMOND_SIZE, walls, rows, cols)
        # 
        if parts:
            DrawWallList(maze_surface, COLOR[COLOR_RED], DIAMOND_SIZE, parts, rows, cols)
            DrawWallList(maze_surface, COLOR[COLOR_GREEN], DIAMOND_SIZE, [rand_wall], rows, cols)
            DrawWallList(maze_surface, COLOR[COLOR_CYAN], DIAMOND_SIZE, [diff_wall], rows, cols)

        # 贴maze
        screen.blit(maze_surface, (POSX, POSY))

        # 打印文字提示
        if findEndPoint:
            screen.blit(score_surface, (POSX+50, POSY+rows*22))
        # 帧率
        clock.tick(25)

        pygame.display.update()
    return 

# 
def DrawWalls(screen, DIAMOND_SIZE, walls, rows, cols):
    for cx in range( cols):
        for ry in range(rows):
            px,py = 1 + (cx) * DIAMOND_SIZE[0], 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)
    return 

# 
def DrawWallList(screen, color, DIAMOND_SIZE, wlist, rows, cols):
    for r,c,d in wlist:
        px,py = 1 + (c) * DIAMOND_SIZE[0], 1 + (r) * DIAMOND_SIZE[1]
        if d == 0:
            pygame.draw.line(screen, color, (px, py), (px, py+DIAMOND_LEN), 2)
        if d == 1:
            pygame.draw.line(screen, color, (px, py), (px+DIAMOND_LEN, py), 2)
    return 


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

多通路迷宫寻路(寻路加找宝箱)

多通路迷宫寻路(寻路加找宝箱)