随机舆图天生算法，是Roguelike游戏的主要课题
那么有没有一种不须要手动预设内容的随机算法，只须要调度一些参数，它就可以天生出看起来都雅，也不会产生去世图，还能确保天生的刷怪点位置合理的方法呢？本日我们就将深入地探索一下一个寻路算法——Dijkstra算法，只要轻微调度一下利用的“手腕”，这个奇妙的、被用于探求最短路径算法就会成为一个极其强大的随机舆图天生算法，并且对精通于设计数学函数的数值策划来说，可以轻松地用几个参数就玩转这个“Dijkstra随机舆图天生法”。
01 深度解读Dijkstra算法
我们常日理解的Dijkstra是一个探求2点之间最短路径的算法，这个算法每每与他的两个分外形态Floyd算法和AStar算法齐名。
Dijkstra算法本身非常好理解，即在舆图中的某个点作为出发点，然后向四面八方展开探求，每进入一个格子都累加一个Cost值，然后对付舆图上每一个格子都算出走进这个格子的最短路径，即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数组。到此，我们的准备事情也就完成了，接下来就要开始天生房间的主要算法了。首先我们回顾一下，一个数值策划要在这里详细做一些什么样的事情呢？
根据迷宫和层数算出舆图信息：这是用于随机舆图天生的最基本数据。切块算法：只管在本文里举了一个例子，但是这并不是惟一的例子，我们当然可以用其他数学方法来确定切块的办法和房间连线的办法，总之末了可以得到每个“块”的数据就行了。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算法的妙用来算出，而这统统的关键，在于数值策划对付一些数学函数的设计。
当深入理解一个算法的实际事情事理之后，思考并修正他的用法，从而做到一些“非大众化”的用场，每每在游戏设计中是可以起到奇效的，关键看设计师有没有能力利用好——“没有低等的法术，只有低等的法师”。