生成多层迷宫-wilson算法

原创文章禁止转载

多层迷宫生成

We begin the algorithm by initializing the maze with one cell chosen arbitrarily.
Then we start at a new cell chosen arbitrarily, and perform a random walk until we reach a cell already in the maze—however,
if at any point the random walk reaches its own path, forming a loop,
we erase the loop from the path before proceeding.
When the path reaches the maze, we add it to the maze.
Then we perform another loop-erased random walk from another arbitrary starting cell,
repeating until all cells have been filled.

This procedure remains unbiased no matter which method we use to arbitrarily choose starting cells.
So we could always choose the first unfilled cell in (say) left-to-right, top-to-bottom order for simplicity.

我们任意选择一个单元格开始初始化迷宫算法。
然后我们随机选择一个新单元格，开始执行随机漫步，直到我们到达迷宫中已经存在的单元格，然而，
如果在任意一点随机漫步到达自己的路径，形成一个循环，在继续之前从路径中删除循环。
当路径到达迷宫时，我们将其添加到迷宫中。
然后我们从另一个任意的起始单元执行另一个循环擦除的随机漫步，
重复，直到填充完所有单元格。

无论我们使用哪种方法来选择开始单元格，这个过程都是无偏的。
因此，为了简单起见，我们可以按照从左到右、从上到下的顺序选择第一个未填充的单元格。

源码

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

# We begin the algorithm by initializing the maze with one cell chosen arbitrarily.
# Then we start at a new cell chosen arbitrarily,# and perform a random walk until we reach a cell already in the maze—however, 
# if at any point the random walk reaches its own path, forming a loop,
# we erase the loop from the path before proceeding.
# When the path reaches the maze, we add it to the maze. 
# Then we perform another loop-erased random walk from another arbitrary starting cell, 
# repeating until all cells have been filled.

# This procedure remains unbiased no matter which method we use to arbitrarily choose starting cells.
#  So we could always choose the first unfilled cell in (say) left-to-right, top-to-bottom order for simplicity.

# 我们任意选择一个单元格开始初始化迷宫算法。
# 然后我们随机选择一个新单元格，开始执行随机漫步，直到我们到达迷宫中已经存在的单元格，然而，
# 如果在任意一点随机漫步到达自己的路径，形成一个循环，在继续之前从路径中删除循环。
# 当路径到达迷宫时，我们将其添加到迷宫中。
# 然后我们从另一个任意的起始单元执行另一个循环擦除的随机漫步，
# 重复，直到填充完所有单元格。

# 无论我们使用哪种方法来选择开始单元格，这个过程都是无偏的。
# 因此，为了简单起见，我们可以按照从左到右、从上到下的顺序选择第一个未填充的单元格。


