2. 地图建模：栅格地图的构建与数据结构设计
做路径规划，第一步不是写算法，而是先把“世界”描述清楚。
我刚开始接触A*算法时，踩过最大的坑就是——地图没建好，算法跑得再漂亮也是白搭。你想想看，机器人连自己周围是墙还是路都搞不清，它怎么规划路径？
所以这一章，咱们就聊聊地图建模。说白了，就是把真实环境翻译成计算机能理解的数据结构。
2.1 栅格地图的基本概念
栅格地图（Grid Map）是目前最常用的地图表示方式之一。它的思路很简单：把环境切分成一个个小格子，每个格子要么是“可通过”，要么是“不可通过”。
我个人习惯用0表示空闲，1表示障碍物。为什么？因为这样在代码里判断起来最直观。
核心思想： 用二维数组存储地图，每个元素代表一个栅格的状态。
举个例子，一个5×5的简单地图：
// 0 = 空闲，1 = 障碍物
int map[5][5] = {
{0, 0, 0, 0, 0},
{0, 1, 1, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 1, 1, 0},
{0, 0, 0, 0, 0}
};嗯，这里要注意：地图的尺寸决定了算法的搜索空间。地图越大，搜索时间越长。我在项目中遇到过，一个1000×1000的地图，如果不做优化，A*跑起来能让你等到怀疑人生。
2.2 障碍物的表示方式
障碍物怎么表示？其实就两种思路：
- 静态障碍物： 在初始化时直接写入地图数组
- 动态障碍物： 运行时实时更新地图数据
我曾经在一个仓储机器人项目里，需要处理动态障碍物——比如其他机器人临时停靠。那时候我用的方法是：维护一个独立的障碍物列表，每次路径搜索前先更新地图。
避坑指南： 我曾经把动态障碍物直接写进地图数组，结果导致路径规划时地图被永久修改，后续搜索全乱套了。后来我学乖了——每次搜索前复制一份地图副本，在副本上操作。
障碍物还可以有“代价”属性。比如：
| 障碍物类型 | 代价系数 | 说明 |
|---|---|---|
| 空地 | 1.0 | 正常通行 |
| 草地 | 2.0 | 通行较慢 |
| 泥地 | 3.0 | 通行困难 |
| 墙壁 | ∞ | 不可通行 |
你想想看，如果机器人走草地和走空地的代价一样，那它可能就会选择穿过草地——但实际场景中，草地可能更耗电、更容易打滑。所以给不同地形赋予不同代价，更符合真实情况。
2.3 四邻域与八邻域移动代价
这是很多初学者容易搞混的地方。我简单说一下：
- 四邻域： 只能上下左右移动
- 八邻域： 可以上下左右 + 四个对角线方向
移动代价怎么算？
四邻域很简单，每步代价固定为1。但八邻域就有讲究了——对角线移动的距离是√2 ≈ 1.414，所以代价不能和直线移动一样。
我建议： 直线移动代价设为10，对角线移动代价设为14。这样用整数计算，避免浮点数精度问题。
// 移动代价定义
const int STRAIGHT_COST = 10; // 直线移动
const int DIAGONAL_COST = 14; // 对角线移动
// 判断移动方向
if (dx == 0 || dy == 0) {
cost = STRAIGHT_COST;
} else {
cost = DIAGONAL_COST;
}为什么会这样？因为A*算法中，代价计算直接影响路径质量。如果对角线代价设得太低，算法会倾向于走对角线，路径看起来会“飘”；设得太高，又可能绕远路。
注意： 八邻域移动时，要检查对角线是否被障碍物挡住。比如你要往右上角走，但右边和上边都有障碍物，那这个对角线移动就不合法。我曾经没做这个检查，结果机器人穿墙了……
2.4 地图数据结构设计
数据结构设计得好，代码写起来就顺手。我个人常用的结构是这样的：
// 栅格节点结构体
typedef struct {
int x, y; // 坐标
int g_cost; // 起点到当前点的代价
int h_cost; // 当前点到终点的估计代价
int f_cost; // g_cost + h_cost
int is_obstacle; // 是否为障碍物
int parent_x; // 父节点坐标（用于回溯路径）
int parent_y;
} GridNode;
// 地图类
class GridMap {
private:
int width, height;
GridNode** nodes; // 二维数组
public:
GridMap(int w, int h);
~GridMap();
bool is_valid(int x, int y); // 检查坐标是否合法
bool is_walkable(int x, int y); // 检查是否可通行
int get_cost(int x1, int y1, int x2, int y2); // 计算移动代价
void set_obstacle(int x, int y, bool value); // 设置障碍物
};嗯，这里要注意几点：
- 内存管理： 大地图建议用一维数组模拟二维，减少内存碎片
- 边界检查： 每次访问地图前都要检查坐标是否越界
- 父节点记录： 这是路径回溯的关键，千万别漏了
个人经验： 我习惯把地图数据和搜索逻辑分开。地图只负责“存储和查询”，搜索算法只负责“计算和决策”。这样后期换算法（比如换成JPS）时，地图代码完全不用动。
2.5 知识体系总览
为了让你更直观地理解本章内容，我画了一张结构图：
这张图把本章的核心内容串起来了。从地图构建到障碍物表示，再到移动代价计算，最后落到数据结构设计——每一步都环环相扣。
好了，地图建模就聊到这儿。记住一句话：地图建得好，算法跑得顺。别嫌这一步麻烦，后面你会感谢自己花时间把地图设计清楚的。
公众号:蓝海资料掘金营，微信deep3321