寻路算法 找到NPC最好的行走路径

引言

寻路，本质上是要解决一个看似简单的问题：给定游戏世界中的点A和点B，AI该如何智能地从A移动到B？这个问题的复杂性在于，A和B之间往往存在大量可能的路径，但只有一条是最佳路径。仅仅找到一条从A到B的有效路径是远远不够的，理想的寻路算法需要遍历所有可能的情况，然后从中比较出最优路径。

本文将围绕搜索空间的表示、可接受的启发式算法以及贪婪最佳优先算法展开深入探讨。

搜索空间的表示

最简单的寻路算法设计是将图作为数据结构。图由多个节点组成，任意相邻节点之间通过边连接。在内存中表示图有多种方式，其中最简单的是邻接表。在邻接表表示中，每个节点包含一系列指向其相邻节点的指针，图中的所有节点可以存储在标准的数据结构容器中。下图展示了简单图的可视化形象和数据表示。

在游戏中实现寻路的第一步是将游戏世界用图来表示，常见的方法有以下几种：

• 正方形或六边形格子分区：将游戏世界划分为一个个正方形（或六边形）的格子，相邻节点即为格子中相邻的正方形。这种方法在回合制策略游戏中较为流行，例如《文明》和XCOM。
• 路点（Waypoints）：在实时动作游戏中，NPC通常不会按照网格一格一格地移动，因此主流游戏常使用路点或导航网格。路点最早由id Software在20世纪90年代早期的第一人称射击游戏（FPS）中引入。关卡设计师可以在游戏世界中设置AI能够到达的位置，这些位置被视为图中的节点，边可以自动生成。例如，设计师手动组合节点时，系统会自动判断两点之间是否有障碍，若无障碍则在两点间生成边。然而，路点存在明显缺点，AI只能在节点和边的位置移动，即使路点组成三角形，也不能保证三角形内部可通行。这会导致游戏世界中要么存在大量不可到达区域，使AI行为显得不自然；要么需要大量路点，增加寻路算法的计算时间。因此，使用路点时需要在性能和精确度之间进行权衡。
• 导航网格（Navigation Mesh）：导航网格是另一种解决方案，图中的节点实际上是凸多边形，相邻节点为相邻的凸多边形。这种表示方式可以用较少数量的凸多边形表示整个游戏世界区域，从而减少图中的节点数量。在导航网格中，凸多边形内部的任意位置都被认为是可通行的，这使得AI有更多的移动空间，寻路算法能够返回更自然的路径。此外，导航网格还具有其他优点，例如在处理不同大小的角色时，使用路点可能需要为每个角色创建一份图，而导航网格只需一份，并能高效计算不同角色可到达的区域。而且，导航网格可以完全自动生成，这也是近年来使用路点的游戏越来越少的原因。例如，虚幻引擎早期使用路点作为寻路空间的表示，如《战争机器》；但近年来，虚幻引擎已改用导航网格，如《战争机器3》，这一转变促使行业内大量采用导航网格。

需要注意的是，寻路空间的表示方式并不完全影响寻路算法的实现。为了简化问题，后续例子将使用正方形格子，但寻路算法并不关心数据是表示为正方形格子、路点还是导航网格。

可接受的启发式算法

所有寻路算法都需要一种数学方法来估算某个节点是否值得选择。大多数游戏会使用启发式函数，用ℎ(x)表示，用于估算从某个位置到目标位置的开销。理想情况下，启发式函数的结果越接近真实开销越好。如果其估算值始终小于或等于真实开销，则该启发式函数是可接受的；若高估了实际开销，寻路算法可能无法找到最佳路径。对于正方形格子，常见的启发式计算方法有以下两种：

• 曼哈顿距离（Manhattan Distance）：曼哈顿距离是一种在大都市中估算城市距离的方法。例如，某个建筑可能距离当前位置有5个街区远，但实际可能没有一条长度刚好为5个街区的路。曼哈顿距离假设不能沿对角线方向移动，因此只有在这种情况下才能使用该启发式函数。如果允许对角线移动，曼哈顿距离会经常高估真实开销。在2D格子中，曼哈顿距离的计算公式如下：（此处应补充具体公式）
• 欧几里得距离（Euclidean Distance）：欧几里得距离使用标准距离公式估算直线路径。与曼哈顿距离不同，欧几里得距离可用于其他寻路表示中计算启发式函数，如路点或导航网格。在2D格子中，欧几里得距离的计算公式为：（此处应补充具体公式）

