Key-Interval A*

新的Key-Interval A*算法显著加速网格寻路

研究人员开发了Key-Interval A* (KIA*)，这是一种旨在显著加速网格寻路的新型算法。该方法采用轻量级预处理，利用区间创建自由空间的压缩表示，重点关注表示结构变化的键区间。KIA*然后在此抽象图上进行类似A*的搜索，无需单元格级别的局部搜索即可有效地重建网格路径。实验表明，KIA*在各种基准测试中保持路径最优性并实现卓越的运行时性能，尤其是在结构化和游戏地图上。