简介面向智能车竞赛与嵌入式图像处理开发者这份可运行源码包专注于八邻域扫线算法在赛道识别与边界判断中的应用。算法针对光线干扰、差比和及计算量问题进行了优化输出像素生长方向信息适合需要快速部署路径识别功能的工程实践。资源共9个文件以C源码、头文件、Makefile构建脚本和Markdown说明文档为主构建脚本可用于直接编译部署说明文档梳理算法与调优思路全部代码与文档压缩后仅15KB结构紧凑。已有320人学习下载可作为备赛练习、入门学习或二次开发时的参考。通过源码可直观了解八邻域扫线的边界判定流程配合TC264硬件适配层与编译配置可快速验证差比和图像处理效果配套优化指南还点明了算法对图像质量要求高、需注意稳定性等工程要点方便读者在实际调车中少走弯路。1. 智能车八邻域算法到底是什么栅格地图上的信息传播规则做智能车路径规划的人迟早会撞上八邻域这个词。我在给某高校实训小车做栅格地图避障时第一版规划器用的是四邻域路径绕得像老太太走路后来换成八邻域转弯明显顺了路线缩短了将近三分之一但调试过程也踩了不少坑。这里先给一个结论八邻域不是一种算法而是一套栅格地图上的邻居定义规则——把当前格子周围的 8 个方向上、下、左、右、左上、右上、左下、右下全部纳入计算范围用在膨胀处理、障碍物检测、路径搜索和信息传播四种任务里。它解决的核心问题是“从任何一个格子出发下一步能去哪里、代价是多少”。本文给出一份可直接运行的 C 源码并把它嵌进 A* 路径规划里讲清楚参数怎么设、边界怎么处理、哪些地方最容易翻车。2. 八邻域的四种任务与最小复现从邻居定义到可跑通的临时脚本2.1 八邻域到底在“算”什么邻居集合与方向数组先建立一个统一抽象。假设栅格地图是一个二维数组每个格子存 0 或 10 代表可通行1 代表障碍。当前格子坐标记为 (r, c)行号向下增大列号向右增大。那么八邻域就是在其周围 8 个方向上各取一个格子方向编号从正上方开始顺时针旋转记成 0 到 7。我一般用一个静态数组来定义这 8 个方向的偏移量// 方向偏移表: {行偏移, 列偏移, 单位代价} // 0上, 1右上, 2右, 3右下, 4下, 5左下, 6左, 7左上 static const int kDirs[8][2] { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} }; static const double kCost[8] {1.0, 1.414, 1.0, 1.414, 1.0, 1.414, 1.0, 1.414};为什么方向集合是 8 而不是 4因为对角移动的代价与直行不同。直行从一个格子中心到相邻格子中心距离是 1 个格宽斜向移动距离是根号 2约 1.414。如果代码里把所有方向统一按 1 计费规划器会疯狂“抄近路”走斜线最后路径呈现锯齿。kCost 数组就是为这个准备的后面 A* 的 G 代价直接从这里取。2.2 最小复现脚本二十行 Python 验证邻居行为在写 C 工程之前我习惯先用 Python 快速验证逻辑。下面这段脚本不依赖任何第三方库功能是给定地图和一个起点把八邻域中所有可通行的格子打出来# -*- coding: utf-8 -*- # 最小八邻域采样脚本: 验证邻居顺序和边界过滤逻辑 DIRS [(-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1)] def get_neighbors(grid, r, c): rows len(grid) cols len(grid[0]) result [] for dr, dc in DIRS: nr, nc r dr, c dc if nr 0 or nr rows or nc 0 or nc cols: continue # 越界即不可达 if grid[nr][nc] 1: continue # 障碍物 result.append((nr, nc)) return result if __name__ __main__: grid [ [0, 0, 0, 0], [0, 1, 1, 0], [0, 0, 0, 0], ] print(get_neighbors(grid, 1, 2)) # 起点放在障碍物右边这段代码过滤条件只有两条越界丢弃、障碍丢弃。逻辑说明先算偏移后的坐标再判断是否在地图范围内最后查地图值。三个判断的先后顺序不能变——必须先查行列边界再查障碍否则数组会越界访问。运行后你会发现起点 (1, 2) 的 8 个邻居里正上方 (0, 2) 是空地、右上方 (0, 3) 是空地、正下方 (2, 2) 是空地但左上和正左都被障碍挡住返回结果里自然没有它们。2.3 四邻域与八邻域怎么选一张对比表说清适用场景很多新手拿到栅格地图就问“该用哪种”。答案取决于任务对路径长度的敏感度和车辆运动模型。四邻域只允许横平竖直的移动路径通常是曼哈顿风格转折多、总长度偏长八邻域允许斜穿路径更短但对车辆最小转弯半径完全不敏感时才能直接用。据我经验对于低速巡检小车、仓储 AGV 这类允许原地差速转向的场景八邻域更合适对于阿克曼转向的车型八邻域规划出的折线往往转不过去需要后接平滑或者干脆用四邻域加曲线拟合。维度四邻域八邻域邻居数量48移动方向上下左右增加 4 个对角方向对角代价不支持1.414路径长度偏长明显缩短转角平滑度直角多45° 角仍需平滑常见用途简单巡逻、走迷宫全局路径规划、膨胀处理还有一类任务是“八邻域找边界”常用于连通域标记从某个障碍格出发沿八邻域扩散给整片障碍打同一个编号。这时候用八邻域会把人字形相连的两个障碍判成同一个连通块而四邻域不会。这个差异在雷达点云投影成栅格后特别明显处理时务必想清楚你的“连通”语义是什么。3. 把八邻域落成 C 可运行源码工程结构、核心函数与编译命令3.1 工程文件清单与构建方式整理好的可运行源码我命名为“模拟项目X”结构上刻意保持极简只留必要文件方便你直接抄走改。完整清单如下文件作用CMakeLists.txt构建脚本生成可执行文件grid.h栅格地图结构体与接口声明grid.cpp地图加载、邻居获取、障碍检测实现main.cpp演示程序读地图、跑一遍八邻域遍历并输出结果构建方式用 CMake命令只有两行mkdir build cd build cmake .. make ./grid_demo ../map.txtmap.txt 是文本地图每行一串 0 和 10 是空地1 是障碍物。我一般会把第一行写成“行数 列数”方便动态分配内存。文件中所有代码均不依赖 ROS 或第三方库纯标准 C11任何带编译器的环境都能跑。3.2 核心实现邻居收集与对角穿墙检测下面是 grid.h 的接口定义。这里我把行和列的语义写死在注释里因为后面所有代码都靠这个约定对齐一旦搞反整个规划器行为都会错乱。// grid.h #ifndef GRID_H #define GRID_H #include vector #include string // 栅格坐标: row 为行号(0在上), col 为列号(0在左) struct GridPos { int row; int col; }; class Grid { public: Grid(); // 从文本文件加载地图, 格式见 README bool loadFromFile(const std::string path); int rows() const { return rows_; } int cols() const { return cols_; } // 判断某格是否可通行 bool isWalkable(int row, int col) const; // 获取当前格子的全部可行邻居(八邻域) std::vectorGridPos getNeighbors(int row, int col) const; private: int rows_ 0; int cols_ 0; std::vectorstd::vectorint data_; }; #endifgetNeighbors 是全部逻辑的核心直接上实现// grid.cpp 片段 #include grid.h #include fstream #include sstream std::vectorGridPos Grid::getNeighbors(int row, int col) const { // 偏移表: 上, 右上, 右, 右下, 下, 左下, 左, 左上 static const int dr[8] {-1, -1, 0, 1, 1, 1, 0, -1}; static const int dc[8] {0, 1, 1, 1, 0, -1, -1, -1}; std::vectorGridPos result; for (int i 0; i 8; i) { int nr row dr[i]; int nc col dc[i]; // 边界过滤必须放在最前面 if (nr 0 || nr rows_ || nc 0 || nc cols_) { continue; } // 目标格自身是障碍, 跳过 if (data_[nr][nc] 1) { continue; } // 对角移动需要检查两侧拐角: 防止斜穿墙角 if (dr[i] ! 0 dc[i] ! 0) { if (data_[row dr[i]][col] 1 || data_[row][col dc[i]] 1) { continue; } } result.push_back({nr, nc}); } return result; }这段代码里的第三个判断是对角穿墙检查属于血泪经验。现象是规划出的路径斜着从两个障碍格中间的角点滑过去在地图上看就是贴着墙根切角真车走的时候会蹭墙。原因在于目标格虽然是空地但它和目标格之间并不是完全“敞通”的。比如从 (r, c) 走到 (r-1, c1)只有当 (r-1, c) 和 (r, c1) 至少有一个空缺时车辆才有物理空间斜穿。我采取的策略是“两侧都要可通行”才放行这样杜绝切角代价是某些拥挤区域的路径会变绕。如果你做的是仿真环境可以放宽但实车我建议保留这个检查。3.3 主程序演示遍历全部格子验证邻居数量main.cpp 里我放了一个很实用的自检逻辑——统计每个格子的可行邻居数量。这个统计结果能帮你快速发现地图数据问题比如孤立点、被障碍完全围死的死胡同。// main.cpp #include grid.h #include iostream int main(int argc, char** argv) { if (argc 2) { std::cerr 用法: ./grid_demo map.txt std::endl; return 1; } Grid grid; if (!grid.loadFromFile(argv[1])) { std::cerr 地图加载失败 std::endl; return 1; } int unreachable_cnt 0; std::cout 各格子可达邻居数: std::endl; for (int r 0; r grid.rows(); r) { for (int c 0; c grid.cols(); c) { if (!grid.isWalkable(r, c)) { std::cout # ; continue; } auto neighbors grid.getNeighbors(r, c); std::cout neighbors.size() ; if (neighbors.empty()) { unreachable_cnt; } } std::cout std::endl; } std::cout 孤立可通行格数量: unreachable_cnt std::endl; return 0; }运行后终端会打印一张和地图大小一致的“邻居数量图”0 表示没有可走邻居。如果地图中间出现大范围 0说明地图数据在连接性上有问题。逻辑说明isWalkable 内部只做越界和障碍判断而 getNeighbors 做了完整过滤所以遍历时一定要先 isWalkable 再 getNeighbors避免重复处理障碍格。参数说明地图文件加载时我会忽略空行和以 # 开头的注释行这个行为在 loadFromFile 里实现便于直接维护地图文本。4. 在 A* 路径规划里用八邻域G 代价、启发式函数与优先级队列4.1 G 代价设定为什么对角线必须用 1.414把八邻域接进 A* 时最常见的翻车点就是代价图省事。有人把 8 个方向的 G 增量一律写成 1跑出来的路径会在两个等价路径之间反复横跳路径长度显示正确但实际轨迹呈锯齿状。原理上A* 的正确性依赖 G 代价与真实移动距离成正比。斜向移动的实际距离是根号 2 倍格宽如果你按 1 计搜索器会低估斜向移动的代价从而偏好斜线因为同样到达终点斜线步数更少、累计 G 更小。我一般这样组织数据在 Grid 类中增加一个静态方法输入两点坐标差返回移动代价。核心逻辑如下// 在 grid.h 中追加 static double moveCost(int dr, int dc) { if (dr 0 dc 0) return 0.0; if (dr ! 0 dc ! 0) return 1.414; // 对角 return 1.0; // 直行 }注意这里的 dr 和 dc 只能是 -1、0、1 三选一因为八邻域限定了一步只走一格。如果你把步长扩展成 2 格这个函数就得改成欧氏距离。还要注意 G 代价是浮点数A* 比较器里要用 epsilon 或直接比较 double不要用整数。4.2 启发式函数八邻域场景不能用曼哈顿距离八邻域允许斜向移动曼哈顿距离会高估实际代价导致搜索扩展更多节点、规划变慢欧氏距离会低估代价虽然最终路径依然正确但扩展范围变大。业界标准做法是 octile 距离公式为double octileDistance(int dr, int dc) { int dmax std::max(std::abs(dr), std::abs(dc)); int dmin std::min(std::abs(dr), std::abs(dc)); return dmax (1.414 - 1.0) * dmin; }这个公式的思路是从起点到终点最多能斜走 dmin 步剩下 dmax - dmin 步只能直走。理解这一点后你就能推导出为什么四邻域场景用曼哈顿、八邻域场景用 octile。相关改进还有一个细节启发式函数的值必须不大于真实剩余代价否则 A* 会退化成贪心搜索。octile 距离在八邻域下正好满足这个条件所以它既是高效也是最优的选择。4.3 A* 主循环的可运行实现下面给出完整 A* 主循环它在第 3 章 Grid 类基础上工作。我使用标准库的 priority_queue 做开放列表用二维数组存 G 值和父节点代码量约 80 行适合直接抄进自己的项目。#include grid.h #include queue #include cmath #include algorithm #include iostream struct Node { double f; // 总代价 double g; // 已走代价 int row; int col; bool operator(const Node other) const { return f other.f; } }; std::vectorGridPos aStar(const Grid grid, GridPos start, GridPos goal) { const int rows grid.rows(); const int cols grid.cols(); std::vectorstd::vectordouble g_score( rows, std::vectordouble(cols, 1e18)); std::vectorstd::vectorGridPos parent( rows, std::vectorGridPos(cols, {-1, -1})); std::priority_queueNode, std::vectorNode, std::greaterNode open; g_score[start.row][start.col] 0; open.push({0.0, 0.0, start.row, start.col}); const int dr[8] {-1, -1, 0, 1, 1, 1, 0, -1}; const int dc[8] {0, 1, 1, 1, 0, -1, -1, -1}; while (!open.empty()) { Node current open.top(); open.pop(); if (current.row goal.row current.col goal.col) { // 回溯路径并返回 std::vectorGridPos path; GridPos p {current.row, current.col}; while (p.row ! start.row || p.col ! start.col) { path.push_back(p); p parent[p.row][p.col]; } path.push_back(start); std::reverse(path.begin(), path.end()); return path; } for (int i 0; i 8; i) { int nr current.row dr[i]; int nc current.col dc[i]; if (nr 0 || nr rows || nc 0 || nc cols) continue; if (!grid.isWalkable(nr, nc)) continue; // 对角穿墙检查, 与 grid.cpp 中一致 if (dr[i] ! 0 dc[i] ! 0) { if (!grid.isWalkable(current.row dr[i], current.col) || !grid.isWalkable(current.row, current.col dc[i])) { continue; } } double step_cost (dr[i] ! 0 dc[i] ! 0) ? 1.414 : 1.0; double tentative_g current.g step_cost; if (tentative_g 1e-9 g_score[nr][nc]) { g_score[nr][nc] tentative_g; parent[nr][nc] {current.row, current.col}; double heuristic octileDistance(std::abs(nr - goal.row), std::abs(nc - goal.col)); open.push({tentative_g heuristic, tentative_g, nr, nc}); } } } return {}; // 路径不存在 }这里有几个必须说明的参数。优先级队列存放的是 f g h 的估值但 g_score 数组里存的是确定最优的 G 值两者用途不同。代码里用 tentative_g 1e-9 做浮点比较是为了避免 1.414 累加产生的误差导致路径无法更新。还有一点需要注意priority_queue 允许同一个格子被多次入队g_score 数组负责最终裁决这属于典型的“延迟删除”策略。如果你换用 std::set 做开放列表需要自己实现 Find 和 Update代码会涨一倍。对于地图不超过 1000×1000 的智能车场景priority_queue 方案足够。5. 八邻域避坑指南5 个让路径规划翻车的细节5.1 对角线穿墙路径从墙角斜切过去现象规划出的路径在障碍物的角上走对角线车模贴着障碍边缘滑过去仿真里看不出来实车测试时传感器报警。原因邻居过滤函数只判断了目标格是否可通行没有检查对角移动路径上的拐角格。从 (r, c) 走向 (r-1, c1) 时车辆实际会经过 (r-1, c) 和 (r, c1) 两个格子的角点这两个角点任一是障碍物理上就过不去。解决在 getNeighbors 和 A* 主循环里都加上拐角检查。代码见第 3.2 节和第 4.3 节。我采取的是“两侧都必须可通行”的严格策略。如果你做的是足球机器人这类允许挤压边界的场景可以放宽成“至少一侧可通行”但一定要全局统一否则会出现同一个路径在不同逻辑下结果不一致的玄学问题。5.2 八个方向统一 G 代价路径走出锯齿形现象路径总长度看起来短了但放大看全是折返和小锯齿车辆频繁转向实际行驶时间反而变长。原因G 代价全部写成 1导致斜向移动被低估搜索器疯狂选择斜向格子路径被“压扁”成锯齿线。解决严格执行直行 1.0、对角 1.414 的代价设定。同时启发式函数换成 octile否则 G 和 H 的度量单位不一致搜索效率会明显下降。调试方法把路径打印出来逐个计算相邻点之间的距离如果发现相邻点之间既有直行又有斜行但距离比例不对基本就是 G 代价出了问题。5.3 边界点邻居越界程序直接崩溃现象地图边缘的格子调用 getNeighbors 时数组越界程序在 Debug 模式下中断Release 模式下数据随机错乱。原因先查障碍值后查边界越界的坐标已经拿去访问 data_[nr][nc]。解决把边界判断放在最前面顺序固定为“算新坐标 → 查行列边界 → 查障碍值 → 查拐角”。这是一个非常基础的顺序问题但我在接手别人代码时至少遇到过三次。建议把这段判断封装成一个私有方法 safeWalkable(row, col)内部统一处理越界和障碍所有外部调用都走它一劳永逸。5.4 把“八邻域”泛化成“周围都要看”行为一团乱麻现象目标检测、避障、路径规划三段代码同时用了同一套八邻域逻辑但每段代码各自的“邻居”语义不同结果互相打架。原因八邻域只是一个采样规则。膨胀处理中“周围格有障碍就把当前格也标成障碍”和 A* 搜索中“下一步能走到哪个格”本质是两回事。前者是图像形态学操作不涉及移动代价后者是图搜索必须有代价和连通性语义。解决不要共用一个函数。我习惯在代码里区分两个名字getNeighborsForSearch 和 getNeighborsForInflate。前者带穿墙检查和代价后者只做范围采样。接口一旦分开就再也不会出现把膨胀结果直接当搜索图导致的地图“虚胖”问题。5.5 坐标轴方向混乱行和列反了所有结果全部镜像现象地图在文件里明明是对的但规划出的路径左右翻转或者起点终点连线呈镜像。原因地图文件用“行 列”存储而读取代码按“x y”处理导致 row 和 col 互换八邻域偏移表也随之错乱。解决在 Grid 类中严格统一坐标语义所有接口参数都叫 row 和 col不出现 x 和 y。地图文件第一行写清楚格式。还有一个笨但有效的小技巧在第 3.3 节的自检程序里打印邻居数量图从终端上一眼就能看出坐标是否镜像。我在某公司实训小车上就用这个办法定位过一起坐标颠倒的 Bug前后只花了十分钟。6. 终端可视化验证法一屏看清邻居顺序与路径质量6.1 用 ANSI 字符画快速渲染地图和路径调试八邻域相关代码我最常用的不是可视化工具而是一段 30 行的终端渲染脚本。它能把地图、障碍、起点、终点和规划路径一次性打印在终端里所有符号使用纯文本粘贴到任何环境都能跑# 终端路径渲染脚本 # 地图: 0空地 1障碍, 路径: 2路径点 def render(grid, pathNone, startNone, goalNone): path_set set(path or []) for r, row in enumerate(grid): line for c, val in enumerate(row): if (r, c) start: line S elif (r, c) goal: line E elif (r, c) in path_set: line * elif val 1: line # else: line . print(line) # 示例: 8x8 地图, 障碍物在中间区域 map_data [ [0,0,0,0,0,0,0,0], [0,0,0,1,1,0,0,0], [0,0,0,1,1,0,0,0], [0,0,0,0,0,1,0,0], [0,0,1,1,0,1,0,0], [0,0,1,0,0,1,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], ] path [(0,0), (1,1), (2,2), (3,3), (3,4), (4,5), (5,5), (6,6), (7,7)] render(map_data, pathpath, start(0,0), goal(7,7))运行后终端会输出一个 8×8 的字符地图S 是起点E 是终点* 是路径# 是障碍。这个可视化方法背后有一个我在调试中反复吃亏后悟出的逻辑路径规划问题中数值本身难看出问题但符号图能立刻暴露穿墙、绕远、锯齿三类典型错误。如果你发现路径贴着障碍但没穿墙通常是本节开头说的切角问题如果路径大步绕远通常是启发式函数高估如果路径密集锯齿通常是 G 代价定义问题。这三个判断在图形化界面里反而不如终端字符直观。6.2 验证清单每次改完代码后跑这四步我现在的习惯是每改完一次邻居逻辑就按下面四步做验证。第一步用 5×5 的全空地地图检查邻居数量中间格应返回 8 个邻居角格 3 个边格 5 个有任何一个数不对立刻停。第二步在 3×3 地图的角落放一个障碍确认对角穿墙检查生效。第三步用第 4 章的 A* 在带障碍地图上跑一遍检查路径上所有相邻点之差是否都在 [-1, 1] 范围内。第四步把路径总长度和曼哈顿距离对比如果两者差值超过 10%说明路径有明显绕路需要回看启发式参数。这四步全部跑通基本可以放心把代码接到实车上。最后分享一个教训有一次我把障碍值从 1 改成 255忘了同步修改 isWalkable 的判断整个规划器行为完全改变但终端渲染图看起来一切正常。从那以后我强制要求地图数据的值域必须集中管理所有阈值写在头文件里并加注释。这个习惯帮我避开了后来多次类似的坑。希望这篇笔记里的源码、参数和避坑清单能帮到你尤其是那些准备把八邻域算法从仿真搬到真车上的开发者少走一段我走过的弯路。本文还有配套的精品资源点击获取 
长河君 · 2026/10/18 15:54:49 · 阅读 1.2k 八邻域算法详解：从栅格地图到A*路径规划的C++实践
简介面向智能车竞赛与嵌入式图像处理开发者这份可运行源码包专注于八邻域扫线算法在赛道识别与边界判断中的应用。算法针对光线干扰、差比和及计算量问题进行了优化输出像素生长方向信息适合需要快速部署路径识别功能的工程实践。资源共9个文件以C源码、头文件、Makefile构建脚本和Markdown说明文档为主构建脚本可用于直接编译部署说明文档梳理算法与调优思路全部代码与文档压缩后仅15KB结构紧凑。已有320人学习下载可作为备赛练习、入门学习或二次开发时的参考。通过源码可直观了解八邻域扫线的边界判定流程配合TC264硬件适配层与编译配置可快速验证差比和图像处理效果配套优化指南还点明了算法对图像质量要求高、需注意稳定性等工程要点方便读者在实际调车中少走弯路。1. 智能车八邻域算法到底是什么栅格地图上的信息传播规则做智能车路径规划的人迟早会撞上八邻域这个词。我在给某高校实训小车做栅格地图避障时第一版规划器用的是四邻域路径绕得像老太太走路后来换成八邻域转弯明显顺了路线缩短了将近三分之一但调试过程也踩了不少坑。这里先给一个结论八邻域不是一种算法而是一套栅格地图上的邻居定义规则——把当前格子周围的 8 个方向上、下、左、右、左上、右上、左下、右下全部纳入计算范围用在膨胀处理、障碍物检测、路径搜索和信息传播四种任务里。它解决的核心问题是“从任何一个格子出发下一步能去哪里、代价是多少”。本文给出一份可直接运行的 C 源码并把它嵌进 A* 路径规划里讲清楚参数怎么设、边界怎么处理、哪些地方最容易翻车。2. 八邻域的四种任务与最小复现从邻居定义到可跑通的临时脚本2.1 八邻域到底在“算”什么邻居集合与方向数组先建立一个统一抽象。假设栅格地图是一个二维数组每个格子存 0 或 10 代表可通行1 代表障碍。当前格子坐标记为 (r, c)行号向下增大列号向右增大。那么八邻域就是在其周围 8 个方向上各取一个格子方向编号从正上方开始顺时针旋转记成 0 到 7。我一般用一个静态数组来定义这 8 个方向的偏移量// 方向偏移表: {行偏移, 列偏移, 单位代价} // 0上, 1右上, 2右, 3右下, 4下, 5左下, 6左, 7左上 static const int kDirs[8][2] { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} }; static const double kCost[8] {1.0, 1.414, 1.0, 1.414, 1.0, 1.414, 1.0, 1.414};为什么方向集合是 8 而不是 4因为对角移动的代价与直行不同。直行从一个格子中心到相邻格子中心距离是 1 个格宽斜向移动距离是根号 2约 1.414。如果代码里把所有方向统一按 1 计费规划器会疯狂“抄近路”走斜线最后路径呈现锯齿。kCost 数组就是为这个准备的后面 A* 的 G 代价直接从这里取。2.2 最小复现脚本二十行 Python 验证邻居行为在写 C 工程之前我习惯先用 Python 快速验证逻辑。下面这段脚本不依赖任何第三方库功能是给定地图和一个起点把八邻域中所有可通行的格子打出来# -*- coding: utf-8 -*- # 最小八邻域采样脚本: 验证邻居顺序和边界过滤逻辑 DIRS [(-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1)] def get_neighbors(grid, r, c): rows len(grid) cols len(grid[0]) result [] for dr, dc in DIRS: nr, nc r dr, c dc if nr 0 or nr rows or nc 0 or nc cols: continue # 越界即不可达 if grid[nr][nc] 1: continue # 障碍物 result.append((nr, nc)) return result if __name__ __main__: grid [ [0, 0, 0, 0], [0, 1, 1, 0], [0, 0, 0, 0], ] print(get_neighbors(grid, 1, 2)) # 起点放在障碍物右边这段代码过滤条件只有两条越界丢弃、障碍丢弃。逻辑说明先算偏移后的坐标再判断是否在地图范围内最后查地图值。三个判断的先后顺序不能变——必须先查行列边界再查障碍否则数组会越界访问。运行后你会发现起点 (1, 2) 的 8 个邻居里正上方 (0, 2) 是空地、右上方 (0, 3) 是空地、正下方 (2, 2) 是空地但左上和正左都被障碍挡住返回结果里自然没有它们。2.3 四邻域与八邻域怎么选一张对比表说清适用场景很多新手拿到栅格地图就问“该用哪种”。答案取决于任务对路径长度的敏感度和车辆运动模型。四邻域只允许横平竖直的移动路径通常是曼哈顿风格转折多、总长度偏长八邻域允许斜穿路径更短但对车辆最小转弯半径完全不敏感时才能直接用。据我经验对于低速巡检小车、仓储 AGV 这类允许原地差速转向的场景八邻域更合适对于阿克曼转向的车型八邻域规划出的折线往往转不过去需要后接平滑或者干脆用四邻域加曲线拟合。维度四邻域八邻域邻居数量48移动方向上下左右增加 4 个对角方向对角代价不支持1.414路径长度偏长明显缩短转角平滑度直角多45° 角仍需平滑常见用途简单巡逻、走迷宫全局路径规划、膨胀处理还有一类任务是“八邻域找边界”常用于连通域标记从某个障碍格出发沿八邻域扩散给整片障碍打同一个编号。这时候用八邻域会把人字形相连的两个障碍判成同一个连通块而四邻域不会。这个差异在雷达点云投影成栅格后特别明显处理时务必想清楚你的“连通”语义是什么。3. 把八邻域落成 C 可运行源码工程结构、核心函数与编译命令3.1 工程文件清单与构建方式整理好的可运行源码我命名为“模拟项目X”结构上刻意保持极简只留必要文件方便你直接抄走改。完整清单如下文件作用CMakeLists.txt构建脚本生成可执行文件grid.h栅格地图结构体与接口声明grid.cpp地图加载、邻居获取、障碍检测实现main.cpp演示程序读地图、跑一遍八邻域遍历并输出结果构建方式用 CMake命令只有两行mkdir build cd build cmake .. make ./grid_demo ../map.txtmap.txt 是文本地图每行一串 0 和 10 是空地1 是障碍物。我一般会把第一行写成“行数 列数”方便动态分配内存。文件中所有代码均不依赖 ROS 或第三方库纯标准 C11任何带编译器的环境都能跑。3.2 核心实现邻居收集与对角穿墙检测下面是 grid.h 的接口定义。这里我把行和列的语义写死在注释里因为后面所有代码都靠这个约定对齐一旦搞反整个规划器行为都会错乱。// grid.h #ifndef GRID_H #define GRID_H #include vector #include string // 栅格坐标: row 为行号(0在上), col 为列号(0在左) struct GridPos { int row; int col; }; class Grid { public: Grid(); // 从文本文件加载地图, 格式见 README bool loadFromFile(const std::string path); int rows() const { return rows_; } int cols() const { return cols_; } // 判断某格是否可通行 bool isWalkable(int row, int col) const; // 获取当前格子的全部可行邻居(八邻域) std::vectorGridPos getNeighbors(int row, int col) const; private: int rows_ 0; int cols_ 0; std::vectorstd::vectorint data_; }; #endifgetNeighbors 是全部逻辑的核心直接上实现// grid.cpp 片段 #include grid.h #include fstream #include sstream std::vectorGridPos Grid::getNeighbors(int row, int col) const { // 偏移表: 上, 右上, 右, 右下, 下, 左下, 左, 左上 static const int dr[8] {-1, -1, 0, 1, 1, 1, 0, -1}; static const int dc[8] {0, 1, 1, 1, 0, -1, -1, -1}; std::vectorGridPos result; for (int i 0; i 8; i) { int nr row dr[i]; int nc col dc[i]; // 边界过滤必须放在最前面 if (nr 0 || nr rows_ || nc 0 || nc cols_) { continue; } // 目标格自身是障碍, 跳过 if (data_[nr][nc] 1) { continue; } // 对角移动需要检查两侧拐角: 防止斜穿墙角 if (dr[i] ! 0 dc[i] ! 0) { if (data_[row dr[i]][col] 1 || data_[row][col dc[i]] 1) { continue; } } result.push_back({nr, nc}); } return result; }这段代码里的第三个判断是对角穿墙检查属于血泪经验。现象是规划出的路径斜着从两个障碍格中间的角点滑过去在地图上看就是贴着墙根切角真车走的时候会蹭墙。原因在于目标格虽然是空地但它和目标格之间并不是完全“敞通”的。比如从 (r, c) 走到 (r-1, c1)只有当 (r-1, c) 和 (r, c1) 至少有一个空缺时车辆才有物理空间斜穿。我采取的策略是“两侧都要可通行”才放行这样杜绝切角代价是某些拥挤区域的路径会变绕。如果你做的是仿真环境可以放宽但实车我建议保留这个检查。3.3 主程序演示遍历全部格子验证邻居数量main.cpp 里我放了一个很实用的自检逻辑——统计每个格子的可行邻居数量。这个统计结果能帮你快速发现地图数据问题比如孤立点、被障碍完全围死的死胡同。// main.cpp #include grid.h #include iostream int main(int argc, char** argv) { if (argc 2) { std::cerr 用法: ./grid_demo map.txt std::endl; return 1; } Grid grid; if (!grid.loadFromFile(argv[1])) { std::cerr 地图加载失败 std::endl; return 1; } int unreachable_cnt 0; std::cout 各格子可达邻居数: std::endl; for (int r 0; r grid.rows(); r) { for (int c 0; c grid.cols(); c) { if (!grid.isWalkable(r, c)) { std::cout # ; continue; } auto neighbors grid.getNeighbors(r, c); std::cout neighbors.size() ; if (neighbors.empty()) { unreachable_cnt; } } std::cout std::endl; } std::cout 孤立可通行格数量: unreachable_cnt std::endl; return 0; }运行后终端会打印一张和地图大小一致的“邻居数量图”0 表示没有可走邻居。如果地图中间出现大范围 0说明地图数据在连接性上有问题。逻辑说明isWalkable 内部只做越界和障碍判断而 getNeighbors 做了完整过滤所以遍历时一定要先 isWalkable 再 getNeighbors避免重复处理障碍格。参数说明地图文件加载时我会忽略空行和以 # 开头的注释行这个行为在 loadFromFile 里实现便于直接维护地图文本。4. 在 A* 路径规划里用八邻域G 代价、启发式函数与优先级队列4.1 G 代价设定为什么对角线必须用 1.414把八邻域接进 A* 时最常见的翻车点就是代价图省事。有人把 8 个方向的 G 增量一律写成 1跑出来的路径会在两个等价路径之间反复横跳路径长度显示正确但实际轨迹呈锯齿状。原理上A* 的正确性依赖 G 代价与真实移动距离成正比。斜向移动的实际距离是根号 2 倍格宽如果你按 1 计搜索器会低估斜向移动的代价从而偏好斜线因为同样到达终点斜线步数更少、累计 G 更小。我一般这样组织数据在 Grid 类中增加一个静态方法输入两点坐标差返回移动代价。核心逻辑如下// 在 grid.h 中追加 static double moveCost(int dr, int dc) { if (dr 0 dc 0) return 0.0; if (dr ! 0 dc ! 0) return 1.414; // 对角 return 1.0; // 直行 }注意这里的 dr 和 dc 只能是 -1、0、1 三选一因为八邻域限定了一步只走一格。如果你把步长扩展成 2 格这个函数就得改成欧氏距离。还要注意 G 代价是浮点数A* 比较器里要用 epsilon 或直接比较 double不要用整数。4.2 启发式函数八邻域场景不能用曼哈顿距离八邻域允许斜向移动曼哈顿距离会高估实际代价导致搜索扩展更多节点、规划变慢欧氏距离会低估代价虽然最终路径依然正确但扩展范围变大。业界标准做法是 octile 距离公式为double octileDistance(int dr, int dc) { int dmax std::max(std::abs(dr), std::abs(dc)); int dmin std::min(std::abs(dr), std::abs(dc)); return dmax (1.414 - 1.0) * dmin; }这个公式的思路是从起点到终点最多能斜走 dmin 步剩下 dmax - dmin 步只能直走。理解这一点后你就能推导出为什么四邻域场景用曼哈顿、八邻域场景用 octile。相关改进还有一个细节启发式函数的值必须不大于真实剩余代价否则 A* 会退化成贪心搜索。octile 距离在八邻域下正好满足这个条件所以它既是高效也是最优的选择。4.3 A* 主循环的可运行实现下面给出完整 A* 主循环它在第 3 章 Grid 类基础上工作。我使用标准库的 priority_queue 做开放列表用二维数组存 G 值和父节点代码量约 80 行适合直接抄进自己的项目。#include grid.h #include queue #include cmath #include algorithm #include iostream struct Node { double f; // 总代价 double g; // 已走代价 int row; int col; bool operator(const Node other) const { return f other.f; } }; std::vectorGridPos aStar(const Grid grid, GridPos start, GridPos goal) { const int rows grid.rows(); const int cols grid.cols(); std::vectorstd::vectordouble g_score( rows, std::vectordouble(cols, 1e18)); std::vectorstd::vectorGridPos parent( rows, std::vectorGridPos(cols, {-1, -1})); std::priority_queueNode, std::vectorNode, std::greaterNode open; g_score[start.row][start.col] 0; open.push({0.0, 0.0, start.row, start.col}); const int dr[8] {-1, -1, 0, 1, 1, 1, 0, -1}; const int dc[8] {0, 1, 1, 1, 0, -1, -1, -1}; while (!open.empty()) { Node current open.top(); open.pop(); if (current.row goal.row current.col goal.col) { // 回溯路径并返回 std::vectorGridPos path; GridPos p {current.row, current.col}; while (p.row ! start.row || p.col ! start.col) { path.push_back(p); p parent[p.row][p.col]; } path.push_back(start); std::reverse(path.begin(), path.end()); return path; } for (int i 0; i 8; i) { int nr current.row dr[i]; int nc current.col dc[i]; if (nr 0 || nr rows || nc 0 || nc cols) continue; if (!grid.isWalkable(nr, nc)) continue; // 对角穿墙检查, 与 grid.cpp 中一致 if (dr[i] ! 0 dc[i] ! 0) { if (!grid.isWalkable(current.row dr[i], current.col) || !grid.isWalkable(current.row, current.col dc[i])) { continue; } } double step_cost (dr[i] ! 0 dc[i] ! 0) ? 1.414 : 1.0; double tentative_g current.g step_cost; if (tentative_g 1e-9 g_score[nr][nc]) { g_score[nr][nc] tentative_g; parent[nr][nc] {current.row, current.col}; double heuristic octileDistance(std::abs(nr - goal.row), std::abs(nc - goal.col)); open.push({tentative_g heuristic, tentative_g, nr, nc}); } } } return {}; // 路径不存在 }这里有几个必须说明的参数。优先级队列存放的是 f g h 的估值但 g_score 数组里存的是确定最优的 G 值两者用途不同。代码里用 tentative_g 1e-9 做浮点比较是为了避免 1.414 累加产生的误差导致路径无法更新。还有一点需要注意priority_queue 允许同一个格子被多次入队g_score 数组负责最终裁决这属于典型的“延迟删除”策略。如果你换用 std::set 做开放列表需要自己实现 Find 和 Update代码会涨一倍。对于地图不超过 1000×1000 的智能车场景priority_queue 方案足够。5. 八邻域避坑指南5 个让路径规划翻车的细节5.1 对角线穿墙路径从墙角斜切过去现象规划出的路径在障碍物的角上走对角线车模贴着障碍边缘滑过去仿真里看不出来实车测试时传感器报警。原因邻居过滤函数只判断了目标格是否可通行没有检查对角移动路径上的拐角格。从 (r, c) 走向 (r-1, c1) 时车辆实际会经过 (r-1, c) 和 (r, c1) 两个格子的角点这两个角点任一是障碍物理上就过不去。解决在 getNeighbors 和 A* 主循环里都加上拐角检查。代码见第 3.2 节和第 4.3 节。我采取的是“两侧都必须可通行”的严格策略。如果你做的是足球机器人这类允许挤压边界的场景可以放宽成“至少一侧可通行”但一定要全局统一否则会出现同一个路径在不同逻辑下结果不一致的玄学问题。5.2 八个方向统一 G 代价路径走出锯齿形现象路径总长度看起来短了但放大看全是折返和小锯齿车辆频繁转向实际行驶时间反而变长。原因G 代价全部写成 1导致斜向移动被低估搜索器疯狂选择斜向格子路径被“压扁”成锯齿线。解决严格执行直行 1.0、对角 1.414 的代价设定。同时启发式函数换成 octile否则 G 和 H 的度量单位不一致搜索效率会明显下降。调试方法把路径打印出来逐个计算相邻点之间的距离如果发现相邻点之间既有直行又有斜行但距离比例不对基本就是 G 代价出了问题。5.3 边界点邻居越界程序直接崩溃现象地图边缘的格子调用 getNeighbors 时数组越界程序在 Debug 模式下中断Release 模式下数据随机错乱。原因先查障碍值后查边界越界的坐标已经拿去访问 data_[nr][nc]。解决把边界判断放在最前面顺序固定为“算新坐标 → 查行列边界 → 查障碍值 → 查拐角”。这是一个非常基础的顺序问题但我在接手别人代码时至少遇到过三次。建议把这段判断封装成一个私有方法 safeWalkable(row, col)内部统一处理越界和障碍所有外部调用都走它一劳永逸。5.4 把“八邻域”泛化成“周围都要看”行为一团乱麻现象目标检测、避障、路径规划三段代码同时用了同一套八邻域逻辑但每段代码各自的“邻居”语义不同结果互相打架。原因八邻域只是一个采样规则。膨胀处理中“周围格有障碍就把当前格也标成障碍”和 A* 搜索中“下一步能走到哪个格”本质是两回事。前者是图像形态学操作不涉及移动代价后者是图搜索必须有代价和连通性语义。解决不要共用一个函数。我习惯在代码里区分两个名字getNeighborsForSearch 和 getNeighborsForInflate。前者带穿墙检查和代价后者只做范围采样。接口一旦分开就再也不会出现把膨胀结果直接当搜索图导致的地图“虚胖”问题。5.5 坐标轴方向混乱行和列反了所有结果全部镜像现象地图在文件里明明是对的但规划出的路径左右翻转或者起点终点连线呈镜像。原因地图文件用“行 列”存储而读取代码按“x y”处理导致 row 和 col 互换八邻域偏移表也随之错乱。解决在 Grid 类中严格统一坐标语义所有接口参数都叫 row 和 col不出现 x 和 y。地图文件第一行写清楚格式。还有一个笨但有效的小技巧在第 3.3 节的自检程序里打印邻居数量图从终端上一眼就能看出坐标是否镜像。我在某公司实训小车上就用这个办法定位过一起坐标颠倒的 Bug前后只花了十分钟。6. 终端可视化验证法一屏看清邻居顺序与路径质量6.1 用 ANSI 字符画快速渲染地图和路径调试八邻域相关代码我最常用的不是可视化工具而是一段 30 行的终端渲染脚本。它能把地图、障碍、起点、终点和规划路径一次性打印在终端里所有符号使用纯文本粘贴到任何环境都能跑# 终端路径渲染脚本 # 地图: 0空地 1障碍, 路径: 2路径点 def render(grid, pathNone, startNone, goalNone): path_set set(path or []) for r, row in enumerate(grid): line for c, val in enumerate(row): if (r, c) start: line S elif (r, c) goal: line E elif (r, c) in path_set: line * elif val 1: line # else: line . print(line) # 示例: 8x8 地图, 障碍物在中间区域 map_data [ [0,0,0,0,0,0,0,0], [0,0,0,1,1,0,0,0], [0,0,0,1,1,0,0,0], [0,0,0,0,0,1,0,0], [0,0,1,1,0,1,0,0], [0,0,1,0,0,1,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], ] path [(0,0), (1,1), (2,2), (3,3), (3,4), (4,5), (5,5), (6,6), (7,7)] render(map_data, pathpath, start(0,0), goal(7,7))运行后终端会输出一个 8×8 的字符地图S 是起点E 是终点* 是路径# 是障碍。这个可视化方法背后有一个我在调试中反复吃亏后悟出的逻辑路径规划问题中数值本身难看出问题但符号图能立刻暴露穿墙、绕远、锯齿三类典型错误。如果你发现路径贴着障碍但没穿墙通常是本节开头说的切角问题如果路径大步绕远通常是启发式函数高估如果路径密集锯齿通常是 G 代价定义问题。这三个判断在图形化界面里反而不如终端字符直观。6.2 验证清单每次改完代码后跑这四步我现在的习惯是每改完一次邻居逻辑就按下面四步做验证。第一步用 5×5 的全空地地图检查邻居数量中间格应返回 8 个邻居角格 3 个边格 5 个有任何一个数不对立刻停。第二步在 3×3 地图的角落放一个障碍确认对角穿墙检查生效。第三步用第 4 章的 A* 在带障碍地图上跑一遍检查路径上所有相邻点之差是否都在 [-1, 1] 范围内。第四步把路径总长度和曼哈顿距离对比如果两者差值超过 10%说明路径有明显绕路需要回看启发式参数。这四步全部跑通基本可以放心把代码接到实车上。最后分享一个教训有一次我把障碍值从 1 改成 255忘了同步修改 isWalkable 的判断整个规划器行为完全改变但终端渲染图看起来一切正常。从那以后我强制要求地图数据的值域必须集中管理所有阈值写在头文件里并加注释。这个习惯帮我避开了后来多次类似的坑。希望这篇笔记里的源码、参数和避坑清单能帮到你尤其是那些准备把八邻域算法从仿真搬到真车上的开发者少走一段我走过的弯路。本文还有配套的精品资源点击获取