在这篇文章中,我将介绍如何使用方向场(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:
接下来,左边的格子出队:
它左边的格子接受了交易并加入队列:
玩家上方的格子提出交易,但没有邻居接受:
耐心等待后,最右边更新后的格子出队。它的邻居都没有兴趣:
最后,最左边更新后的格子出队。同样,没有邻居接受交易:
队列现在为空,意味着每个格子都没有比当前选择更好的指针选项。此时,网格已经完全更新,每个格子再次知道从自己到玩家的最短路径。从底部角落开始的敌人现在有了更合理的路径:
![更新后的路径](https://blogger.googleusercontent.com/img/a/AVvXsEheK5UMw0HrdfCCn2x-crAaz6IiacI3YbjOv