地下城随机关卡是如何生成的
发表于2017-03-01
为什么会有随机关卡的存在,是因为一款游戏想要得到玩家们的喜爱,就要从内容关卡的设计上着手,但由于创造的过程太消耗时间,所以多数游戏会采用随机关卡的方式吸引玩家,从而增加游戏的可玩性,那在地下城中随机关卡是如何生成的呢?看看下面的介绍你就知道了。
从张峰前辈的帖子(http://gad.qq.com/article/detail/7173693)中看到一张动态图,我断定这是一个随即关卡生成的示意图,我对随机生成关卡非常有兴趣,所以就到处去找出处。
如果没有翻墙软件(VPN)我是不可能用上Google的,如果不用Google我是不会找到出处的。
所以非常感谢Tngrnow,非常感谢Google图片搜索功能。
搜索过程:
1、Google图搜-->
韩国网站This is game mh4 子论坛-->没有线索
日本一个猎奇网站-->找到了一条描述信息(蓝色区域)-->
![](http://gameweb-img.qq.com/gad/20170301/phpmpcwjx.1488369363.png)
看到图片上传时间,我有些郁闷,我们这些人好像与世隔绝太久时间了。
Google-->找到了http://postd.cc/procedural-dungeon-generation-algorithm/
(日本网站,我认为这个算法真的是日本人写的)
网站上面有一个链接,点击-->https://github.com/adonaac/blog/issues/7
(好强大的github,这才是源地址)
上面是搜索过程,下面介绍一下随即关卡生成的算法
一、生成房间:
1、在一个圆形范围内生成随机点;
http://stackoverflow.com/questions/5837572/generate-a-random-point-within-a-circle-uniformly
![](http://gameweb-img.qq.com/gad/20170301/phpPWTPgo.1488369861.png)
2、以随机点为中心生成生成一些宽度、高度随机的长方形(房间),这些房间被放置在一个圆形的范围内中,TKdev的算法使用了正态分布生成房间大小;
![](http://gameweb-img.qq.com/gad/20170301/phpGau9Z6.1488369783.gif)
二、分离房间:
在圆圈内生成的房间是重叠在一起的,想办法让他们不要重叠在一起:
1、沿X轴或者Y轴向远离中心点的位置移动;
2、里中心点越远的房间最终位置越靠外;
![](http://gameweb-img.qq.com/gad/20170301/phpjeNKyk.1488369981.gif)
作者最后的结论认为使用物理引擎来做这个更简单。
![](http://gameweb-img.qq.com/gad/20170301/phpkH6Ilu.1488370004.gif)
拓展:假如做一个水平探索或者竖直探索的游戏,地下城该如何声称
解决办法:将生成范围调整为一个左右长,上下短的椭圆区域。
![](http://gameweb-img.qq.com/gad/20170301/phpqkiwWm.1488370019.gif)
生成竖版关卡
![](http://gameweb-img.qq.com/gad/20170301/php9699Jt.1488370034.gif)
生成横版关卡
三、生成主要房间
设定一个算法,选出大小合适的房间作为主要房间,作者并没有介意这些房间的位置 ...(万一生成的地图中主要房间都在一条直线上呢...)
![](http://gameweb-img.qq.com/gad/20170301/phpqWPqmK.1488370135.gif)
四、生成三角树
以所有主要房间的中心点为端点,生成一张由三角形构成的平面
1、线段不能交叉;
2、一个端点(房间)不能包含在太多的三角形中
![](http://gameweb-img.qq.com/gad/20170301/phpHh54sW.1488370157.gif)
五、生成通道树
将上面的三角数目变成最小生成树(去问程序),确保所有房间都可以到达。
![](http://gameweb-img.qq.com/gad/20170301/phphDaAPI.1488370179.gif)
但是最小生成树有一个问题:线性关卡(除非有剧情的地下城,地下城线性关卡是比较无趣的)
最后作者做了修改:添加8-10%左右的线段。
![](http://gameweb-img.qq.com/gad/20170301/phpjmj4MY.1488370226.gif)
六、生成走廊
1、生成关卡连接线:横线、竖线、横加竖(L型);
![](http://gameweb-img.qq.com/gad/20170301/phpHT3kai.1488370281.png)
2、将连接线上的非主要房间作为走廊的骨架;
![](http://gameweb-img.qq.com/gad/20170301/php1Mn4ZE.1488370293.png)
3、生成道路,用于覆盖没有被非主要房间覆盖的地方。
![](http://gameweb-img.qq.com/gad/20170301/phpxsNnkW.1488370308.png)
Steam上面,基于该算法制作的游戏
http://store.steampowered.com/app/278620/
![](http://gameweb-img.qq.com/gad/20170301/phpa88u6w.1488370546.png)
玩家评论
根据作者的文章,其他人制作的关卡生成器
https://github.com/piotr-j/dungen
https://github.com/JnyJny/DungeonGenerator
这是一个可以在线测试的关卡生成器(有些关卡太不着调了)
千万不要用360出品的浏览器,Firefox没问题
http://piotrjastrzebski.io/dungen/dungen/
在圆内生成随机点
http://stackoverflow.com/questions/5837572/generate-a-random-point-within-a-circle-uniformly