五、寻路基础
你现在知道了如何创建一个基于磁贴的游戏世界，也知道了如何创建一个可以在这个世界中导航的玩家角色。但是你如何创造出能够四处游荡并独自探索世界的精灵呢？花一点时间播放一个名为 tileBasedLineOfSight.html 的示例原型，你可以在本章的源文件中找到它(如图 5-1 所示)。迷宫中有三个怪物，它们随机四处游荡，直到发现外星角色，然后毫不留情地追逐他。
图 5-1。怪物自主导航游戏世界，追逐玩家角色
这些怪物似乎有一种智能，表现得就像你所期望的生物一样。但是，当然，这只是一种有效的错觉，这要归功于一系列游戏编程技术，这些技术被广泛称为寻路:如何让精灵能够自主解释和导航游戏世界。在这一章中，你将学习所有寻路的基础知识，包括:
-
如何分析和解释一个精灵所处的环境？
-
在迷宫中随机移动。
-
寻找离目标最近的方向。
-
视线:如何知道一个精灵是否能看到另一个精灵？
寻路实际上是人工智能(AI)的一种基本形式，你将能够应用这些技术，不仅仅是广泛的不同游戏，而是任何需要在更大的数据集中根据上下文解释一些数据的含义的编程问题。而且，这很容易做到！因此，让我们从一些寻路的基本原则开始，并从那里开始。
在迷宫中随机移动
从寻路开始的最好地方是首先创建随机在迷宫中移动的精灵。运行 randomMovement.html 文件，你会发现图 5-1 所示的相同迷宫游戏的一个更简单的版本。这些怪物不是主动寻找外星角色，而是在十字路口随机改变方向。让我们来看看这段代码是如何工作的，我们将在过程中学习所有的寻路基础知识。
方向和速度
当怪物精灵在游戏的设置函数中被创建时，它们被初始化为两个重要的属性:方向和速度，在下面的精灵创建代码中突出显示:
monsters = mapMonsters.map(mapMonster => {
let monster = g.sprite(monsterFrames);
monster.x = mapMonster.x;
monster.y = mapMonster.y;
**monster.direction = "none";**
**monster.speed = 4;**
monsterLayer.addChild(monster);
mapMonster.visible = false;
return monster;
});
方向是一个字符串，它被初始化为“none”——你将看到我们如何在前面给它分配新的字符串值。速度是精灵每帧应该移动的像素数，它应该是一个可以均匀划分为贴图的 tilewidth 和 tileheight 大小的数。我们将需要使用这些方向和速度值来帮助给怪物新的随机方向和速度。
在游戏循环中移动精灵
实际上，选择怪物的新方向并让它们移动的代码在游戏循环中运行。实现这一点的代码需要做四件重要的事情:
-
找出怪物是否在地图方格的正中央。
-
如果是，选择一个新的随机方向。
-
使用怪物的新的随机方向和速度来找到它的速度。
-
使用新的速度来移动怪物。
这是游戏循环中完成这一切的代码。
monsters.forEach(monster => {
**//1\. Is the monster directly centered over a map tile cell?**
if (isCenteredOverCell(monster)) {
**//2\. Yes, it is, so find out which are valid directions to move.**
**//`validDirections` returns an array which can include any**
**//of these string values: "up", "right", "down"or "left" or**
monster.validDirections = validDirections(
monster, wallMapArray, 0, world
);
**//3\. Can the monster change its direction?**
if (canChangeDirection(monster.validDirections)) {
**//4\. If it can, randomly select a new direction from the monsters valid directions**
monster.direction = randomDirection(monster, monster.validDirections);
}
**//5\. Use the monster's direction and speed to find its new velocity**
let velocity = directionToVelocity(monster.direction, monster.speed);
monster.vx = velocity.vx;
monster.vy = velocity.vy;
}
**//6\. Move the monster**
monster.x += monster.vx;
monster.y += monster.vy;
});
这是非常高级的代码。您可以看到所有重要的功能都隐藏在五个重要的函数中:isCenteredOverCell、validDirections、canChangeDirection、randomDirection 和 directionToVelocity。我们将依次研究这些函数，以找出它们的确切工作原理。
精灵是否位于平铺单元格的中心？
正如你在第 3 章中了解到的，如果你的精灵在一个基于瓷砖的世界中，当他们正好在一个单元的中心时改变方向，他们将会更加准确和精确地移动。因此，如果使用名为 isCenteredOverCell 的辅助函数来解决这个问题，代码要做的第一件事就是。为它提供一个 sprite，如果 sprite 居中，isCenteredOverCell 将返回 true，否则返回 false。
function isCenteredOverCell(sprite) {
return Math.floor(sprite.x) % world.tilewidth === 0
&& Math.floor(sprite.y) % world.tileheight === 0
}
这是一段有趣的 boiler plate 代码，显示了模数运算符(%)有时是多么的有用。(提醒一下，模数运算符告诉您除法运算的余数是多少。)上面的代码找出 sprite 的 x 和 y 左上角位置除以 tile 的宽度和高度，余数是否为零。如果是的话，那么你就知道这个精灵在一个 x/y 位置上，这个位置绝对平均地划分了瓷砖的尺寸。而且，这只能意味着一件事:精灵在单元格上精确地对齐。这是一个聪明的把戏——谢谢你，模数运算符！
如果精灵是居中的，下一步就是找出精灵可以选择的可能的有效方向。
寻找有效的方向
validDirections 函数分析精灵当前所在的地图环境，并返回一个字符串数组，其中包含精灵可以移动的所有可能的有效方向。
monster.validDirections = validDirections(
monster, **//The sprite**
wallMapArray, **//The tile map array**
0, **//The gid value that represents an empty tile**
world **//The world object. It needs these properties:**
**//`tilewidth`, `tileheight` and `widthInTiles`**
);
validDirections 返回的数组可以包含以下五个字符串值中的任何一个:“上”、“下”、“左”、“右”或“无”。它是如何解决这个问题的非常有趣，所以让我们先来看看整个 validDirections 函数，然后我将一步一步地向您介绍它是如何工作的。
function validDirections(sprite, mapArray, validGid, world) {
**//Get the sprite's current map index position number**
let index = g.getIndex(
sprite.x,
sprite.y,
world.tilewidth,
world.tileheight,
world.widthInTiles
);
**//An array containing the index numbers of tile cells**
**//above, below and to the left and right of the sprite**
let surroundingCrossCells = (index, widthInTiles) => {
return [
index - widthInTiles, **//Cell above**
index - 1, **//Cell to the left**
index + 1, **//Cell to the right**
index + widthInTiles, **//Cell below**
];
};
**//Get the index position numbers of the 4 cells to the top, right, left**
**//and bottom of the sprite**
let surroundingIndexNumbers = surroundingCrossCells(index, world.widthInTiles);
**//Find all the tile gid numbers that match the surrounding index numbers**
let surroundingTileGids = surroundingIndexNumbers.map(index => {
return mapArray[index];
});
**//`directionList` is an array of 4 string values that can be either**
**//"up", "left", "right", "down" or "none", depending on**
**//whether there is a cell with a valid gid that matches that direction**
let directionList = surroundingTileGids.map((gid, i) => {
**//The possible directions**
let possibleDirections = ["up", "left", "right", "down"];
**//If the direction is valid, choose the matching string**
**//identifier for that direction. Otherwise, return "none"**
if (gid === validGid) {
return possibleDirections[i];
} else {
return "none";
}
});
**//We don't need "none" in the list of directions, so**
**//let's filter it out (it’s just a placeholder)**
let filteredDirectionList = directionList.filter(direction => direction != "none");
**//Return the filtered list of valid directions**
return filteredDirectionList;
}
现在让我们看看这实际上是如何工作的！
精灵周围的瓷砖
validDirections 函数做的第一件事是找出哪些地图图块围绕着 sprite。一个名为 surroundingCrossCells 的函数使用 sprite 在 map 数组中的索引号来解决这个问题。它返回一个由四个地图索引号组成的数组，分别代表 sprite 上方、左侧、右侧和下方的单元格。
let surroundingCrossCells = (index, widthInTiles) => {
return [
index - widthInTiles, **//Cell above**
index - 1, **//Cell to the left**
index + 1, **//Cell to the right**
index + widthInTiles, **//Cell below**
];
};
let surroundingIndexNumbers =
surroundingCrossCells(index, world.widthInTiles);
图 5-2 显示了这些单元格相对于精灵的位置，以及它们匹配的贴图数组索引号。在这个例子中，迷宫的每一行有 11 个单元，怪物精灵的位置索引号是 38。精灵周围的贴图数组索引号从顶部开始顺时针方向依次为 27、39、49 和 37。
图 5-2。找到精灵周围的单元格
我们现在有一个名为 surroundingIndexNumbers 的数组，它告诉我们 sprite 周围单元格的索引号。但这还不够。我们还需要知道这些像元的 gid 值是多少，这样我们就知道它们包含哪种类型的图块。请记住，我们希望允许精灵移动到空瓷砖，但防止它移动到墙砖。所以下一步就是使用这些索引号来精确地找出在这些位置上的瓷砖精灵。让我们将 surroundingIndexNumbers 映射到一个新数组，该数组告诉我们这些单元格的实际 gid 编号。以下是如何:
let surroundingTileGids = surroundingIndexNumbers.map(index => {
return mapArray[index];
});
例如，图 5-2 、27、39、49 和 35 中的索引号现在将映射到包含以下 gid 值的新数组:0、0、2 和 0。数字 0 代表一间空牢房，数字 2 代表一面墙。图 5-3 说明了这一点。
图 5-3。通过获取其 gid 编号，找出周围单元格中的瓷砖类型
有效方向
下一步是给 sprite 可以移动到的四个可能方向中的每一个赋予方向名称，作为字符串。方向名称可以是以下任何一种:“向上”“左”、“右”、“下”或“无”以下代码将我们的 surroundingTileGids 数组映射到一个名为 directionList 的新数组，该数组包含这些方向字符串。
let directionList = surroundingTileGids.map((gid, i) => {
**//The possible directions**
let possibleDirections = ["up", "left", "right", "down"];
**//If the direction is valid, choose the matching string**
**//identifier for that direction. Otherwise, return "none"**
if (gid === validGid) {
return possibleDirections[i];
} else {
return "none";
}
});
任何无效的 gid 都被赋予方向名“none”图 5-4 展示了 directionList 函数产生的结果数组。
图 5-4。找到方向名称
我们实际上并不需要“none”值，所以让我们把它过滤掉(它只是作为一个占位符):
let filteredDirectionList = directionList.filter(direction => {
return direction != "none"
});
filteredDirectionList 现在是我们的最终数组，它包含精灵可以移动的所有有效方向:
["up", "left", "right"]
(或者，如果精灵被完全包围，这个数组将会是空的——但是我们将会实现它！)
这个数组由 validDirections 函数返回，它完成了寻路过程中的第一个主要步骤。
怪物能改变方向吗？
实际上在地图上只有特定的地方怪物应该改变他们的方向。
-
当他们在十字路口时。
-
如果他们在死胡同里。
-
或者他们是否被四面的墙困住(在这种情况下，他们应该完全停止移动)。
图 5-5 中的 X 标记了这三个地图条件在我们正在使用的迷宫中的位置。
图 5-5。找到方向名称
如果怪物不在符合其中一个条件的地图位置，他们会继续他们当前的方向。
很容易搞清楚这些怪物目前的地图位置类型是什么。如果在 validDirections 数组中没有元素，那么您知道 sprite 被捕获了。
let trapped = validDirections.length === 0;
如果 validDirections 数组中只有一个元素，就知道 sprite 在死胡同中。
let inCulDeSac = validDirections.length === 1;
这些都很简单，但是现在我们如何知道一个精灵是否在一个十字路口呢？首先，问问自己，“什么是通道路口？”仔细看看图 5-5 ，问问你自己如果一个精灵在任何标有 x 的地图位置，那么在 validDirections 数组中会有什么值。对，没错！通道交叉点将总是包含值“左”或“右”和“上”或“下”图 5-6 说明了这一点。
图 5-6。通道交点总是包含一个左/右值和一个上/下值
下面是如何用代码来表达这一点:
let up = validDirections.find(x => x === "up"),
down = validDirections.find(x => x === "down"),
left = validDirections.find(x => x === "left"),
right = validDirections.find(x => x === "right"),
atIntersection = (up || down) && (left || right);
如果一个 Intersection 为真，你就知道这个精灵在一个标有 x 的通道交叉点上。
我们现在知道如何分辨一个精灵是被困在死胡同里，还是在十字路口。所以让我们把这些代码打包成一个更大的函数，叫做 canChangeDirection。如果这些条件中的任何一个为真，它将返回 true，否则返回 false。
function canChangeDirection(validDirections = []) {
**//Is the sprite in a dead-end (cul de sac.) This will be true if there's only**
**//one element in the `validDirections` array**
let inCulDeSac = validDirections.length === 1;
**//Is the sprite trapped? This will be true if there are no elements in**
**//the `validDirections` array**
let trapped = validDirections.length === 0;
**//Is the sprite in a passage? This will be `true` if the the sprite**
**//is at a location that contain the values**
**//"left" or "right" and "up" or "down"**
let up = validDirections.find(x => x === "up"),
down = validDirections.find(x => x === "down"),
left = validDirections.find(x => x === "left"),
right = validDirections.find(x => x === "right"),
atIntersection = (up || down) && (left || right);
**//Return `true` if the sprite can change direction or `false` if it can't**
return trapped || atIntersection || inCulDeSac;
}
现在我们有了一种方法来判断一个精灵是否在一个可以改变方向的地图位置，让我们看看如何给它一个新的随机方向。
选择一个随机的方向
现在我们知道了精灵的有效方向，我们要做的就是随机选择一个。randomDirection 函数从 validDirections 数组中随机返回一个字符串:“up”、“left”、“right”或“down”如果没有有效的方向，这意味着精灵在所有的边上都被陷印，函数返回字符串“陷印”下面是实现这一点的 randomDirection 数组:
function randomDirection(sprite, validDirections = []) {
**//The `randomInt` helper function returns a random integer between a minimum**
**//and maximum value**
let randomInt = (min, max) => {
return Math.floor(Math.random() * (max - min + 1)) + min;
};
**//Is the sprite trapped?**
let trapped = validDirections.length === 0;
**//If the sprite isn't trapped, randomly choose one of the valid**
**//directions. Otherwise, return the string "trapped"**
if (!trapped) {
return validDirections[randomInt(0, validDirections.length - 1)];
} else {
return "trapped"
}
}
将方向字符串转换为速度数字
我们现在知道精灵应该朝哪个方向移动。但是，为了使该信息对移动精灵有用，我们需要将方向字符串转换成表示精灵速度的数字。一个名为 directionToVelocity 的函数完成了这项工作:它返回一个具有 vx 和 vy 属性的对象，这些属性对应于精灵应该移动的方向。
function directionToVelocity(direction = "", speed = 0) {
switch (direction) {
case "up":
return {
vy: -speed,
vx: 0
}
break;
case "down":
return {
vy: speed,
vx: 0
};
break;
case "left":
return {
vx: -speed,
vy: 0
};
break;
case "right":
return {
vx: speed,
vy: 0
};
break;
default:
return {
vx: 0,
vy: 0
};
}
};
如果怪物的方向是“被困”，默认情况下将被触发，代表怪物速度的 vx 和 vy 值将为零。
若要使精灵移动，请用这些值更新精灵的速度:
let velocity = directionToVelocity(monster.direction, monster.speed);
monster.vx = velocity.vx;
monster.vy = velocity.vy;
然后将它们应用到精灵的当前位置:
monster.x += monster.vx;
monster.y += monster.vy;
这就是如何让一个怪物在迷宫中随机移动！
猎杀外星人
随机移动怪物是一个好的开始，但对于一个更具挑战性的游戏，你会希望你的怪物主动寻找并追捕玩家角色。运行本章源文件中的 closestDirection.html 文件，获得这样一个系统的交互示例，如图 5-7 所示。
图 5-7。怪物总是选择离玩家角色最近的方向
无论他们在迷宫的哪个位置，怪物们总是会选择向更接近玩家角色的方向移动。
计算向量
要做到这一点，你需要知道怪物的四个可能方向中的哪一个最接近外星人。第一步是在怪物和外星人的中心点之间画一个矢量。矢量只是一条看不见的数学线，在它的许多用途中，可以用来计算两个精灵之间的距离和角度。向量由两个值 vx 和 vy 表示，您可以像这样计算两个精灵之间的向量:
let vx = spriteTwo.centerX - spriteOne.centerX,
vy = spriteTwo.centerY - spriteOne.centerY;
vx 告诉我们 X 轴上物体之间的距离。vy 告诉我们 Y 轴上物体之间的距离。vx 和 vy 变量一起描述了对象之间的向量。
向量只是一条线的数学表示——你实际上看不到它显示在屏幕上。但是，如果你能看到它，它可能看起来像图 5-8 中两个精灵中心之间的黑色对角线。
图 5-8。矢量可以帮助你计算出两个精灵之间的距离和角度
为了让怪物猎杀外星人，我们必须在水平或垂直方向移动它，使它和外星人之间的距离达到最大值。为什么会这样？看看图 5-9 。
图 5-9。沿着精灵之间距离最大的轴移动怪物
很明显，怪物要想靠近玩家，应该选择沿着 X 轴的左方向。然而，X 轴也是物体之间距离最大的轴。不直观，但真实！
现在我们知道了这一点，我们可以使用一个简单的 if/else 语句来告诉我们哪个方向是离目标最近的方向:“上”、“下”、“左”或“右”。这里有一个名为 closest 的函数，它将所有这些打包并为我们返回正确的值:
let closest = () => {
**//Plot a vector between spriteTwo and spriteOne**
let vx = spriteTwo.centerX - spriteOne.centerX,
vy = spriteTwo.centerY - spriteOne.centerY;
**//If the distance is greater on the X axis...**
if (Math.abs(vx) >= Math.abs(vy)) {
**//Try left and right**
if (vx <= 0) {
return "left";
} else {
return "right";
}
}
**//If the distance is greater on the Y axis...**
else {
**//Try up and down**
if (vy <= 0) {
return "up"
} else {
return "down"
}
}
};
现在让我们看看如何将它与我们现有的代码集成起来。
寻找最近的方向
打开本章源文件中的 closesestDirection.js 文件，您会在 play 函数(游戏循环)中找到这段代码，它负责移动怪物并选择它们的新方向。除了第 4 步之外，它与我们在本章开始时使用的代码完全相同。
monsters.forEach(monster => {
**//1\. Is the monster directly centered over a map tile cell?**
if (isCenteredOverCell(monster)) {
**//2\. Yes, it is, so find out which are valid directions to move.**
**//`validDirections` returns an array which can include any**
**//of these string values: "up", "right", "down", "left" or "none"**
monster.validDirections = validDirections(
monster, wallMapArray, 0, world
);
**//3\. Can the monster change its direction?**
if (canChangeDirection(monster.validDirections)) {
**//4\. If it can, choose the closest direction to the alien**
monster.direction = closestDirection(monster, alien, monster.validDirections);
}
**//5\. Use the monster's direction and speed to find its new velocity**
let velocity = directionToVelocity(monster.direction, monster.speed);
monster.vx = velocity.vx;
monster.vy = velocity.vy;
}
**//6\. Move the monster**
monster.x += monster.vx;
monster.y += monster.vy;
唯一的新代码行是这一行:
monster.direction = **closestDirection(monster, alien, monster.validDirections)**;
一个名为 closestDirection 的新功能负责计算并返回怪物最接近外星人的有效方向。如果没有与最近方向匹配的有效方向，它会选择一个随机方向。下面是完成所有这些工作的完整 closestDirection 函数:
function closestDirection(spriteOne, spriteTwo, validDirections = []) {
**//A helper function to find the closest direction**
let closest = () => {
**//Plot a vector between spriteTwo and spriteOne**
let vx = spriteTwo.centerX - spriteOne.centerX,
vy = spriteTwo.centerY - spriteOne.centerY;
**//If the distance is greater on the X axis...**
if (Math.abs(vx) >= Math.abs(vy)) {
**//Try left and right**
if (vx <= 0) {
return "left";
} else {
return "right";
}
}
**//If the distance is greater on the Y axis...**
else {
**//Try up and down**
if (vy <= 0) {
return "up"
} else {
return "down"
}
}
};
**//The closest direction that's also a valid direction**
let closestValidDirection = validDirections.find(x => x === closest());
**//The `randomInt` helper function returns a random**
**//integer between a minimum and maximum value**
let randomInt = (min, max) => {
return Math.floor(Math.random() * (max - min + 1)) + min;
};
**//Is the sprite trapped?**
let trapped = validDirections.length === 0;
**//If the sprite isn't trapped, choose the closest direction**
**//from the `validDirections` array. If there's no closest valid**
**//direction, then choose a valid direction at random**
if (!trapped) {
if (closestValidDirection) {
return closestValidDirection;
} else {
return validDirections[randomInt(0, validDirections.length - 1)];
}
} else {
return "trapped"
}
}
这个函数的工作方式是首先在两个精灵之间绘制一个向量，然后计算出哪个方向最接近猎人 spriteOne 到达目标 spriteTwo。该代码检查该方向是否也在 validDirections 数组中。如果是，则选择最近的方向，如果不是，则选择新的随机方向。
这个系统运行良好，但有一个小问题:怪物知道哪个方向离外星人最近，即使他们的视线被迷宫墙挡住了。也许怪物们在用声音来探测外星人的位置，用心灵感应来交流，或者，不太可能，他们真的很聪明？从美学角度来看，这个系统是可行的——它看起来是正确的，并且是一个具有挑战性的游戏。但是你可能想创建一个游戏，在这个游戏中，怪物们只有在能够真正看到没有墙壁阻挡的外星人时才会做出反应。我们可以通过使用一种叫做视线的基本游戏设计技术来实现这个特性。
视线
你如何判断一个精灵是否能看到另一个精灵？在两个精灵之间画一个向量，然后沿着向量在均匀间隔的点上检查障碍物。如果矢量是完全无障碍的，那么你知道你有两个精灵之间的直接视线。
运行本章源文件中的 lineOfSight.html 文件进行交互示例，如图 5-10 所示。在屏幕上拖放不同组合的外星人、怪物和墙壁精灵。一条红线在怪物和外星人之间延伸，代表视线。如果视线通畅，小精灵之间的界线变暗，怪物张开嘴。
图 5-10。检查两个精灵之间的视线
其工作方式是沿着两个精灵之间的向量(线)不可见地放置一系列点。如果这些点中的任何一个接触到一个盒子，那么你就知道视线被挡住了。如果这些点都没有接触到任何一个盒子，那么精灵之间就有一条清晰的视线。图 5-11 对此进行了说明。
图 5-11。沿线标绘点，并检查每个点是否与方框发生碰撞
让我们一步一步地浏览一下您需要编写的代码。
计算向量
第一步是在两个精灵的中心绘制一个向量。
let vx = spriteTwo.centerX - spriteOne.centerX,
vy = spriteTwo.centerY - spriteOne.centerY;
接下来，我们需要找出向量的长度，以像素为单位。向量的长度被称为它的大小，你可以这样算出来:
let magnitude = Math.sqrt(vx * vx + vy * vy);
我们想要沿着这个向量在均匀间隔的位置上绘制点。为了帮助我们做到这一点，让我们创建一个名为 segment 的变量来确定这些点之间的距离。
let segment = spriteOne.width;
通常你不希望点与点之间的距离小于你最小的精灵的宽度或高度。这是因为如果点之间的空间太大，点碰撞测试可能会跳过并错过较小的障碍精灵。
现在我们知道了精灵之间向量的长度，也知道了碰撞点之间每一段的长度，我们可以计算出我们需要使用多少碰撞点。
let numberOfPoints = magnitude / segment;
例如，如果向量的大小是 256 个像素，每个线段的长度是 64 个像素，那么点数将是 4。
寻找碰撞点的位置
我们现在有足够的信息来计算碰撞点在向量上的 x/y 位置。我们将借助一个名为 points 的函数来实现这一点，该函数返回一个包含具有 x 和 y 属性的对象的数组。我们将能够使用点对象的数组来测试每个点和障碍物之间的碰撞。下面是创建点对象数组的点函数:
let points = () => {
**//Initialize an array that is going to store all our points**
**//along the vector**
let arrayOfPoints = [];
**//Create a point object for each segment of the vector and**
**//store its x/y position as well as its index number on**
**//the map array**
for (let i = 1; i <= numberOfPoints; i++) {
**//Calculate the new magnitude for this iteration of the loop**
let newMagnitude = segment * i;
**//Find the unit vector**
let dx = vx / magnitude,
dy = vy / magnitude;
**//Use the unit vector and newMagnitude to figure out the x/y**
**//position of the next point in this loop iteration**
let x = spriteOne.centerX + dx * newMagnitude,
y = spriteOne.centerY + dy * newMagnitude;
**//Push a point object with x and y properties into the `arrayOfPoints`**
arrayOfPoints.push({x, y});
}
**//Return the array of point objects**
return arrayOfPoints;
};
points 函数的核心是一个循环，它可以为任意数量的点创建点对象。循环做的第一件事是通过将循环索引值乘以 segment 的值来创建一个新的 Magnitude 值。
let newMagnitude = segment * i;
如果有四个点，并且每个线段的宽度是 64 个像素，则在循环的每次迭代中，newMagnitude 将具有值 64、128、194 和 256。
接下来的两行代码算出了单位向量是什么，由变量名 dx 和 dy 表示。
let dx = vx / magnitude,
dy = vy / magnitude;
单位向量(也称为归一化向量)只是小精灵之间主向量的一个微小的缩小版本，长度不到一个像素。它指向与主向量相同的方向，但是因为它是向量可能的最小尺寸，我们可以用它来创建不同长度的新向量。
你可以在本书的配套书籍中找到完整的矢量数学初学者指南，【HTML5 和 JavaScript 的高级游戏设计 (Apress，2015)。它非常详细地解释了所有这些概念，并提供了大量如何在游戏开发中使用它们的实际例子。
将单位矢量乘以新的星等，并将结果加到 spriteOne 的位置上，将得到矢量上各点的 x/y 位置。
let x = spriteOne.centerX + dx * newMagnitude,
y = spriteOne.centerY + dy * newMagnitude;
图 5-12 显示了如果有四个 numberOfPoints 并且段宽度为 64 像素，那么循环的每次迭代看起来会是什么样子。
图 5-12。找出向量上每个点的位置
这些点的 x/y 值存储在 point 对象中，并被推入一个名为 arrayOfPoints 的数组中。
arrayOfPoints.push({x, y});
当循环结束时，arrayOfPoints 将包含一个对象列表，这些对象的 x 和 y 属性与我们在上一步中计算的 x 和 y 值相匹配。points 函数返回此数组:
return arrayOfPoints;
我们现在可以像这样调用 points 函数来访问这个数组:
points()
这将动态地重新计算并返回新的点数数组，只要我们在游戏中需要它们。
测试与障碍物碰撞的点
我们现在需要一些方法来弄清楚这些点中是否有任何一个碰到了障碍。我们可以使用名为 hitTestPoint 的基本几何碰撞函数来检查具有 x/y 属性的单点对象是否与矩形 sprite 相交。如果有冲突，hitTestPoint 返回 true，如果没有冲突，返回 false。
let hitTestPoint = (point, sprite) => {
**//Find out if the point's position is inside the area defined**
**//by the sprite's left, right, top and bottom sides**
let left = point.x > sprite.x,
right = point.x < (sprite.x + sprite.width),
top = point.y > sprite.y,
bottom = point.y < (sprite.y + sprite.height);
**//If all the collision conditions are met, you know the**
**//point is intersecting the sprite**
return left && right && top && bottom;
};
我们现在可以使用 hitTestPoint 来检查每个点和每个可能阻挡视线的障碍物精灵之间的碰撞。以下是如何:
let noObstacles = points().every(point => {
return obstacles.every(obstacle => {
return !(hitTestPoint(point, obstacle))
});
});
如果 noObstacles 是真的，那么我们知道视线是清晰的。
视线功能
让我们将前几节学到的所有技术放在一起，构建一个可重用的视线函数，如果两个精灵之间有清晰的视线，该函数将返回 true，如果没有，则返回 false。下面是你如何在游戏代码中使用它:
monster.lineOfSight = lineOfSight(
monster, **//Sprite one**
alien, **//Sprite two**
boxes, **//An array of obstacle sprites**
16 **//The distance between each collision point**
);
第四个参数确定碰撞点之间的距离。为了获得更好的性能，请将该值设置为一个较大的值，直至达到最小 sprite 的最大宽度(如 64 或 32)。要获得更高的精度，请使用较小的数字。
你可以使用视线值来决定如何改变游戏中的某些东西。在 lineOfSight.html 示例文件中，它用于打开怪物的嘴，并增加两个精灵之间连接线的 alpha 值。
if (monster.lineOfSight) {
monster.show(monster.states.angry)
line.alpha = 1;
} else {
monster.show(monster.states.normal)
line.alpha = 0.3;
}
(查看 lineOfSight.js 文件中的源代码，了解如何工作的完整细节，尤其是如何初始化怪物的不同状态。)
这是完整的视线功能。
function lineOfSight(
spriteOne, **//The first sprite, with `centerX` and `centerY` properties**
spriteTwo, **//The second sprite, with `centerX` and `centerY` properties**
obstacles, **//An array of sprites which act as obstacles**
segment = 32 **//The distance between collision points**
) {
**//Plot a vector between spriteTwo and spriteOne**
let vx = spriteTwo.centerX - spriteOne.centerX,
vy = spriteTwo.centerY - spriteOne.centerY;
**//Find the vector's magnitude (its length in pixels)**
let magnitude = Math.sqrt(vx * vx + vy * vy);
**//How many points will we need to test?**
let numberOfPoints = magnitude / segment;
**//Create an array of x/y points, separated by 64 pixels, that**
**//extends from `spriteOne` to `spriteTwo`**
let points = () => {
**//Initialize an array that is going to store all our points**
**//along the vector**
let arrayOfPoints = [];
**//Create a point object for each segment of the vector and**
**//store its x/y position as well as its index number on**
**//the map array**
for (let i = 1; i <= numberOfPoints; i++) {
**//Calculate the new magnitude for this iteration of the loop**
let newMagnitude = segment * i;
**//Find the unit vector**
let dx = vx / magnitude,
dy = vy / magnitude;
**//Use the unit vector and newMagnitude to figure out the x/y**
**//position of the next point in this loop iteration**
let x = spriteOne.centerX + dx * newMagnitude,
y = spriteOne.centerY + dy * newMagnitude;
**//Push a point object with x and y properties into the `arrayOfPoints`**
arrayOfPoints.push({x, y});
}
**//Return the array of point objects**
return arrayOfPoints;
};
**//Test for a collision between a point and a sprite**
let hitTestPoint = (point, sprite) => {
**//Find out if the point's position is inside the area defined**
**//by the sprite's left, right, top and bottom sides**
let left = point.x > sprite.x,
right = point.x < (sprite.x + sprite.width),
top = point.y > sprite.y,
bottom = point.y < (sprite.y + sprite.height);
**//If all the collision conditions are met, you know the**
**//point is intersecting the sprite**
return left && right && top && bottom;
};
**//The `noObstacles` function will return `true` if all the tile**
**//index numbers along the vector are `0`, which means they contain**
**//no obstacles. If any of them aren't `0`, then the function returns**
**//`false` which means there's an obstacle in the way**
let noObstacles = points().every(point => {
return obstacles.every(obstacle => {
return !(hitTestPoint(point, obstacle))
});
});
**//Return the true/false value of the collision test**
return noObstacles;
}
现在你知道如何判断两个精灵之间是否有清晰的视线了。而且，你也知道如何让精灵在迷宫环境中导航。你需要学习的最后一件事是如何结合这两种技术——别担心，这比你想象的要容易得多！
基于瓷砖的视线
运行本章源文件中的 tileBasedLineOfSight.html 文件，获得如何在基于瓷砖的迷宫环境中实现视线寻路系统的工作示例。在这个例子中，怪物们只有在一条通道上没有障碍的情况下才会追逐外星人，如图 5-13 所示。
图 5-13。怪物只有在看到外星人时才会追逐它
我们将对我们的视线系统进行两项修改，使其在基于瓷砖的迷宫环境中工作良好:
-
我们将使用基于瓷砖的碰撞而不是基于几何体的碰撞来检查精灵之间的向量上是否有任何点接触到任何墙壁。
-
我们将限制精灵之间的向量为直角。这意味着我们只允许 0 度、90 度或 180 度的角度来测试视线。
让我们看看如何添加这两个新特性，然后使用它们来构建一个新的 tileBaseLineOfSight 函数。
基于图块的碰撞
在迷宫游戏环境中使用基于图块的碰撞系统的优点是非常高效。在一个大型游戏中，您可以同时进行数百个基于图块的碰撞测试，而不会有任何明显的性能影响。基于几何的碰撞更加数学化，所以；尽管它可能非常精确，但是您要付出性能代价。
在我们之前的视线示例中，我们使用了一个名为 hitTestPoint 的基于几何的碰撞函数，该函数检查一个点是否在矩形区域内。如何使用基于瓷砖的碰撞来测试一个点和一个精灵之间的碰撞？我们需要测试一个点的贴图数组索引号是否对应于我们想要测试碰撞的精灵的贴图数组索引号。这意味着我们需要将每个点的 x/y 位置号转换成地图数组索引号。我们已经知道如何去做，使用一个叫做 getIndex 的函数，你在第 3 章中已经学会了:
function getIndex(x, y, tilewidth, tileheight, mapWidthInTiles) {
**//Convert pixel coordinates to map index coordinates**
let index = {};
index.x = Math.floor(x / tilewidth);
index.y = Math.floor(y / tileheight);
**//Return the index number**
return index.x + (index.y * mapWidthInTiles);
};
如果你有一个点的数组，所有的点都有与它们在地图上的位置相对应的索引号，你就知道它们会与任何有相同索引号的物体发生碰撞。然后，您可以通过使用该点的索引号来查找该位置的像元的 gid 值，从而准确地找出该点与什么对象发生碰撞。
mapArray[point.index]
如果该点的 gid 号与您感兴趣的对象的 gid 号相匹配，那么您就遇到了冲突。
对于视线碰撞测试，您特别要寻找与不包含任何障碍物的细胞的碰撞。在我们在本书中使用的例子中，所有没有障碍物的空单元的 gid 数都是 0。这意味着您可以遍历视线向量中的每个点，如果它们的索引号都对应于 gid 值 0，那么您就知道没有冲突。
let noObstacles = points().every(point => {
return mapArray[point.index] === 0
});
在上面的例子中，如果 noObstacles 返回 true，那么你就有一个清晰的视线。您将提前看到这一小段代码是如何用于我们完整的基于图块的碰撞系统的。但首先，我们如何限制我们的视线测试只允许直角？
限制角度
在我们之前的视线例子中，怪物精灵拥有 360 度的视野。在迷宫游戏的例子中，怪物的视线被限制在直角。这意味着怪物看不到对角线上的拐角；他们只能看到正前方的东西。这对玩家来说更容易一点，也有助于更自然的迷宫游戏体验。
在我们找到如何实现它之前，让我们先找到如何计算一个向量(一条线)的角度。如你所知，向量由两个值定义:vx 和 vy。这是我们用来在两个精灵之间绘制矢量的代码:
let vx = spriteTwo.centerX - spriteOne.centerX,
vy = spriteTwo.centerY - spriteOne.centerY;
你可以用这个简单的公式计算出这个向量的角度，单位是度:
let angle = Math.atan2(vy, vx) * 180 / Math.PI;
限制视线角度的第一步是创建一个包含所有有效角度的数组。例如，要将角度限制为 90 度，请使用这些角度:
let angles = [90, -90, 0, 180, -180];
下一步是创建一个函数，将向量的角度与数组中的角度进行比较。如果匹配，函数返回 true，如果不匹配，函数返回 false。这里有一个 validAngle 函数可以做到这一点:
let validAngle = (vx, vy, angles) => {
**//Find the angle of the vector between the two sprites**
let angle = Math.atan2(vy, vx) * 180 / Math.PI;
**//If the angle matches one of the valid angles, return**
**//`true`, otherwise return `false`**
if (angles.length !== 0) {
return angles.some(x => x === angle);
} else {
return true;
}
};
现在让我们看看如何使用这些新技术来构建一个可重用的基于图块的视线功能。
tileBasedLineOfSight 函数
这是新的 tileBasedLineOfSight 函数，它实现了基于图块的碰撞，并将角度限制为 90 度。你将提前学习如何在游戏中使用它。
function tileBasedLineOfSight(
spriteOne, **//The first sprite, with `centerX` and `centerY` properties**
spriteTwo, **//The second sprite, with `centerX` and `centerY` properties**
mapArray, **//The tile map array**
world, **//The `world` object that contains the `tilewidth**
**//`tileheight` and `widthInTiles` properties**
emptyGid = 0, **//The Gid that represents and empty tile, usually `0`**
segment = 32, **//The distance between collision points**
angles = [] **//An array of angles to which you want to**
**//restrict the line of sight**
) {
**//Plot a vector between spriteTwo and spriteOne**
let vx = spriteTwo.centerX - spriteOne.centerX,
vy = spriteTwo.centerY - spriteOne.centerY;
**//Find the vector's magnitude (its length in pixels)**
let magnitude = Math.sqrt(vx * vx + vy * vy);
**//How many points will we need to test?**
let numberOfPoints = magnitude / segment;
**//Create an array of x/y points that**
**//extends from `spriteOne` to `spriteTwo`**
let points = () => {
**//Initialize an array that is going to store all our points**
**//along the vector**
let arrayOfPoints = [];
**//Create a point object for each segment of the vector and**
**//store its x/y position as well as its index number on**
**//the map array**
for (let i = 1; i <= numberOfPoints; i++) {
**//Calculate the new magnitude for this iteration of the loop**
let newMagnitude = segment * i;
**//Find the unit vector**
let dx = vx / magnitude,
dy = vy / magnitude;
**//Use the unit vector and newMagnitude to figure out the x/y**
**//position of the next point in this loop iteration**
let x = spriteOne.centerX + dx * newMagnitude,
y = spriteOne.centerY + dy * newMagnitude;
**//The getIndex function converts x/y coordinates into**
**//map array index positon numbers**
let getIndex = (x, y, tilewidth, tileheight, mapWidthInTiles) => {
**//Convert pixel coordinates to map index coordinates**
let index = {};
index.x = Math.floor(x / tilewidth);
index.y = Math.floor(y / tileheight);
**//Return the index number**
return index.x + (index.y * mapWidthInTiles);
};
**//Find the map index number that this x and y point corresponds to**
let index = getIndex(
x, y,
world.tilewidth,
world.tileheight,
world.widthInTiles
);
**//Push the point into the `arrayOfPoints`**
arrayOfPoints.push({
x, y, index
});
}
**//Return the array**
return arrayOfPoints;
};
**//The tile-based collision test.**
**//The `noObstacles` function will return `true` if all the tile**
**//index numbers along the vector are `0`, which means they contain**
**//no walls. If any of them aren't 0, then the function returns**
**//`false` which means there's a wall in the way**
let noObstacles = points().every(point => {
return mapArray[point.index] === emptyGid
});
**//Restrict the line of sight to right angles only**
**//(we don't want to use diagonals)**
let validAngle = () => {
**//Find the angle of the vector between the two sprites**
let angle = Math.atan2(vy, vx) * 180 / Math.PI;
**//If the angle matches one of the valid angles, return**
**//`true`, otherwise return `false`**
if (angles.length !== 0) {
return angles.some(x => x === angle);
} else {
return true;
}
};
**//Return `true` if there are no obstacles and the line of sight**
**//is at a 90 degree angle**
if (noObstacles === true && validAngle() === true) {
return true;
} else {
return false;
}
}
而那就是瓷砖为主的视线——解决了！
摘要
开始寻路时你需要知道的所有基础知识都在这一章里。您已经学习了如何分析和解释精灵所处的环境，以及如何使用这些信息来决定精灵应该向哪个方向移动。它应该选择一个随机的方向，还是一个最接近目标的方向？你还学到了每个游戏开发者都需要知道的最重要的技术之一:如何确定视线。现在，您知道了如何在基于几何体和基于图块的碰撞环境中使用视线。正如你将在前面的章节中看到的，所有这些技能不仅对寻路有用，也是构建初级人工智能的基础。当然，你可以在你的等轴游戏地图上使用同样的技术！
你在这一章学到的技能将带你走得很远，但是还有一个更重要的寻路技能你需要知道:如何找到两点之间的最短路径。这就是下一章要讲的！
版权属于：月萌API www.moonapi.com，转载请注明出处
