问题描述
假设你想要一个 N × M 网格上的简单迷宫，有一条路径，有很多死胡同，但这看起来正确"(即有人手工制作，没有太多小死胡同以及所有这些).有没有已知的方法可以做到这一点?
Say you want a simple maze on an N by M grid, with one path through, and a good number of dead ends, but that looks "right" (i.e. like someone made it by hand without too many little tiny dead ends and all that). Is there a known way to do this?
推荐答案
来自 http://www.astrolog.org/labyrnth/algrithm.htm
Recursive backtracker:这与下面描述的递归backtracker求解方法有些相关，需要堆叠到迷宫的大小.雕刻时，尽可能贪婪，如果有一个与当前单元格相邻的部分，请始终雕刻成未制作的部分.每次移动到一个新单元格时，将前一个单元格推入堆栈.如果当前位置旁边没有未制作的单元格，则将堆栈弹出到上一个位置.当您从堆栈中弹出所有内容时，迷宫就完成了.该算法导致迷宫具有尽可能高的河流"因子，具有更少但更长的死角，并且通常是非常长且曲折的解决方案.它运行得非常快，尽管 Prim 的算法要快一些.递归回溯不能用作墙加法器，因为这样做往往会导致沿着外边缘的解决方案路径，其中迷宫的整个内部通过单个茎连接到边界.
他们只产生 10% 的死胡同
They produce only 10% dead ends
是由该方法生成的迷宫的示例.
is an example of a maze generated by that method.
这篇关于生成迷宫的好算法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！