HPA与NavigationMesh相关资料

https://blog.csdn.net/tchenjiant/article/details/49510845

unity寻路——一劳永逸地解决寻路问题

译者：trcj

原文：http://www.ai-blog.net/archives/000152.html

通常我都会尽量避免对业内游戏产品或开发者们评头论足。

但这回我不得不破一次例。

我要讨论一些关于寻路的问题。为了证明这些问题至今仍然存在，我本着娱乐的精神制作了这个视频。

（译注：原视频缺失。）

所有片段都录自对应游戏的最新版本。

正如你所看到的，我们在构建一个健壮的寻路系统上还有很长的路要走，这些方方面面的问题甚至存在于一些顶级产品中。

并不是说这是当今游戏的通病。因为时下许多游戏确实拥有高质量的寻路，而且视频里的寻路大部分时间也表现良好。

但是仍有太多的游戏还在使用九十年代的方法。

（说明：为了录制之便，视频里出现的大多数游戏都属于PC平台角色扮演类型，因为当时我的电脑上就只安装了这些游戏。事实上，这些问题不限于任何类型或平台，甚至在主机平台的游戏里也多有出现。）

就我所知，大多数游戏使用路径点（waypoint graph）来实现寻路，它正是我们所碰到的这些问题的首因。

我认为路径点这一做法已经过时。这篇文章将阐述路径点的缺陷，同时通过五条主要论据介绍另一种更为可行的方法。

我曾经在八、九十年代使用过路径点寻路，当时我们面对诸多苛刻的技术限制，不得不舍弃很多东西。

现如今我们身处一个亿万美元的产业之中。面对的平台拥有多核处理器和与日俱增的海量内存，完全具备了实现一个合理的寻路系统的条件。

业内AI开发者中有一句话：“寻路已不是问题。”我们有针对各种寻路问题的各种解决办法，只不过不常使用而已。

而我想说的是，没有任何理由不一劳永逸地总结出一套放之四海而皆准的寻路方案。

为什么路径点不适合用于寻路

让我们来看看一个路径点系统究竟是什么样子。下面是魔兽世界里暴风城一隅。

图1. 魔兽世界暴风城一隅

这是该区域典型的路径点分布图。

图2. 同一区域的路径点分布图

现在我们介绍另一种实现方法，使用凸多边形来表示AI单位可以移动的范围。这种方式可以为AI提供大量的关于周围世界的额外信息，赋予其极大的灵活性。

这种寻路网格（navigation mesh）看上去是这个样子的：

图3. 使用寻路网格来标识的同一个区域

现在，我们来逐一列举路径点寻路的五大缺陷。

1. 一些游戏需求的路径点数目过大。

大型开放性区域通常需要散布大量的路径点来实现丰富的移动效果。

如果使用寻路网格，数个多边形足矣，且寻路更为快捷。

举个例子。下图展示了魔兽中的重镇“哈兰”。这是一大块开放型区域，NPC漫-游其间。为了方便演示，我移除了镇子中的旗帜、喷泉。

图4. 哈兰（略修改）

在路径点系统中，我们需要放置众多路径点以覆盖整个地区。即便如此，NPC仍会选择到一些曲曲折折的路径，除非我们继续添加比下图多得多的路径点。

图5. 覆遍路径点的哈兰

如果使用寻路网格，寥寥数个多边形即可描述整片区域。

图6. 寻路网格描述的哈兰

寻路网格使我们免于遍历众多的路径点，效率自然也提高很多。

2. 路径点让结果路径呈现“锯齿状”的弯折。

路径点把寻路单位限制在你创作的路径图中。这意味着单位始终沿着固定轨迹运动，并且几乎永远不会选择由A到B的最短路径，因为最优的直线路径很少能与路径图吻合。

这将导致不自然的寻路，寻路单位走动时会在一段锯齿状的曲折路径上忽左忽右。

以A至B取径点为例。

图7. 哈兰的两个路径点

这是按照前述路径点图得出的取径结果。

图8.由A至B使用路径点进行取径

可以看出，AI单位沿着黄色的路径行走时会经历数次弯折。

理想情况下，在我们选好路径后，可以做一些平滑处理，比如沿着路径点构建出一条Catmull-Rom样条曲线。

问题在于，路径点网络没有任何线路以外的信息，很难安全可信地对路径进行平滑调整。

试想一下在线路之外如何创建出一条平滑路径，而保证这条新路径不会引导你摔下索桥。

