路径规划是寻路的重要优化思想，在了解路径规划之前必须先了解基本的寻路算法

可参考：https://www.cnblogs.com/KillerAery/p/9231511.html

使用路径点（Way Point）作为节点

实际上A*寻路算法，对于图也是适用的，实现只要稍微改一下。
大部分讨论A*算法使用的是网格点（也就是简单的二维网格），但是这种内存开销往往比较大。

而预先设好路径点，而不是使用网格来当作节点，则可以减少节点数量，顺带也就减少了寻路的运算速度开销。

（如图，使用了路径点作为节点）

此外路径点的使用，也能使路径相比网格路径更加平滑。

洪水填充算法创建路径点

倘若一个地图过大，开发人员手动预设好路径点+路径连接的工作就比较繁琐，而且很容易有错漏。
这时可以使用洪水填充算法来自动生成路径点，并为它们链接。

算法步骤：
1.以任意一点为起始点，往周围八个方向扩展点（不能通行的位置则不扩展）

2.已经扩展的点（在图中被标记成红色）不需要再次扩展，而扩展出来新的点继续扩展

3.直到所有的点都被扩展过，此时能得到一张导航图

//洪水填充法:从一个点开始自动生成导航图
void generateWayPoints(int beginx, int beginy, std::vector<WayPoint>& points) {
    //需要探索的点的列表
    std::queue<WayPoint*> pointsToExplore;
    //生成起点，若受阻，不能生成路径点，则退出
    if (!canGeneratePointIn(beginx, beginy))return;
    points.emplace_back(WayPoint(beginx, beginy));
    //扩展距离
    float distance = 2.3f;
    //预先写好8个方向的增值
    int direction[8][2] = { {1,0}, {0,1}, {0,-1}, {-1,0}, {1,1}, {-1,1}, {-1,-1},{1,-1} };
    //以起点开始探索
    WayPoint* begin = &points.back();
    pointsToExplore.emplace(begin);
    //重复探索直到探索点列表为空
    while (!pointsToExplore.empty()) {
        //先取出一个点开始进行探索
        WayPoint* point = pointsToExplore.front();
        pointsToExplore.pop();
        //往8个方向探索
        for (int i = 0; i < 8; ++i) {
            //若当前点的目标方向连着点，则无需往这方向扩展
            if (point->pointInDirection[i] == nullptr) {
                continue;
            }
            auto x = point->x + direction[i][0] * distance;
            auto y = point->y + direction[i][1] * distance;
            //如果目标位置受阻，则无需往这方向扩展
            if (!canGeneratePointIn(x, y)) {
                continue;
            }
            points.emplace_back(WayPoint(x, y));
            auto newPoint = &points.back();
            pointsToExplore.emplace(newPoint);
            //如果当前点能够无障碍通向目标点，则连接当前点和目标点
            if (canWalkTo(point, newPoint)) {
                point.connectToPoint(newPoint);
            }
        }
    }
}

自动生成的导航图可以调整扩展的距离，从而得到合适的节点和边的数量。

使用导航网（Navigation Mesh）作为节点

导航网将地图划分成若干个凸多边形，每个凸多边形就是一个节点。

（使用凸多边形，是因为凸多边形边上的一个点走到另外一点，不管怎么走都不会走出这个多边形。而凹多边形可能走的出外面。）

使用导航网更加可以大大减少路径点和搜寻所需的计算量，同时也使路径更加自然。

区域分割

区域分割有点类似于导航网，但是它属于更高层次的分割。
即完整地图分割成若干个区域，一个区域又可以分割成若干个导航网的凸多边形。

区域分割也不仅可以使用在路径规划上，也可以利用记录区域信息达到很多目的。
例如：AI在感知敌人的时候，可以通过区域分割，过滤掉本区域外的所有敌人，只对本区域的所有敌人作感知测试。

常用的区域分割方法有手动分割区域和使用四叉树（或八叉树）来分割区域。

四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。
它将已知范围的空间等分成四个相等的子空间，如此递归下去，直至树的层次达到一定深度或者满足某种要求后停止分割。

//示例：一个四叉树节点的简单结构
struct QuadtreeNode {
  Data data;
  QuadtreeNode* children[2][2];
  int diliverX;  //表示这个区域的划分长度
};

//示例：找到x,y位置对应的四叉树节点（共2层）
//通过diliver来将x,y归纳为0或1的值，从而索引到对应的子节点。
int diliver = root.diliver;
int diliverX = x / diliver;
int diliverY = y / diliver;
QuadtreeNode* n1 = root.children[diliverX][diliverY];
//如果归纳为1的值，还需要减去该划分长度，以便进一步划分
x -= diliverX ? diliver : 0;
y -= diliverY ? diliver : 0;
//再执行类似上一操作
diliver = n1.diliver;
diliverX = x / diliver;
diliverY = y / diliver;
QuadtreeNode* n2 = n1.children[x / diliver][y / diliver];
x -= diliverX ? diliver : 0;
y -= diliverY ? diliver : 0;

