假设我们要在N x M网格上创建一个简单的迷宫，该迷宫有一条路径，并且有很多死角，但是看起来"正确"(即就像有人手工制作的那样，没有太多微小的死角，所有这些)。有已知的方法吗？

解决方案

回答

奇怪的是，通过稍微更改"规范"规则并从随机配置开始，Conway的《生命游戏》似乎产生了相当不错的迷宫！

(我不记得确切的规则，但这是一个非常简单的修改，倾向于"致密化"细胞群……)

回答

来自http://www.astrolog.org/labyrnth/algrithm.htm

Recursive backtracker: This is somewhat related to the recursive backtracker solving method described below, and requires stack up to the size of the Maze. When carving, be as greedy as possible, and always carve into an unmade section if one is next to the current cell. Each time you move to a new cell, push the former cell on the stack. If there are no unmade cells next to the current position, pop the stack to the previous position. The Maze is done when you pop everything off the stack. This algorithm results in Mazes with about as high a "river" factor as possible, with fewer but longer dead ends, and usually a very long and twisty solution. It runs quite fast, although Prim's algorithm is a bit faster. Recursive backtracking doesn't work as a wall adder, because doing so tends to result in a solution path that follows the outside edge, where the entire interior of the Maze is attached to the boundary by a single stem.

他们只产生10％的死角

http://www.astrolog.org/labyrnth/sample/recursiv.gif

是通过该方法生成的迷宫的一个示例。