你或许会寻思是否有其他方法可循，不幸的是，在路径点的体制下，没有。如果我们冒险偏离路线哪怕一点，都有可能酿成坠崖或撞墙的惨剧。我们像路径点图一样对路线之外的东西一无所知。

所以安全起见，我们只好采用最悲观的策略，老老实实待在路线中。

如果使用寻路网格，取径结果则会大为不同：

图9. 在寻路网格中由AB漫-游

因为能够通过寻路网格得知寻路单位的安全活动范围，我们得以以任意方式调整取径结果，只要保证在网格之内即可。

（“哦，”你可能会说，“但是我可以在路径点图中开启更多的连接来达到平滑目的！如果需要NPC直行，我会打开镇中所有节点之间的连接。”

“但是这会导致数据指数级的爆炸，”我回应…“在这个例子里或许额外40或50连接已经足够。但是随着区域增大，你需要应付的节点间的连接数会直逼O(N^2)。”

“好吧，”你又说，“那样的话，我就把相邻三点围成的区域标记为‘开放’，这样AI就可以在这块区域中自由行动啦。”

“这正是一个多边形…而你刚创建了一个寻路网格，”我提醒道）。

寻路网格包含活动范围的精确大小，这意味着可以随意使用样条曲线平滑我们的路径，唯一要注意的就是保持曲线在网格内。

回到暴风城一例，下图分别展示了路径点取径（红色）和经过平滑处理的寻路网格取径（蓝色）结果。

图10. 路径点取径（红色）及经平滑处理的寻路网格取径（蓝色）

3. 路径点取径不允许路径修正，这使得动态避开障碍物变得极其困难。

路径点图缺少路线之外的数据，即便对于偏离分毫的区域也无法给出参考信息。

这意味着你不大可能通过修改路径来动态避开障碍物。

想象一个搁置在暴风城石桥上的沉重大木箱。

使用路径点寻路，我们将束手无策。如果箱子横在路线上，我们完全不知道从左边还是右边绕开它，如果箱子完全挡住了去路，我们也不知道是否应该改道。我们只能猜，盼望不要落入水中。

图11. 难以移动的大箱子横在桥当中

如果使用寻路网格，事情就好办多了。参照网格提供的活动范围，我们对箱子进行碰撞检测，调整路径绕过障碍，并可以始终保持在网格的安全区域中。

图12. 绕过箱子行进

当然，你也可以在路径点图中新加路径点来解决问题，直到你的路径点像野草一样稠密（而你的寻路性能像蜜糖一样粘滞）。

不知你意下如何，我倒是宁可在大多边形里运行我的A*算法，也不愿在数以百计的路径点中。

4. 路径点不支持寻路参数不同的多个单位。

寻路点不支持寻路单位具有不同的高度、宽度、旋转角度等寻路参数。这意味着你不能仅用一张统一的路径图来匹配游戏中所有的单位类型。

当说起AI寻路，一般我们会想到角色在游戏中漫-游。

但是AI系统需要控制多种寻路单位---坦克、飞机、轮船、气垫船、摩托车、兽人、地精、龙、伐木巨人、浮空游荡的生物、等等。很多时候，单位需要根据各自的大小、体型和运动参数来寻路。这些都需要寻路系统给予支持。

举个例子。设想沙漠中有一座掩体，四周环绕沙袋。

图13. 沙漠中的掩体

如果是一名士兵，他大可以沿着沙袋行走（下图红色箭头）。

但如果是一辆装甲坦克，就不得不与沙袋保持一定距离以避免碰撞（蓝色箭头）。

图14. 士兵和坦克沿沙袋行进的路线

使用路径点方法，你无法仅使用一张路径图同时处理两种情况。你需要为坦克和士兵各建一张图。如果加入一个摩托车单位，你还要再建一张。以后每加入一个不同单位你都得新建一张。

如果使用寻路网格，就简单多了。

图15. 覆盖掩体外围的寻路网格

注意上图中沙袋弯角处两个浅绿色拐点。假设士兵碰撞半径为1米，坦克碰撞半径为5米，仅使用同一个寻路网格我们也能容易地可以生成两种规格的路径。我们只需要计算一条顺着沙袋外沿的路径，然后移出来1米或5米即可。

图16. 覆盖掩体外围的寻路网格

再举一个例子。想象一名驾驶摩托车的士兵。不比徒步，摩托车很难在行驶时小角度转弯。

