数值策划如何玩转 Dijkstra 算法来设计随机地图

对于 Roguelike 类游戏而言，随机地图是一个非常核心的元素，而在很多 Diablolike 游戏中，随机地图也依然表现得非常活跃。我们可能看到过很多随机地图的生成算法，包括且不限于 GDC 以及 GMTK 等知名的游戏交流媒体的分享。但是绝大多数随机算法都会要求手工预设关卡的大多内容，包括 Diablo 等著名的游戏在内，都是预先拼好了一些地图，然后只是在随机位置随机挑选了这些地图中的几个用上。毕竟这样做的好处是：地图看起来是美的，而且不会有死图（即发生入口无法通向出口的情况），并且刷怪位置相对合理。

那么有没有一种不需要手动预设内容的随机算法，只需要调整一些参数，它就可以生成出看起来美观，也不会产生死图，还能确保生成的刷怪点位置合理的方法呢？今天我们就将深入地探索一下一个寻路算法 --Dijkstra 算法，只要稍微调整一下使用的"手法"，这个奇妙的、被用于寻找最短路径算法就会成为一个极其强大的随机地图生成算法，并且对精通于设计数学函数的数值策划来说，可以轻松地用几个参数就玩转这个"Dijkstra 随机地图生成法"。

01、深度解读 Dijkstra 算法

我们通常了解的 Dijkstra 是一个寻找 2 点之间最短路径的算法，这个算法往往与他的两个特殊形态 Floyd 算法和 AStar 算法齐名。

Dijkstra 算法本身非常好理解，即在地图中的某个点作为起点，然后向四面八方展开寻找，每进入一个格子都累加一个 Cost 值，然后对于地图上每一个格子都算出走进这个格子的最短路径，即 Cost 值最小的从起点点通向通向这个格子路线，最终遍历完所有的格子之后，获得最短的路线。如图所示：

大多情况下，Dijkstra 的开销都很大，所以在 Greedy Best-First 的思路结合之下，产生了 AStar 寻路。但是 Dijkstra 并没有因为 AStar 的出现就退出游戏开发的舞台，他依然在战棋类 SLG 中活跃：

在战棋 SLG 中，角色的移动范围可以通过 Dijkstra 算法得出，毕竟每一个角色的行动力是有限的，并且地图中的地形会影响行动力，同时敌方角色的临近格子行动力消耗也会进一步提高，所以 Dijkstra 算法被巧妙地用于"不寻找目标点，而是寻找到行动力足以达到的点"。

到这里是最基础的 Dijkstra 算法的介绍，接着我们需要更进一步的去思考一些问题。我们通常使用 Dijkstra 算法的时候，检查单元格的规则都是"周围的格子"，但是假如有些格子是一个传送门入口，走进去以后可以从 n 个出口中选择一个，这时候寻路算法需要做出什么改变呢？如图所示：

如果绿色是起点，红色是终点，通常我们的寻路法就会产生出一条黑线的路线，但是当我们为地图上增加了传送门入口（蓝色圆圈），走进这个传送门，就可以从 3 个橙色圆圈的传送门出口中任意选择一个作为出口的时候，问题就出现了，因为蓝色的格子一下子代表了 3 个其他格子。因此我们可以发现，事实上我们只把 Dijkstra 算法用于 Tilebased 游戏寻路的时候，理所应当的觉得"周围的格子"作为"下一个格子"是这个算法的一部分，但实际上，对于 Dijkstra 算法而言，如何选取"下一个格子"，是需要设计的一部分。

如上图所示，Dijkstra 算法的"下一个格子"其实是"下一个 node"，也就是根据一个规则加入到判断列表里的，如果是传送门他应该是这样的：

由于走进 B 相当于走进 B1 或 B2 或 B3，所以我们打断了 B 这个"不存在的格子"，链接了 B1\B2\B3。这正是 Dijkstra 算法的核心之一 --"路径的节点规则"。

02、随机地图的准备工作

在了解了 Dijkstra 算法的性质之后，我们就要开始准备巧妙地使用它来生成随机地图了。但是在这之前，我们还需要一些步骤，这些随机地图生成的步骤其实是不需要 Dijkstra 算法的。

在这里我们需要数值策划设计的第一个内容是：地图信息 = f (迷宫，层数)，这个函数的本意也就是根据地图的难度系数，来算出当前地图的一些信息，这些信息至少要包含：

