随机迷宫生成算法整理分析
前言
前段时间学校游戏开发课大作业,做了一个Roguelike的恐怖游戏。搜集整理了一些迷宫生成的算法。
当初也受了indienova上一些文章的启发。现在在此把学到的一些东西理一理分享出来。
第一次写这种东西,感觉有点啰嗦,还请大家不要介意,也可以直接看项目地址
代码写在Unity环境下,应该可以直接使用。
第一种算法
先上一张图
这是我最早拍脑袋凭着感觉写的一个算法结果,给定区域长宽和分支概率,可以生成一张迷宫图。
这完全就是随机挖洞大法,其步骤如下:
- 计算当前扫描点周围可以挖的方块
- 随机选一个方块挖开
- 若周围还有可挖方块,按分支概率随机挖开另一方块,设为新扫描点
- 所有扫描点执行
1
操作 - 若周围无方块可挖,中止此扫描点工作。
可以看出,这个算法有相当的缺陷,生成的迷宫总面积不可控,在运气不好的极端情况下,会产生比预期面积小很多的迷宫。
即使我们将分支概率调到100%,依旧会有黑色的空洞存在:
而且生成的迷宫非常扭曲怪诞,这很克苏鲁。或许我们可以风格化一下……
此时的迷宫已经勉强可以使用,但是与传统迷宫的差别依旧非常大。
它的斜线非常多。这会使得游戏过程中包含八个方向,对玩家的方向感是极大的考验,很难再记住地图,容易晕头转向。
对于这个算法,相比室内环境,更适合生成自然环境下迷宫。也可以作为无主线、弱主线沙盘游戏的大地图生成的一环。
递归分割
接下来这个算法与第一个就是两个极端——生成完全没有斜线的迷宫。
话不多说,先上图:
在介绍本算法前,需要提出一个概念
完美迷宫Perfect maze:没有回路,也没有孤立区域的迷宫。用图论来解释,就是可以用生成树表示的迷宫,迷宫中两点有且仅有一条路径。
这个算法是一个分治算法,即将一块大的生成区域分成4块小区域分别生成迷宫并保证联通,以此类推,直到不可细分。
分块很简单,长宽上各取一个随机数即可。如何保证迷宫完美呢?
我们看极端情况,对于一个田字形区域,生成完美迷宫的方法是敲开三堵墙。
利用分治算法的特性,每一层递归都是完美迷宫,直到全图生成完美迷宫。
算法不难,注意递归状态的边界情况就行。
这种分治递归的痕迹在生成的地图俯视图上很明显,但对于置身其中的玩家或许就不是了。
它生成的迷宫完全没有斜线,横平竖直,同时会生成4*4的小房间。
用作城市地图、或建筑环境的迷宫非常合适。
当然在游戏中地图没有回路是非常致命的,一个完美迷宫会让玩家疲于奔命,并不方便设计玩法。
对于回路,我们只需要消除死路就行了,也就是那些三面临墙的格子,在地图生成完后遍历死路,按一定概率打通即可。
生成树算法 Kruskal & Prim
绝大多数的编程问题都可以用数学工具解决,当然我们的迷宫生成算法也不例外。
数学中最适合表达迷宫的符号莫过于 图
,下面两个算法是迷宫生成中应用最普遍的理论之二。
首先我们需要将地图转换为便于数学表达的形式。
之前两个算法在处理地图时都是以 方块
为单位的,即每一个方块不是墙就是路。
而 图
的基本组成是 点
与 边
,对于一个待处理的迷宫,我们做如下转换。
迷宫大小10*10,其中白块代表 点
,红块代表 边
,而黑块代表 虚无
,只是填充物质罢了。
如果一个 图
中,任意两 点
都能通过 边
组成的路径联通,称之为 连通图
。
而如果一个 连通图
上没有回路,则我们可以称之为 树
,因为没有回路,所以每对点之间有且仅有一条路径联通。
可以看到,树
与我们完美迷宫的概念不谋而合,所以现在我们的任务是找到包含所有点的一棵 树
。
最小生成树
生成树,顾名思义,就是从给定的 点
,边
集合中生成一棵符合要求的树。
下面介绍的两种最小生成树算法都可以胜任。
虽然写作最小生成树,但这两个算法其实可以做到“按一定条件生成树”。
“最小”是算法的典型描述,即在有权边的集合中找出权值最小的树。原算法使用贪心算法求解。
而在这里,我们的条件就是:随机。
下面简单介绍一下这两个算法的步骤:
两个算法都需要 点
的集合E
,与 边
的集合V
。对于上图,E
代表所有白块,V
代表所有红块
Kruskal:
一开始每个点将自己作为单独的一棵树。
- 从
V
中随机选出一条边v
- 判断
v
两端的e1
,e2
是否属于一棵生成树- 是,无动作
- 否,绘制
e1
,v
,e2
并合并树
- 从
V
中删除v
- 当
V
不为空,则返回 1. ,V
为空则完成
ps:判断与合并两点所在树可以使用并查集相关算法,因为最近有点忙(懒),还没研究透,我代码里用了比较笨的全图标记,应该会在近期更新代码到并查集
===============
Prim:初始V
为空,所有e
∈E
标记为0
- 随机选一个点
e
- 将与
e
相连的边的集合{Ve}
并入入V
,e标记为1 - 从
V
中随机选一条边v
- 判断v两端情况
- 均为1:无动作
- 一个0一个1:将为0的点
e
标记为1,绘制v
,e
,将e
连接的边并入V
- 均为0:不可能
- 从
V
中删除v
- 当所有
e
∈E
均被标记为1,结束,否则返回 3. 。
ps:可以维护一个包含所有v
∈V
的标记表,防止被重复并入V
,提高效率
以上为算法步骤,建议配合代码食用更佳。
下为运行结果
前者为Kruskal,后者为Prim。白路黑墙。
可以看到两个算法的生成迷宫风格几乎一样,并且都较为接近传统迷宫。可以用于各类需要迷宫生成的游戏。
值得一提的是这两个算法都可以加入房间,只需将房间预先生成,在将剩余可生成的点与边的集合放入算法中运行即可。
关于这个详细可以参考房间和迷宫:一个地牢生成算法
到这里关于游戏中迷宫生成最常用的几个算法已经写完了。除了上述几种以外,迷宫的生成方法还深度广度优先搜索之类很多。
此外还有诸多适用于特定游戏系统的地图生成算法,如MC中的噪音,Unexplored中的环状地图等
想把随机的房间加入,加入一个出口点,多个入口,全联通模式。可以吗
赞啊,大家可以仔细看看,研究下