地下城随机关卡是如何生成的
发表于2017-03-01
为什么会有随机关卡的存在，是因为一款游戏想要得到玩家们的喜爱，就要从内容关卡的设计上着手，但由于创造的过程太消耗时间，所以多数游戏会采用随机关卡的方式吸引玩家，从而增加游戏的可玩性，那在地下城中随机关卡是如何生成的呢？看看下面的介绍你就知道了。
从张峰前辈的帖子（http://gad.qq.com/article/detail/7173693）中看到一张动态图，我断定这是一个随即关卡生成的示意图，我对随机生成关卡非常有兴趣，所以就到处去找出处。
如果没有翻墙软件（VPN）我是不可能用上Google的，如果不用Google我是不会找到出处的。
所以非常感谢Tngrnow,非常感谢Google图片搜索功能。
搜索过程：
1、Google图搜-->
韩国网站This is game mh4 子论坛-->没有线索
日本一个猎奇网站-->找到了一条描述信息（蓝色区域）-->
看到图片上传时间，我有些郁闷，我们这些人好像与世隔绝太久时间了。
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
2、以随机点为中心生成生成一些宽度、高度随机的长方形（房间），这些房间被放置在一个圆形的范围内中，TKdev的算法使用了正态分布生成房间大小；
二、分离房间：
在圆圈内生成的房间是重叠在一起的，想办法让他们不要重叠在一起：
1、沿X轴或者Y轴向远离中心点的位置移动；
2、里中心点越远的房间最终位置越靠外；
作者最后的结论认为使用物理引擎来做这个更简单。
拓展：假如做一个水平探索或者竖直探索的游戏，地下城该如何声称
解决办法：将生成范围调整为一个左右长，上下短的椭圆区域。
生成竖版关卡
生成横版关卡
三、生成主要房间
设定一个算法，选出大小合适的房间作为主要房间，作者并没有介意这些房间的位置 ...（万一生成的地图中主要房间都在一条直线上呢...）
四、生成三角树
以所有主要房间的中心点为端点，生成一张由三角形构成的平面
1、线段不能交叉；
2、一个端点（房间）不能包含在太多的三角形中
五、生成通道树
将上面的三角数目变成最小生成树（去问程序），确保所有房间都可以到达。
最小生成树但是最小生成树有一个问题：线性关卡（除非有剧情的地下城，地下城线性关卡是比较无趣的）
最后作者做了修改：添加8-10%左右的线段。
生成非线性树六、生成走廊
1、生成关卡连接线：横线、竖线、横加竖（L型）；
2、将连接线上的非主要房间作为走廊的骨架；
3、生成道路，用于覆盖没有被非主要房间覆盖的地方。
Steam上面，基于该算法制作的游戏
http://store.steampowered.com/app/278620/
玩家评论
根据作者的文章，其他人制作的关卡生成器
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