转载

简单聊聊迷宫生成

前言

这几天在做项目时遇到了瓶颈，到处去翻资料找寻解决灵感，在indienova翻到篇翻译文章讲地牢生成算法，这篇文章本身倒没太多让人耳目一新的东西（不过作者在文章里用的示例确实很赞，动态的展示算法实现的过程，非常的清晰），但里面提到了一个前辈—— Jamis Buck，顺藤摸瓜的就去看了他的博客（http://weblog.jamisbuck.org/），结果一着迷就花了一天工夫在上面，这位前辈对迷宫生成的研究确实深！而且还出了本书叫《Maze for programmers》，可惜国内并不能买到。

简单聊聊迷宫生成

有人在评论里称他为“The King of Mazes”。

这位前辈在一篇文章里（点击阅读原文可跳转至此网址）总结了他这么多年来搜集总结的11种迷宫生成算法，虽然并没有全部都消化一遍，但也确实受益匪浅。

这里我就简单介绍下这里面我最喜欢的2种算法—— Growing Tree algorithm和Eller’s algorithm。在这里具体算法实现我可能不会完全介绍，主要是介绍下算法的思路，因为我觉得算法最大的作用不是拿来就用，而是开阔思路，除非它刚好完全符合你现在的需要，你可以奉行下“拿来主义”。而且有些算法需要自己去按照思路自己实现一遍才能更加感受到它的精妙。

Growing Tree algorithm

这个算法其实很容易理解，就是从一个迷宫起点开始做一个类似随机深度优先搜索，直到无法前进为止。然后通过一个启发式算法从已经探索过的节点中，寻找一个结点再一次重复上一步，直到整个迷宫里所有的结点都被探索过为止。算法过程中需要一个数据结构用来存储所有可能做为起点的节点列表。

这个算法也是Jamis Buck自己目前最喜欢的算法。因为这个算法有一个很神奇的地方，就在于它可以通过调整启发算法变成另外2个算法（ recursive backtracker & Prim’s algorithm ）。简单说，如果每次都挑选最新加入的一个节点，那么这个算法就等同于 recursive backtracker，而如果每次都去随机选取，它的实现就跟 Prim’s algorithm 非常类似。

令人惊艳的算法 —— Eller’s algorithm

这个算法简直令我吃惊！在看到这个算法之前，我一直都觉得做迷宫生成是一个图类遍历问题，但是这个算法的厉害之处就在于，它的迷宫是一行一行，一格一格生成的。它的实现过程，嗯，你可以想像一个老式打字机，在那一格一格把迷宫给你敲出来，仿佛迷宫已经生成好了，只是打印出来而已。所以，这个算法几乎是一个标准的O(m*n)算法，也基本上是所有算法里最快的。

简单聊聊迷宫生成