下图中，很明显摩托车手可以从当前位置驶进上方的房间（红线），却很难拐进右侧的过道中，因为角度刁钻（橙线）。不论何种寻路，都需要解决这个问题。

图17. 摩托车可以驶进上面房间（红线）却无法进入右边（橙线）

如果使用寻路网格，仍然简单。在寻路过程中我们只要留意转弯角度及距离，剔出那些短距离小角度的路径即可。

但使用路径点寻路，则基本上不大可能。因为无法使用徒步士兵的路径点，我们至少要为摩托车单独新建一张路径点图。而这种做法无疑导致冗余。

5. 路径点没有足够信息以支持AI除寻路以外的功能。

AI寻路其实不仅仅是为了漫-游，还需要从路径信息中得知在世界中如何移动。

游戏角色需要向寻路系统频繁查询：是否可以移动到这里？那里又如何？

如今游戏日渐演变出靠动画驱动的移动系统，开始允许动画师们通过动作控制角色的移动。这意味着如果要知道播放某个动画会产生什么后果，就需要知道动画结束时角色的位置，同时需要知道该位置是否恰巧在一堵墙中，或是掉出了悬崖，又或是关卡设计师不想让玩家进入的地方。

举个例子。下图中的剑客有四种位移：左右平移、后退、腾空20英尺后于8英尺开外落地。

图18. 一个包含四种位移动作的剑客

为了确保这个剑客做动作时不会一头扎进砖墙里，我需要预先根据碰撞网格，监测每个动作是否可行。

是的，你可以使用碰撞系统，它总能提供有用的信息，对于游戏世界中动态运动的物体，它通常也是知会AI相关信息的唯一办法。

但是碰撞检测代价高昂，如果你只关心静态物体，使用寻路网格无疑更为快捷。

另外，尽管我可以使用碰撞检测来计算角色和某点间是否有墙体遮挡，碰撞系统却无法告诉我剑客落地的位置是否正处于关卡设计师设定的禁区…这些只有通过寻路网格来判断。

如果上述内容仍不能让你信服，下面就让我通过一些关于路径点和寻路网格的问答，来打消你的疑虑吧。

Q & A

在寻路网格上取径是否会降低效率？

一点也不会。寻路网格其实也是一张图（graph），正如路径点图一样，它们的核心寻路过程也极为相似。不同之处在于寻路网格图中每一个节点都关联一个多边形。

下图展示了被图结构关联起来的多边形。

图19. 寻路网格的构架是一张图（红色）

A*算法始终运行在某个图结构中，无论它是方格、路径点图还是寻路网格图。

大多数情况下，寻路网格的性能和路径点接近。在使用寥寥数个节点覆盖一片区域时（例如图6），寻路网格性能提升显著。

寻路网格是否会耗费更多内存？

手法正确的话，不会。

寻路网格结构精简。总的来说，相比用于供渲染的模型网格，寻路网格不足其数分之一。相比碰撞模型，寻路模型关心的面数更少（它忽略墙、顶棚和其他脚力不可及的区域），而且往往使用更大号的多边形覆盖给定区域。

最坏情况下，寻路网格在每个图节点上使用的顶点数目也许会多于路径点图。但很多时候，如图6的哈兰，寻路网格要比路径点简洁许多。

大多数你展示的例子都出自角色扮演游戏。为什么没看到第一人称射击游戏存在这类问题？

很多FPS游戏都存在这个问题，不过缘于该类游戏本身玩法，此类问题不易被定位。

- 大多数AI都不会存活太久，难以发现其寻路缺陷。

- AI通常在你进入视线后即停下射击，寻路一般偏短。

- 许多单人FPS游戏中，AI少动，更倾向于原地朝你放枪。

- 当今许多FPS游戏提供AI队友，它们击毙敌方AI，不留任何长距离跑路的机会。

这里有一个半条命2的例子。通过一点小实验，不难发现梯子上的卫兵被限制在梯子中间直上直下的一条路线上，始终寻找着照面时刻射杀你的机会。

（译注：原视频再次缺失。）

如果你取消远程武器强制角色们近身肉搏---《光晕》里的星盟士兵，《先头部队》里的克隆杀手，或者《银河战士》里的浮游者---便会发现路径点突然成为了一个极其不堪的选择（这也是上述三个游戏使用寻路网格替代路径点的原因之一）。

瞧，我理解你的意思，但是设计师们需要在游戏里放置掩体点、巡逻路径等。这对我们游戏的AI来说必不可少。

当然！即便使用了寻路网格，你仍然可以这么做。

