我正在计算一个网格内的寻路，我已经建立了一个统一的网格。节点（三维网格中的单元）靠近我认为可访问的“可站立”曲面，它们用于我的路径查找为了获得更多的细节（比如能够找到小楼梯），我网格中的可访问单元数量已经相当大，在更大的建筑物中有几千个（每个网格单元为0.5x0.5x0.5 m，网格是具有真实世界尺寸的房间）。即使我只使用网格中的一小部分实际单元来寻找巨大的弹药，也会减慢算法的速度除此之外，它还可以使用加权曼哈顿距离启发式算法，通过网格找到正确的路径。
想象一下我的网格是这样的，网格就在里面（可以是更多或更少的立方体，但它总是立方的），但是寻路将不会在所有的小立方体上计算，只是一些标记为可访问的立方体（通常在网格的底部，但这取决于网格有多少层）。
我希望减少寻路的搜索空间…我已经研究过像hpa*这样的聚类算法和其他的聚类算法，比如markov，但是它们似乎都最适合用于节点图而不是网格。一个明显的解决方案是增加构建网格的小立方体的大小，但是我会在寻路过程中丢失很多细节，而且它不会那么健壮我怎么能把这些小立方体聚在一起呢？当我进行路径查找时，典型的搜索空间就是这样的（蓝色是可访问的，绿色是路径）：
正如你所看到的，有很多立方体要搜索，因为它们之间的距离很小！
不用担心，目前网格是一个非最佳的寻路解决方案。
有人知道如何减少网格中的立方体数量吗？在我减少空间之后，我将如何访问邻居：）现在它只查看最近的邻居，同时扩展搜索空间。
最佳答案
我想到了几个可能性。
高级寻路
首先，你的a*搜索可能会搜索整个问题空间。例如，你住在得克萨斯州的奥斯汀，想进入加拿大阿尔伯塔省某个地方的一座特殊建筑。一个简单的A*算法将在搜索墨西哥和美国之前搜索加拿大。
考虑创建第二层a*来解决这个问题例如，你首先会知道哪些州可以往返于加拿大，然后是哪些省可以到达阿尔伯塔省，然后是卡尔加里，最后是卡尔加里动物园。从某种意义上说，你从一个概述开始，然后用更详细的路径填充它。
如果有巨大的级别，例如skyrim，则可能需要在城镇（多个建筑）、地区（多个城镇）甚至国家（多个地区）之间添加寻路层如果你在做GPS系统，你甚至可能需要大陆。如果我们成为星际飞船，我们的宇宙飞船可能包含行星、扇区甚至星系的寻路层。
通过使用图层，可以显著缩小搜索区域，特别是在不同区域不使用相同坐标系的情况下（如果其中一个区域需要经纬度，另一个区域需要三维笛卡尔坐标，而下一个区域需要通过时间维度进行寻路，则很难估计一个a*探路者的距离。）
更有效的算法
在三维空间中，寻找有效的算法变得更加重要，因为在搜索时需要扩展更多的节点。Dijkstra搜索扩展x^2个节点将搜索x^3，x是开始和目标之间的距离一个4D游戏需要更高的寻路效率。
基于网格的寻路的好处之一是，您可以利用地形特性，如路径对称性。如果两条路径以不同的顺序由相同的运动组成，则不需要同时找到这两条路径。这是一个非常有效的算法Jump Point Search发挥作用的地方。
这里是a*（左）和jps（右）的并排比较。展开/搜索的节点显示为红色，墙显示为黑色：
注意，它们都找到了相同的路径，但是jps很容易搜索不到a*的十分之一。
到目前为止，我还没有看到一个正式的三维实现，但我已经帮助了另一个用户generalize the algorithm to multiple dimensions。
简化网格（图形）
在搜索过程中删除节点的另一种方法是在搜索之前删除它们例如，你真的需要在开放区域中的节点，在那里你可以信任一个更愚蠢的人工智能来找到它的路吗？如果要构建不更改的级别，请创建一个脚本，将它们解析为最简单的网格，其中只包含重要节点。
这实际上被称为“离线寻路”；基本上是在需要找到路径之前找到计算路径的方法如果您的级别保持不变，则每次更新级别时运行脚本几分钟将很容易减少PathFind时间的90%。毕竟，在事情变得紧急之前，你已经完成了大部分工作与你成长的城市相比，这就像试图在一个新城市周围找到自己的路；知道地标意味着你不需要地图。
跳转点搜索使用的“对称性破坏”的类似方法是由该算法的创建者daniel harabor介绍的。它们在其中一个his lectures中提到，并允许您预处理级别以仅在寻路网格中存储跳转点。
聪明的启发式
许多学术论文都指出a*的成本函数是f(x) = g(x) + h(x)，这并不能说明你可以使用其他函数，乘以成本函数的权重，甚至可以将领土热图或最近死亡人数作为函数来实现。这些可能会创建次优路径，但它们会大大提高搜索的智能性。当你的对手在最短路径上有一个瓶颈，并且很容易让任何人通过时，谁会在乎它呢？与其让人工智能变得愚蠢，不如确定它能安全地达到目标。
例如，你可能想阻止算法让敌人进入秘密区域，这样他们就不会向玩家透露这些秘密区域，这样他们的人工智能就好像不知道这些秘密区域所有你需要实现的是一个统一的成本函数，在这些“禁区”内的任何一点。在这样的游戏中，当玩家的路径变得过于昂贵时，敌人会放弃对其的追捕。另一个很酷的选择是“嗅”玩家最近去过的区域（因为许多算法不喜欢负成本，所以临时增加了未访问位置的成本）。
如果您知道哪些地方不需要搜索，但无法在算法逻辑中实现，只需简单地增加它们的成本就可以避免不必要的搜索有很多方法可以利用启发式来简化和通知您的寻路，但您最大的收益将来自跳跃点搜索。
编辑：跳转点搜索使用与A*相同的启发式方法隐式地选择寻路方向，因此您可以在很小的程度上实现启发式，但是它们的成本函数不是节点的成本，而是两个节点之间的旅行成本（A*通常搜索相邻的节点，因此节点的成本和前往该节点的成本之间的区别往往会被打破。）
摘要
尽管八叉树/四叉树/b-树在碰撞检测中很有用，但它们并不适用于搜索，因为它们基于图形的坐标而不是其连接来剖分图形。将图（词汇表中的网格）分层为超级图（区域）是一个更有效的解决方案。
希望我已经介绍了你会发现有用的东西。
祝你好运！
关于algorithm - 使用(部分)统一网格表示减少3D A *寻路中的节点数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37298294/