地下城随机关卡生成算法

小篱

　　为什么会有随机关卡的存在，是因为一款游戏想要得到玩家们的喜爱，就要从内容关卡的设计上着手，但由于创造的过程太消耗时间，所以多数游戏会采用随机关卡的方式吸引玩家，从而增加游戏的可玩性，那在地下城中随机关卡是如何生成的呢？看看下面的介绍你就知道了。

　　从张峰前辈的帖子中看到一张动态图，我断定这是一个随即关卡生成的示意图，我对随机生成关卡非常有兴趣，所以就到处去找出处。

　　如果没有翻墙软件（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、在一个圆形范围内生成随机点；

　　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/questio ... -a-circle-uniformly

GAD编译

avi9111

不错哦，最近为什么又多了这类分享，游戏婴儿潮都长大了么？？