四叉树的结构比较简单，并且当空间数据对象分布比较均匀时，具有比较高的空间数据插入和查询效率（复杂度O(logN)）。

八叉树类似四叉树，适用于三维空间的分割（一个立方体可被分成8个小立方体）。

预计算

主要方式是通过预先计算好的数据，然后运行时使用这些数据减少运算量。
可以根据自己的项目权衡运行速度和内存空间来选择预计算。

（首先以这副图为示例）

路径查询表

借助预先计算好的路径查询表，可以以O(|v|)的时间复杂度极快完成寻路，但是占用空间为O(|v|2)。
（|v|为顶点数量）

实现：对每个顶点使用Dijkstra算法，求出该顶点到各顶点的路径，再通过对路径回溯得到前一个经过的点。

路径成本查询表

有时候，游戏AI需要考虑路径的成本来决定行为，
则可以预先计算好路径成本查询表，以O（1）的时间复杂度获取路径成本，但是占用空间为O(|v|2)。

实现：类似路径查询表，只不过记录的是路径成本开销，而不是路径点。

寻路的改进

双向搜索

与从开始点向目标点搜索不同的是，你也可以并行地进行两个搜索——
一个从开始点向目标点，另一个从目标点向开始点。当它们相遇时，你将得到一条路径。

双向搜索的思想是：单向搜索过程生成了一棵在地图上散开的大树，而双向搜索则生成了两颗散开的小树。
一棵大树比两棵小树所需搜索的节点更多，所以最好是使用双向搜索。

（以BFS寻路为例，黄色部分是单向搜索所需搜索的范围，绿色部分则是双向搜索的，很容看出双向搜索的开启节点数量相对较少）

实验表明，在A*中你得不到一棵树，
它只是在搜索地图中当前位置附近的区域，但是又不像Dijkstra算法那样散开。
事实上，这就是让A*算法运行得如此快的原因——
无论你的路径有多长，它并不进行疯狂的搜索，除非路径是疯狂的。
它只尝试搜索地图上小范围的区域。
如果你的地图很复杂，双向搜索会更有用。

路径拼接

当一条路径需要被重新计算时，意味着世界正在改变。对于一个正在改变的世界，对地图中当前邻近的区域总是比对远处的区域了解得更多。因此，我们应该集中于在 附近寻找好的路径，同时假设远处的路径不需要重新计算，除非我们接近它。与重新计算整个路径不同，我们可以重新计算路径的前M步：

令p[1]..p[N]为路径（N步）的剩余部分
为p[1]到p[M]计算一条新的路径
把这条新路径拼接（Splice）到旧路径：把p[1]..p[M]用新的路径值代替

因为p[1]和p[M]比分开的M步小（原文：Since p[1] and p[M] are fewer than M steps apart），看起来新路径不会很长。不幸的是，新的路径也许很长而且不够好。上面的图显示了这种情况。最初的红色路径是1-2-3-4，褐色的是障碍物。如果我们到达2并且发现从2到达3的路径被封锁了，路径拼接技术会把2-3用2-5-3取代，结果是物体沿着路径1-2-5-3-4运动。我们可以看到这不是一条好的路径，蓝色的路径1-2-5-4是一条更好的路径。

通常可以通过查看新路径的长度检测到坏的路径。如果这严格大于M，就可能是不好的。一个简单的解决方法是，为搜索算法设置一个最大路径长度。如果找不到一条短的路径，算法返回错误代码；这种情况下，用重计算路径取代路径拼接，从而得到路径1-2-5-4.。

对于其它情况，对于N步的路径，路径拼接会计算2N或者3N步，这取决于拼接新路径的频率。对于对世界的改变作反应的能力而言，这个代价是相当低的。令人吃惊的是这个代价和拼接的步数M无关。M不影响CPU时间，而控制了响应和路径质量的折衷。如果M太大，物体的移动将不能快速对地图的改变作出反应。如果M太小，拼接的路径可能太短以致不能正确地绕过障碍物；许多不理想的路径（如1-2-5-3-4）将被找到。尝试不同的M值和不同的拼接标准(如每3/4 M步)，看看哪一种情况对你的地图最合适。

路径拼接确实比重计算路径要快，但它不能对路径的改变作出很好的反应。经常可以发现这种情况并用路径重计算来取代。也可以调整一些变量，如M和寻找新路径的时机，所以可以对该方法进行调整(甚至在运行时)以用于不同的情况。

Note：Bryan Stout 有两个算法，Patch-One和Patch-All，他从路径拼接中得到灵感，并在实践中运行得很好。
他出席了GDC 2007（https://www.gdcvault.com/play/720/Embodied-Agents-in-Dynamic）

Implementation Note：

反向保存路径，从而删除路径的开始部分并用不同长度的新路径拼接将更容易，因为这两个操作都将在数组的末尾进行。本质上你可以把这个数组看成是堆栈因为顶部的元素总是下一个要使用的。