Maze Algorithms
Maza Create Algo
Binary tree algorithm
是一个挖墙算法，初始是一张网格
从四个角随便选一个，然后往对角扩张
具体扩张方式是从起点往对角方向遍历每一个网格，对于每一个网格，在对角方向上会有两个相邻的网格，随机选一个把两者之间的墙砸了
这个算法是每个单元格的操作是可以并行执行的
[!EXAMPLE] 从左下往右上的生成结果
可见这个算法得到的迷宫特点是对角方向最边上的行与列是空的，因为他们只有一个符合要求的邻居
而且，迷宫墙壁整体是有往对角方向延申的趋势的，因为压根就没有往左下走的入口
此外，我们还需要自己选一个入口和出口
Sidewinder
还是一个挖墙算法，初始是一张网格
第一行格子先全部连接，从第二行开始，我们先选最左边那个格子，然后接下来抛硬币决定要不要连接下一个格子
抛硬币抛到不连接了，就停止，现在我们得到了一个长方形，我们称这几个格子组成了一个 run
我们可以改变抛硬币概率分布来调整这个长方形大致的长度
最后还需要在一个 run 里面的几个格子中选一个，将其上面的那面墙打破
如果这一行还有格子没加入 run，就开一个新 run 重复上面的操作，直到这一行所有格子都操作过了，然后对每一行都这么干，搞定
可见我们可以对每一行进行并行运算
[!EXAMPLE]
可见整体会有从南北方向上的延申趋势
Aldous-Broder random walk
还是一个挖墙算法，初始是一张网格
- 随机选取一个 cell 作为起点
- 随机 link 一个还没访问过的邻居
- 将该邻居作为新的起点
- 随机 link 一个还没访问过的邻居，否则结束
[!EXAMPLE]
A-B 这个算法没有 bias，整体十分均衡
但是无法并行运算，一个个随机下来会很慢
[!QUOTE] What does bias mean?
Wilson's Algorithm
还是一个挖墙算法，初始是一张网格
和 A-B algo 差不多，random, no bias, inefficient
这俩个算法生成的迷宫无法区分
- 随机选一个 cell 标记为 visited
- 随机选择另一个 cell 作为起点
- 执行一个 loop-erased random walk，每一步选择一个随机邻居
- 因为我们不是一边 walk 一边标记 visited，所以可能出现 loop
- 出现了 loop，我们就回退到 loop 里的第一个 cell，然后继续 walk
- 如果这个邻居是 visited 的，就结束这次 walk，并把这个 walk 的所有 cell 标记为 visited，同时按 walk 顺序将他们 link 在一起
- 重复 2~4，直到所有 cell 都是 visited
[!EXAMPLE]
recursive backtracker
- 随机选择一个 cell 作为起点
- random walk，link to unvisited neighbor，如果发现走到死路了，就是回到上一个 cell，重复 2
显然我们借助一个 stack
[!EXAMPLE]
这个算法是有 bias 的，它会有一条最长的、扭曲的、很少 dead end 的路径
且由于使用了 stack，内存效率不高