# PathFindingTest

**Repository Path**: eoralmilk/path-finding-test

## Basic Information

- **Project Name**: PathFindingTest
- **Description**: 用于检验寻路算法
- **Primary Language**: Unknown
- **License**: GPL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2023-07-17
- **Last Updated**: 2023-07-24

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# PathFindingTest

用于检验寻路算法

使用Unity 2021.3.16f1c1

## 进度
- 实现基础的4向或者8向邻接点检测的AStar算法。同时添加了Post Smooth。
- 基本JPS（跳点寻路）算法，同样也有Post Smooth
- JPS+已完成（寻路图完全预处理）

## 问题
- AStar在h cost比率大于1时，性能提升很多，但是jps好像几乎没有，可能是因为jps的节点位置是离散且不确定的，节点普遍密度不够，且并不均匀，因此受h值影响不大。所以我认为jps里给个标准h值就好了，能尽量找到最近的路线。
- JPS主要的优势是OpenList中添加的节点通常比AStar要少很多，这节省了维护PriorityQueue排序的消耗，但是JPS需要check的节点数量远比AStar要多，尤其是在大而空旷的地图中。
- AStar的优势是除非障碍挡路，否则是不会受到周围环境的复杂程度影响的。就是说挡路的障碍物越少，AStar速度越快。如果障碍很多，JPS则更有优势。
- 总的来说JPS的特点是以大量的提前的check，来筛选出“感兴趣”的节点添加到PriorityQueue（例如障碍物拐点）。这决定了它的check计算量大，PriorityQueue维护计算量小。
- AStar则是简单粗暴的一步步check并添加到OpenList，每一步都在试图接近目标。

### BasicJPS 总结
- 优点:
  1. PriorityQueue维护计算量小。在复杂的环境，障碍物较多时，对比AStar来说性能提升明显。
  2. 节点数少，便于进行如post smooth等后处理。
- 缺点：
  1. check数量非常大，一般比AStar的检测数量大得多。因此在宽阔的障碍稀疏的地图中可能性能消耗较大，甚至于耗时大过AStar。
  2.  因为jps查询的节点是离散的，所以很难到做像是规避一些特定地形的Cell的寻路模式。比如避开难以行走的粗糙表面。即使修改跳点规则也很难在处理大量跳点和check大量节点的情况下保证计算速度。
  3. 几乎不受高h值的影响，难以通过修改h值来加速寻路。

  
---
- AStar h = g
![AStar](./readme_astar01.png "AStar h = g")

- AStar h = 1.3g
![AStar](./readme_astar02.png "AStar h = 1.3g")
如图所示：  
在AStar中，h值提高搜索速度同时也会导致搜索的路线有额外的“倾向性”，使得寻得的路径不一定是最短的。
但是如果在寻路后进行post smooth做后处理，一定程度上可以减少这些绕远的影响。  
这张图里蓝色的路径就是post smooth过的路线，可见单位如果按照处理后的路线行动，并不会绕远。  
值得注意的是，post smooth在grid map中的工作是使用LineOfSight方法检查两个节点之间的可通过性，保证smooth后的路径是可以通行的。所以不用担心smooth后路径会撞到障碍。  
不过对于单位真正的移动来说它不一定完全按照寻得的路径移动，可能还有一层“真实的移动路径”，单位真正移动时仍有可能碰撞上障碍物。这个需要其他办法来避免，比如添加RVO，ORCA等避障算法。

- JPS h = 1.3g
![AStar](./readme_jps01.png "JPS h = 1.3g")
h值对JPS的提升不太明显，同时对结果的最优性影响也不大。

## JPS跳点优化的可能
### 1. 完全预处理:
常见的优化方法是完全预处理。

计算出每个节点在8向方向上最近的**跳点**或者**障碍物**或者**边界**的距离，检索跳点操作时直接获取到跳点或者直接结束跳点进程。

或者只记录4向的跳点预测，因为对角线方向的跳点检索实际上的对水平垂直方向检测进行迭代的结果。

- 缺点：
1. 预处理过程缓慢，计算量很大，但是因为结果是确定性的（节点只改变自身的跳点预测记录，只从寻路图中获取障碍物状态），因此可以分区域多线程处理。
2. 难以执行局部更新：当地图很大时，更新局部的通过性状态也将导致大量节点需要重新执行跳点预测，只更新一个节点的通过性状态其范围最糟糕情况甚至要更新整张地图。
- 优点：
3. 对某次寻路来说性能提升非常明显，越大越空旷的地图提升效果越好。

### 2. 部分预处理：
如果只考虑将跳点的过程加速，例如一次性跳多个节点。
我们是否可以平衡快速的局部更新和单次寻路的消耗呢。  
这就引出了下文中我所设想的算法。


## 四向连续性区域预测

我们逐步介绍这个概念。

### **1. 四向空旷区域预测:**
- 每个节点记录水平和垂直的4个方向的最近的障碍物距离，我们可以只检索N个格子，如果N个格子内没有障碍物，我们记录`空旷区域数值`为N，如果距离当前节点的第X个节点是障碍物，我们记录`空旷区域数值`为X
- 执行水平和垂直跳点是，如果当前节点的对应跳点方向的`空旷区域数值x1`与两侧节点的`空旷区域数值x2`相同都为X，我们可以直接向后跳X个顶点。循环此操作直到:
  -  x1 != x2 则选择较小的值进行长距离跳点。然后按照正常的跳点（步长为1）继续迭代跳点检索过程。
  -  如果触及边界，跳点检索失败因而结束。
