完美迷宫生成算法

Perfect maze

Perfect maze又称standard maze,指没有回路,没有不可达区域的迷宫。用图论的语言来说,就是可以用spanning tree表示的迷宫,保证迷宫中任意两个格子间都有唯一的路径。本文旨在探讨如何随机生成棋盘状perfect maze。迷宫格子的邻居的定义采用von Neumann neighborhood,即水平竖直方向相邻的四个格子。

变形Kruskal算法

说得通俗点,就是“随机拆墙”。

一开始假设所有墙都在。如果当前不满足“任意两个格子间都有唯一路径”,那么就随机选择一堵墙,要求墙两端的格子不连通,即它们对应的两个顶点不在一个connected component里。

把这堵墙拆掉,即在后墙两端的格子对应的顶点间建立一条边,此时connected component数就减少一了。不断地找墙、拆墙,最后就能形成一个看上去挺随机的迷宫。

伪代码

W = 所有墙
T = {}
number_of_components = N*N
while number_of_components > 1
  (u, v) = W.pop
  if component(u) != component(v)
    T << (u, v)
    merge component(u) and component(v)

最后T集合就是spanning tree中的边,即所需拆除的墙。

实现

考虑转化为图论模型后我们需要的操作,只有两个,即:

  • 判断两个元素是否在一个集合中(两个顶点是否在同一个connected component里),
  • 合并两个集合(合并两个connected component)。

对于这个问图,有经典的disjoin-set forest算法可以在近似线性的时间复杂度里解决这个问题。

Aldous-Broder算法

很简单,随机选择一个格子作为起点,每次随机选择一个邻居格子走过去,如果目标格子不与当前格子连通则打通它们之间的墙。

Haskell实现