• 房间的个数：我们知道大多 roguelike 地图是需要房间的，房间个数越多，则迷宫对于玩家来说难度越大。因此对于我们生成地图来说，房间的个数也是一个核心数据，不知道房间个数就没法生成难度合适的随机地图了。

• 每个房间的最大、最小尺寸：这个尺寸的宽度高度是可以不同的，但是我们最好认为他们是相等的，这样可以让房间的位置相对更加均匀一些。而最小尺寸应该是小于最大尺寸的，如果相等一样会影响一些随机的效果。

• 房间之间的连线最小单元格数：房间之间还是需要有路线连接的，路线的最小长度是可以要求的，这应该是个自然数，如果是 0，则可能生成出墙壁紧挨着的 2 个房间，会影响美观，当然这也可以在生成之后进行补正，比如消除一堵墙壁等。

• 房间之间的连线最大单元格数：这应该是一个大于最小 tile 数的存在，这样才有了随机的余地。

• 房间怪物数信息：这个信息将被用于生成怪物的刷新点。

• 最小经过房间数：我们知道 Roguelike 地图可能会有这样的需求，就是我到达这一层之后，至少要走过多少个房间才能遇到去一下层的入口。如果这个值是 0，则有可能来到这一层的第一个房间就有下楼的楼梯；当然这个数字肯定是不能大于等于房间数的，不然就走不通了，建议是取房间数的一半。

当以上地图数据得出之后，我们就可以确定出本层地图横向纵向需要的"块"数，所谓的"块"即每个随机房间出现的范围。为了确保地图尽可能接近正方形范围（这仅仅是为了"美观"），可以这样：横向的块数 =（"房间的个数"的平方根）向上取整，纵向的块数 =（总房间数 / 横向块数）向上取整。也就是说，比如是 7 个房间的地图，在这里会被划分为 3x3 个块，如图所示：

我们可以很简单的算出一个"块"的单元格数：横向格数 = 房间最大横向格数 + 横向连线最大 tile 数；纵向格数 = 房间最大纵向格数 + 纵向连线最大 tile 数。而每个块的格数乘以块数，就能算出地图横向和纵向总共有多少个单元格。

当确定完单元格之后，我们要解决一个问题就是块数 > 房间数的问题，如果是等于，就没有什么问题，但是如果是大于，我们就首先要随机取出（总块数-房间数）行（或者列），然后在这些行（或者列）中取出 1 个"块"删除掉，如图所示（图中取行）：

我们随机了第 1 行和第 3 行，各去掉一个"块"。这样房间数正好是 2+3+2=7 个。然后我们对于每一行进行随机分块，这个分块的过程，确定了每一个"块"拥有的横向、纵向单元格数量，这个最小单元格数应该不小于房间的最小宽度（高度）+ 横向（纵向）最短连接单元格数。均摊之后的块很可能是这样的：

从上图我们可以看出，切块之后，"块"与"块"之间的连接图也产生了（上图中只列出了 1 号"块"的连接关系），而每个"块"中仅有 1 个房间，所以"块"的连接关系，也是房间的"初步连接关系"，之所以是初步的，因为我们后期还会打断一些连接。

确定完连接之后，我们就要随机找出每一个"块"中的一个随机点，作为这个"块"的房间的"中心点"，这个中心点的范围，至少得符合房间最终能在"块"内，且尽可能符合最长最短链接单元格的要求。到这里每一个"块"的属性、也就是每个房间的基础数据就产生了，这个数据中包含了：

• 房间 id：这个房间的 id

• "中心点"坐标：这是用于生成房间的核心数据。

• 链接房间数组：这个房间可以连接到的房间的 id 数组。

到此，我们的准备工作也就完成了，接下来就要开始生成房间的重要算法了。首先我们回顾一下，一个数值策划要在这里具体做一些什么样的工作呢？

1、根据迷宫和层数算出地图信息：这是用于随机地图生成的最基本数据。

2、切块算法：尽管在本文里举了一个例子，但是这并不是惟一的例子，我们当然可以用其他数学方法来确定切块的方式和房间连线的方式，总之最后可以获得每个"块"的数据就行了。

03、妙用 Dijkstra 生成"房间"

当我们完成了每一个"块"的数据之后，就可以遍历每个"块"，对每个块进行房间的生成了。首先我们要拿出：

房间的中心点，这是我们用 Dijkstra 算法的"寻路起点"。