关键在于分离两个系统。你使用一个（寻路网格）来实现寻路及漫-游，使用另一个（设计师放置的这些点）告诉AI如何与游戏世界交互。

寻路网格不应该成为你使用任何系统的障碍，它只是简单地为丰富AI寻路提供了额外信息。

举个例子。我们设置了巡逻路径（紫色）让卫兵在城镇附近巡逻，为一个老家伙设置特殊的点让他每天到护城河边垂钓（红色）。掩体点方便暴风城的法师和术士们做FPS式的决斗时寻找掩护。

图20. 多种地标点（所有颜色）和寻路网格共存

好吧，但是放置寻路网格难道不会花费很多时间吗？

整体来说，手动放置寻路网格的工作量不会比设置路径点来的更繁重。两种体制下，放置寻路信息的时间都远远小于游戏中测试它们的时间。

以我的经验来说，放置一个中等规格的FPS关卡寻路网格需要花费1-3小时时间。

创建一个寻路网格编辑器相对比较简单。你要实现的功能就是放置顶点到游戏世界中，选取并将他们组织成多边形。你可以通过多边形邻边共享的顶点来决定寻路网格之间的连通性。

同时，有一些中间件可以帮你完成构建寻路网格和实时寻路的工作，例如xaitment， NavPower，PathEngine及Kynapse。这些解决方案都在日渐完善中。

如果我有一个爬楼梯的AI怎么办？我们的设计师可不喜欢为楼梯上每个台阶铺设一个寻路网格。

寻路网格只是标识了Ai可以行动的区域。它不能用于代替碰撞检测模型---你的NPC仍然需要碰撞系统来支持游戏中的碰撞。

你只需一个大矩形覆盖整个楼梯即可。

难道我不能给每个路径点赋一个半径信息，用圆来替代点？这样我就可以知道那些区域可以走动。这是正他们在robotics里的做法…

这个方法在某些场合行得通，但是游戏中的大多数区域遍布弯弯角角的街道和建筑。圆形无法和这些空间契合得很好，在覆盖该类型区域的便利性上较使用多边形相去甚远。

下方展示了在暴风城使用圆形扩展路径点进行寻路的示意图。

图21. 路径点扩展为圆

（小轶事：当我在《机甲战士4：复仇》小组工作时，我们发现在户外表现良好的圆形系统一旦应该用到城镇中立刻不再适用。我们最终解决了这个问题，但是得到一个教训：圆和城市水火不容！）

与此同时，留下边角也是很重要的。在图16的沙漠掩体一例中，我们使用寻路网格的边角针对士兵和坦克不同的形体、大小和运动参数生成不同的路径。圆图不支持边角，所以为不同单位创建不同路径也会变得相当困难。

我的游戏已经有了碰撞模型，我能用它作为寻路网格吗？

你可以试试，但这可不是个好主意。

碰撞模型被优化以便于碰撞、而非寻路。它往往包含比寻路需要的多得多的多边形，因此你的寻路算法会变得很慢。

例如，一条鹅卵石街道上的碰撞模型也许有1000个多边形，而只需一个寻路矩形。一个建筑顶棚的碰撞模型含50个多边形，但根本不需要寻路网格（因为我们的角色或许永远不会走上屋顶）。

同时，寻路网格的一部分优势在于它不仅仅告诉你寻路单位可以移动的范围；还告诉你设计师想让他们在哪里移动。

如果你让你的设计师手动创建寻路网格，他就可以标识某处“AI免进。这里拒绝任何单位进入，因为这个游戏设定如此。”这些信息是碰撞模型永远给不了的。

上面所有的例子里寻路网格似乎都是到2D空间的投射。我如何处理道路穿过桥洞，何时能够通过何时不能，或者多楼层建筑的情况？

寻路网格能优雅地解决这些问题。下面是魔兽世界沙塔斯寻路网格分布的样子（简便起见，我省略了桥远侧的部分网格）。

图22. 沙塔斯，覆盖桥上或穿行桥下的寻路网格

在寻路网格中，每个多边形通常存储有一个表示通行高度的参数。例如，穿行于桥下的多边形被标识为7英尺，那么那些高于7英尺的单位将无法从桥洞通过。

对于多楼层建筑的情况，每个楼层有独立的寻路网格，之间通过楼梯的寻路网格连接（当然，电梯略棘手）。

我不相信会有放之四海而皆准的办法。不同的游戏需求不同的寻路之法。

