多层迷宫生成

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

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#!/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)


maze_def.py

链接地址
maze_def.py

maze.py

链接地址
maze.py

draw_maze.py

链接地址
draw_maze.py

生成的多层迷宫

2层迷宫

3层迷宫

gif演示

3层迷宫

生成多层迷宫-Aldous-Broder算法