在游戏中，随机地图有算法动态生成，通常用在策略类游戏中，比较著名的采用随机地图的游戏有《文明》系列，《英雄无敌》系列，《暗黑破坏神》系列等。
随机地图每次生成都不同，能带给玩家可重复的代入未知感和探索乐趣。
生成随机地图有多种方法，一般取决于游戏地图的类型。一般户外自然场景的随机地图使用分形或噪声随机算法生成令人可信的自然随机地形。而一般地下城类型的场景使用二维随机迷宫算法。另有一些游戏支持随机地图模版或脚本来创建新的随机地图。
本文将会介绍《iMonster》项目实际开发迭代中，采用的随机游戏地图生成方法。
1、起点
最初游戏副本设定是迷宫样式，地图基本元素是tile，即格子迷宫。不同格子上发生不同事件。入口出口都在边缘上。首先要根据需求做技术选型：
·分形或噪声随机地图生成技术上显得很上流。从成功应用来看生成的地图也很漂亮。
但是存在以下问题，1应用地图场景很大，不符合我们副本的大小要求。2实现工作量很大，性价比不高。3时间复杂度往往非常高，相对我们副本游戏时间很不合算。
·使用《英雄无敌》用脚本和模版做随即扩展的地图，实现成本和时间复杂度也很高，我们游戏不也不需要mod扩展。
·地下城类似的封闭空间的二维迷宫地图，其tile组织结构和我们需求非常类似。实现和时间复杂度都在可控范围内。
所以，抛弃上流和华丽的浮云，我们先从满足最基本需求入手，快速开发一个原型来验证我们的gameplay。
2、技术原型
一个二维的M*N矩阵，矩阵中每一项为0表示不可通过，1表示可通过。通过算法在该矩阵中生成一个全连通(每个可通过节点到另一个可通过节点有且只有一个通路)的拓扑树（树的定义？在图论中，树是任意两个顶点间有且只有一条路径的图。或者说，只要没有回路的连通图就是树）。
遍历树的算法：深度优先遍历或广度优先遍历每一个tx的程序员在学习数据结构时都应该有所了解，（忘了？请参考深度优先搜索）。
生成全连通的迷宫就是求解一个随机生成树。可以使用某一遍历方法遍历寻访以下图中的空白节点，并将访问过程中经过的非空白节点清为路径。当每个空白节点都访问到了，迷宫就生成了。
其中
表示初始空白节点。
表示障碍物，
表示挖出来的路径。
这里我们使用了深度优先遍历，深度优先会产生较少的分支，较少分支会使得玩家寻访迷宫简单。更适合我们游戏的需求。
深度优先遍历时，在遍历下一个节点时，会取随机方向。这里我们可以控制一下生成风格迥异的迷宫，如果每次取随机的方向都尽量跟上一次不同则是下面左图的效果，如果每次取随机的方向尽量跟上一次相同则是下面右图效果，如果每次都是独立取随机方向则是下图中间效果。
这个随机方向惯性可以抽象为一个数值，供策划填写。
为了降低迷宫的难度，我们随机挖掉一些障碍物（下左图中的"⊙"）。挖掉百分比可以由GD控制。这样我们就得到了第一个版本的实现。
3、细节改进
除了生成迷宫，还需要根据配置，在迷宫的空白tile上布置各个事件，宝箱，陷阱，传送点等。最初就是在所有未分配的空白tile集合里取随机。很快策划就发现“这两个宝箱怎么放在一起啊”，“这条路上全是陷阱，还让不让人活了？！”。好吧，新需求产生了，并入新迭代。
原来空白待选tile只有“分配了事件”和“未分配事件”这两个状态。这些信息是不足与解决事件在地理距离上互斥的需求的，我们需要给空白待选tile一个可选概率值。
初始每个空白待选tile的候选概率值都为100，选取其中一个为宝箱，则该选取tile的概率值减100（降为0），该选取tile上线左右距离为1的tile的候选概率值减100，距离为2的tile的候选概率值减50，距离为3的tile的候选概率值减少25。这样根据候选概率值加和随机选取下一个候选空白tile时就有了权值。候选概率值越低的被选中的概率越低。有效的解决了事件地理分布过于“贫富不均”的问题。
4、持续进化
目前每个地图生成核心参数为W(宽)，H(高)，Hole(额外删除障碍数)。随着游戏开发持续进行，很快发现原有迷宫型地图有两个问题：1地图Hole设置的少则迷宫太密集太窄。走起来感觉“闷”，Hole设置的太高，则地图太零碎，太离散不自然。2所有的障碍tile都是1*1的，美术同学在发挥时空间不大，都是散碎的小地图部件，看起来很“呆板”。
下左图为15*15，Hole为10。下右图为15*15，Hole为50。
稍微分析一下，是我们的生成树算法只能解决连通性，不能解决自然连续，疏密相间，过渡自然这些属于“美学”的特性。怎么办？计算美学这个概念是不是马上出现在脑子里，是不是分形学，Perlin噪声，侵蚀系统这些上流词汇又在不停的诱惑你。停一停，该醒醒了，技术风险，项目进度，持续交付，人力成本这些都在恶狠狠地盯着你。
让我们再进一步分析分析。“疏密相间，过渡自然”是什么，无非就是有的地方多填充点障碍，有的地方多挖点空白。首先想到的是不是在初始图上有的空白集中填成障碍，有的障碍集中填成空白。但是等等，我们做的毕竟是个通路地图，一定要保证有通路，不能有“飞地”，不能有不连通的空白。填障碍的时候一定要保证地图连通性。填一格算一下么，时间复杂度怎么保证。填的时候做些限制，分成井字布局填充么，那做出来的东西还是很呆板。
在看看我们的生成树，某些树上节点的删除是不是不影响连通性。很快我们就能找到这些点。这些点对于树来说就是叶节点，对于迷宫来说就是死路头（见下左图）。这些点填充为障碍是不影响整个地图的连通性（见下右图）。
这些叶子节点去除会产生更多叶子节点。依次递归填充便会产生如下地图（查找叶子节点的时间复杂度并不高）
OK，这样是不是很容易就做到了疏密相间和保持连通（保持只少一条边到另一条边的连通还需要多做些判断工作）。不过原来的挖路功能也需要修改，只有和空白格子相邻的障碍格子可以删除，否则就会产生“飞地”。这个过程就有点像河水侵蚀大陆，只有河岸才能被侵蚀。我们把清空障碍，产生大片空地的参数形象的称之为侵蚀系数。把刚才删除叶子节点的参数形象称为堆积系数。
现在我们有了W(宽)，H(高)，Accumulation (障碍堆积系数)，Erosion(障碍侵蚀系数)四个核心参数。我们看看此次进化后的效果
15 15 30 2015 15 30 40
15 15 10 515 15 80 8
配合不同的参数配置，可以达到策划预想的稀疏效果。使得地图表现更丰富，更具自然特性。
5、进一步？
后续又加入了模版功能，可以自定义一些有特殊模版外形的地图，比如菱形地图。以下是同一个随机种子和不同的控制参数生成的几幅地图。
特性：
1、服务器和客户端可以用同一个随机种子和几个额外控制参数分别生成出相同的副本地图。
2、只针对地形生成，本算法空间占用只随地图尺寸W*H成线性增长。时间消耗都在可控范围内，之前测试中生成10000个25*25尺寸，堆积系数30，侵蚀系数25耗时在1.3秒；尺寸升到35*35，10000个地图耗时增加到2.6秒。完全满足实时动态需求。
3、随机地图在地图设计感，解密元素上有很大欠缺，不过这些不能只靠地形体现，需要更完整的系统来实现。
网友评论