如果你正制作一个纯2D策略类游戏，那么一个基于方格的寻路算法更为合适，因为格子允许更快捷地访问任意地块。

否则，寻路网格真的是3D世界中解决寻路及地形物理的最佳方法。

我想在自己的游戏中实现寻路网格。有没有资料可以帮助我理清如何生成网格，如何在其上寻路，以及如何在游戏中优化它们？

我所知道的资料如下：

"Simplified 3D Movement and Pathfinding Using Navigation Meshes" by Greg Snook (Game Programming Gems)

"Polygon Soup for the Programmer's Soul: 3D Pathfinding" by Greg Hjelstrom and Patrick Smith (GamaSutra.com)

"Building a Near-Optimal Navigation Mesh" by Paul Tozour (AI Game Programming Wisdom)

"Efficient Navigation Mesh Implementation" by John C. O'Neill (Journal of Game Development, March 2004)

"Search Space Representations" by Paul Tozour (AI Game Programming Wisdom 2)

"A Fast Approach To Navigation Meshes" by Stephen White and Christopher Christensen (Game Programming Gems 3)

"Choosing a Relationship Between Path-Finding and Collision" by Thomas Young (Game Programming Gems 3)

"Improving on Near-Optimality: More Techniques for Building Navigation Meshes" by Fredrik Farnstrom (AI Game Programming Wisdom 3)

"Smoothing a Navigation Mesh Path" by Geraint Johnson (AI Game Programming Wisdom 3)

"Dynamically Updating a Navigation Mesh via Efficient Polygon Subdivision" by Paul Marden and Forrest Smith (AI Game Programming Wisdom 4)

"Intrinsic Detail in Navigation Mesh Generation" by Colt McAnlis and James Stewart (AI Game Programming Wisdom 4)

"Navigation Mesh Generation: An Empirical Approach" by David Hamm (AI Game Programming Wisdom 4)

"Navigation Mesh Generation in Highly Dynamic Worlds" by Ramon Axelrod (AI Game Programming Wisdom 4)

