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

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

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

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