以下代码改编自某个Haskell的recursive backtracking算法:

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
import Control.Applicative
import Control.Monad
import Control.Monad.Cont
import Control.Monad.ST
import Data.Array
import Data.Array.ST
import Data.STRef
import System.Random
import Debug.Trace
data Maze = Maze { rightWalls, belowWalls :: Array (Int, Int) Bool }
rand :: Random a => (a, a) -> STRef s StdGen -> ST s a
rand range g = do
(a, g') <- liftM (randomR range) $ readSTRef g
a <$ writeSTRef g g'
maze :: Int -> Int -> StdGen -> ST s Maze
maze w h gen = do
let mk = newArray ((0,0), (w-1,h-1)) :: Bool -> ST s (STArray s (Int, Int) Bool)
visited <- mk False
right <- mk True
bottom <- mk True
gen <- newSTRef gen
let
walk 1 (x,y) = return ()
walk c u@(x,y) = do
writeArray visited u True
let ns = [(x-1,y) | x > 0] ++ [(x+1,y) | x+1 < w] ++ [(x,y-1) | y > 0] ++ [(x,y+1) | y+1 < h] :: [(Int,Int)]
i <- rand (0, length ns - 1) gen
let v@(x', y') = ns !! i
wall = if x == x' then bottom else right
g = (min x x', min y y')
hasWall <- readArray wall g
seen <- readArray visited v
if seen
then
walk c v
else
writeArray wall g False >> walk (c-1) v
(,) <$> rand (0, w-1) gen <*> rand (0, h-1) gen >>= walk (w*h)
Maze <$> freeze right <*> freeze bottom
maze :: Int -> Int -> StdGen -> ST s Maze
maze w h gen = do
let mk = newArray ((0,0), (w-1,h-1)) :: Bool -> ST s (STArray s (Int, Int) Bool)
visited <- mk False
right <- mk True
bottom <- mk True
gen <- newSTRef gen
let
walk 1 gen (x,y) = return ()
walk c gen u@(x,y) = do
writeArray visited u True
let ns = [(x-1,y) | x > 0] ++ [(x+1,y) | x+1 < w] ++ [(x,y-1) | y > 0] ++ [(x,y+1) | y+1 < h] :: [(Int,Int)]
i <- rand (0, length ns - 1) gen
let v@(x', y') = ns !! i
wall = if x == x' then bottom else right
g = (min x x', min y y')
hasWall <- readArray wall g
seen <- readArray visited v
if seen
then
walk c gen v
else
writeArray wall g False >> walk (c-1) gen v
(,) <$> rand (0, w-1) gen <*> rand (0, h-1) gen >>= walk (w*h) gen
Maze <$> freeze right <*> freeze bottom
printMaze :: Maze -> IO ()
printMaze (Maze right bottom) = do
putStrLn $ concat (replicate (maxX + 1) "._") ++ "."
forM_ [0..maxY] $ \y -> do
putStr "|"
forM_ [0..maxX] $ \x -> do
putStr $ if bottom ! (x, y) then "_" else " "
putStr $ if right ! (x, y) then "|" else "."
putChar '\n'
where
(maxX, maxY) = snd $ bounds right
main = getStdGen >>= stToIO . maze 12 13 >>= printMaze

该算法的优点是能等概率地生成每一棵spanning tree。

Recursive backtracking算法

上述随机拆墙使用到的Kruskal算法是求minimum spanning tree问题最广为人知的两个算法之一,另一个就是Prim算法,那么后者能不能解决这个问题呢?有种类似变形Prim的算法。

和变形Kruskal算法一样,一开始假设所有墙都存在,伪代码如下:

S = {(0,0)}
T = {}
while visited.size != n * n
  u = S.pop
  for v in neighbors(u).random_shuffle
    if component(v) != component(u)
      T << (u, v)
      S << v

最后T集合就是spanning tree中的边,即所需拆除的墙。

如果经典的Prim算法实现看作是维护了一个priority queue来维护connected component中的点,那么这里S可以用比priority queue简单的stack或queue来实现。原因是我们求的不是minimum spanning tree,所有顶点的权值可以看作是相同的;所有边的权值也可以看作是相同的。

如果用stack代替priority queue,那么我们就甚至无需显示维护一个stack了,直接使用程序函数调用时系统维护的栈。

  • 随机选择一个顶点作为起点
  • 对于当前点的每一个邻点,如果这个邻点和当前点不在同一个connected component,
    那么就在它们之间建立一条边,即把它们之间的墙拆掉,并且递归调用该步骤,当前点设置为这个邻点。

Haskell实现

下面实现来自http://megasnippets.com/source-codes/haskell/maze_generation

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
import Control.Monad
import Control.Monad.ST
import Data.Array
import Data.Array.ST
import Data.STRef
import System.Random
rand :: Random a => (a, a) -> STRef s StdGen -> ST s a
rand range gen = do
(a, g) <- liftM (randomR range) $ readSTRef gen
gen `writeSTRef` g
return a
data Maze = Maze {rightWalls, belowWalls :: Array (Int, Int) Bool}
maze :: Int -> Int -> StdGen -> ST s Maze
maze width height gen = do
visited <- mazeArray False
rWalls <- mazeArray True
bWalls <- mazeArray True
gen <- newSTRef gen
liftM2 (,) (rand (0, maxX) gen) (rand (0, maxY) gen) >>=
visit gen visited rWalls bWalls
liftM2 Maze (freeze rWalls) (freeze bWalls)
where visit gen visited rWalls bWalls here = do
writeArray visited here True
let ns = neighbors here
i <- rand (0, length ns - 1) gen
forM_ (ns !! i : take i ns ++ drop (i + 1) ns) $ \there -> do
seen <- readArray visited there
unless seen $ do
removeWall here there
visit gen visited rWalls bWalls there
where removeWall (x1, y1) (x2, y2) = writeArray
(if x1 == x2 then bWalls else rWalls)
(min x1 x2, min y1 y2)
False
neighbors (x, y) =
(if x == 0 then [] else [(x - 1, y )]) ++
(if x == maxX then [] else [(x + 1, y )]) ++
(if y == 0 then [] else [(x, y - 1)]) ++
(if y == maxY then [] else [(x, y + 1)])
maxX = width - 1
maxY = height - 1
mazeArray = newArray ((0, 0), (maxX, maxY))
:: Bool -> ST s (STArray s (Int, Int) Bool)
printMaze :: Maze -> IO ()
printMaze (Maze rWalls bWalls) = do
putStrLn $ '+' : (concat $ replicate (maxX + 1) "---+")
forM_ [0 .. maxY] $ \y -> do
putStr "|"
forM_ [0 .. maxX] $ \x -> do
putStr " "
putStr $ if rWalls ! (x, y) then "|" else " "
putStrLn ""
forM_ [0 .. maxX] $ \x -> do
putStr "+"
putStr $ if bWalls ! (x, y) then "---" else " "
putStrLn "+"
where maxX = fst (snd $ bounds rWalls)
maxY = snd (snd $ bounds rWalls)
main = getStdGen >>= stToIO . maze 11 8 >>= printMaze

C实现

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
##include <stdbool.h>
##include <stdio.h>
##include <stdlib.h>
##include <string.h>
##define N 92
bool R[N][N], D[N][N], v[N][N];
int m, n;
void dfs(int r, int c)
{
int d = rand() % 4, dd = rand()%2 ? 1 : 3;
v[r][c] = true;
for (int i = 0; i < 4; i++) {
int rr = r + (int[]){-1,0,1,0}[d],
cc = c + (int[]){0,-1,0,1}[d];
if ((unsigned)rr < m && (unsigned)cc < n && ! v[rr][cc]) {
if (d % 2)
R[r][c - (d == 1)] = true;
else
D[r - (d == 0)][c] = true;
dfs(rr, cc);
}
d = (d + dd) % 4;
}
}
int main()
{
scanf("%d%d", &m, &n);
dfs(0, 0);
for (int c = 0; c < n; c++)
printf("._");
printf(".\n");
for (int r = 0; r < m; r++) {
printf("|");
for (int c = 0; c < n; c++) {
putchar(D[r][c] ? ' ' : '_');
putchar(R[r][c] ? '.' : '|');
}
printf("\n");
}
}

Eller算法(以行为单位的随机拆墙)

对于直接输出的算法来说,上述算法额外数据结构的空间复杂度都是和迷宫大小同阶的,其实我们只需要和迷宫宽(或高)同阶的额外空间就够了。

这个算法我所了解的出处是某届IOCCC的一个作品。http://homepages.cwi.nl/~tromp/maze.html给出了该作品的描述,后文我给出的实现也借鉴了链接中给出的代码。

先考虑第一行,随机拆掉一些格子的右墙。维护若干双线循环链表,每个链表表示这行连通的格子。所以拆墙后,如果第一行有x堵墙,那么就有x-1条链表。之后要决定哪些格子和下面一行相连。

._._._._._._.
|_. |_._. | |

在上图中,有2堵墙,有三个格子被决定和下面一行相连。最右边的格子没有和左边相连,但是只要它的下墙被拆除,那么它最终还是会和所有格子连通。因此这堵下墙的拆除是必需的。

接下来要处理第二行了,依旧是决定哪些格子的右墙须要被拆除。但要注意如果格子i的右墙即格子ii+1之间的墙被拆除了,那么必须保证在上面各行格子ii+1不连通。到这里为什么要使用链表维护连通性就明显了,我们需要快速判断格子ii+1在当前行之前有没有连通来决定它们俩之间的墙能否被拆除,用union-find算法当然可行,但链表更方便。

在决定完拆除第二行一些格子的右墙后,考虑哪些格子需要和下一行(即第三行)相连,假设我们的决定是这样的:

._._._._._._.
|_. |_._. | |
| |_._._. . |

这里注意到第二行最左边的格子,它的右墙没有被拆除,所以它的下墙必须被拆除以保证最终它会和其他格子连通。

然后考虑第三行哪些格子的右墙要被拆除:

._._._._._._.
|_. |_._. | |
| |_._._. . |
|_._. | |_| |

注意上图第三行最后两个格子,它们之间有墙,这堵墙不能被拆除,理由是第二行时它们已经连通了。

之后几行如法炮制:

._._._._._._.
|_. |_._. | |
| |_._._. . |
|_._. | |_| |
|_._._. | | |
| | ._._. | |
| |_._._| ._|

然后开始处理最后一行。最后一行的任务有点特殊,因为下墙不能被拆除(迷宫边界),需要拆除若干右墙使得最后一行的几个连通分支并在一起。发现不得不写成这样:

._._._._._._.
|_. |_._. | |
| |_._._. . |
|_._. | |_| |
|_._._. | | |
| | ._._. | |
| |_._._| ._|
|_._._._._._|

Disjoin-set forest的删除元素操作

之前的例子中我们发现每一行我们做了两步决策,拆右墙和拆下墙。有些时候右墙不能被拆除,是因为墙两边的格子在之前行已经被连通了。拆右墙就相当于合并两个集合。

右墙决策产生之后,有些下墙是必须拆的,即当它自成一个集合时。如果不拆下墙,那么在下一行,这个格子就和其他不连通了,所以得自成一个集合。

推敲我们需要实现的操作:并、查、从集合中删除一个元素,如果只有连两个操作,那么很简单,直接套用 disjoin-set forest 就好了。难点就在于如何支持“从集合中删除一个元素”这一操作。删除其实也是更新,引入时间因素后,就可以用一条更新记录来代替一个删除操作,但要注意把被删除的记录置为无效状态。删除一个元素,可以看作:引入一个新顶点,改变格子指向顶点的映射。

删除元素

如图,在格子0删除下墙前没有虚线边以及虚线顶点3。删除格子0的下墙后,需要让格子0对应的元素(顶点0)自成一个集合。做法是把蓝线(格子指向顶点的映射)换成红色虚线。尽管有顶点1和2在disjoin-set forest中已经指向顶点3,但是我们做的这个删除操作不会影响到它们。

用linked list实现disjoin sets

上一节通过改造disjoin-set forest使其支持删除元素的操作,但是改造后空间复杂度就没有吸引力了,因为所有产生的顶点数目可能是迷宫大小级别。

仔细研究我们用到的操作:

  • 合并:只有相邻格子所对应集合会合并;
  • 比较两个格子是否在一个集合中:只有相邻格子会被比较。

用一个链表表示一个connected component,并且让链表的元素按编号排序。那么对于格子i,查找其对应的链表中节点的后继是否对应格子i+1就能知道格子ii+1是否在同一个connected component。对于合并操作,以及让一个格子自成一个集合的操作,链表也都能出色地完成任务。

第一行

再来看:

._._._._._._.
|_. |_._. | |

行间有两堵墙,需要三个链表:

L[0] = 1, L[1] = 0; R[0] = 1, R[1] = 0
L[2] = 4, L[3] = 2, L[4] = 3; R[2] = 3, R[3] = 4, R[4] = 2
L[5] = 5; R[5] = 5

第二行

现在考虑第二行,上面的链表状态代表的迷宫如下:

._._._._._._.
|_. |_._. | |
| | | | | | |

决定拆除一些墙后:

._._._._._._.
|_. |_._. | |
| | . . . . |

相应地,链表状态变成:

L[0] = 0; R[0] = 0
L[1] = 5, L[2] = 1, L[3] = 2, L[4] = 3, L[5] = 4; R[1] = 2, R[2] = 3, R[3] = 4, R[4] = 5, R[5] = 1

接着决定拆掉一些下墙:

._._._._._._.
|_. |_._. | |
| |_._._. . |

那么格子1 、2、3都得自成一个集合,链表状态变成:

L[0] = 0; R[0] = 0
L[1] = 1; R[1] = 2
L[2] = 2; R[2] = 2
L[3] = 3; R[3] = 3
L[4] = 5, L[5] = 4; R[4] = 5, R[5] = 4

第三行

目前第三行尚未考虑拆墙,由上面的链表状态得出的连通信息:格子0、1、2、3互不连通,格子4、5连通,恰好能反应下图:

._._._._._._.
|_. |_._. | |
| |_._._. . |
| | | | | | |

OCaml实现

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
let eller m n =
let l = Array.create (n+1) 0 in
let r = Array.create (n+1) 0 in
for i = 0 to n-1 do
print_string "._";
l.(i) <- i;
r.(i) <- i
done;
l.(n) <- n-1;
print_string ".\n|";
for y = 0 to m-2 do
for x = 0 to n-1 do
let w = l.(x+1) in
let pat1 =
if x <> w && Random.int 3 <> 0 then begin
r.(w) <- r.(x);
l.(r.(w)) <- w;
r.(x) <- x+1;
l.(x+1) <- x;
'.'
end else
'|'
in
let pat0 =
if x <> l.(x) && Random.int 3 <> 0 then begin
l.(r.(x)) <- l.(x);
r.(l.(x)) <- r.(x);
l.(x) <- x;
r.(x) <- x;
'_'
end else
' '
in
print_char pat0;
print_char pat1
done;
print_string "\n|"
done;
for x = 0 to n-1 do
let w = l.(x+1) in
let pat1 =
if x <> w && (x == l.(x) || Random.int 3 <> 0) then begin
r.(w) <- r.(x);
l.(r.(w)) <- w;
r.(x) <- x+1;
l.(x+1) <- x;
'.'
end else
'|'
in
l.(r.(x)) <- l.(x);
r.(l.(x)) <- r.(x);
l.(x) <- x;
r.(x) <- x;
print_char '_';
print_char pat1
done;;
Scanf.scanf "%d %d" eller

C实现

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
##include <stdio.h>
##include <stdlib.h>
##define N 92
int L[N], R[N];
int main()
{
char pat[3] = {};
int m, n;
scanf("%d%d", &m, &n);
for (int i = 0; i < n; i++) {
printf("._");
L[i] = R[i] = i;
}
L[n] = n - 1;
printf(".\n|");
while (m--) {
for (int i = 0; i < n; i++) {
int j = L[i + 1];
if (i != j && rand() % 3) {
L[R[j] = R[i]] = j;
L[R[i] = i + 1] = i;
pat[1] = '.';
} else
pat[1] = '|';
if (i != L[i] && rand() % 3) {
L[R[i]] = L[i];
R[L[i]] = R[i];
L[i] = R[i] = i;
pat[0] = '_';
} else
pat[0] = ' ';
printf(pat);
}
printf("\n|");
}
pat[0] = '_';
for (int i = 0; i < n; i++) {
int j = L[i + 1];
if (i != j && (i == L[i] || rand() % 3)) {
L[R[j] = R[i]] = j;
L[R[i] = i + 1] = i;
pat[1] = '.';
} else
pat[1] = '|';
L[R[i]] = L[i];
R[L[i]] = R[i];
L[i] = R[i] = i;
printf(pat);
}
}

推荐阅读

Maze Generation: Eller’s Algorithm给出了关于Eller算法的详细描述。

Maze Classification给出了非常详细的迷宫生成算法和解法列表。