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

对于Roguelike游戏来说，随机地图是非常核心的元素，在很多Diablolike游戏中，随机地图还是非常活跃的我们可能见过很多生成随机地图的算法，包括但不限于GDC，GMTK等知名游戏传播媒体的分享但是大部分随机算法都会要求关卡的大部分内容，包括暗黑破坏神等著名游戏，都预装了一些地图，然后在随机地点随机抽取其中的一小部分地图使用毕竟这样做的好处是地图看起来很美，不会出现死图，刷怪的位置也相对合理

那么，有没有不需要手动预设内容的随机算法呢只需要调整一些参数，就能生成很美的图像，不会产生死图像更何况还能保证生成的刷点在合理的位置今天，我们将深入探讨一种寻路算法——Dijkstra算法只要我们稍微调整一下所使用的技巧，这个用来寻找最短路径的奇妙算法就会变成一个极其强大的随机地图生成算法，而对于精通设计数学函数的数值规划来说，我们只需要几个参数就可以轻松玩转这个Dijkstra随机地图生成方法

1.深度解读Dijkstra算法。

我们通常所知的Dijkstra是一种寻找两点间最短路径的算法这种算法往往和他的两种特殊形式Floyd算法和AStar算法一样出名

Dijkstra算法本身很好理解，就是以地图中的某个点为起点，然后向各个方向搜索每次它进入一个网格，一个成本值被累积然后，对于地图上的每个网格，计算进入这个网格的最短路径，即从起点引出通向这个网格的成本值最低的路线最后遍历完所有网格，得到最短路径

大多数情况下，Dijkstra的开销是非常高的，于是在贪婪的Best—First思想的组合下，AStar寻路应运而生但是Dijkstra并没有因为AStar的出现而退出游戏开发的舞台

在兵棋SLG中，一个角色的移动范围可以通过Dijkstra算法得到毕竟每个角色的机动性都是有限的，地图中的地形也会影响机动性与此同时，敌方角色的邻格机动性消耗也会进一步提高，所以巧妙地使用了Dijkstra算法来寻找机动性足够的点而不是目标点

这里介绍一下最基本的Dijkstra算法，接下来还需要进一步思考一些问题通常我们在使用Dijkstra算法时，检查单元格的规则是包围网格，但如果有些网格是一个传送门入口，你走进去就可以选择N个出口中的一个这个时候应该对寻路算法做哪些改变

如果绿色是起点，红色是终点，通常我们的寻路方法会产生一条黑线路线但是当我们在地图上增加一个传送门入口，走进这个传送门，我们可以选择三个橘色圈传送门出口中的任意一个作为出口，问题就出现了，因为蓝色格子同时代表了另外三个格子所以我们可以发现，其实当我们只使用Dijkstra算法进行基于Tilebased的游戏寻路时，我们自然会认为包围网格是这个算法的一部分，但实际上对于Dijkstra算法来说，如何选择下一个网格是需要设计的一部分

如上图，Dijkstra算法的下一个网格其实就是下一个节点，按照一个规则加入到判断列表中。如果它是一个门户，它应该是这样的:

既然走进B相当于走进B1或者B2或者B3，我们就打断B的不存在的网格，链接B1B2B3这就是Dijkstra算法的核心之一——路径的节点规则

02.随机地图的准备

了解了Dijkstra算法的本质之后，我们就准备熟练地使用它来生成随机地图了但在此之前，我们还需要一些步骤这些随机的地图生成步骤其实并不需要Dijkstra算法

这里需要数值规划设计的第一个内容:地图信息= f .这个函数的初衷是根据地图的难度系数计算出当前地图的一些信息，至少应该包括:

房间数量:我们知道大多数罗格里的地图都需要房间房间越多，玩家的迷宫难度越大所以对于我们的地图生成来说，房间数量也是一个核心数据如果我们不知道房间的数量，我们就不能生成适当难度的随机地图

每个房间的最大和最小尺寸:这个尺寸的宽度和高度可以不一样，但是我们最好认为它们是相等的，这样房间的位置就可以相对统一一些最小尺寸要小于最大尺寸，如果相等会影响一些随机效果

房间之间连接的单元的最小数量:房间仍然需要通过路线连接可以要求路径的最小长度，它应该是一个自然数如果为0，可能会生成两个相邻墙的房间，影响外观当然这也可以在生成后纠正，比如消除一面墙

房间之间连接的单元格的最大数量:这应该是一个大于最小平铺数量的数字，以便有随机的空间。

怪物数量信息:该信息将用于生成怪物的刷新点。

最小通过房间数:我们知道罗格里克地图可能有这样一个需求，就是我到了这一层之后，至少要走过多少个房间才能遇到下一层的入口如果这个值为0，有可能这一层的第一个房间会有楼梯通往楼下，当然，这个数一定不能大于等于房间数，否则不行建议是取房间数的一半

当获得上述地图数据后，我们就可以确定该级别地图水平和垂直方向所需的块数所谓块，就是每个随机房间的范围为了保证地图尽可能接近正方形范围，可以这样做:水平块数=向上取整，垂直块数=向上取整

我们很容易计算出一个块中的单元数:水平单元数=房间中水平单元的最大数量+水平连接中瓷砖的最大数量，垂直网格的数量=房间中垂直网格的最大数量+垂直连接线的最大平铺数量将每个方块的方块数乘以方块数，就可以算出地图中有多少个水平和垂直的单元格

