在这篇文章中，我将介绍如何使用方向场（Direction Fields）为浏览器游戏引入快速且动态的路径规划功能。
最近，我发布了一款名为《Build + Brawl》的免费浏览器游戏，它是用Unity开发的。在游戏中，玩家需要操控角色躲避成群的敌人。游戏环境中存在不可穿越的障碍物——有些是随机生成的，有些是玩家放置的——敌人必须绕过这些障碍物才能接近玩家。
虽然像A*这样的算法可以解决一般的路径规划问题，但《Build + Brawl》有几个特殊的需求促使我开发了自己的解决方案：
- 游戏中可能有数百个敌人同时向玩家移动。
- 敌人从不同的随机位置出发。
- 玩家角色可以移动。
- 玩家可以在游戏过程中添加或移除障碍物。
- 游戏必须在浏览器中实时运行，不能有卡顿，且只能使用单线程。
在高性能的桌面环境中，A*算法运行良好，但在浏览器中却会导致明显的卡顿。接下来的两部分将详细介绍我是如何解决这个问题的。
第一部分：追踪移动目标
首先，我们暂时忽略玩家可以添加或移除障碍物的情况，专注于一个更简单的问题：即使玩家在移动，敌人也能找到通往玩家的路径。《Build + Brawl》中有几个特点，A*算法并没有充分利用：
- 玩家每次只能移动一格。随着玩家移动，路径不太可能发生剧烈变化，大多数变化只会发生在玩家附近的区域。每次玩家移动时都从头到尾重新计算路径是低效的。
- 所有敌人都朝着同一个目标移动。两个经过同一格子的敌人，即使时间不同，之后也应该遵循相同的路径（假设玩家没有移动）。将每个敌人视为独立的路径规划实体无法利用这一点，因为即使位置相似的敌人也会从头开始计算路径。
总的来说，似乎有机会进行大量的路径缓存，并在玩家移动时进行最小化的更新。我最终采用的方法受到了方向场的启发：
方向场显示了函数在每个点的斜率，也就是函数的方向。如果我们能为游戏中的敌人计算类似的东西呢？如果我们预先计算每个位置（x, y）的敌人应该朝哪个方向移动，那么路径规划的成本将与屏幕上敌人的数量无关，因为所有敌人都可以参考同一个预先计算的方向场。
为了构建路径规划方向场，我们首先将地图划分为大小相等的格子。每个格子将保存两个数据：
- 指向其相邻格子的指针。从格子X指向格子Y意味着“当敌人在格子X时，其通往玩家的最短路径会经过格子Y。”你可以将其视为方向场的“方向”。包含玩家的格子指向自己。
- 一个距离值，表示从该格子到玩家的路径长度。格子X的距离值为N意味着“从格子X到玩家的最短路径长度为N格。”包含玩家的格子的距离值为0。
如果我们为每个格子都计算了这些值，那么路径规划问题就解决了：敌人只需检查当前格子的指针，移动到相邻的格子，然后重复这个过程，直到到达玩家。
我们需要解决两个问题来获得这些值：
- 在地图初始化时为每个格子计算指针和距离。
- 随着玩家移动，更新格子的指针和距离。
我们可以通过假设地图上没有障碍物来简化问题（1）。这是我们空白的网格，玩家位于中心：
由于没有障碍物，敌人可以穿越任何格子，因此每个格子只需指向玩家：如果格子位于玩家下方，则指向上方的邻居；如果位于玩家上方，则指向下方；如果位于玩家左侧，则指向右侧；如果位于玩家右侧，则指向左侧。每个格子的距离值等于1加上它所指向的邻居的距离值。
不幸的是，我们还没有完成，因为玩家不会永远待在那个格子里。为了处理玩家移动，我们需要解决问题（2）。幸运的是，玩家每次只能移动一格。这意味着，当玩家移动时，每个格子都有一个“默认”选项：按照之前的路径移动，但当到达玩家之前的位置时，再从那里移动到玩家的新位置。这个默认选项为每个格子提供了相同的指针，并且距离值比之前增加了1（因为它必须到达玩家之前的位置，然后再移动一格）。我们首先将每个格子更新为使用默认路径，并将它们的距离值增加1：
但这个默认路径并不总是最短路径。例如，如果一个敌人在玩家下方，而玩家向下移动一格，敌人先移动到玩家之前的位置，然后再向下移动到玩家的新位置，这是低效的：
我们需要找到所有有新的最短路径的格子。首先，所有与玩家新位置相邻的格子都有新的路径：只需指向玩家！我们可以更新它们的指针，并将它们的距离值设置为1：
我们将这些更新后的格子放入一个队列（标记为黄色）。我们称这个队列为“卖家”，因为我们的格子将提供一些“交易”。我们逐个从队列中取出格子，取出的格子会向它的邻居提供交易：“指向我！然后你的距离值将只是1加上我的距离值！”
假设右边的格子先出队：
这个格子（灰色）向它的邻居（紫色）宣布：“如果你指向我，你到玩家的距离将只有2！”每个邻居格子会检查它们当前的距离值。如果提供的距离比它们当前的距离短，它们就会接受交易：邻居格子指向出队的格子，并将其距离值设置为1加上出队格子的距离值。
在这个例子中，唯一接受交易的格子是右边的格子，它之前指向玩家上方的格子：
更新后的邻居现在可以向它的邻居提供新的交易，因此它加入队列等待轮到自己。这个过程一直持续，直到卖家队列为空；现在，玩家下方的格子轮到它了。它向它的邻居提供交易——距离为2——但没有邻居感兴趣，因为它们的距离值已经是2：
接下来，左边的格子出队：
它左边的格子接受了交易并加入队列：
玩家上方的格子提出交易，但没有邻居接受：
耐心等待后，最右边更新后的格子出队。它的邻居都没有兴趣：
最后，最左边更新后的格子出队。同样，没有邻居接受交易：
队列现在为空，意味着每个格子都没有比当前选择更好的指针选项。此时，网格已经完全更新，每个格子再次知道从自己到玩家的最短路径。从底部角落开始的敌人现在有了更合理的路径：
正如我们在这里看到的，这种方法中许多格子根本不需要检查，从而避免了每次玩家移动时对整个网格的完全更新。
第二部分：添加和移除障碍物
在第一部分中，我们构建了一个方向场，指向玩家在地图上的移动位置。但我们假设没有障碍物阻挡敌人的移动；如果总是这样，我们可以让敌人直接直线移动向玩家！在《Build + Brawl》中，玩家可以在游戏过程中添加和移除障碍物。随着障碍物的添加和移除，通往玩家的最短路径可能会发生变化，因为路线可能会打开或被阻挡。例如，如果我们在玩家左侧放置一个障碍物，我们在第一部分中找到的路径就不再有效：
我们需要更新方向场，绕过障碍物：
首先，我们需要弄清楚如何处理新障碍物的添加。简单来说，每当放置一个障碍物时，我们可以从头重新计算每个格子的指针和距离。然而，直观上，大多数格子不需要更新：我们只需要更新那些最短路径最终经过现在不可通行的格子的格子。
为此，我们可以从不可通行的格子开始，逆向工作：找到所有指向它的格子，然后找到所有指向这些格子的格子，依此类推，直到找到所有最终经过不可通行格子的格子。然后，我们希望表明我们不再知道这些格子的最短路径，因此我们取消它们的指针，并将它们的距离值设置为无穷大。
在上面的例子中，有两个格子指向现在不可通行的格子：
因此，我们取消它们的指针；有一个格子指向其中一个：
因此，我们也取消它的指针：
完成后，我们有很多格子指向空。我们需要找到它们到玩家的新最短路径并重置它们的指针。我们从一个新的队列开始，包含所有未设置的格子。与第一部分中充满卖家的队列不同，这个队列充满了买家：队列中的每个格子都会在其邻居中寻找最佳交易。
只要队列不为空，我们就从队列中取出一个格子。我们从障碍物左侧的格子开始：
出队的格子找到距离值最短的邻居。出队的格子现在可以决定：我应该指向这个邻居吗？如果是，出队的格子的距离值将是1加上邻居的距离值。如果这比出队的格子当前的距离值短，那么它接受交易并相应地更新其指针和距离值。在这个例子中，最佳交易是向上移动，距离为4：
每当一个格子更新时，它的邻居会听到这个好交易并加入买家队列，以防它们通过新更新的邻居获得更短的路径：
接下来，障碍物下方的格子出队；它找到一条长度为2的路径：
右下角的格子出队。它可以选择一条长度为3的路径和一条长度为5的路径，因此它选择较短的路径：
队列中还有一些格子，但没有找到更好的交易，因此在遍历它们时没有添加任何内容。在过程结束时，所有路径被破坏的格子现在都有了新的指针，其他格子也有机会通过这些新路径进行规划。
结果
方向场方法在浏览器中没有产生明显的卡顿，允许游戏扩展到更多的敌人，最重要的是，解决这个问题非常有趣。希望这对遇到类似问题的人有所帮助！
