使Randomized Prim's算法生成多层迷宫

多层迷宫生成

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。把墙从列表中移除。

源码

#!/usr/bin/python3.7
# -*- coding: utf-8 -*-
# create by 火苗999℃
import random
import pygame
from draw_maze import *
from maze import *
from maze_def import *

# 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。把墙从列表中移除。


# 找格子周围没打通的墙
def find_wall(walls, x, y, z,levels, rows, cols):
    ret = []
    if x > 1 and walls[x-1][y][z] == WALL:
        ret.append((x-1,y,z, LR))
    if y > 1 and walls[x][y-1][z] == WALL:
        ret.append((x,y-1,z, FB))
    if x < cols - 2 and walls[x+1][y][z] == WALL:
        ret.append((x+1,y,z, LR))
    if y < rows - 2 and walls[x][y+1][z] == WALL:
        ret.append((x,y+1,z, FB))
    if z > 0 and walls[x][y][z-1] == WALL:
        ret.append((x,y,z-1, UD))
    if z < levels-1 and walls[x][y][z+1] == WALL:
        ret.append((x,y,z+1, UD))
    return ret


# 随机墙
def prim_maze_demo(levels, rows, cols):
    levels=2*levels-1
    rows=2*rows+1
    cols=2*cols+1
    # 初始化地图
    maze_map=maze_init_draw(levels,rows,cols)
    # 设置起点
    x=1
    y=1
    z=0
    # 起点加入记录
    # 标记为迷宫的一部分
    maze_map[x][y][z] = CELL_VISIT
    # 墙列表
    walllist=[] 
    ws = find_wall(maze_map, x, y, z, levels, rows, cols)
    walllist.extend(ws)
    # 
    posx,posy=None,None
    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                return
        if walllist:
            # 随机选一个墙
            x, y, z, d = random.choice(walllist)
            # 移除墙
            walllist.remove((x,y,z,d))
            maze_map[x][y][z]=WALL_VISIT # 标记墙已访问(演示用)
            if d == FB:
                # 如果这面墙分隔的两个单元格只有一个单元格被访问过，那么：
                if (maze_map[x][y-1][z] == CELL_NO_VISIT or maze_map[x][y+1][z] == CELL_NO_VISIT) and (maze_map[x][y-1][z] != maze_map[x][y+1][z]):
                    #1.把墙打通，将未访问的单元格标记成为迷宫的一部分
                    maze_map[x][y][z]=NOWALL
                    if maze_map[x][y-1][z] == CELL_NO_VISIT:
                        gy=y-1
                    else:
                        gy=y+1
                    maze_map[x][gy][z]=CELL_VISIT
                    #2.将单元格相邻的墙加入到墙列表中
                    ws = find_wall(maze_map, x, gy , z, levels, rows,cols)
                    walllist.extend(ws)
            elif d == LR:
                # 如果这面墙分隔的两个单元格只有一个单元格被访问过，那么：
                if (maze_map[x-1][y][z] == CELL_NO_VISIT or maze_map[x+1][y][z] == CELL_NO_VISIT) and (maze_map[x-1][y][z] != maze_map[x+1][y][z]):
                    #1.把墙打通，将未访问的单元格标记成为迷宫的一部分
                    maze_map[x][y][z]=NOWALL
                    if maze_map[x-1][y][z] == CELL_NO_VISIT:
                        gx=x-1
                    else:
                        gx=x+1
                    maze_map[gx][y][z]=CELL_VISIT   
                    #2.将单元格相邻的墙加入到墙列表中
                    ws = find_wall(maze_map, gx, y , z, levels, rows,cols)
                    walllist.extend(ws)
            elif d == UD:
                # 如果这面墙分隔的两个单元格只有一个单元格被访问过，那么：
                if (maze_map[x][y][z-1] == CELL_NO_VISIT or maze_map[x][y][z+1] == CELL_NO_VISIT) and (maze_map[x][y][z-1] != maze_map[x][y][z+1]):
                    #1.把墙打通，将未访问的单元格标记成为迷宫的一部分
                    maze_map[x][y][z]=NOWALL
                    if maze_map[x][y][z-1] == CELL_NO_VISIT:
                        gz=z-1
                        # 楼梯
                        maze_map[x][y][gz]=STAIRS_U
                        if maze_map[x][y][z+1] == CELL_VISIT:
                            maze_map[x][y][z+1]=STAIRS_D
                        else:
                            maze_map[x][y][z+1]=STAIRS_UD
                    else:
                        gz=z+1
                        # 楼梯
                        maze_map[x][y][gz]=STAIRS_D
                        if maze_map[x][y][z-1] == CELL_VISIT:
                            maze_map[x][y][z-1]=STAIRS_U
                        else:
                            maze_map[x][y][z-1]=STAIRS_UD
                    #2.将单元格相邻的墙加入到墙列表中
                    ws = find_wall(maze_map, x, y , gz, levels, rows,cols)
                    walllist.extend(ws)

            #2.如果墙两面的单元格都已经被访问过，那就从列表里移除这面墙
            for x1,y1,z1,d1 in walllist:
                if d1 == FB:
                    if y1 > 1 and y1 < rows-2 and maze_map[x1][y1-1][z1] != CELL_NO_VISIT and maze_map[x1][y1+1][z1] != CELL_NO_VISIT:
                        walllist.remove((x1,y1,z1,d1))
                        maze_map[x1][y1][z1]=WALL_VISIT # 标记墙已访问(演示用)
                elif d1 == LR:
                    if x1 > 1 and x1 < cols-2 and maze_map[x1-1][y1][z1] != CELL_NO_VISIT and maze_map[x1+1][y1][z1] != CELL_NO_VISIT:
                        walllist.remove((x1,y1,z1,d1))
                        maze_map[x1][y1][z1]=WALL_VISIT # 标记墙已访问(演示用)
                elif d1 == UD:
                    if z1 > 0 and z1 < levels-1 and  maze_map[x1][y1][z1-1] != CELL_NO_VISIT and maze_map[x1][y1][z1+1] != CELL_NO_VISIT:
                        walllist.remove((x1,y1,z1,d1))
                        maze_map[x1][y1][z1]=WALL_VISIT # 标记墙已访问(演示用)
        # 
        draw_maze(maze_map, levels, rows, cols, (x,y,z), not walllist)
        time_passed = clock.tick(30)
        pygame.display.update()
    return 



# main
if __name__ == "__main__":
    '''main'''
    prim_maze_demo(3, 5, 8)