贪婪最佳优先算法

在了解了启发式函数后，我们可以实现一个相对简单的算法：贪婪最佳优先算法。贪婪算法是指在每一步决策中，不考虑长期规划，只选择当前看起来最优的答案。在贪婪最佳优先算法的每一步，算法会检查所有相邻节点，并选择启发式开销最低的节点。

虽然这种方法看似合理，但贪婪最佳优先算法通常只能得到次优路径。例如，在下图中，绿色正方形是起始节点，红色正方形是目标节点，灰色正方形表示不可穿越区域，箭头表示贪婪最佳优先算法所选择的路径。可以看到，路径中存在不必要的向右移动，因为在当时该节点的启发式开销最低。理想的路径应该一开始就向下走，但这需要一定的规划能力，而贪婪算法恰恰缺乏这种能力。大多数游戏需要比贪婪最佳优先算法更优的寻路方案，但后续的寻路算法都基于贪婪最佳优先算法，因此我们需要先理解贪婪算法的实现。

节点数据结构

为了实现贪婪最佳优先算法，我们需要定义每个节点所需存储的数据。除了图的相邻信息外，还需要额外的数据：

class Node:
def __init__(self):
self.parent = None  # 用于跟踪当前访问节点的父节点
self.h = 0.0  # 存储节点的ℎ(x)值

parent成员变量用于跟踪当前访问节点的父节点，在不同编程语言中，它可能是指针或引用。其作用是构建链表，从终点回溯到起点，算法完成后，通过遍历该链表可得到最终路径。浮点数h存储节点的ℎ(x)值，算法在选择节点时会倾向于选择h值最小的节点。

开放集合和封闭集合

算法还需要两个用于临时存储节点的容器：开放集合和封闭集合。

• 开放集合（Open Set）：存储当前需要考虑的所有节点。由于需要频繁查找最低ℎ(x)值的节点，开放集合可以使用类似于二叉堆或优先级队列的容器。
• 封闭集合（Closed Set）：包含所有已经被算法估值的节点。一旦节点进入封闭集合，算法将不再对其进行考虑。为了提高查找节点是否存在于封闭集合的效率，可使用搜索时间复杂度优于O(n)的数据结构，如二叉搜索树。

算法实现

以下是贪婪最佳优先算法的主要实现步骤：

# 初始化数据
currentNode = startNode
closedSet = set()
openSet = PriorityQueue()  # 假设使用优先级队列实现开放集合
closedSet.add(currentNode)

while True:
# 遍历当前节点的所有相邻节点
for n in get_adjacent_nodes(currentNode):
if n in closedSet:
continue
n.parent = currentNode
if n not in openSet:
compute_h(n)  # 计算节点n的ℎ(x)值
openSet.put(n, n.h)  # 将节点n加入开放集合

# 如果开放集合为空，寻路失败
if openSet.empty():
break

# 从开放集合中选择ℎ(x)值最小的节点
currentNode = openSet.get()
closedSet.add(currentNode)

# 如果当前节点为目标节点，退出循环
if currentNode == endNode:
break

# 构造最终路径
path = []
node = endNode
while node is not None:
path.append(node)
node = node.parent
path.reverse()

算法分析

贪婪最佳优先算法虽然简单，但通常只能得到次优路径。其主要问题在于缺乏长期规划能力，只关注当前步骤的最优选择。然而，后续的寻路算法大多基于该算法进行改进，因此理解贪婪最佳优先算法是进一步学习寻路算法的基础。

综上所述，本文介绍了寻路算法中搜索空间的表示方法、可接受的启发式算法以及贪婪最佳优先算法。通过对这些内容的深入理解，我们可以为后续学习更复杂的寻路算法打下坚实的基础。