"Crowds in a Polygon Soup: Next-Gen Path Planning" by David Miles (http://www.navpower.com/gdc2006_miles_david_pathplanning.ppt)

注意：如果你有相关资料想在此列出，请邮件联系我。

实际有多少游戏成功应用了寻路网格？

这里有一个名单：

光晕2

光晕3

先头部队

反恐精英：起源

银河战士

银河战士2：回声

银河战士3：堕落

杰克与达斯特：旧世界的遗产

杰克2

杰克3

神秘海域：德雷克船长的宝藏

疤面煞星：掌握世界

…更多的例子枚不胜举。

看起来所有扮酷的同学都用了这个。

好吧，它或许对你适用，但是我们之前所有的游戏使用的都是路径点寻路，表现良好。

如大家所说，如果它还能用，就别去管它…而且你说的那些问题我们一个都还没碰到哩。

目光放长远点，想象一二十年以后的光景。

到那时，你认为你的游戏会不会包含众多不同的AI控制的不同角色，各自又有不同的体型、大小、运动参数？

玩家们会不会想要和他们一样聪明的AI伙伴？

你的游戏会不会比今天更庞大、更复杂、更具变化性？

你会不会同时拥有有数量众多的AI角色---多到简单的转向和规避障碍已经不足以满足AI间丰富高效的交互？

你的游戏会不会引入高仿真的物理系统，玩家们会不会随心所欲地使用物理和AI角色打成一片？

玩家们可不可以把游戏世界改造得面目全非？

会不会有AI在多人游戏中完全替代真实玩家？

二十年后的游戏会是什么样子我们无从得知，可以预见的是我们需要更高级的AI，虚拟角色们需要更多的数据来演绎环境，优化寻路，应对千变万化的游戏世界。

http://www.ufgame.com/findaipath.html

https://github.com/SebLague/Pathfinding/tree/master/Episode%2002%20-%20grid

https://github.com/DevonCrawford/A-Pathfinding-Visualization

https://danny0ner.github.io/Pathfinding-Optimization/

寻路优化

寻路是许多游戏的重要资源，BFS，DJikstra或A *等基本算法在某些游戏中可以正常工作，但在某些情况下，特别是在大型地图上，它们可能很慢，让你的游戏暂停一会儿直到它找到路径或减慢游戏速度。这使得它的优化变得如此重要，因为你希望你的程序或游戏尽可能快，以便将来可能扩展。

在本文档中，您将找到A的快速解释，对它的一些小优化，对从A算法派生的最常用优化的解释以及实现HPA算法的指南。

提醒A *算法

A *算法旨在找到从单个起始到单个目标节点的路径。该算法使用一个简单的算法来计算您的路径，该算法是目的地的距离。将已经行驶的和估计的距离加在一起，它首先扩展了最有希望的路径。由于它几乎检查每条路径以找到距离的路径，我们可以说它找到的路径几乎总是最优的。

正如我们在图像中看到的那样，从白色中心广场开始，A *搜索他周围的方块并沿着最近的方格到达目的地。当它找到目的地时，它返回每个方格的父节点之后的路径，即它们从中扩展的方形的父节点。

这是我们在实现A *算法时所做的事情：

找到最接近您的位置的节点并将其声明为start node并将其放在打开的列表中。

虽然打开列表中有节点：

从具有最小F分数的打开列表中选择节点。把它放在关闭的清单上（你不想再考虑它）。

对于不在关闭列表中的每个邻居（相邻小区）。

将其父级设置为当前节点。

计算G得分（从起始节点到该邻居的距离）并将其添加到打开列表中

通过将启发式添加到G值来计算F得分。

基本寻路优化

我们有很多方法可以优化寻路，对其进行微小的改动。它们的变化将使它更快，但不如概念优化那么快，这将在后面解释。此外，某些方法在某些情况下无法返回最佳搜索，但如果您的地图是间隔较大的地图而没有很多障碍，则它们是一个很好的实现。如果我们想要更快地完成路径寻找而不必对我们的算法进行大的更改，我们可以：•使用无序列表。我们每个循环必须做的事情之一是找到得分最低的节点。使用无序列表，我们不需要搜索该节点，因此它将位于第一个位置。

•使用贴图或堆而不是列表也会加速算法。迭代时这种数据结构更快，因此当您需要搜索节点时它将非常有用。你可以使用无序的地图和堆，所以第一个建议在这里也很有用。

•分离寻路。这意味着您的单位不需要一帧中的完整路径，因为它们不会在该帧中通过它。您可以为路径查找设置循环限制，因此如果找不到目标并到达目标，则保存它已关闭的最后一个节点，然后继续下一帧的路径。如果您的寻路循环限制太低，此方法可能会导致错误，因为如果找不到出路，它可能会在大的封闭区域上进行搜索。但是如果你确定你的地图没有冒这个风险并且你的循环限制是一个可接受的数字，它将帮助你寻找很多。

•节点中的变量is_open或is_close。您可以为节点创建一个变量，如果该节点位于打开或关闭的列表中，则该变量为true。有了这个，当你需要在列表中搜索一个节点时，你可以访问它，看看它是否只在该列表上查找该变量，而不是查看它在整个列表中的位置。这会减少您在NxN图块地图中打开的列表中的搜索，通过打开（N）打开（1）。

•在真实路径寻找之前执行较低级别的寻路。您可以预先计算分离节点的地图，并在需要查找路径时首先使用该地图。使用它，您将获得到目的地的分离节点的路径。当你有这个路径时，你可以开始在分离的帧中使用从一个节点到另一个节点的路径寻找，就像分离路径寻找但没有循环限制一样，你将路径到路径的第一个低级节点，然后等待下一帧继续到下一个节点的路径，直到找到目的地。

概念寻路优化

我们将概念优化称为优化，以改变寻路搜索节点的方式。路径寻找节点搜索方式的每一个小变化都可以根据您的地图分布或移动方式优化您的路径寻找。请注意，路径查找的某些概念优化将更好或更差，具体取决于地图更改的位置或是否为静态或取决于障碍物的位置。有一些很好的概念优化，但我们将讨论其中两个：HPA和JPS。

HPA

分层路径寻找基于预处理到目的地的较低级别路径寻找，较低级别将在群集中保留，其距离和彼此的最佳路径是预先计算的。一旦我们进行了较低级别的寻路，我们将使用其预先计算的最佳路径穿过每个群集并获得到目的地的快速路径。

正如我们在图像中看到的那样，网格在群集上划分，并且此群集具有将它们连接到其他群集的出口。一旦我们连接它们，我们就会在正确的图像中看到类似的东西，在那里我们可以看到到达另一个边缘的成本。这种预先计算的成本在选择最佳路径方面非常有用。

现在，让我们看一个我们在S中的例子，我们想要去G.这个算法很简单，我们只用簇做一个正常的a *，一旦我们有了路径，我们就用成本来自一个簇尽可能快地到下一个。

请记住，您可以使用自己的群集创建自己的网格，听起来很明显，但您可以根据地图的分布创建网格。使用自己的网格，您可以使一些群集更大，其他群集适合房间或地图的其他区域，这将阻止您在房间中进行较低级别的寻路，如果您可以在该房间中安装群集而不是2,3那个房间或更多集群。

利弊：

每种优化在某些情况下都比其他优化更好，让HPA预先计算距离和路径在您的地图始终更新的游戏中不会是最佳的，并且更改将使您的HPA再次重新计算路径和距离，如果更改将需要一些时间相当可观。您可以创建自己的网格这一事实是如此的神，因此它可以帮助您优化地图的同意区域。对于没有太多障碍的间隔地图，HPA不是最佳选择。这并不意味着它更糟糕，只是意味着其他优化如JPS在间隔区域获胜。

JPS

跳转点搜索算法的基础是扩展基数的起始节点，以达到无法继续扩展的区域。我们现在将解释它，但如果你认为这很简单，如果你可以用另一个节点访问该位置并且迭代的节点较少，为什么还要将节点添加到列表中？

与HPA不同的是，使用JPS，您无需预先计算任何内容，只需花费更少的时间来迭代打开和关闭列表。我们需要知道，JPS利用网格的规律性，这意味着如果我们有不同成本的地图的图块或区域，JPS会将它们作为统一成本网格，因为它看起来并不是所有节点所以它不相关。此外，通过利用规律性，不需要从每个图块的每个方向扩展，并且在开放和关闭列表上迭代许多节点，每个像A *这样的单元格。仅扫描瓷砖就足以检查附近是否有任何“有趣”，我们称之为跳跃点。现在我们将处理解释扫描过程，基本上我们如何扩展节点以及如何找到跳转点。

在进入JPS的算法之前，让我们来谈谈它的基础，邻居修剪：

节点x由其父节点展开，该节点用箭头引用。正如我们所看到的，可以检查所有节点在水平或对角线上进行搜索，如箭头所示，而不必为节点x传递。这意味着我们可以使用父节点检查所有这些节点，因此不需要x。现在让我们谈谈什么是强迫邻居：

强制邻居是无法从节点X扩展的节点，正如我们在图像中看到的那样，如果我们按照灰色-图块上的箭头，我们就无法到达突出显示的节点。我们无法从另一个节点到达的节点称为强制邻居。请记住，正在扩展的节点始终位于障碍物旁边，后面的磁贴将成为强制邻居。

JPS算法解释

我们从p（x）开始并开始在水平方向扩展节点。我们发现p（x）上方的区块被阻塞，因此我们找到第一个强制邻居X.我们停止扩展p（x）并开始扩展x。我们水平扩展X，因此它找到了Y.Y在它上面有一个被阻挡的区块，所以我们将Y标记为强制邻居，并且我们将无法将Z作为邻居标记为Z. 在这种情况下有两种可能性。当我们发现Y上方有一个阻塞的区块时，我们只将Z作为强制邻居并继续扩展Z，但是如果我们也添加Y，我们有一条直接路径，我们不必在X和之间进行寻路。 Z，因为这是我们不想做的事情。算法一直以这种方式继续。您可以先按顺序进行搜索。首先进行水平搜索，然后是垂直搜索，然后是对角线，这是正常的，

让我们使用对角线搜索来看这个JPS。我们从旁边的p（x）阻塞区块开始，我们接下来要做的是将X作为强制邻居。我们在垂直方向扩展p（x）但我们没有找到任何有趣的东西，所以我们传递给下一个邻居。我们开始扩展X，而我们扩展它时我们遇到与p（x）相同的问题我们有一个障碍物向下X所以我们添加一个强制邻居W，我们继续扩展X.如果我们继续扩展X对角线，我们将发现当我们在Y中扩展时，我们发现目标Z，所以我们将两者都添加为强制邻居，这样我们就可以获得一条简单的路径，并且我们创建了路径，因为我们找到了目标。

优点和缺点：

正如我们之前所说，在网格上有不同的成本对JPS不起作用，因此你有一个不同成本的网格，这不是你的最佳优化。由于地图间距越大，您所拥有的跳跃点越少，迭代速度越快。您不需要预先处理任何内容，地图可以改变您想要的方式，它不会影响JPS。

如果您不清楚JPS如何在这里工作，您可以通过网络查看A *，Djikstra，JPS和其他工作人员。是一个有用的网站，可以在您看到他们进行搜索时了解他们的工作对象。PathFinding.js

寻路优化实施

现在，我们将解释一个简单的表单，使用节点映射优化您的寻路。此方法基于退出已关闭列表而不是迭代打开列表创建节点映射，我们将检查节点是否已处于打开或关闭列表中。我们将从正常的Pathfinding开始。现在是设置地图的时刻，现在我们将创建具有地图大小的节点地图。

现在，通过这个节点数组，我们可以通过输入它在网格上的位置来访问地图中的每个节点，这在迭代时非常有用。有一次我们有节点映射，我们开始使用A *函数。我们要做的第一件事是用地图填充节点的地图，因此不会对它们进行评估，因为我们将使用std :: fill（第一项，最后一项，Node）;

*注意：size是地图的宽度+高度。接下来我们要做的是为我们的开放列表创建一个priority_queue。正如我们之前所说的那样，拥有优先级队列会加快队列的迭代速度，我们将始终在列表顶部放置得分最低的节点，这样我们就不需要搜索它了。

如果你不知道比较是什么，它是一个简单的结构，有一个运算符来比较节点的分数来组织它们。

下一步是创建一个FirstNode指针节点，该节点将信息保存在地图中并将其推送到打开列表。我使用DistanceTo函数来计算启发式距离。

注意* GetPathNode接收位置并返回节点映射的Pathnode的指针。

此时我们已准备好从while循环开始。我们将调整它以使用指向节点映射的指针并检查它们是否已经处于打开或关闭列表中。

我们将当前设置为地图中的最低得分节点，如果我们将其添加到关闭列表中，我们确实喜欢，但我们只将其设置为bool on_close为true。是时候找到邻居，看看他们是否已经被添加到列表中。

现在我们创建一个指向item节点的temp，它将为我们提供一个指向地图的指针，并检查它的bool以查看它是否已经像关闭列表或打开列表中那样被解决。这样做我们摆脱了A *所面临的最大问题，迭代列表以找到节点所在的id。其余的继续像普通A *一样，如果我们找到到该节点的较短路径，我们只需将其父节点设置为当前节点。*注意：CalculateFopt是一个计算g和h的函数，并根据距离是对角线还是直线来设置它。我们要做的最后一件事是，当我们找到目的地时，回溯节点直到我们找到第一个节点。

我们可以通过回拨到该位置并将该位置更新为其父级直到它没有父级来轻松完成。我们使用节点映射而不是列表完成了路径查找！

##优化的结论我一直在尝试在120x120路径上制作最难的路径，优化的路径确实需要最多20 ms，而正常的A *确实需要~200-600 ms

你可以在github下载项目（顶部的链接），然后试一试！

参考文献：

http://zerowidth.com/2013/05/05/jump-point-search-explained.html

http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter17_Pathfinding_Architecture_Optimizations.pdf

http://www.intelligence.tuc.gr/~robots/ARCHIVE/2015w/Projects/LAB51326924/jps.html

https://gamedevelopment.tutsplus.com/tutorials/how-to-speed-up-a-pathfinding-with-the-jump-point-search-algorithm-gamedev-5818

http://aigamedev.com/open/review/near-optimal-hierarchical-pathfinding/

https://qiao.github.io/PathFinding.js/visual/

https://github.com/Danny0ner/Pathfinding-Optimization

https://www.cs.upc.edu/~npelechano/Pelechano_HNAstar_prePrint.pdf

https://github.com/Rydra/HierarchicalPathfinder

https://github.com/hugoscurti/hierarchical-pathfinding

https://stackoverflow.com/questions/23743780/path-finding-with-multiple-levels

https://www.ocr.org.uk/administration/stage-4-results/calculating-a-level-a-star/

http://aigamedev.com/open/review/near-optimal-hierarchical-pathfinding/

https://en.wikipedia.org/wiki/Taxicab_geometry

https://gamedevelopment.tutsplus.com/tutorials/how-to-speed-up-a-pathfinding-with-the-jump-point-search-algorithm--gamedev-5818

https://www.hiveworkshop.com/threads/terrain-based-pathfinding.234615/

https://www.gamedev.net/forums/topic/172880-warcraft-3-pathfinding/

https://www.hiveworkshop.com/threads/pathfinding-in-warcraft3.224712/

https://www.codeofhonor.com/blog/the-starcraft-path-finding-hack

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。