JPSPlusWithGoalBounding

JPSPlusWithGoalBounding JPS+ 与目标约束 (Goal Bounding) 此项目实现了使用 JPS+ 与目标约束的 2D 网格路径搜索。JPS+ 是 Jump Point Search 路径搜索算法的优化预处理版本。目标约束是一种节点剪枝路径搜索技术。目标约束概念最初由 Steve Rabin 在 2015 年 1 月提出，并于 2015 年 3 月在旧金山举办的 GDC AI Summit 讲座 "JPS+: 比 A* 快 100 倍" 中首次向公众展示。此演示可在 www.gdcvault.com 上查看，PowerPoint 幻灯片属于本项目的一部分。

目标边界是一种节点剪枝技术,可大大加快路径搜索速度。目标边界是计算和存储每个节点边的轴对齐边界框的概念,该边界框包含通过该边可最优到达的所有节点。在运行时,如果目标节点包含在该边的轴对齐边界框中,则只会探索该边(相邻节点)。目标边界可应用于任何搜索空间(网格、图形、NavMesh 等),使用任何搜索算法(Dijkstra、A*、JPS+ 等),并且搜索空间可以是单向的,且节点之间的成本不均匀。使用目标边界的折衷方案是,必须在离线环境中对目标边界数据进行预处理,耗时为 O(n^2),因此无法支持搜索空间的动态运行时修改(添加或删除边/墙)。目标边界需要线性存储数据,O(n),与搜索空间相关(通常每个节点边有 4 值,网格表示法每个节点有 8 个边,总共为 32 值)。

JPS+ 是由 Steve Rabin 在 2014 年 6 月 Harabor 和 Grastien 在 ICAPS 上发布之前一个月独立发明的。关于 JPS+ 的描述可以在 CRC Press 出版的《Game AI Pro 2》一书中找到（2015 年 4 月）。JPS+ 是 Jump Point Search 的优化预处理版本。JPS+ 是一种节点剪枝技术，类似于 Goal Bounding，但这两种技术彼此是互补的，它们以不同的方式剪枝节点。JPS+ 仅适用于具有均匀成本的网格搜索空间。由于 JPS+ 的预处理，搜索