寻路算法

1.强迫邻居：

就是指某个节点（x）上下左右有障碍，在由某方向经过这个节点的时候，如果有方向的分量垂直于障碍的方向，则在障碍一侧的斜向点就是节点（x）的强迫邻居

如上图所示，有两个要素：

a.带有搜索方向（剪头）

b.带有障碍（上下左右都行）

private Dir HaveStrictNeigh(Vector2 cur, Dir dir)

{

    bool c1, c2;

    switch (dir)

    {

        case Dir.Left:

            c1 = !IsValidPos(MoveDir(cur, Dir.Up)) && IsValidPos(MoveDir(cur, Dir.UpLeft))&& IsValidPos(MoveDir(cur, Dir.Left));

            c2 = !IsValidPos(MoveDir(cur, Dir.Down)) && IsValidPos(MoveDir(cur, Dir.DownLeft))&& IsValidPos(MoveDir(cur, Dir.Left));

            if (c1 && c2)

            {

                return Dir.Left;

            }

            else if (c1)

                return Dir.UpLeft;

            else if (c2)

            {

                return Dir.DownLeft;

            }

            break;

        case Dir.Up:

2.跳点

跳点需要满足下面三个条件之一：

a.节点是寻路的起点/终点

b.节点至少有一个强迫邻居

c.如果父节点在斜方向（意味着这是斜向搜索），节点的水平或垂直方向上有满足条件a，b的点

举个例子：

黄色节点的父节点是在斜方向，其对应分解成向上和向右两个方向，因为在右方向发现一个蓝色跳点，因此黄色节点也应被判断为跳点

（黄色点为起点，蓝色点为跳点）

寻路流程：

1.openlist取一个权值最低的节点，然后开始搜索

2.搜索时先进行 直线搜索 （上下左右四个方向搜索，直到出现跳点或者到边界），

3.再进行 斜向搜索 （四个斜方向搜索，只前进一步），如果有跳点就加入openlist，知道当前方向完成搜索。

4.如果斜方向没有出现跳点或者到边界，就用进一步的斜点，在直线搜索+斜向搜索，直到所有方向都完成

5.从openlist权值最低的节点进行搜索，直到openlist为空或者找到重点

_和A 相比，优缺点：_*

1.使用JPS算法比A 更快（绝大部分地图），内存占用更小，因为openlist少了很多节点（最差的情况和A

一样，最差的是每个障碍都不连续，中间都有缝隙，这样所有地方都是跳点了）

2.只适用于网格节点类型，不支持Navmesh或者路径点寻路方式