生成迷宫的好算法是什么? [英] What's a good algorithm to generate a maze?

问题描述

假设你想要一个 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 的算法要快一些.递归回溯不能用作墙加法器，因为这样做往往会导致沿着外边缘的解决方案路径，其中迷宫的整个内部通过单个茎连接到边界.

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% 的死胡同

They produce only 10% dead ends

是由该方法生成的迷宫的示例.

is an example of a maze generated by that method.

这篇关于生成迷宫的好算法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！