Roguelike 开发小组

创建于:2016-04-16

创建人: eastecho

92 信息 1355 成员
Roguelike 开发的相关讨论

随机迷宫生成算法整理分析

cocolate 2016-10-31

前言

前段时间学校游戏开发课大作业,做了一个Roguelike的恐怖游戏。搜集整理了一些迷宫生成的算法。

当初也受了indienova上一些文章的启发。现在在此把学到的一些东西理一理分享出来。

第一次写这种东西,感觉有点啰嗦,还请大家不要介意,也可以直接看项目地址

代码写在Unity环境下,应该可以直接使用。

第一种算法

先上一张图

Image title


这是我最早拍脑袋凭着感觉写的一个算法结果,给定区域长宽和分支概率,可以生成一张迷宫图。

这完全就是随机挖洞大法,其步骤如下:

  1. 计算当前扫描点周围可以挖的方块
  2. 随机选一个方块挖开
  3. 若周围还有可挖方块,按分支概率随机挖开另一方块,设为新扫描点
  4. 所有扫描点执行 1 操作
  5. 若周围无方块可挖,中止此扫描点工作。

可以看出,这个算法有相当的缺陷,生成的迷宫总面积不可控,在运气不好的极端情况下,会产生比预期面积小很多的迷宫。
即使我们将分支概率调到100%,依旧会有黑色的空洞存在:

而且生成的迷宫非常扭曲怪诞,这很克苏鲁。或许我们可以风格化一下……

而且生成的迷宫非常扭曲怪诞,这很克苏鲁。或许我们可以风格化一下……


此时的迷宫已经勉强可以使用,但是与传统迷宫的差别依旧非常大。
它的斜线非常多。这会使得游戏过程中包含八个方向,对玩家的方向感是极大的考验,很难再记住地图,容易晕头转向。

对于这个算法,相比室内环境,更适合生成自然环境下迷宫。也可以作为无主线、弱主线沙盘游戏的大地图生成的一环。

递归分割

接下来这个算法与第一个就是两个极端——生成完全没有斜线的迷宫。
话不多说,先上图:

迷人的大迷宫

在介绍本算法前,需要提出一个概念

完美迷宫Perfect maze:没有回路,也没有孤立区域的迷宫。用图论来解释,就是可以用生成树表示的迷宫,迷宫中两点有且仅有一条路径。

这个算法是一个分治算法,即将一块大的生成区域分成4块小区域分别生成迷宫并保证联通,以此类推,直到不可细分。

分块很简单,长宽上各取一个随机数即可。如何保证迷宫完美呢?
我们看极端情况,对于一个田字形区域,生成完美迷宫的方法是敲开三堵墙。

利用分治算法的特性,每一层递归都是完美迷宫,直到全图生成完美迷宫。
算法不难,注意递归状态的边界情况就行。

这种分治递归的痕迹在生成的地图俯视图上很明显,但对于置身其中的玩家或许就不是了。

它生成的迷宫完全没有斜线,横平竖直,同时会生成4*4的小房间。
用作城市地图、或建筑环境的迷宫非常合适。

当然在游戏中地图没有回路是非常致命的,一个完美迷宫会让玩家疲于奔命,并不方便设计玩法。
对于回路,我们只需要消除死路就行了,也就是那些三面临墙的格子,在地图生成完后遍历死路,按一定概率打通即可。

生成树算法 Kruskal & Prim

绝大多数的编程问题都可以用数学工具解决,当然我们的迷宫生成算法也不例外。
数学中最适合表达迷宫的符号莫过于 ,下面两个算法是迷宫生成中应用最普遍的理论之二。

首先我们需要将地图转换为便于数学表达的形式。
之前两个算法在处理地图时都是以 方块 为单位的,即每一个方块不是墙就是路。
而  的基本组成是  与  ,对于一个待处理的迷宫,我们做如下转换。

Image title

迷宫大小10*10,其中白块代表 ,红块代表 ,而黑块代表 虚无,只是填充物质罢了。

如果一个  中,任意两  都能通过  组成的路径联通,称之为 连通图

而如果一个 连通图 上没有回路,则我们可以称之为 ,因为没有回路,所以每对点之间有且仅有一条路径联通。

可以看到, 与我们完美迷宫的概念不谋而合,所以现在我们的任务是找到包含所有点的一棵 

最小生成树

生成树,顾名思义,就是从给定的 , 集合中生成一棵符合要求的树。
下面介绍的两种最小生成树算法都可以胜任。

虽然写作最小生成树,但这两个算法其实可以做到“按一定条件生成树”。
“最小”是算法的典型描述,即在有权边的集合中找出权值最小的树。原算法使用贪心算法求解。

而在这里,我们的条件就是:随机。

下面简单介绍一下这两个算法的步骤:

两个算法都需要  的集合E,与  的集合V。对于上图,E代表所有白块,V代表所有红块

Kruskal:
一开始每个点将自己作为单独的一棵树。

  1. V中随机选出一条边v
  2. 判断v两端的e1e2是否属于一棵生成树
    • 是,无动作
    • 否,绘制e1,v,e2并合并树
  3. V中删除v
  4. V不为空,则返回 1. ,V为空则完成

ps:判断与合并两点所在树可以使用并查集相关算法,因为最近有点忙(懒),还没研究透,我代码里用了比较笨的全图标记,应该会在近期更新代码到并查集

===============

Prim:初始V为空,所有eE标记为0

  1. 随机选一个点e
  2. 将与e相连的边的集合{Ve}并入入V,e标记为1
  3. V中随机选一条边v
  4. 判断v两端情况
    • 均为1:无动作
    • 一个0一个1:将为0的点e标记为1,绘制v,e,将e连接的边并入V
    • 均为0:不可能
  5. V中删除v
  6. 当所有eE均被标记为1,结束,否则返回 3. 。

ps:可以维护一个包含所有vV的标记表,防止被重复并入V,提高效率

以上为算法步骤,建议配合代码食用更佳。

下为运行结果

Image title

前者为Kruskal,后者为Prim。白路黑墙。

可以看到两个算法的生成迷宫风格几乎一样,并且都较为接近传统迷宫。可以用于各类需要迷宫生成的游戏。

值得一提的是这两个算法都可以加入房间,只需将房间预先生成,在将剩余可生成的点与边的集合放入算法中运行即可。
关于这个详细可以参考房间和迷宫:一个地牢生成算法

到这里关于游戏中迷宫生成最常用的几个算法已经写完了。除了上述几种以外,迷宫的生成方法还深度广度优先搜索之类很多。
此外还有诸多适用于特定游戏系统的地图生成算法,如MC中的噪音,Unexplored中的环状地图等


(转发自:原日志地址

近期喜欢的会员

 
eastecho 2016-11-03

赞啊,大家可以仔细看看,研究下

 
hsl9999 2017-08-04

想把随机的房间加入,加入一个出口点,多个入口,全联通模式。可以吗

 
cocolate 2017-08-07

hsl9999 可以参考文章最后给出文章里的房间生成算法。

我给出的后两个图论相关算法是不限地图形状的,可以直接用到生成完房间的地图上。

然后对每个房间设定门的数量,将房间周围路径纳入生成路径的备选。

 

加入 indienova

  • 建立个人/工作室档案
  • 建立开发中的游戏档案
  • 关注个人/工作室动态
  • 寻找合作伙伴共同开发
  • 寻求线上发行
  • 更多服务……
登录/注册