# 随机格子
def wilson_maze_demo(levels, rows, cols):
    if 0 == levels % 2:
        levels+=1
    if 0 == rows % 2:
        rows+=1
    if 0 == cols % 2:
        cols+=1
    # 初始化全为墙
    maze_map = maze_init_draw(levels, rows, cols)
    # maze_map=[[[ WALL for z in range(levels)]for y in range(rows)] for x in range(cols)]
    # 设置起点
    x=1
    y=1
    z=0
    # 我们任意选择一个单元格开始初始化迷宫算法。
    # 然后我们随机选择一个新单元格，开始执行随机漫步，直到我们到达迷宫中已经存在的单元格，然而，
    # 如果在任意一点随机漫步到达自己的路径，形成一个循环，在继续之前从路径中删除循环。
    # 当路径到达迷宫时，我们将其添加到迷宫中。
    # 然后我们从另一个任意的起始单元执行另一个循环擦除的随机漫步，
    # 重复，直到填充完所有单元格。

    # 无论我们使用哪种方法来选择开始单元格，这个过程都是无偏的。
    # 因此，为了简单起见，我们可以按照从左到右、从上到下的顺序选择第一个未填充的单元格。
    tmpgrids = [] # 临时路径
    tmpwalls = [] # 临时路径中的墙
    notusegrids = [] # 没有访问过的格子
    for tz in range(0, levels, 2):
        for tx in range(1, cols, 2):
            for ty in range(1, rows, 2):
                notusegrids.append((tx,ty,tz))
                maze_map[tx][ty][tz]=CELL_NO_VISIT
    
    # 随机一个格子标记为迷宫
    nowx,nowy,nowz = random.choice(notusegrids)
    notusegrids.remove((nowx,nowy,nowz))
    maze_map[nowx][nowy][nowz]=VISIT
    # 开始点
    nowx,nowy,nowz = notusegrids[0]
    # 加入临时路径
    tmpgrids.append((nowx,nowy,nowz))
    posx,posy=None,None
    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                return
        # 还有格子未访问
        if  notusegrids:
            directions = []
            # 可随机方向
            if nowy > 1:
                directions.append('f')
            if nowx > 1:
                directions.append('l')
            if nowy < rows-2:
                directions.append('b')
            if nowx < cols-2:
                directions.append('r')
            if nowz < levels-1:
                directions.append('u')
            if nowz > 0:
                directions.append('d')
            if len(directions):
                # 随机一个方向
                move = random.choice(directions)
                if move == 'f':
                    newy = nowy-2
                    newx = nowx
                    newz = nowz
                    opwall=(nowx,nowy-1,nowz)
                    nextgrid=(newx,newy,newz)
                if move == 'l':
                    newy = nowy
                    newx = nowx-2
                    newz = nowz
                    opwall=(nowx-1,nowy,nowz)
                    nextgrid=(newx,newy,newz)
                if move == 'b':
                    newy = nowy+2
                    newx = nowx
                    newz = nowz
                    opwall=(nowx,nowy+1,nowz)
                    nextgrid=(newx,newy,newz)
                if move == 'r':
                    newy = nowy
                    newx = nowx+2
                    newz = nowz
                    opwall=(nowx+1,nowy,nowz)
                    nextgrid=(newx,newy,newz)
                if move == 'u':
                    newy = nowy
                    newx = nowx
                    newz = nowz+2
                    opwall=(nowx,nowy,nowz+1)
                    nextgrid=(newx,newy,newz)
                if move == 'd':
                    newy = nowy
                    newx = nowx
                    newz = nowz-2
                    opwall=(nowx,nowy,nowz-1)
                    nextgrid=(newx,newy,newz)
                # 
                if (newx, newy, newz) in tmpgrids:
                    # 随机到环路,删除环路
                    i = tmpgrids.index((newx, newy, newz))
                    tmpgrids=tmpgrids[:i+1]
                    tmpwalls=tmpwalls[:i]
                    nowx=newx
                    nowy=newy
                    nowz=newz
                elif maze_map[newx][newy][newz] != CELL_NO_VISIT:
                    # 遇到到迷宫
                    tmpwalls.append(opwall)
                    # 加入迷宫
                    for (x,y,z) in tmpgrids:
                        notusegrids.remove((x,y,z))
                        maze_map[x][y][z]=VISIT
                    for (x,y,z) in tmpwalls:
                        # 打通墙壁 
                        maze_map[x][y][z]=NOWALL
                        if z%2 == 1: # UD 标记上下楼梯
                            if maze_map[x][y][z-1] == VISIT:
                                maze_map[x][y][z-1]=STAIRS_U
                            elif maze_map[x][y][z-1] == STAIRS_D:                             
                                maze_map[x][y][z-1]=STAIRS_UD
                            if maze_map[x][y][z+1] == VISIT:
                                maze_map[x][y][z+1]=STAIRS_D
                            elif maze_map[x][y][z+1] == STAIRS_U:                             
                                maze_map[x][y][z+1]=STAIRS_UD
                        else:
                            maze_map[x][y][z]=NOWALL
                    tmpgrids=[]
                    tmpwalls=[]
                    if notusegrids:
                        # 选择一个新单元格，开始执行随机漫步
                        nowx,nowy,nowz = notusegrids[0]   
                        tmpgrids.append((nowx,nowy,nowz))
                else: 
                    # 加入临时路径   
                    tmpgrids.append(nextgrid)
                    tmpwalls.append(opwall)
                    nowx=newx
                    nowy=newy
                    nowz=newz
        # 
        draw_maze(maze_map, levels, rows, cols, (nowx,nowy,nowz), not notusegrids)
        
        if tmpgrids:
            for (xi,yi,zi) in tmpgrids:
                a = zi % 2
                b = zi // 2
                px, py = 1 + xi * DIAMOND_SIZE[0] + a * (cols*DIAMOND_LENGTH+10),  1 + yi * DIAMOND_SIZE[1] + b*(rows*DIAMOND_LENGTH+10)
                screen.blit(DIAMOND_W, (px, py))

        if tmpwalls:
            for (xi,yi,zi) in tmpwalls:
                a = zi % 2
                b = zi // 2
                px, py = 1 + xi * DIAMOND_SIZE[0] + a * (cols*DIAMOND_LENGTH+10),  1 + yi * DIAMOND_SIZE[1] + b*(rows*DIAMOND_LENGTH+10)
                screen.blit(DIAMOND_W, (px, py))
 
        time_passed = clock.tick(30)
        pygame.display.update()
    return 

# main
if __name__ == "__main__":
    '''main'''
    wilson_maze_demo(3, 15, 17)

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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198

生成的多层迷宫

gif演示

其它文件

maze.py
draw_maze.py
maze_def.py