确定小区后，我们要解决的一个问题就是块数gt，房间数的问题，如果等于，没有问题，但是如果大于，我们就先随机取出行，然后在这些行中取出一个块来删除，如图:

我们随机选择了第一行和第三行，并分别移除了一个块所以房间数正好是2+3+2=7然后我们把每一行随机分成块在这个过程中，我们确定每个块的水平和垂直单元的数量该最小单元数量应不小于房间的最小宽度+水平连接单元的最短数量

从上图中我们可以看到，切割后也产生了块之间的连接图，每个块只有一个房间，所以块之间的连接关系也是房间的初步连接关系，这是初步的，因为我们后面会断开一些连接。

确定连接后，我们会在每个块中随机找一个随机点作为这个块中房间的中心点这个中心点的范围至少要满足房间最终能在块中的要求，并尽可能满足最长和最短的链接单元格的要求这里生成了每个块的属性，也就是每个房间的基础数据

房间id:该房间的id

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

链接房间数组:此房间可以连接到的房间的id数组。

至此，我们的准备工作已经完成，接下来就是开始生成房间的重要算法了首先我们来复习一下，一个数值策划在这里应该做哪些工作

1.根据迷宫和层数计算地图信息:这是随机地图生成最基础的数据。

2.切割算法:虽然本文给出了一个例子，但不是唯一的例子我们当然可以用其他数学方法来确定切割方法和房间连接方法简而言之，我们最终可以得到每个块的数据

03.巧用Dijkstra生成房间

当我们完成每个区块的数据后，我们可以遍历每个区块并为每个区块生成房间。首先我们必须想出:

房间的中心点，也就是我们Dijkstra算法的寻路起点。

房间的大小:取宽和高中较大的一个，然后除以2，向下取整作为成本值，将其分配给起点

有了这两条信息，我们就启动了把周围的8个网格作为下一个网格的规则，作为Dijkstra算法的下一个网格规则和战棋的SLG搜索移动范围差不多，唯一不同的是这个单元格的费用消耗是随机的，而且这个随机不是无脑随机1—2他应该有一个算法，比如离起点越近，越不可能是2，这是最基本的规则

Cost=f就是这个随机算法，是基于这个房间的信息当然，更多需要的信息也可以传入，这取决于游戏的设计

使用Dijkstra算法生成房间有两个基本原因:

第一，房间最后不一定是长方形的当然，如果成本都是1，那么最后就是正方形了这是一个特例

以cost=0的网格为墙，生成一个房间。当然，只要我们调整这个成本=f功能，可能会发生有趣的变化:

比如Y方向更容易画出高成本，可以让地图更接近平面的:

例如，当网格的Y值大于起点的Y值时，则成本=初始成本:

可以看出，只要调整Cost=f，地图的形状就可以接近设计的预期效果这里还会有一个附加问题，房间里的堵点和刷点是怎么产生的事实上，我们已经有了从中心向外扩散的规则，所以刷分和分块完全可以符合数学函数:IsPoint = f ，即这个点是刷还是分块是由参数x，y和这个网格的剩余成本值决定的比如随机选取所有成本=3的方块作为刷怪点，这些刷怪点会靠近中间，这样玩家走进房间时，无论他来自哪个方向，都不会遇到被刷脸的情况

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

房间的形状:整个房间占据了那些方块，这些方块是阻挡细胞。

怪点:房间里的怪格被刷至于上面刷了什么奇怪的东西，不是房间决定的，是楼层信息，难度等要搞清楚刷什么奇怪的东西在这里，它只提供给怪物关于他们的出生地点

在这一步中，数值规划的核心工作是:

每个网格的代价算法，也就是Cost=f的函数，包括它的参数和计算过程。

刷怪点和遮挡的算法，根据每个格子的情况，计算当前格子是遮挡还是刷怪点。

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

04.巧用Dijkstra生成路线

当房间生成后，我们可以使用AStar来生成两个房间之间的连通单元这是一件很简单的事情，但在此之前，我们还有工作还记得开头的最小通过房间数吗满足这种需求的方法是中断房间之间的一些连接，以保证路线能够达标

首先，我们要确定房间之间的联系，并把它做成地图:

然后我们通过这个地图得到随机的起点和终点，如果最小通过房间数gt，0，意味着起点和终点必须是两个不同的网格。假设最小通过房间数=3，起点为3，终点为6，那么我们要中断一些连接:

我们需要中断的是，起点到终点的距离将为lt，3的关键环节在打破关键环节后，还可以在非关键位置打破几个这个突破口的基础仍然可以是一个数值规划设计的算法

摘要

至此，一楼的随机地图就算完成了，房间，怪物，关卡，宝箱等可以通过Dijkstra算法的妙用来计算，而这一切的关键在于数值规划对一些数学函数的设计

在深刻理解了一个算法的实际工作原理后，去思考和修改它的用法从而达到一些非大众化的用途，往往能在游戏设计中起到奇效关键看设计者有没有能力用好——没有劣等的法术，只有劣等的法师

声明：本网转发此文章，旨在为读者提供更多信息资讯，所涉内容不构成投资、消费建议。文章事实如有疑问，请与有关方核实，文章观点非本网观点，仅供读者参考。