# 完美迷宫生成算法

## Perfect maze

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

## 变形Kruskal算法

### 伪代码

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)

### 实现

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

## Recursive backtracking算法

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

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

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

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

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

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

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

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

### 用linked list实现disjoin sets

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

#### 第一行

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

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

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

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

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

## 推荐阅读

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

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