六、寻找最短路径
我们需要解决寻路的最后一个主要领域:在迷宫中寻找最短的路径。事实证明，这不仅仅是一个有趣的题外话，而是你需要知道的最重要的游戏设计技巧之一。
到目前为止，我们在书中提到的所有玩家控制系统都涉及到用键盘或鼠标在屏幕上移动玩家。但是游戏通常采用点击控制系统。将鼠标指向地图上的某个地方，然后单击。这个角色会走到那里，并神奇地找到到达目的地的最短路径，同时巧妙地避开任何障碍。图形冒险游戏使用这种控制系统，几乎所有的策略和回合制游戏都是如此。它是如何工作的？这正是你将在本章中发现的！
沿着最短路径移动角色实际上是一个由两部分组成的过程:
-
寻找最短路径:这包括测试起点和终点之间所有最可能的瓷砖。你需要弄清楚哪些瓷砖能让你更快到达目的地，哪些包含要避开的障碍物。在这个测试的最后，你会得到一系列告诉你最短路径的方块。
-
跟随路径中的瓷砖:你最终得到的瓷砖阵列就像是游戏角色可以跟随的面包屑。告诉角色跟随这些面包屑从它的开始位置到目的地。
如果第一步看起来很复杂，那就是复杂！但是好消息是已经找到了很好的解决方案。这意味着你不需要担心想出自己的解决方案——你可以选择一个现成的，并在你的游戏中实现它。
您可以使用许多不同的寻路算法，包括最佳优先、广度优先和 Dijkstra 算法。所有人都会合理地解决这个问题。但最好的一般被认为是 A (A 星)。A算法具有最佳的整体性能，并且非常灵活。如果你只需要学习一种寻路算法，A*就是了。
A*是由 Peter Hart、Nils Nilsson 和 Bertram Raphael 在 20 世纪 60 年代开发的。这是对 Dijkstra 算法的修改，这是一种寻路算法，由先驱计算机科学家 Edsger Dijkstra 在 20 世纪 50 年代提出。
在我向你展示如何在游戏中使用 A*之前，我们先来详细了解一下算法是如何工作的。
了解 A*
我们可以为我们的进化祖先感到骄傲。由于良好的寻路能力，他们都成功地避开了更大的原生动物，避开了咬牙切齿的恐龙牙齿，并避免了成为斯特克方丹洞穴底部的化石残骸。寻路是一项技能，它对于像树蛙一样在亚马逊生存就像能够在早上赶上公共汽车一样重要。这是一种生存技能，可以让你自动计算出从 A 点到 B 点的最短路径，而不会被吃掉、饿死或上班迟到。看一眼图 6-1 ，你马上就能看到 A 点和 b 点之间的最短路径。寻路是我们 DNA 的一部分。
图 6-1。A 点和 B 点之间的最短路径是什么？这对我们人类来说是显而易见的，但你如何向计算机解释呢？
另一方面，电脑就像养尊处优、屡获殊荣的波斯猫。他们整天无所事事，花太多时间在网络上，睡得很多。他们没有像我们一样，在无数个千年的原始汤里磨砺出自己的技能。我们需要用最直截了当的声音告诉他们，“这条路很好！”或者“这条路不好走！”用一根粗糙的棍子威胁他们。
但是什么是“好的道路”呢？在寻找最短路径的情况下，它是让你更快到达目的地的路径。问题是电脑看不到大局。他们一次只能看到一小步。所以告诉计算机如何找到最短路径的策略是这样的:
-
将整个路径分成许多小步骤。
-
对于每一步，想清楚下一步该做什么。
-
采取下一步，重复这个过程，直到你到达你应该到达的地方。
但是计算机必须仍然能够区分好的路径和坏的路径。让我们看看如何帮助它解决这个问题。
计算成本
解开这个谜:
每天早上都会有一份报纸送到你家门口。最便宜的取货方式是什么？
A.打开前门。
B.走出后门，跳过你花园的栅栏，跑进小巷，叫一辆出租车，绕着街区骑到你的前门？
选项 A 是免费的，但选项 B 花费你大约 4.75 美元的出租车费。这意味着选项 B 更贵。
“昂贵”是 A算法用来描述在两点之间移动需要多少工作的术语。A计算出到达目的地的最便宜的路线。它通过为你在这条路上可能采取的每一步分配一个成本来做到这一点。成本最低的步骤是更好的步骤。A*通过寻找最低成本的移动和最便宜的路径来工作。
A有自己的一套术语和词汇。成本和费用是其中的两个术语，正如您将看到的，它们是描述其一些核心概念的一种便捷方式。我将在前面介绍其他几个具体的 A术语。请特别留意即将出现的术语“节点”和“启发式”!
图 6-2 解释了我所说的成本是什么意思。想象你是一个培养皿中的细菌，自由漂浮，在 a 点关注自己的事情。突然，一个巨大、饥饿的单细胞变形虫的影子笼罩着你，唯一的目标是包容你的细胞物质。你知道如果你不马上躲起来，你会有麻烦的。你只能躲在两个地方:B 点或 c 点。你有一瞬间的时间来决定哪一个是最近的。
图 6-2。B 和 C 哪个最接近 A？
在图 6-2 中的例子中，旅行到 B 点比旅行到 C 点需要大约三分之一的时间，事实上，从 a 点旅行到 B 点需要的时间正好是 1.41 倍，这意味着 C 点是你需要游泳来逃离那个阿米巴原虫的地方。值 1.41 是对角旅行的成本。
在基于矩形网格的游戏世界中，只有两种运动选择，并且每种选择都有代价:
-
对角:成本 14。
-
直跨:横着走或者竖着走，成本 10。
这些成本是多少并不重要，只要它们成比例地代表了向这些方向移动所需的时间。所以，14 比 10 和 1.4 比 1 的比例是一样的，我们不需要担心小数。如果您愿意，您当然可以在自己的代码中使用 1.4 和 1。图 6-3 显示了单元间移动的成本。
图 6-3。穿越细胞的成本
现在我们有办法向计算机描述什么是好的路径:成本最低的路径。
图 6-4 显示了从 A 到 b 的两条可能路径，你不仅可以清楚地看到路径 1 是最短的，而且恰好是最便宜的。
图 6-4。最短的路径也是最便宜的
前面我提到过，计算机在任何给定时间只能看到路径中的一步。你可以从图 6-3 中看到，每一步都是到达 b 点的代价最小的一步，但这只有在你已经知道路径的结果后才是显而易见的。计算机在开始构建路径之前并不知道这一点。它如何直接从 A 点知道下一步该做什么？
寻找第二步
在 A的术语中，路径中的每一步都称为一个节点。就我们而言，节点只是二维数组或网格中的单元。但是，从现在开始，我将开始称它们为节点，这样你们就可以习惯这个术语了。你会发现它在其他文本的寻路讨论中被广泛使用。A使用术语节点是因为除了矩形网格之外，没有理由不能用其他方式划分空间，例如使用六边形或圆形。但是就我们的目的而言，当你听到我谈论节点时，只要知道我指的是网格单元。
A*从 A 点开始搜索最短路径，A 点是父节点。父节点是路径上明确的、确定的步骤。显然，我们知道 A 点将是第一步，所以它自动成为第一个父节点。
如果我们知道第一步是什么，我们如何找到第二步？A*必须检查父节点周围的所有八个单元，以发现哪一个是下一个最可能的候选。图 6-5 显示了作为父节点的点 A，以及它需要检查的所有周围节点。(如果这些节点中的任何一个碰巧是墙或不可通过的物体，它会忽略它们。)
图 6-5。检查父节点周围的所有节点，看哪一个可能是路径中下一个最有可能的步骤
周围的每个单元格都将当前父节点声明为其父节点。在 A*算法中执行此操作的代码如下所示:
surroundingNode.parent = currentParent;
这一点很重要，因为这意味着 A*可以通过跟踪父节点来追踪到目的地的最佳路径。现在不要太担心这个，因为您将在前面的页面中看到它是如何工作的。请记住，每个节点都有一个父属性，用于跟踪路径中它所链接到的节点。
A然后需要找出从父节点到周围子节点的开销。原来这恰好是一个重要的数字，所以 A将这个代价称为 G，图 6-6 显示了所有周围节点的 G 代价。
图 6-6。每个周围的节点都有一个成本，在 A*的术语中称为 G
A*然后计算出哪个周围节点离目的地 B 点更近。它计算从 B 点到每个周围节点的旅行成本。(挡在路上的墙被视为暂时不存在，但正如您将看到的，这将通过以后的测试得到补偿。)图 6-7 显示了从第一个周围节点到 b 点的路径，可以看到它计算出从那个节点到测试路径的开销为 54。
图 6-7。计算从每个周围节点到 B 点的每条路径的开销
这种距离测试被称为启发式。启发式简单地说就是通过尝试和错误找出一些东西。(它源自希腊语作品 heuriskein ，意为寻找。)然而，启发式不是随机试错法。这是在一套逻辑规则中的反复试验，很可能会产生我们正在寻找的答案。A不知道周围的子节点中哪一个会以开销最小的路径结束，所以它只尝试所有八个。每条启发式路径的成本恰好也很重要，所以 A将这个成本称为 H 。
实际上有三种常用的计算启发式路径的方法:曼哈顿、欧几里德和对角线。我们将在本章后面的“理解试探法”一节中详细讨论每一个。现在，只要知道这些是计算从周围的测试节点到目的地点的距离的具体方法。
A*计算出每个周围子节点的 H 成本。如果将 H 和 G 成本结合起来，就会得出第三个成本，即最终成本，称为 F。图 6-8 显示了每个节点的所有 G、H 和 F 成本。
图 6-8。通过将 G 和 H 成本相加，找出每个节点的最终 F 成本
获胜者是 F 成本最低的节点。你能看见吗？它是直接位于父节点右侧的一个，如图 6-9 所示。
图 6-9。具有最低 F 成本的节点成为路径中最有可能的下一步
该节点现在成为潜在的新父节点。A还不确定这是否是最好的第二步，但据它所知，这是一个继续检查的好地方。(事实上，这不是最好的第二步，但 A很快就会发现这一点，正如您将看到的。)
从图 6-9 中可以看到，每个父节点都代表了通往 b 点的路径中的一个潜在步骤。我使用了潜在步骤这个词，因为 A在做更多的检查之前并不确定任何给定的父节点是否是最佳步骤。你已经可以在图 6-9 中看到一个问题。新的父节点是而不是*最好的下一步。最好从 a 点沿对角线向上移动。图 6-10 对此进行了说明。
图 6-10。显而易见的首选并不总是最好的。A*如何计算出从起点斜向上移动更好？
幸运的是，A有一个系统可以交叉检查节点，剔除像这样的低效节点。A通过保持两个列表来跟踪用于路由的可能的最佳父节点:
-
封闭列表:这是一个不需要检查的节点列表。每当找到一个新的父节点，它就会被添加到这个列表中。
-
开放列表:这是围绕每个父节点的所有节点的列表。它们是需要检查的节点。
当一个新的潜在父节点检查所有周围的节点时，它在开放列表上查看每个节点的先前 G 成本。图 6-11 显示了它正上方的节点之前的 G 成本是 14。
图 6-11。旧的 G 成本是 14。它的新成本会多还是少？
为了找到它的新 G 成本，A*采用父节点的当前 G 值，再加上 10，这是向上移动一个节点的成本。这使得新的 G 成本达到 20 英镑。图 6-12 对此进行了说明。
图 6-12。将父节点的 G 成本(10)与向上移动一个节点的成本(10)相加，以找到新的 G 成本(20)
如果发现新的开销更低，A*会将节点的父节点更改为当前父节点:
if (newG < oldG) {
surroundingNode.parent = currentParent;
} else {
don't change the surrounding node's parent
}
但是如果新的 G 成本更高，节点的父节点不会改变。这个例子就是这种情况。它将保留在第一步中分配给它的父节点，即开始节点。我们正在检查的当前父节点被排除在外。
这非常重要，因为 A*通过它们的父节点将节点链接在一起，就像一条链一样，从而创建了路径。
A*对所有其他周围的节点运行相同的检查，并根据它们需要运行新的父节点的情况来计算它们新的 G 开销，如图 6-13 所示。
图 6-13。通过路由经过当前父节点的路径，找出其他节点的 G 开销是否更小。他们不是
从图 6-13 可以看出，通过当前父节点，所有节点的 G 代价会更高。这意味着它们都不会将其父代更改为当前父代。现任家长是吐司！它没有孩子，所以它肯定不会是最短路径的一部分。
但是 A*仍然需要确定下一步测试哪个节点。它会忽略墙节点和上一个父节点。它选择 F 代价最低的下一个节点作为新的父节点，如图 6-14 所示。
图 6-14。具有最低 F 成本的周围节点成为新的父节点
但是，如果一些节点具有相同的成本，会发生什么呢？从图 6-13 可以看到，父节点正上方和正下方的节点并列第一，都是同样的低分 54。在这种情况下，A会选择循环中最先运行该检查的节点。如果恰好是错误的，这将在以后通过进一步的检查来纠正。但纯属偶然，这一次得分最低的第一个节点也恰好是更好的选择。它被选为新的父节点，A继续检查。
也很可能会有不止一条可能的最短路径。A*构建的是由它如何选择成本固定的节点决定的。
我们目前已经测试了两个节点，并选择了第三个，如图 6-15 所示。
图 6-15。三个节点是路径上的步骤的候选，但是哪一个将进行最后的调试？
但是这些节点中只有两个是路径的一部分。我们怎么知道？因为右上方的节点已经将开始节点指定为其父节点。这是将两个节点链接在一起的关系，如图 6-16 所示。它构成了道路的前两步。
图 6-16。开始节点是右上节点的父节点。这种关系将节点链接在一起
通过父节点链接节点
A*然后继续遵循相同的逻辑，直到它到达目的节点，点 b。在一个非常大的游戏世界中，这可能涉及检查数百个节点。
当 A*最终构建路径时，它会跟踪从父节点到父节点的路径，以将起点和终点链接在一起。如图 6-17 所示。
图 6-17。最终路径中的每个节点都有一个对其父节点的引用
当 A到达目的地 B 点时，它停止检查。A然后只需要从 B 点向后工作，跟随父节点，来构造路径。A*算法产生一个数组，告诉你需要走过的每个节点，以找到从 A 点到 b 点的最短路线。
现在您已经理解了这个理论，让我们来看看实际的 JavaScript 代码。
代码中的 A*
现在应该很明显，节点在 A*宇宙中是非常重要的东西。每个节点需要存储相当多的信息:
-
它的位置(它在网格上的行和列)。
-
它的 G、H 和 F 成本。
-
它的父节点。
因此，创建一个节点对象来存储这些信息是有意义的。
创建节点图
处理节点的第一步是创建一个叫做节点图的东西。节点地图是一个二维数组，与游戏的迷宫地图完全匹配。但是，节点图的每个单元都包含一个节点对象。这些节点对象将存储我们需要的所有重要的节点属性和值。
这里有一个名为 nodes 的简单函数，它为地图数组中的每个单元格返回一个 node 对象数组。
let nodes = (mapArray, mapWidthInTiles) => {
return mapArray.map((cell, index) => {
**//Figure out the row and column of this cell**
let column = index % mapWidthInTiles;
let row = Math.floor(index / mapWidthInTiles);
**//The node object**
return node = {
f: 0,
g: 0,
h: 0,
parent: null,
column: column,
row: row,
index: index
};
});
};
每个节点对象都包括成本属性、对其父节点的引用以及行、列和索引信息，这些信息将使我们能够将节点与其在 map 数组中的位置相匹配。您将看到如何在我们接下来要看的 shortestPath 函数的上下文中使用它。
最短路径函数
我们 A*代码的核心是最短路径函数。它返回一个包含从 A 点到 b 点的最短路径的数组。下面是一个如何调用它的示例，包括要使用的参数。
let path = shortestPath(
getIndex(alien.x, alien.y, 64, 64, 13), **//The start map index**
getIndex(g.pointer.x, g.pointer.y, 64, 64, 13)), **//The destination index**
wallMapArray, **//The map array**
13, **//Map width, in tiles**
[2, 3], **//Obstacle gid array**
"manhattan" **//Heuristic to use**
);
如你所见，这些参数与我们之前看到的信息相匹配。我们还没有讨论的一件事是使用什么样的启发式方法。我将在“理解启发式”一节中解释启发式选项及其工作原理。
下面是整个 shortestPath 函数。除了一些额外的检查，它需要确保所有的数据都是有效的，正如我在描述 A*算法如何工作时解释的那样，它正在进行路径查找。通读所有注释，并尝试将代码与之前的描述匹配。
function shortestPath(
startIndex,
destinationIndex,
mapArray,
mapWidthInTiles,
obstacleGids = [],
heuristic = "manhattan"
) {
**//The `nodes` function creates the array of node objects**
let nodes = (mapArray, mapWidthInTiles) => {
return mapArray.map((cell, index) => {
**//Figure out the row and column of this cell**
let column = index % mapWidthInTiles;
let row = Math.floor(index / mapWidthInTiles);
**//The node object**
return node = {
f: 0,
g: 0,
h: 0,
parent: null,
column: column,
row: row,
index: index
};
});
};
**//Initialize the shortestPath array**
let shortestPath = [];
**//Initialize the node map**
let nodeMap = nodes(mapArray, mapWidthInTiles);
**//Initialize the closed and open list arrays**
let closedList = [];
let openList = [];
**//Declare the "costs" of travelling in straight or diagonal lines**
let straightCost = 10;
let diagonalCost = 14;
**//Get the start node**
let startNode = nodeMap[startIndex];
**//Get the current center node. The first one will**
**//match the path's start position**
let centerNode = startNode;
**//Push the `centerNode` into the `openList`, because**
**//it's the first node that we're going to check**
openList.push(centerNode)
**//Get the current destination node. The first one will**
**//match the path's end position**
let destinationNode = nodeMap[destinationIndex];
**//All the nodes that are surrounding the current map index number**
let surroundingNodes = (index, mapArray, mapWidthInTiles) => {
**//Find out what all the surrounding nodes are (including those that**
**//might be beyond the borders of the map – we’ll filter these out ahead**
**//in the `validSurroundingNodes` function)**
let allSurroundingNodes = [
nodeMap[index - mapWidthInTiles - 1],
nodeMap[index - mapWidthInTiles],
nodeMap[index - mapWidthInTiles + 1],
nodeMap[index - 1],
nodeMap[index + 1],
nodeMap[index + mapWidthInTiles - 1],
nodeMap[index + mapWidthInTiles],
nodeMap[index + mapWidthInTiles + 1]
];
**//Optionally exlude the diagonal nodes, which is often perferable**
**//for 2D maze games**
let crossSurroundingNodes = [
nodeMap[index - mapWidthInTiles],
nodeMap[index - 1],
nodeMap[index + 1],
nodeMap[index + mapWidthInTiles],
];
**//Find the valid sourrounding nodes, which are ones inside**
**//the map border that don't incldue obstacles. Optionally change `allSurroundingNodes`**
**//to `crossSurroundingNodes` to prevent the path from choosing diagonal routes**
**//between nodes**
let validSurroundingNodes = allSurroundingNodes.filter(node => {
**//The node will be beyond the top and bottom edges of the**
**//map if it is `undefined`**
let nodeIsWithinTopAndBottomBounds = node !== undefined;
**//Only return nodes that are within the top and bottom map bounds**
if (nodeIsWithinTopAndBottomBounds) {
**//Some Boolean values that tell us whether the current map index is on**
**//the left or right border of the map, and whether any of the nodes**
**//surrounding that index extend beyond the left and right borders**
let indexIsOnLeftBorder = index % mapWidthInTiles === 0
let indexIsOnRightBorder = (index + 1) % mapWidthInTiles === 0
let nodeIsBeyondLeftBorder
= node.column % (mapWidthInTiles - 1) === 0
&& node.column !== 0;
let nodeIsBeyondRightBorder = node.column % mapWidthInTiles === 0
**//Find out whether of not the node contains an obstacle by looping**
**//through the obstacle gids and and returning `true` if it**
**//finds any at this node's location**
let nodeContainsAnObstacle = obstacleGids.some(obstacle => {
return mapArray[node.index] === obstacle;
});
**//If the index is on the left border and any nodes surrounding it are beyond the**
**//left border, don't return that node**
if (indexIsOnLeftBorder) {
return !nodeIsBeyondLeftBorder;
}
**//If the index is on the right border and any nodes surrounding it are beyond the**
**//right border, don't return that node**
else if (indexIsOnRightBorder) {
return !nodeIsBeyondRightBorder;
}
**//Return `false` if the node contains an obstacle**
else if (nodeContainsAnObstacle) {
return false;
}
**//If this passes the checks above, it means the index must be**
**//inside the area defined by the left and right borders.**
**//So, return the node**
else {
return true;
}
}
});
**//Return the array of `validSurroundingNodes`**
return validSurroundingNodes;
};
**//Heuristic methods**
**//1\. Manhattan**
let manhattan = (testNode, destinationNode) => {
let h
= Math.abs(testNode.row - destinationNode.row)
* straightCost + Math.abs(testNode.column - destinationNode.column)
* straightCost;
return h;
};
**//2\. Euclidean**
let euclidean = (testNode, destinationNode) => {
let vx = destinationNode.column - testNode.column,
vy = destinationNode.row - testNode.row,
h = Math.floor(Math.sqrt(vx * vx + vy * vy) * straightCost);
return h;
};
**//3\. Diagonal**
let diagonal = (testNode, destinationNode) => {
let vx = Math.abs(destinationNode.column - testNode.column),
vy = Math.abs(destinationNode.row - testNode.row),
h = 0;
if (vx > vy) {
h = Math.floor(diagonalCost * vy + straightCost * (vx - vy));
} else {
h = Math.floor(diagonalCost * vx + straightCost * (vy - vx));
}
return h;
};
**//Loop through all the nodes until the current `centerNode` matches the**
**//`destinationNode`. When they're the same we know we've reached the**
**//end of the path**
while (centerNode !== destinationNode) {
**//Find all the nodes surrounding the current `centerNode`**
let surroundingTestNodes = surroundingNodes(centerNode.index, mapArray, mapWidthInTiles);
**//Loop through all the `surroundingTestNodes` using a classic `for` loop**
**//(A `for` loop gives us a marginal performance boost. A* is extremely performance**
**//hungery, so even a small performance boost with each loop iteration can**
**//amount to a significant boost overall)**
for (let i = 0; i < surroundingTestNodes.length; i++) {
**//Get a reference to the current test node**
let testNode = surroundingTestNodes[i];
**//Find out whether the node is on a straight axis or**
**//a diagonal axis, and assign the appropriate cost**
**//A. Declare the cost variable**
let cost = 0;
**//B. Do they occupy the same row or column?**
if (centerNode.row === testNode.row || centerNode.column === testNode.column) {
**//If they do, assign a cost of "10"**
cost = straightCost;
} else {
**//Otherwise, assign a cost of "14"**
cost = diagonalCost;
}
**//C. Calculate the costs (g, h and f)**
**//The node's current cost**
let g = centerNode.g + cost;
**//The cost of travelling from this node to the**
**//destination node (the heuristic)**
let h;
switch (heuristic) {
case "manhattan":
h = manhattan(testNode, destinationNode);
break;
case "euclidean":
h = euclidean(testNode, destinationNode);
break;
case "diagonal":
h = diagonal(testNode, destinationNode);
break;
default:
throw new Error("Oops! It looks like you misspelled the name of the heuristic");
}
**//The final cost**
let f = g + h;
**//Find out if the testNode is in either**
**//the openList or closedList array**
let isOnOpenList = openList.some(node => testNode === node);
let isOnClosedList = closedList.some(node => testNode === node);
**//If it's on either of these lists, we can check**
**//whether this route is a lower-cost alternative**
**//to the previous cost calculation. The new G cost**
**//will make the difference to the final F cost**
if (isOnOpenList || isOnClosedList) {
if (testNode.f > f) {
testNode.f = f;
testNode.g = g;
testNode.h = h;
**//Only change the parent if the new cost is lower**
testNode.parent = centerNode;
}
}
**//Otherwise, add the testNode to the open list**
else {
testNode.f = f;
testNode.g = g;
testNode.h = h;
testNode.parent = centerNode;
openList.push(testNode);
}
**//The `for` loop ends here**
}
**//Push the current centerNode into the closed list**
closedList.push(centerNode);
**//Quit the loop if there's nothing on the open list.**
**//This means that there is no path to the destination or the**
**//destination is invalid, like a wall tile**
if (openList.length === 0) {
return shortestPath;
}
**//Sort the open list according to final cost**
openList = openList.sort((a, b) => a.f - b.f);
**//Set the node with the lowest final cost as the new centerNode**
centerNode = openList.shift();
**//The `while` loop ends here**
}
**//Now that we have all the candidates, let's find the shortest path!**
if (openList.length !== 0) {
**//Start with the destination node**
let testNode = destinationNode;
shortestPath.push(testNode);
**//Work backwards through the node parents**
**//until the start node is found**
while (testNode !== startNode) {
**//Step through the parents of each node,**
**//starting with the destination node and ending with the start node**
testNode = testNode.parent;
**//Add the node to the beginning of the array**
shortestPath.unshift(testNode);
**//...and then loop again to the next node's parent till you**
**//reach the end of the path**
}
}
**//Return an array of nodes that link together to form**
**//the shortest path**
return shortestPath;
}
使用最短路径函数
在本章的源文件中，你会找到一个名为 shortestPath.html 的文件夹。运行程序，你会看到一个外星角色坐在一个简单的迷宫环境中。用鼠标点击任意位置，程序会画出从外星人所在位置到鼠标所在位置的最短路径，如图 6-18 。
图 6-18。单击任意位置绘制最短路径
这个程序的工作原理是计算外星人精灵和鼠标位置之间的最短路径。如您所知，shortestPath 函数返回一个节点数组。每个节点都有一个行和列属性，我们可以使用该信息在屏幕上为数组中的每个节点显示一个黑色的方形精灵。
下面是来自程序设置函数的相关代码。一个名为 currentPathSprites 的数组中填充了黑色的方形 Sprites，每次释放鼠标指针时，这些 sprites 都会匹配最短路径的节点。
**//An array to store the sprites that will be used to display**
**//the shortest path**
currentPathSprites = [];
**//The mouse pointer's `release` function runs the code that**
**//calculates the shortest path and draws that sprites that**
**//represent it**
g.pointer.release = () => {
**//calculate the shortest path**
let path = shortestPath(
getIndex(alien.x, alien.y, 64, 64, 13), **//Start map index**
getIndex(g.pointer.x, g.pointer.y, 64, 64, 13), **//End index**
wallMapArray, **//Map array**
13, **//Map width**
[2, 3], **//Obstacle gids**
"manhattan" **//Heuristic**
);
**//Use Hexi's `remove` method to remove any possible**
**//sprites in the `currentPathSprites` array**
g.remove(currentPathSprites);
**//Display the shortest path**
path.forEach(node => {
**//Figure out the x and y location of each square in the path by**
**//multiplying the node's `column` and `row` by the height, in**
**//pixels, of each square: 64**
let x = node.column * 64,
y = node.row * 64;
**//Create the square sprite and set it to the x and y location**
**//we calculated above**
let square = g.rectangle(64, 64, "black");
square.x = x;
square.y = y;
**//Push the sprites into the `currentPath` array,**
**//so that we can easily remove them the next time**
**//the mouse is clicked**
currentPathSprites.push(square);
});
};
为了完整起见，您会注意到上面的代码使用了一个方便的函数 remove，它内置在渲染引擎中。它的工作是从渲染器中移除单个精灵或精灵数组中的任何精灵。下面是完成这项工作的 remove 函数，以防您需要在自己的程序中做类似的事情:
function remove(...sprites) {
**//Remove sprites that's aren't in an array**
if (!(sprites[0] instanceof Array)) {
if (sprites.length > 1) {
sprites.forEach(sprite => {
sprite.parent.removeChild(sprite);
});
} else {
sprites[0].parent.removeChild(sprites[0]);
}
}
**//Remove sprites in an array of sprites**
else {
let spritesArray = sprites[0];
if (spritesArray.length > 0) {
for (let i = spritesArray.length - 1; i >= 0; i--) {
let sprite = spritesArray[i];
sprite.parent.removeChild(sprite);
spritesArray.splice(spritesArray.indexOf(sprite), 1);
}
}
}
}
可以看到，只要有了 shortestPath 数组，就有很多方法可以使用它。在前面的例子中，我将向您展示如何使用它来让游戏角色走过迷宫。但首先，让我们来看一个我到目前为止一直在策略上回避的话题:启发式。
理解启发式
到达目的地的最短路径通常不止一条，如图 6-19 所示。
图 6-19。三条路径长度相同，但它们选择的路线不同
没有哪条路径比另一条路径更好或更差，它们都具有相同的成本。但每个都有独特的风格。这种风格依赖于 A*用来计算路径的试探法。
试探法是一种迷你算法，它的工作是根据一个简单的公式计算出距离。三种著名的试探法经常与 A*一起使用:曼哈顿法、欧几里德法和对角线法。图 6-20 显示了最短路径函数中每个启发式算法产生的不同路径。你更喜欢哪个？
图 6-20。不同的试探法产生不同的路径
shortestPath 函数根据提供给它的最后一个参数选择要使用的启发式算法。
let path = shortestPath(
getIndex(alien.x, alien.y, 64, 64, 13),
getIndex(g.pointer.x, g.pointer.y, 64, 64, 13),
wallMapArray,
13,
[2, 3],
**"manhattan"**
);
while 循环中的 switch 语句通过将工作委托给指定的启发式方法来查找 H 的值。
let h;
switch (heuristic) {
case "manhattan":
h = manhattan(testNode, destinationNode);
break;
case "euclidean":
h = euclidean(testNode, destinationNode);
break;
case "diagonal":
h = diagonal(testNode, destinationNode);
break;
default:
throw new Error("Oops! It looks like you misspelled the name of the heuristic");
}
每种启发式方法以不同的方式计算起点和终点之间的距离。曼哈顿方法是最简单的。它只是将行和列相加，然后将总和乘以成本。它忽略任何可能的对角线捷径。
let manhattan = (testNode, destinationNode) => {
let h
= Math.abs(testNode.row - destinationNode.row)
* straightCost + Math.abs(testNode.column - destinationNode.column)
* straightCost;
return h;
};
它之所以被称为曼哈顿，是因为如果你走在纽约市(曼哈顿岛)的街道上，你将无法通过任何一个街区走对角线的捷径。
忽略可能的对角路线使得曼哈顿启发式算法处理起来更快。这一点很重要，因为 A*是一个极度消耗 CPU 的算法。如果你需要在每一帧上为很多游戏角色做寻路，曼哈顿会为你节省一些性能影响。但是，因为它不考虑对角线路由，所以它可能不总是保证绝对最短路径。
欧几里得方法使用勾股定理来计算距离。
let euclidean = (testNode, destinationNode) => {
let vx = destinationNode.column - testNode.column,
vy = destinationNode.row - testNode.row,
h = Math.floor(Math.sqrt(vx * vx + vy * vy) * straightCost);
return h;
};
欧几里得方法确实考虑到了对角线，所以它产生了看起来非常自然的路径。但是，由于饥饿的 Math.sqrt 方法，它的处理速度比曼哈顿方法稍慢。
对角线法补偿了直线穿过或对角移动的成本，因此最终得到非常准确的成本估计。这意味着 A*可能需要做更少的搜索并产生更快的结果，它肯定会产生最短的可能路径。
let diagonal = (testNode, destinationNode) => {
let vx = Math.abs(destinationNode.column - testNode.column),
vy = Math.abs(destinationNode.row - testNode.row),
h = 0;
if (vx > vy) {
h = Math.floor(diagonalCost * vy + straightCost * (vx - vy));
} else {
h = Math.floor(diagonalCost * vx + straightCost * (vy - vx));
}
return h;
};
没有一种正确的启发式方法可以使用。你只需要决定哪种路径对你正在制作的游戏来说是最自然的。
圆角
我们当前的 A*算法有一个潜在的问题:它通过在单元格之间选择对角线捷径来计算最短路径。这是准确的，但它给迷宫游戏带来了一个问题。在大多数迷宫游戏中，你会希望你的角色沿着墙的边缘行走，所以沿着对角线抄近路看起来会很奇怪。图 6-21 说明了这种困境。
图 6-21。迷宫游戏路径通常不应该在拐角处对角切割
有一个简单的解决方案可以防止路径在拐角处走对角线捷径:不要检查任何与当前中心测试节点对角线相邻的节点。在我们的示例 A*实现中的代码的 current surroundingNodes 函数中，测试了当前中心节点周围的所有八个节点:
let al**lSurroundingNodes** = [
nodeMap[index - mapWidthInTiles - 1],
nodeMap[index - mapWidthInTiles],
nodeMap[index - mapWidthInTiles + 1],
nodeMap[index - 1],
nodeMap[index + 1],
nodeMap[index + mapWidthInTiles - 1],
nodeMap[index + mapWidthInTiles],
nodeMap[index + mapWidthInTiles + 1]
];
let validSurroundingNodes = **allSurroundingNodes**.filter(node => {/*...*/};
为了防止出现对角线，只需测试中心节点正上方、正下方以及正左右的节点:
let **crossSurroundingNodes** = [
nodeMap[index - mapWidthInTiles],
nodeMap[index - 1],
nodeMap[index + 1],
nodeMap[index + mapWidthInTiles],
];
let validSurroundingNodes = **crossSurroundingNodes**.filter(node => {/*...*/};
这就是全部了！
走在小路上
现在我们知道如何找到一条路，我们需要教我们的游戏角色如何沿着这条路走。你可以在 walkPath.html 项目中找到一个这样的例子。点击迷宫中的任何地方，外星人精灵将采取最短的路线到达那里。A*算法使用我们刚刚看到的修改来允许路径圆角，如图 6-22 所示。
图 6-22。点击地图上的任何地方，游戏角色就会走到那里
这是通过使用 shortestPath 函数创建一个新的 x/y 点的 2D 数组来实现的。这些点被称为路点。每个路点代表路径中每个节点的 x/y 位置。这些点然后被用来告诉精灵向哪个方向移动。让我们看看让所有这些工作的代码。
首先，setup 函数定义了指针的释放方法。它在两个新变量 destinationX 和 destinationY 中捕获指针的 x 和 y 位置。它还将一个名为 calculateNewPath 变量的布尔变量设置为 true，以标记在下一个机会应该计算一个新路径。setup 函数还定义了一个名为 wayPoints2DArray 的变量，稍后将使用该变量来存储 x/y 道路点对。
**//An array that will be used to store sub-arrays of**
**//x/y position value pairs that we're going to use**
**//to change the velocity of the alien sprite**
wayPoints2DArray = [];
**//A Boolean that will be set to true when the pointer**
**//is clicked, and set to false when the new path**
**//is calculated**
calculateNewPath = false;
**//The pointer’s `release` method, which is called when the left mouse button**
**//or touch point is released**
g.pointer.release = () => {
**//Set the new path's destination to the pointer's**
**//current x and y position**
destinationX = g.pointer.x;
destinationY = g.pointer.y;
**//Set `calculateNewPath` to true**
calculateNewPath = true;
};
其余的重要代码在游戏循环中，在我们在本书中使用的实现中，发生在一个名为 play 的函数中。这里是完整的代码，注释解释了每个部分是如何工作的。(这段代码使用了您在前面章节中学到的 isCenteredOverCell 和 getIndex 辅助函数。)
function play() {
**//Find out if the alien is centered over a tile cell**
if (isCenteredOverCell(alien)) {
**//If `calculateNewPath` has been set to `true` by the pointer,**
**//find the new shortest path between the alien and the pointer's**
**//x and y position (`destinationX` and `destinationY`)**
if (calculateNewPath) {
**//calculate the shortest path**
let path = shortestPath(
getIndex(alien.centerX, alien.centerY, 64, 64, 13), **//Start index**
getIndex(destinationX, destinationY, 64, 64, 13), **//End index**
wallMapArray, **//Map array**
13, **//Map width**
[2, 3], **//Gid array**
"manhattan" **//Heuristic**
);
**//Remove the first node of the `path` array. That's because we**
**//don't need it: the alien sprite's current location and the**
**//first node in the `path` array share the same location.**
**//In the code ahead we're going to tell the alien sprite to move**
**//from its current location, to first new node in the path.**
path.shift();
**//If the path isn't empty, fill the `wayPoints2DArray` with**
**//sub arrays of x/y position value pairs.**
if (path.length !== 0) {
**//Get a 2D array of x/y points**
wayPoints2DArray = path.map(node => {
**//Figure out the x and y location of each square in the path by**
**//multiplying the node's `column` and `row` by the height, in**
**//pixels, of each cell: 64**
let x = node.column * 64,
y = node.row * 64;
**//Return a sub-array containing the x and y position of each node**
return [x, y];
});
}
**//Set `calculateNewPath` to `false` so that this block of code.**
**//won't run again inside the game loop. (It can be set to `true`**
**//again by clicking the pointer.)**
calculateNewPath = false;
}
**//Set the alien's new velocity based on**
**//the alien's relative x/y position to the current, next, way point.**
**//Because we are always going to**
**//remove a way point element after we set this new**
**//velocity, the first element in the `wayPoints2DArray`**
**//will always refer to the next way point that the**
**//alien sprite has to move to**
if (wayPoints2DArray.length !== 0) {
**//Left**
if (wayPoints2DArray[0][0] < alien.x) {
alien.vx = -4;
alien.vy = 0;
**//Right**
} else if (wayPoints2DArray[0][0] > alien.x) {
alien.vx = 4;
alien.vy = 0;
**//Up**
} else if (wayPoints2DArray[0][1] < alien.y) {
alien.vx = 0;
alien.vy = -4;
**//Down**
} else if (wayPoints2DArray[0][1] > alien.y) {
alien.vx = 0;
alien.vy = 4;
}
**//Remove the current way point, so that next time around**
**//the first element in the `wayPoints2DArray` will correctly refer**
**//to the next way point that that alien sprite has**
**//to move to**
wayPoints2DArray.shift();
**//If there are no way points remaining,**
**//set the alien's velocity to 0**
} else {
alien.vx = 0;
alien.vy = 0;
}
}
**//Move the alien sprite based on the new velocity**
alien.x += alien.vx;
alien.y += alien.vy;
}
在这个例子中，每当用户点击鼠标时，一个新的路径被计算出来，但是你可以在你自己的游戏中改变这个，这样，每当有任何重要的事情发生，导致精灵改变方向时，路径就会被计算出来。
扩展和定制*
你肯定需要投入一些时间来适应使用 A*并理解它的所有微妙之处。但这肯定是值得努力的，因为它是大多数游戏类型的所有平台上使用的基础游戏设计技术。
A的吸引力很大一部分在于它的灵活性。正如你所看到的，你可以通过改变启发式算法产生不同的路径。但是不仅仅是启发法让 A如此灵活。让我们看看 A*算法提供的其他一些可能性。
可变地形
在本章的例子中，我们只有一种障碍:墙。然而，你在游戏中可能会遇到不同种类的障碍，并非所有的障碍都是无法逾越的。
如果你有一个泥坑游戏会怎么样？角色仍然可以在泥泞中移动，但这会减慢他们的速度。您可以修改 A，使包含 mud 的节点具有高开销。比如当 A遇到 mud 节点时，给你的 G 代价额外 20 或 30 点。然后 A*会计算是绕过泥地快还是抄近路快。
策略游戏一直使用这种技术。部队需要考虑是坚守平原快速行进好，还是慢慢翻山越岭好。这种分析都是通过 A*对不同种类的移动进行成本分析来完成的。
影响力地图
这是另一个有趣的问题，可以用 A解决。想象一下，你有一个敌人 AI 角色正在用 A寻找去地牢的最佳出口。唯一的问题是，你已经发现，你可以很容易地通过藏在出口附近，并在敌人盲目蹒跚而过时击倒他们，从而获得高分。敌人没有办法警告他们的朋友，虽然这可能是最短的路线，但也非常危险。
你可以通过使用所谓的影响图来解决这个问题。如果游戏世界的某个区域变得特别危险，那就让那些节点付出非常高的代价。当 A*搜索路径时，它会避开那些昂贵、危险的区域。
你也可以扩展这个概念来解决很多敌人走同一条路的问题。在许多游戏中，如果所有的敌人都选择相同的最短路径，会显得非常不自然。您可以通过跟踪每个节点选择的路径，并为这些节点分配高成本，来迫使敌人采取不同的路径。A*将会避开已经被其他敌人选择的节点和路径。
Dijkstra 算法
前面我提到过 A是 Dijkstra 算法的修改。在 A上使用 Dijkstra 算法有一个很好的理由:当你不知道路径的最终目的地时。
A和 Dijkstra 算法的唯一区别是 A增加了启发式。在 Dijkstra 的算法中，H 的值总是为零。这意味着当 Dijkstra 的算法开始寻找路径时，它不知道从哪个方向开始寻找。为了找到目标，它必须做比 A*更多的搜索。
但是如果你在一个游戏中不确定角色的最终目的地会是哪里呢？想象一下，你正在设计一个策略或资源管理游戏，你的村民需要收集草莓。小镇周围有四片草莓灌木丛，但你不知道哪片灌木丛离你最近。如果用 Dijkstra 的算法，它会向四面八方向外搜索，直到找到第一个。如果你使用*的话，你将需要计算到每个灌木丛的四条不同的路径，并选择最短的一条。Dijkstra 的算法让你不必这么做，所以在这种情况下它会是一个更好的选择。
如果你想用 Dijkstra 的算法而不是 A，只需要给所有的 H 代价赋值 0。A代码的其余部分将是相同的。
不要多此一举！写这一章是为了让你完全理解 A是如何工作的。它旨在帮助您定制、重写和修改它。但是，JavaScript 中有很多高质量的、开源的 A实现，它们可能更高性能、更灵活，或者更容易实现。Easystar.js 和 Pathfinding.js 是很好的起点。
摘要
本章简要介绍了寻路，这应该会让你思考你自己的游戏有哪些可能。冒险游戏、策略游戏和任何需要复杂人工智能的游戏都将受益于这些技术。你已经学会了从头开始实现你自己的 A*寻路算法所需要知道的一切，以及如何使用它在你基于磁贴的游戏世界中移动精灵。
但是我们绝不会放弃基于磁贴的游戏！在下一章中，你将会学到更多基于图块的游戏设计的秘密:如何使用图块轻松地创建令人惊讶的复杂、自主的 AI 实体，以及如何实现有效的宽相位碰撞检测系统。
版权属于：月萌API www.moonapi.com，转载请注明出处
