3、环境建模：栅格地图、八叉树地图、拓扑地图、Voronoi图
环境建模，说白了就是给无人机画一张它能看懂的地图。你想想看，无人机自己又没有眼睛，它怎么知道哪里能飞、哪里不能飞？全靠我们给它建的这个模型。
我做了这么多年路径规划，踩过最大的坑就是——选错了地图模型。有一次项目赶工期，我随手用了栅格地图，结果无人机在复杂地形里绕了半天出不来。嗯，从那以后我再也不敢轻视环境建模这一步了。
今天咱们就把四种主流的地图模型掰开揉碎讲清楚。每种模型我都会结合自己的项目经验，告诉你什么时候该用、什么时候千万别用。
3.1 栅格地图（Grid Map）
栅格地图是最直观的一种。就是把空间切成一个个小格子，每个格子标记为「可通行」或「不可通行」。就像你玩扫雷游戏一样，每个格子要么安全，要么有雷。
核心思想：用离散的网格单元表示连续空间，每个单元存储占用状态。
我在做室内无人机巡检项目时，就用的栅格地图。因为室内环境结构规整，走廊、房间边界清晰，栅格化之后路径规划特别快。
优点
- 实现简单——二维数组就能搞定，代码量少
- 算法兼容性好——A*、Dijkstra、RRT都能直接跑
- 更新方便——发现障碍物，改对应格子的值就行
- 适合静态环境——仓库、厂房这种固定场景特别好用
缺点
- 分辨率两难——格子大了精度不够，格子小了内存爆炸
- 存储浪费——空旷区域也占内存，其实大部分格子都是空的
- 路径锯齿——规划出来的路径全是折线，无人机飞起来一抖一抖的
- 三维扩展困难——三维栅格地图的内存消耗是立方的，100×100×100就是100万个格子
我的建议：如果你做的是二维平面上的无人机巡检，且环境不大（比如100m×100m以内），栅格地图是最省心的选择。但要是做三维城市飞行，赶紧往下看八叉树。
3.2 八叉树地图（Octree Map）
八叉树地图是栅格地图的升级版。它聪明在哪呢？——哪里需要精细，哪里就多切几刀；哪里空旷，哪里就少切几刀。
我记得第一次接触八叉树是在做森林巡检项目。树林里大部分空间是空的，只有树干和树枝是障碍物。如果用栅格地图，内存直接爆掉。八叉树完美解决了这个问题。
工作原理
八叉树把三维空间递归地分成8个立方体。如果一个立方体全是空的，就不再细分；如果包含障碍物，就继续切8块。这样，空旷区域用一个大格子表示，复杂区域用很多小格子表示。
// 八叉树节点结构（简化版）
struct OctreeNode {
bool is_occupied; // 是否被占用
bool is_leaf; // 是否是叶子节点
OctreeNode* children[8]; // 8个子节点
float size; // 节点大小
Vector3 center; // 节点中心坐标
};优点
- 内存高效——空旷区域只存一个节点，比栅格地图省几十倍内存
- 自适应分辨率——近处精细、远处粗糙，符合传感器特性
- 支持概率更新——每个节点可以存占用概率，处理传感器噪声
- 三维友好——天生就是三维数据结构
缺点
- 实现复杂——指针操作多，容易内存泄漏
- 查询效率波动——最坏情况下要遍历到最深叶子节点
- 动态更新慢——移动障碍物需要重建部分树结构
- 路径规划适配麻烦——A*不能直接在八叉树上跑，需要额外处理
我曾经踩过的坑：有一次在八叉树上直接跑RRT，结果因为节点大小不一致，碰撞检测时好时坏。后来我加了一层「节点均匀化」处理，把不同大小的节点统一成相同分辨率再规划路径，问题才解决。
3.3 拓扑地图（Topological Map）
拓扑地图不关心「空间长什么样」，只关心「哪些地方能去、怎么连通」。它把环境抽象成一张图：节点是关键位置（路口、地标），边是连通路径。
你想想看，我们人类认路也是这样的——「先走到那个红绿灯，然后右转，再直走200米」。没人会记着路上每一块砖的位置吧？拓扑地图就是模仿这种思维方式。
优点
- 极其轻量——几十个节点就能表示整个园区
- 规划速度快——图搜索算法秒出结果
- 适合大范围——城市级、园区级路径规划首选
- 自然支持分层——可以建粗粒度拓扑和细粒度拓扑
缺点
- 精度低——只知道怎么走，不知道具体位置
- 建图困难——自动提取拓扑结构是个研究难题
- 无法处理细节障碍——小障碍物在拓扑图上体现不出来
- 更新成本高——环境变了，拓扑结构可能要重新建
我的经验：拓扑地图最适合做「全局规划」，比如无人机从A栋飞到B栋。但到了B栋附近，就得切换成栅格地图或八叉树做「局部规划」，处理楼宇间的细节障碍。两种地图配合使用，效果最好。
3.4 Voronoi图
Voronoi图是个很有意思的东西。它把空间划分成多个区域，每个区域里只有一个「种子点」。区域内任何位置到该种子点的距离，都比到其他种子点近。
用在路径规划上，Voronoi图的边界线就是「最安全路径」——因为边界上的点离所有障碍物都最远。我做无人机编队飞行时特别喜欢用这个，能保证每架无人机都离障碍物远远的。
优点
- 天然安全——路径沿着障碍物之间的中线走，碰撞风险最低
- 路径平滑——Voronoi边界的曲率变化小，适合无人机飞行
- 支持多目标——多个种子点对应多个目标，天然支持多目标规划
- 数学性质好——有成熟的算法库支持（如CGAL、Boost）
缺点
- 计算量大——高维Voronoi图构建复杂度高
- 动态环境不友好——障碍物移动了，整个图要重新算
- 路径不是最短——安全路径往往比最短路径长很多
- 边界退化问题——障碍物密集时，Voronoi边界变得很窄，无人机过不去
注意：Voronoi图在二维空间表现很好，但扩展到三维就复杂了。三维Voronoi的边界是平面，计算量指数级增长。我一般只在二维平面规划时用Voronoi，三维场景还是老老实实用八叉树。
3.5 四种地图对比总结
| 特性 | 栅格地图 | 八叉树地图 | 拓扑地图 | Voronoi图 |
|---|---|---|---|---|
| 内存占用 | 高 | 低 | 极低 | 中 |
| 规划速度 | 中 | 中 | 快 | 慢 |
| 精度 | 高（取决于分辨率） | 高（自适应） | 低 | 中 |
| 动态适应性 | 好 | 中 | 差 | 差 |
| 三维支持 | 差 | 好 | 中 | 差 |
| 实现难度 | 低 | 高 | 中 | 高 |
| 典型场景 | 室内巡检 | 森林、城市 | 园区、道路网 | 编队、避障 |
3.6 如何选择？我的实战建议
说实话，没有一种地图是万能的。我个人的选择策略是这样的：
- 先看维度——二维场景优先考虑栅格地图或Voronoi图；三维场景直接上八叉树
- 再看范围——小范围（100m以内）用栅格；大范围（公里级）用拓扑
- 最后看动态性——环境变化快用栅格；环境固定用八叉树或Voronoi
还有一个技巧：混合使用。我最近的项目就是拓扑地图做全局规划，八叉树做局部规划，两者之间通过「地图切换层」衔接。效果出奇的好，既保证了全局效率，又兼顾了局部精度。
一句话总结：栅格地图是入门首选，八叉树是三维标配，拓扑地图是大范围利器，Voronoi图是安全路径专家。选对地图，路径规划就成功了一半。
公众号:蓝海资料掘金营，微信deep3321