使用（部分）统一网格表示减少 3D A* 寻路中的节点数
Reduce number of nodes in 3D A* pathfinding using (part of a) uniform grid representation
我正在计算一个网格内的寻路，我已经在周围构建了一个统一的网格。靠近我认为 "standable" 表面的节点（3D 网格中的单元格）我标记为可访问，它们用于我的寻路。为了获得大量细节（比如能够找到小楼梯），我的网格中 可访问 单元格的数量已经变得非常大，在较大的建筑物中有数千个。 （每个网格单元为 0.5x0.5x0.5 米，网格是具有真实世界尺寸的房间）。尽管我只使用网格中实际单元格的一小部分来进行寻路，但巨大的数量会减慢算法速度。除此之外，它工作正常并通过网格找到正确的路径，使用加权曼哈顿距离启发式。
想象一下我的网格看起来像那样并且网格在其中（可以是或多或少的立方体，但它总是立方体），但是不会在所有小立方体上计算寻路，只有少数标记为可访问（通常在网格的底部，但这取决于网格有多少层）。
我希望减少寻路的搜索 space...我研究了 HPA* 如何进行聚类以及其他聚类算法（如马尔可夫），但它们似乎都最适合与节点一起使用图形而不是网格。一个明显的解决方案是只增加构建网格的小立方体的大小，但那样我会在寻路中丢失很多细节并且它不会那么健壮。我如何将这些小立方体聚集在一起？这是我进行寻路时典型搜索 space 的样子（蓝色是可访问的，绿色是路径）：
如您所见，有很多立方体可供搜索，因为它们之间的距离非常小！
没关系，网格目前不是寻路的最佳解决方案。
有没有人知道如何减少我必须搜索的网格中立方体的数量，以及在减少 space 后如何访问邻居？ :) 现在它在扩展搜索时只查看最近的邻居 space。
我想到了几种可能性。
更高级别的寻路
首先是您的 A* 搜索可能正在搜索整个问题 space。例如，您住在德克萨斯州奥斯汀，想进入加拿大艾伯塔省某处的特定建筑物。一个简单的 A* 算法将搜索大量的墨西哥和美国，然后最终在加拿大搜索建筑物。
考虑创建第二层 A* 来解决这个问题。例如，您首先要找出要在哪些州之间旅行才能到达加拿大，然后是哪些省份才能到达艾伯塔省，然后是卡尔加里，然后是卡尔加里动物园。从某种意义上说，您从概述开始，然后用更详细的路径填充它。
如果您有巨大的关卡，例如天际，您可能需要在城镇（多个建筑物）、地区（多个城镇）甚至国家（多个地区）之间添加寻路层。如果您要制作 GPS 系统，您甚至可能需要大陆。如果我们成为星际飞船，我们的 space 飞船可能包含行星、星区甚至星系的寻路层。
通过使用图层，您可以帮助显着缩小搜索范围，尤其是在不同区域不使用相同坐标系的情况下！ （如果其中一个区域需要经纬度，另一个区域需要 3d 笛卡尔坐标，而下一个区域需要通过时间维度进行寻路，则很难为一个 A* 探路者估计距离。）
更高效的算法
寻找有效的算法在 3 个维度上变得更加重要，因为在搜索时有更多的节点需要扩展。扩展 x^2 个节点的 Dijkstra 搜索将搜索 x^3，其中 x 是起点和目标之间的距离。 4D 游戏需要更高的寻路效率。
基于网格的寻路的好处之一是您可以利用路径对称性等地形特性。如果两条路径由不同顺序的相同动作组成，则您不需要同时找到它们。这是称为 Jump Point Search 的非常有效的算法发挥作用的地方。
这是 A*（左）和 JPS（右）的并排比较。 Expanded/searched 节点显示为红色，墙壁显示为黑色：
请注意，他们都找到了相同的路径，但 JPS 轻松搜索不到 A* 搜索结果的十分之一。
截至目前，我还没有看到官方的3维实现，但我已经帮助了另一个用户generalize the algorithm to multiple dimensions。
简化的网格（图表）
另一种在搜索过程中删除节点的方法是在搜索之前删除它们。例如，你真的需要开阔区域的节点，在那里你可以信任一个更愚蠢的人工智能来找到它的方式吗？如果您正在构建不会改变的关卡，请创建一个脚本，将它们解析为最简单的网格，该网格仅包含重要节点。
这个其实叫'offline pathfinding'；基本上是在需要找到路径之前找到计算路径的方法。如果您的关卡保持不变，运行 每次更新关卡时几分钟的脚本将轻松减少 90% 的寻路时间。毕竟，在它变得紧急之前，您已经完成了大部分工作。与您在其中长大的城市相比，这就像在一个新城市中寻找出路一样；了解地标意味着您真的不需要地图。
跳跃点搜索使用的 'symmetry-breaking' 类似方法由算法的创建者 Daniel Harabor 介绍。它们在 his lectures 之一中提到，并允许您预处理关卡以在寻路网格中存储 仅 个跳跃点。
聪明的启发式
很多学术论文都说A*的cost function是f(x) = g(x) + h(x)，这并不明显，你可以使用其他函数，乘以cost functions的权重，甚至实现heatmaps领土或最近的死亡作为功能。这些可能会创建次优路径，但它们会极大地提高搜索的智能性。当你的对手有一个阻塞点并且很容易派遣任何通过它的人时，谁在乎最短路径？最好确定 AI 可以安全地到达目标，而不是让它变得愚蠢。
例如，您可能希望阻止算法让敌人进入秘密区域，以免他们将这些区域透露给玩家，并且让他们的 AI 似乎没有意识到这些区域。要实现这一点，您需要为那些 'off-limits' 区域内的任何点使用统一的成本函数。在这样的游戏中，敌人会在路径变得太昂贵后简单地放弃追捕玩家。另一个很酷的选择是 'scent' 玩家最近去过的区域（通过暂时 增加 未访问位置的成本，因为许多算法不喜欢负成本）。
如果您知道哪些地方不需要搜索，但无法在您的算法逻辑中实现，只需增加它们的成本即可避免不必要的搜索。有很多方法可以利用启发式方法来简化和告知您的寻路，但您最大的收获将来自跳跃点搜索。
编辑：跳跃点搜索使用与 A* 相同的启发式算法隐式选择寻路方向，因此您可以在较小程度上实施启发式算法，但它们的成本函数不是节点的成本，而是相反，在 两个节点之间旅行的成本。 （A* 通常搜索相邻节点，因此节点成本和前往该节点的成本之间的区别往往会被打破。）
总结
虽然 octrees/quad-trees/b-trees 在碰撞检测中很有用，但它们不适用于搜索，因为它们根据坐标分割图形；不在其连接上。将图表（词汇表中的网格）分层为超级图表（区域）是一种更有效的解决方案。
希望我已经涵盖了您会觉得有用的任何内容。
祝你好运！
我正在计算一个网格内的寻路，我已经在周围构建了一个统一的网格。靠近我认为 "standable" 表面的节点（3D 网格中的单元格）我标记为可访问，它们用于我的寻路。为了获得大量细节（比如能够找到小楼梯），我的网格中 可访问 单元格的数量已经变得非常大，在较大的建筑物中有数千个。 （每个网格单元为 0.5x0.5x0.5 米，网格是具有真实世界尺寸的房间）。尽管我只使用网格中实际单元格的一小部分来进行寻路，但巨大的数量会减慢算法速度。除此之外，它工作正常并通过网格找到正确的路径，使用加权曼哈顿距离启发式。
想象一下我的网格看起来像那样并且网格在其中（可以是或多或少的立方体，但它总是立方体），但是不会在所有小立方体上计算寻路，只有少数标记为可访问（通常在网格的底部，但这取决于网格有多少层）。
我希望减少寻路的搜索 space...我研究了 HPA* 如何进行聚类以及其他聚类算法（如马尔可夫），但它们似乎都最适合与节点一起使用图形而不是网格。一个明显的解决方案是只增加构建网格的小立方体的大小，但那样我会在寻路中丢失很多细节并且它不会那么健壮。我如何将这些小立方体聚集在一起？这是我进行寻路时典型搜索 space 的样子（蓝色是可访问的，绿色是路径）：
如您所见，有很多立方体可供搜索，因为它们之间的距离非常小！ 没关系，网格目前不是寻路的最佳解决方案。
有没有人知道如何减少我必须搜索的网格中立方体的数量，以及在减少 space 后如何访问邻居？ :) 现在它在扩展搜索时只查看最近的邻居 space。
我想到了几种可能性。
更高级别的寻路
首先是您的 A* 搜索可能正在搜索整个问题 space。例如，您住在德克萨斯州奥斯汀，想进入加拿大艾伯塔省某处的特定建筑物。一个简单的 A* 算法将搜索大量的墨西哥和美国，然后最终在加拿大搜索建筑物。
考虑创建第二层 A* 来解决这个问题。例如，您首先要找出要在哪些州之间旅行才能到达加拿大，然后是哪些省份才能到达艾伯塔省，然后是卡尔加里，然后是卡尔加里动物园。从某种意义上说，您从概述开始，然后用更详细的路径填充它。
如果您有巨大的关卡，例如天际，您可能需要在城镇（多个建筑物）、地区（多个城镇）甚至国家（多个地区）之间添加寻路层。如果您要制作 GPS 系统，您甚至可能需要大陆。如果我们成为星际飞船，我们的 space 飞船可能包含行星、星区甚至星系的寻路层。
通过使用图层，您可以帮助显着缩小搜索范围，尤其是在不同区域不使用相同坐标系的情况下！ （如果其中一个区域需要经纬度，另一个区域需要 3d 笛卡尔坐标，而下一个区域需要通过时间维度进行寻路，则很难为一个 A* 探路者估计距离。）
更高效的算法
寻找有效的算法在 3 个维度上变得更加重要，因为在搜索时有更多的节点需要扩展。扩展 x^2 个节点的 Dijkstra 搜索将搜索 x^3，其中 x 是起点和目标之间的距离。 4D 游戏需要更高的寻路效率。
基于网格的寻路的好处之一是您可以利用路径对称性等地形特性。如果两条路径由不同顺序的相同动作组成，则您不需要同时找到它们。这是称为 Jump Point Search 的非常有效的算法发挥作用的地方。
这是 A*（左）和 JPS（右）的并排比较。 Expanded/searched 节点显示为红色，墙壁显示为黑色：
请注意，他们都找到了相同的路径，但 JPS 轻松搜索不到 A* 搜索结果的十分之一。
截至目前，我还没有看到官方的3维实现，但我已经帮助了另一个用户generalize the algorithm to multiple dimensions。
简化的网格（图表）
另一种在搜索过程中删除节点的方法是在搜索之前删除它们。例如，你真的需要开阔区域的节点，在那里你可以信任一个更愚蠢的人工智能来找到它的方式吗？如果您正在构建不会改变的关卡，请创建一个脚本，将它们解析为最简单的网格，该网格仅包含重要节点。
这个其实叫'offline pathfinding'；基本上是在需要找到路径之前找到计算路径的方法。如果您的关卡保持不变，运行 每次更新关卡时几分钟的脚本将轻松减少 90% 的寻路时间。毕竟，在它变得紧急之前，您已经完成了大部分工作。与您在其中长大的城市相比，这就像在一个新城市中寻找出路一样；了解地标意味着您真的不需要地图。
跳跃点搜索使用的 'symmetry-breaking' 类似方法由算法的创建者 Daniel Harabor 介绍。它们在 his lectures 之一中提到，并允许您预处理关卡以在寻路网格中存储 仅 个跳跃点。
聪明的启发式
很多学术论文都说A*的cost function是f(x) = g(x) + h(x)，这并不明显，你可以使用其他函数，乘以cost functions的权重，甚至实现heatmaps领土或最近的死亡作为功能。这些可能会创建次优路径，但它们会极大地提高搜索的智能性。当你的对手有一个阻塞点并且很容易派遣任何通过它的人时，谁在乎最短路径？最好确定 AI 可以安全地到达目标，而不是让它变得愚蠢。
例如，您可能希望阻止算法让敌人进入秘密区域，以免他们将这些区域透露给玩家，并且让他们的 AI 似乎没有意识到这些区域。要实现这一点，您需要为那些 'off-limits' 区域内的任何点使用统一的成本函数。在这样的游戏中，敌人会在路径变得太昂贵后简单地放弃追捕玩家。另一个很酷的选择是 'scent' 玩家最近去过的区域（通过暂时 增加 未访问位置的成本，因为许多算法不喜欢负成本）。
如果您知道哪些地方不需要搜索，但无法在您的算法逻辑中实现，只需增加它们的成本即可避免不必要的搜索。有很多方法可以利用启发式方法来简化和告知您的寻路，但您最大的收获将来自跳跃点搜索。
编辑：跳跃点搜索使用与 A* 相同的启发式算法隐式选择寻路方向，因此您可以在较小程度上实施启发式算法，但它们的成本函数不是节点的成本，而是相反，在 两个节点之间旅行的成本。 （A* 通常搜索相邻节点，因此节点成本和前往该节点的成本之间的区别往往会被打破。）
总结
虽然 octrees/quad-trees/b-trees 在碰撞检测中很有用，但它们不适用于搜索，因为它们根据坐标分割图形；不在其连接上。将图表（词汇表中的网格）分层为超级图表（区域）是一种更有效的解决方案。
希望我已经涵盖了您会觉得有用的任何内容。 祝你好运！