- 优点：
  1. 局部更新可行，更新消耗与N值成正比。
  2. 对空旷地图效果好
- 缺点:
    1. 总体提升效果不大
    2. 对障碍物很多的复杂地形来说，意义不大，如果实现的不好，性能消耗反而更大。

### **2. 四向阻塞与空旷区域预测:**
- 基于四向空旷区域预测的思想，但是还要记录每个节点在水平和垂直的4个方向的最近的可通行tile的距离。
- 如果一个节点不是障碍物，则我们用正值记录空旷区间。否则，我们用负值记录阻塞区间。这个值我们称为`连续性预测值`**C**
  - 跳点检测时，如果对应方向的**C**值与两侧的**C值为相同的正值**。直接跳C个点。
  - 如果为相同的负值，那不对，不可能出现这种情况。因为负值为障碍物，跳点主路线的节点不可为障碍物，否则终止跳点。**主路径C值一定为正值。否则不能长距离跳点**
  - 如果**主路径C值为0且非障碍物**，则可以推断下一个节点是障碍物。我们只要检测当前点是否为跳点(注意，如果逻辑正确，这个点一定不是跳点，那么这层检查是可以抛弃的，直接结束)，不论结果如何都要结束了。一般来讲，正确的长距离跳点不会导致主路径为C==0的障碍物节点的情况。
  - 如果C值不同
    - **两侧C值的绝对值与主路径C值相同**，则**继续执行长距离跳点**，跳C个点。因为这里我们能知道，排除上面的情况后，主路径一定是正值，也就是说两侧是连续的障碍物。或者一侧是连续的障碍物另一侧是连续的空旷区间。
    - **绝对值不同，取绝对值最小的C值执行长距离跳点，如果最小的C值为零则向前执行单步跳点检测。**

![AStar](./C_value.png "C值计算")
如图：
- 灰色格子代表障碍物。
- 灰色格子中的C值在代码实现中可以考虑记为负值。
- 我们将N值，或者说C值的最大值设为8
  
我们从最左侧中间一排标记为**绿色的8的节点**开始向右侧逐一计算节点的`C值`。  
可以发现，所有**跳点**（黑框节点）的前一个节点和其左右邻居的`C值`的**绝对值最小值**一定为0。

---
说起来逻辑略显复杂，实际上，代码实现比较简单，不需要太多分支语句。

JumpCheck过程的伪代码
``` cpp
vec2int curr = start;
Cmain = nodes[curr].xxdirC;
Cleft = nodes[curr+leftOffset].xxdirC;
Cright = nodes[curr+rightOffset].xxdirC;
int minAbsC =  Min(Cmain,Abs(Cleft),Abs(Cright);
// 不应该出现这种情况，因为不允许从障碍物开始检索跳点
// 实际代码中可能不需要这层检查
if (Cmain < 0) 
    returm false;

while(true)
{
    while (minAbsC == 0)
    {
        if (Cmain == 0)
            return false;

        curr += oneCellJump;
        if (CheckCurrent())
            return true;

        Cmain = nodes[curr].xxdirC;
        Cleft = nodes[curr+leftOffset].xxdirC;
        Cright = nodes[curr+rightOffset].xxdirC;
        minAbsC =  Min(Cmain,Abs(Cleft),Abs(Cright);
    }

    // 跳到绝对值最小的C对应距离的点
    // 如果主路径绝对值最小,说明主路径前方有障碍物。
    // 这次跳跃会跳到障碍物面前，主节点的C将是0，下个循环开始时将结束跳点进程
    // 如果两侧路径绝对值最小，跳跃完毕后，节点的最小C值应当为0
    // 则向前迈进一步检索跳点
    JumpDir(&curr, minAbsC);

    Cmain = nodes[curr].xxdirC;
    Cleft = nodes[curr+leftOffset].xxdirC;
    Cright = nodes[curr+rightOffset].xxdirC;
    minAbsC =  Min(Cmain,Abs(Cleft),Abs(Cright);
}

```
---
### **3. 混合C值:**
实际上我们还可以进一步优化。

我们可以将两侧节点的C值合并于主节点中，相当于节点在每个方向查询连续空间时，同时查询两侧节点的状态。直接存储绝对值最小值。但是这将导致连续性预测值C值代表的意义产生变化。我们可以将其称为`混合C值`。

![AStar](./Cmix_value.png "混合C值")
如图，X代表障碍物。从标记为6的节点开始向右侧逐一计算节点的`混合C值`。可以发现，所有“跳点”（黑框节点）的前一个节点`混合C值`都为0。

于是代码可以改为

伪代码
``` cpp
vec2int curr = start;
int mixC = nodes[curr].xxdirMixC;

while(true)
{
    while (mixC == 0)
    {
        curr += oneCellJump;

        // 由于我们的C值已经混合在一起了
        // 所以不能确定前方要检测的顶点是否为障碍物
        if (CurretIsBlocked())
            return false;

        if (CheckCurrent())
            return true;

        mixC = nodes[curr].xxdirMixC;
    }

    JumpDir(&curr, mixC);

    mixC = nodes[curr].xxdirMixC;
}

```

### **总结**
上述算法尚未经过实现验证。以后我有机会可以实现一版算法来测试性能。