📚 课程目录第3章复杂地形定义与分类

3. 复杂地形定义与分类

全局路径规划，说白了就是给无人机找一条从起点到终点的路。但地形复杂了，这条路就没那么好找了。我这些年做过的项目里，光是算法选型就踩过不少坑。今天咱们就聊聊三种最常用的全局规划算法——A*、Dijkstra 和 JPS，看看它们在地形数据上到底怎么用。

3.1 A*算法：启发式搜索的经典实践

A* 是我用得最多的算法。它结合了 Dijkstra 的完备性和贪心搜索的效率，核心就是那个估价函数：f(n) = g(n) + h(n)。

g(n) 是从起点到当前节点的实际代价，h(n) 是当前节点到目标点的估计代价。选对 h(n)，A* 的效率能差出好几倍。

3.1.1 地形代价建模

在地形应用中，g(n) 不能只算欧氏距离。我习惯把地形坡度、地表类型、障碍物密度都折算成代价。举个例子：

// 地形代价计算示例
float calculateTerrainCost(Node* current, Node* neighbor) {
    float base_cost = euclidean_distance(current, neighbor);
    float slope_cost = get_slope_factor(current, neighbor);  // 坡度因子
    float surface_cost = get_surface_type_cost(neighbor);    // 地表类型
    float obstacle_cost = get_obstacle_density(neighbor);    // 障碍密度
    
    return base_cost * (1.0 + slope_cost + surface_cost + obstacle_cost);
}

我曾经在一个山地项目中，默认坡度因子设得太低，结果无人机规划的路径直接爬上了 45 度的陡坡。飞控根本拉不起来。后来我把坡度因子调成了指数增长——坡度每增加 10 度，代价翻倍。这才把路径逼到了缓坡区域。

3.1.2 启发函数的选择

启发函数 h(n) 的选择直接影响搜索效率。我常用的几种：

启发函数	适用场景	特点
曼哈顿距离	四方向网格	计算快，但高估代价
欧氏距离	八方向/自由空间	可采纳，搜索节点多
切比雪夫距离	八方向网格	对角移动友好
地形加权距离	复杂地形	精度高，计算量大

我的经验：在复杂地形中，别用曼哈顿距离。它不考虑对角移动，容易把路径引向死胡同。我一般用欧氏距离乘以一个地形系数，既保证可采纳性，又能避开明显的高代价区域。

3.2 Dijkstra算法优化：从基础到工程化

Dijkstra 算法是 A* 的特例——当 h(n) = 0 时，A* 就退化成 Dijkstra。它保证能找到最短路径，但搜索范围太大，在地形数据上跑起来很慢。

我优化 Dijkstra 的思路主要有三个方向：

3.2.1 数据结构优化

别用数组或链表维护开放集。用二叉堆是底线，用斐波那契堆更好。我实测过，在 100 万节点的地形网格上，二叉堆比数组快了将近 200 倍。

// 使用优先队列优化Dijkstra
struct Node {
    int id;
    float cost;
    bool operator>(const Node& other) const {
        return cost > other.cost;
    }
};

std::priority_queue<Node, std::vector<Node>, std::greater<Node>> open_set;

3.2.2 双向搜索

从起点和终点同时跑 Dijkstra，当两个搜索前沿相遇时停止。理论上能减少约 50% 的搜索节点。我在一个 50km² 的城区项目中用过，搜索时间从 12 秒降到了 4 秒。

注意：双向搜索在地形高度变化剧烈的区域容易出问题。我曾经遇到过两个搜索前沿在陡坡两侧相遇，但实际路径需要绕很远。解决方案是：在相遇后做一次路径平滑校验，如果代价异常高，就继续搜索。

3.2.3 地形剪枝

不是所有地形节点都需要搜索。我常用的剪枝策略：

高度阈值剪枝：超出无人机最大飞行高度的区域直接跳过
坡度剪枝：坡度大于 30 度的区域标记为不可通行
障碍物膨胀剪枝：对障碍物做半径膨胀，膨胀区域不参与搜索

3.3 JPS跳点搜索：让A*飞起来

JPS（Jump Point Search）是我近几年才大规模使用的算法。它本质上是对 A* 的加速——在网格地图上，通过识别「跳点」来跳过大量对称路径。

3.3.1 核心思想

在均匀代价的网格中，很多路径是等价的。比如从 (0,0) 到 (2,2)，先右再上和先上再右代价一样。JPS 只搜索那些「不得不拐弯」的点——也就是跳点。

跳点的定义：

当前节点的邻居中有障碍物，导致路径被迫改变方向
当前节点是起点或终点
当前节点所在行/列有强制邻居

3.3.2 跳点搜索流程

// JPS跳点搜索核心逻辑
std::vector<Node*> identifyJumpPoints(Node* current, Direction dir) {
    std::vector<Node*> jump_points;
    Node* next = step(current, dir);
    
    while (next is valid) {
        if (isJumpPoint(next, dir)) {
            jump_points.push_back(next);
            break;
        }
        // 检查对角线方向的强制邻居
        if (hasForcedNeighbor(next, dir)) {
            jump_points.push_back(next);
        }
        next = step(next, dir);
    }
    return jump_points;
}

3.3.3 在地形中的应用

JPS 在平坦地形上效果极好，但复杂地形中需要改造。我做过一个改造方案：

地形类型	JPS适用性	改造方法
城市建筑群	高	直接使用标准JPS
山地丘陵	中	引入地形代价跳点判定
混合地形	低	分区使用不同策略

关键点：在地形代价不均匀的区域，标准 JPS 的跳点判定会失效。我建议的做法是：先对地形做代价分层，在每层内使用 JPS，层间用 A* 连接。这样既保留了 JPS 的速度，又处理了地形变化。

3.4 三种算法的对比与选型

说了这么多，到底该用哪个？我整理了一个对比表：

指标	A*	Dijkstra	JPS
搜索效率	高	低	极高
路径最优性	最优	最优	最优
地形适应性	强	强	弱（需改造）
实现复杂度	中	低	高
内存占用	中	高	低

我个人习惯的选型原则：

地形平坦、网格均匀 → JPS，快得离谱
地形复杂、需要精确代价 → A*，灵活可控
需要保证全局最优、节点数少 → Dijkstra，简单可靠

避坑指南：我曾经在一个项目中迷信 JPS 的速度，直接用在山区地形上。结果跳点判定频繁出错，路径绕了远路不说，还差点撞山。后来老老实实改回 A*，虽然慢了 30%，但路径安全多了。记住：速度不是唯一指标，安全才是。

嗯，这三种算法各有各的脾气。A* 像是个稳重的老工程师，什么地形都能处理，就是慢了点。Dijkstra 像个固执的数学家，非要遍历所有可能才放心。JPS 则像个机灵的年轻人，在平坦路上跑得飞快，但遇到复杂地形就容易迷路。

我建议你在实际项目中，先做地形分析，再选算法。如果地形变化不大，优先考虑 JPS。如果地形复杂，用 A* 加地形代价加权。至于 Dijkstra，我一般只在需要验证最优解或者节点数很少的时候用。