什么是好的算法来生成迷宫？ [英] 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?

推荐答案

从<一个href="http://www.astrolog.org/labyrnth/algrithm.htm">http://www.astrolog.org/labyrnth/algrithm.htm

递归backtracker：这是有些相关的以下描述的递归backtracker求解方法，并且需要堆叠最多的迷宫的大小。当雕刻，是因为贪婪地，始终雕刻成一个没有整理部分，如果一个是靠近当前单元格。移动到新的小区每次推前面的小单元堆栈上。如果没有未建立的细胞旁的当前位置，弹出栈到previous位置。当你突然一切都从堆栈中的迷宫完成。此算法的结果迷宫约尽可能高的河的因素成为可能，用较少的但更长死角，而且通常很长，曲折的解决方案。它运行相当快，虽然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屋！