用目标边界加速 A*

英文原文：http://www.gameaipro.com/GameAIPro3/GameAIPro3_Chapter22_Faster_A_Star_with_Goal_Bounding.pdf

简介

目标边界是一种寻路优化技术，可以在网格上将 A* 的速度提高大约八倍（Rabin 和 Sturtevant 2016），但它适用于任何图形搜索空间，包括航点图或导航网格（导航网格）。目标边界本身不是一种搜索算法，而是一种修剪搜索空间的方法，从而大大减少了寻找目标时需要考虑的节点数量。这是通过离线预处理搜索空间并使用预先计算的数据来实现的，以避免探索许多不通向目标的节点。

本章将介绍目标边界概念，介绍运行时代码，然后展示必要的预处理步骤。然后，我们将讨论实验数据，这些数据显示了标准 A* 实现的有效加速。

目标边界约束

目标边界有三个约束，限制它是否适合在你的游戏中使用：