房间的尺寸：取宽度、高度中较大的一个，然后将其除以 2 后向下取整，作为一个 Cost 值，赋值给起点。

有了这两个信息之后，我们开始"取周围 8 个格子作为下一格"的规则，作为 Dijkstra 算法的"下一格"规则。和战棋类 SLG 搜索移动范围差不多，而唯一的不同则是，这个单元格的 Cost 消耗量是随机的，而这个随机并不是无脑的随机 1-2，他应该有一个算法，比如越接近起点的，越不容易是 2，这是最基础的规则，如图所示，是这样"寻路"的：

Cost=f (...) 就是这个随机算法，依据是这个房间（"块"）的信息，当然也可以传入更多的需要的信息，这取决于游戏的设计。

之所以要用 Dijkstra 算法去生成房间，基础的原因有 2 个：

其一是房间最终不一定是矩形的，当然如果 cost 都是 1，那么最后是一个正方形的，这是特殊情况，通常我们还是希望房间不是矩形的，所以想需要利用 Cost 的算法配合 Dijkstra 算法产生出"非矩形"的房间，如图所示：

把 cost=0（红色）的格子当做墙壁，就生成了房间。当然我们只要调整一下这个 Cost=f (...) 的函数，就可以发生有趣的变化：

比如 y 方向上更容易抽到高 cost，就可以让地图更接近扁的：

再比如当格子的 y 值大于起点 y 值（下方格子），则 cost = 初始 cost：

可见，只要调整 Cost=f (...)，就能让地图的形状接近设计的预期效果，而这里还会追加一个问题，房间内的阻挡和刷怪点是如何产生的。事实上我们已经有了从中心展开的规则，那么刷怪点和阻挡完全是可以符合：IsPoint = f (x, y, cost) 这样一个数学函数的，即是否这个点刷怪或者阻挡，由参数 x,y 和这个格子的剩余 cost 值来决定的。比如"所有 Cost=3 的格子中抽取随机 3 个作为刷怪点"，这些刷怪点就会接近于中间，这样玩家走进房间，不论是从哪个方向走过来的，都不至于遭遇"被怪贴脸"的情况（当然也并不是所有游戏第一时间都需要刷怪的）。

到此，一个房间的生成就完成了，我们从这个生成过程中得出了：

• 房间的形状：整个房间占了那些格子，其中哪些是阻挡单元格。

• 刷怪点：房间里的刷怪单元格，至于上面刷什么怪，不是房间说了算的，是由楼层信息、难度等算出刷什么怪，这里只是提供给怪物他们的出生位置。

• 在这步，数值策划的核心工作就是：

• 每个格子的 Cost 算法，即 Cost=f (...) 的函数，包括其参数以及计算过程。

• 刷怪点、阻挡的算法，根据每个格子的情况，算出当前格子是阻挡还是刷怪点。

• 只要算法设计得好，就可以用来生成任何玩法的 Roguelike 游戏的地图，甚至用在横版动作游戏的地图生成也不是问题。

04、妙用 Dijkstra 生成"路线"

当房间生成完之后，我们可以用 AStar 来生成 2 个房间之间的连线单元格，这是非常简单的一件事情，但是在此之前，我们还有一个工作。还记得开始的时候说的"最小经过房间数"吗？满足这个需求的方式，是把房间之间的一些连线关系打断，以确保路线能达标。

首先我们要将房间（或者原本的"块"）之间的连线确定，制作成"地图"：

然后我们通过这个地图，得出随机的起点和终点，如果"最小经过房间数 > 0"，则代表起点和终点必须是不同的 2 个格子，假设"最小经过房间数"=3，起点为 3，终点为 6，那么我们就必须打断一些连线：

我们需要打断的是，让起点到终点距离会 < 3 的关键链接。在打断了关键链接之后，我们可以在不关键的位置也打断几根，这个打断的依据依然可以是一个数值策划设计的算法。

总结

到此，一层楼的随机地图就算是产生完了，房间、怪物、阻挡、宝箱等等都可以通过 Dijkstra 算法的妙用来算出，而这一切的关键，在于数值策划对于一些数学函数的设计。

当深入了解一个算法的实际工作原理之后，思考并修改他的用法，从而做到一些"非大众化"的用途，往往在游戏设计中是可以起到奇效的，关键看设计师有没有能力运用好 --"没有低等的法术，只有低等的法师"。

本文来自微信公众号：千猴马的游戏设计之道 （ID：baima21th），作者：猴与花果山