做路径规划这些年我最大的一个体会是算法再花哨地图底层表达没选对后面所有优化都是白搭。之前在正方形网格上跑A跑得很顺手直到某次接到一个无人机区域覆盖项目要求轨迹必须贴合蜂窝状的任务扇区才发现正方形网格的八邻域移动模型根本没法直接套用。后来我用了两周多时间把A、遗传算法、蚁群优化和元胞自动机这四种经典算法逐一移植到六边形网格上针对四种实际场景做了对比实验才把整套流程彻底跑通。这篇文章就是那次完整实践的记录包含关键代码、调参经验和那些不跑一遍根本发现不了的坑。1. 为什么是六边形网格路径规划的地图底层逻辑1.1 六边形比正方形网格多出来的两个邻居正方形网格的移动方式无非两种四邻域上下左右和八邻域加上对角。四邻域的转角限制太大路径看起来像在城市里绕街角八邻域虽然灵活但存在对角穿墙的经典问题——两个格子只通过顶点接触机器人从对角线穿过去时实际姿态和路径宽度都对不上。六边形网格天然规避了这两类问题。一个六边形有6个邻居每个邻居都共享一条完整的边不存在点接触穿过的情况。这意味着移动方向更均匀路径转角可以做到60度粒度比正方形四邻域的90度更细腻任意两个相邻格子之间的中心距完全一致不会出现八邻域里斜着走比横着走更远的尴尬对于无人机、机器人这类有实际物理尺寸的载体六边形网格的共边相邻特性直接对应了安全通过性的判断。代价也很明显坐标运算比正方形复杂。正方形只需要(x, y)两个整数六边形如果只用简单的行列号邻居偏移表在不同朝向的网格下会互相矛盾。所以必须先约定坐标系统。1.2 四种典型场景与六边形网格的匹配方式我这一轮实验设计的四种场景分别是场景特点考察重点场景一开阔平原无障碍物算法基础搜索能力与路径效率场景二静态岛屿状障碍物避障能力与路径安全性场景三动态威胁区随时间变化的禁入区域动态重规划能力场景四单格宽度的曲折窄道迷宫狭窄通道通过能力与稳定性这四个场景基本覆盖了实际项目里最常见的路径规划诉求。开阔平原看似简单却能非常直接地暴露启发式函数写没写对——如果六边形距离计算有误A*在无障碍物的情况下也会绕远路。静态障碍物场景是绝大多数路径规划论文的标准实验配置。动态威胁区则是巡检机器人、仓储AGV的典型需求威胁区可能是临时封闭的通道、移动的障碍物投影区域。窄道迷宫最刁钻它考验的是算法是否能把路径精准地控制在单格宽度内不碰壁遗传算法的交叉算子在这种地图上特别容易产生非法个体。我用了一个统一的六边形网格地图生成器随机种子固定保证四个算法跑的是同一张图。这一点非常重要不然对比实验一点都不公平。2. 坐标系统与统一环境封装先把地基夯实2.1 轴向坐标与立方体坐标的选择六边形网格坐标系统主要有三种偏移坐标offset、轴向坐标axial和立方体坐标cube。我强烈建议直接用轴向坐标加立方体坐标互转而不是偏移坐标。偏移坐标就是你在纸上画蜂窝然后按行列编号每行的起点错开半格。这种坐标做渲染很方便但做邻居计算时要区分奇行偶行偏移表很容易写错。轴向坐标用(q, r)两个轴立方体坐标用(x, y, z)三个轴且满足 x y z 0。六边形的6个邻居在轴向坐标下是固定的常量表# axial (q, r) 坐标系下的六方向邻居 HEX_DIRECTIONS [ (1, 0), (1, -1), (0, -1), (-1, 0), (-1, 1), (0, 1) ]这个表的顺序从右上开始顺时针排。为什么要有负值因为六边形的行与行之间有错位单纯靠加1减1表达不了这种错位关系。立方体坐标最大的价值在于距离计算。六边形网格上两个格子的距离不是曼哈顿距离而是立方体坐标差绝对值中的最大值def axial_to_cube(q, r): x q z r y -x - z return x, y, z def cube_distance(a, b): return max(abs(a[0] - b[0]), abs(a[1] - b[1]), abs(a[2] - b[2])) def axial_distance(q1, r1, q2, r2): return cube_distance(axial_to_cube(q1, r1), axial_to_cube(q2, r2))我在最初测试时用过一个错误的启发函数——把轴向坐标当成平面直角坐标算欧氏距离结果A*跑出来的路径在无障碍物地图上都偏离了最优解。这个问题不跑大尺寸地图根本发现不了小地图上差距可能就一格。2.2 障碍物地图生成与统一的代价计算接口为了让四个算法公平对比我封装了一个统一的HexGrid类。它只负责三件事管理网格状态自由/障碍物/起点/终点、生成邻居列表、计算任意两点距离。class HexGrid: def __init__(self, width, height, obstacle_ratio, seed): self.width width self.height height self.rng random.Random(seed) self.obstacles set() # 随机生成障碍物但要保证起点终点附近干净 for q in range(width): for r in range(height): if self.rng.random() obstacle_ratio: if not self._is_near_start_or_goal(q, r): self.obstacles.add((q, r)) def neighbor_list(self, q, r): result [] for dq, dr in HEX_DIRECTIONS: nq, nr q dq, r dr if self._in_bounds(nq, nr): if (nq, nr) not in self.obstacles: result.append((nq, nr)) return result def cost(self, frm, to): # 统一代价相邻格子移动代价为1斜坡等场景可在此扩展 return 1.0统一代价接口是关键。后续如果想加入地形权重泥地、坡道、禁飞区只需要改cost方法四个算法的外层逻辑都不用动。这就是接口设计带来的好维护性。3. A*在六边形网格上的落地细节3.1 邻居生成与启发函数六边形距离的正确写法A*的框架大家都知道open列表、closed集合、g值、f值、回溯父节点。在六边形网格上唯一的区别在于两点第一节点展开时用neighbor_list而不是四方向或八方向。这一步如果前面的邻居偏移表写对了就没问题。第二启发函数必须使用axial_distance而不是欧氏距离的平方根。import heapq def a_star(grid, start, goal): open_heap [(0, start)] g_score {start: 0.0} came_from {} while open_heap: current heapq.heappop(open_heap)[1] if current goal: return reconstruct_path(came_from, start, goal) for nxt in grid.neighbor_list(*current): tentative g_score[current] grid.cost(current, nxt) if tentative g_score.get(nxt, float(inf)): came_from[nxt] current g_score[nxt] tentative f tentative axial_distance(nxt[0], nxt[1], goal[0], goal[1]) heapq.heappush(open_heap, (f, nxt)) return None注意这里有个性能小优化格子的f值第一次入堆之后如果后续又找到了更优的g直接再push一次靠heapq来判断。堆里可能出现同一个节点的多个条目但因为它的f值变小了下一次pop出来的必然是最新最小条目。这种惰性删除方式比自己去更新堆内元素要简单得多。3.2 开放列表优化与路径回溯的实现技巧在六边形网格上跑20×20还是20×20如果单次搜索问题不大但在大尺寸地图比如100×100上频繁调用A*性能问题就暴露了。我实测的优化方式有两个open列表用heapq检查某节点是否在open里不靠遍历而是用g_score字典判断。如果要频繁做路径搜索比如动态场景每秒钟重规划一次可以把启发函数乘以一个权重1.0到1.2之间。权重大于1时A变成weighted A搜索速度加快但代价是路径可能比最优解长几个百分点。动态场景中这个取舍通常很划算。路径回溯的部分有个容易踩坑的地方因为六边形网格的q和r可以是负值字典键不能用二维数组下标而是用元组。既然用了元组就不要在回溯时用判断两个坐标是否相等而是直接用起点作为终止条件。def reconstruct_path(came_from, start, goal): path [goal] current goal while current ! start: current came_from[current] path.append(current) path.reverse() return pathA的路径质量在这种网格上非常稳定。如果启发函数写对了它找到的路径就是理论最优路径。我这边把A作为基准算法后面三个算法都拿它做对比参照。4. 遗传算法不走单点搜索改用种群试错4.1 路径编码与交叉算子的兼容性问题遗传算法GA在路径规划里的第一个难点是编码方式。正方形网格上常用定长编码——固定路径包含N个节点每个节点是坐标值。但六边形网格下定长编码有先天缺陷如果染色体长度L太短在较长路径的多障碍场景下根本没有足够节点到达终点如果L太长大量冗余节点会让交叉操作变得极其低效——两个父代交换片段后子代里可能出现大量重复节点和明显的绕路。我最终用的是变长编码加路径点序列每个基因是一个六边形坐标染色体的长度等于路径经过的格子数。交叉算子用了常见的部分匹配交叉思路找到两条父路径中相同节点同一个格子在相同节点位置做单点交叉交换后半段。def crossover(parent1, parent2): common_nodes set(parent1) set(parent2) if not common_nodes: return parent1, parent2 # 无共同节点直接返回 node random.choice(list(common_nodes)) idx1 parent1.index(node) idx2 parent2.index(node) child1 parent1[:idx1] parent2[idx2:] child2 parent2[:idx2] parent1[idx1:] return child1, child2这个算子的逻辑很直白两个解如果都经过同一个中间格子那它们在这个格子之前和之后是可以互相拼接的。实测效果非常不错收敛速度明显快于定长编码下的随机交叉。4.2 适应度函数、早熟抑制与收敛判据适应度函数是整个GA设计里最需要斟酌的地方。我用的公式是def fitness(path, grid, goal): if not path: return 0.0 if path[-1] ! goal: distance_penalty axial_distance(path[-1][0], path[-1][1], goal[0], goal[1]) else: distance_penalty 0.0 length len(path) return 1.0 / (length 10.0 * distance_penalty)对于碰到障碍物的非法个体在生成阶段就做过滤不让非法路径进入种群。这个处理比在适应度函数里做碰撞惩罚更干净——因为相邻基因之间如果穿过障碍物这个路径本身就是不可执行的留着它只会污染后续交叉和变异。早熟现象是GA在路径规划里最容易翻车的地方。表现就是种群迭代到第20代左右所有个体的路径都趋于一致但明显不是全局最优——它们集体卡在了一个局部最优解里。我用的抑制手段有两条精英保留策略每代把最优的两个个体直接复制到下一代保证不退化自适应变异率种群多样性低于阈值时把变异率从0.05拉高到0.2让个体有更大扰动跳出局部最优。收敛判据我建议用连续N代最优适应度无提升而不是固定迭代次数。固定次数在很多场景下要么不够收敛要么白白浪费算力。我用的是连续30代无提升就终止。5. 蚁群优化信息素如何在六边形邻居间流动5.1 状态转移规则里的修正项蚁群算法ACO在网格路径规划里的核心机制是一只只虚拟蚂蚁从起点出发在每个六边形上按概率选择下一个邻居。状态转移概率是经典的形式def transition_probability(grid, current, neighbor, goal, pheromone, alpha, beta): tau pheromone.get((current, neighbor), initial_pheromone) ** alpha eta (1.0 / (axial_distance(neighbor[0], neighbor[1], goal[0], goal[1]) 1.0)) ** beta return tau * eta这里的eta是启发信息我用的是到终点的六边形距离的倒数再加1这么设计是为了防止距离为0时除零。一个非常容易被忽视的细节是邻居选择时不能选已经访问过的格子。六边形网格的拓扑结构让蚂蚁很容易在一个小闭环里打转如果不加禁忌表蚂蚁会无限循环直到步数上限。5.2 信息素挥发与全局更新的平衡点信息素更新分两步挥发和沉积。挥发的标准公式是def update_pheromone(pheromone, all_paths, best_path, rho, Q): # 挥发 for key in pheromone: pheromone[key] * (1 - rho) # 每只蚂蚁沿其路径沉积 for path in all_paths: deposit Q / path_cost(path) for i in range(len(path) - 1): pheromone[(path[i], path[i1])] deposit # 精英策略对最优路径额外增强 elite_deposit 10.0 * Q / path_cost(best_path) for i in range(len(best_path) - 1): pheromone[(best_path[i], best_path[i1])] elite_deposit挥发系数rho的取值很敏感。我试过0.5结果前期信息素消失太快蚂蚁很难形成稳定的路径共识又试过0.05结果是旧信息素残留过久动态障碍物场景下重规划反应太慢。最终rho取0.2时效果最好前20代收敛明显但在环境变化时也能在10代以内重新调整。信息素的初始值不能设为0。如果初始为0所有边的tau都是0第一轮蚂蚁的选择就完全由启发信息决定失去探索信息的意义。我习惯把初始信息素设为一个略大于0的常数比如0.1。蚁群算法在六边形网格上的路径质量通常略差于A*但它有个独特优势天然支持多目标搜索。如果有多个终点或者需要规划多条备选路径蚁群的群体搜索特性可以直接产出多解这一点A*要做额外改动才做得到。6. 元胞自动机用势能扩散替代显式搜索6.1 波前演化规则与邻居耦合元胞自动机CA的思路和其他三个算法完全不同。它不做从起点出发逐点展开搜索而是把整个地图看成一组元胞通过局部规则迭代演化出一个势能场。我的实现是这样的从终点开始终点势能记为0每一轮演化中每个自由格子将自己的势能更新为所有邻居势能的最小值加1。这个规则不断扩散像水波一样从终点向整个地图蔓延def wavefront_update(grid, potential): new_potential potential.copy() for (q, r) in grid.free_cells: if (q, r) grid.goal: continue neighbor_values [ potential[n] for n in grid.neighbor_list(q, r) if n in potential ] if neighbor_values: new_potential[(q, r)] min(neighbor_values) 1 return new_potential需要重复迭代直到势能场不再变化。这就是典型的波前传播wavefront propagation。从计算角度看这个迭代过程本质上是在解一个动态规划方程每次更新只依赖邻居状态天然适合并行计算。如果地图尺寸很大可以用GPU或者多线程加速这是另外三个算法不太容易做到的。6.2 路径提取与动态障碍的天然优势势能场收敛之后从起点沿梯度下降方向走就能得到路径每次选择周围势能最小的邻居逐步走到终点。因为势能值是终点距离的度量梯度下降走的路径是从起点到终点的最短路径。CA的路径提取代码很简单def extract_path(grid, potential, start): path [start] current start while current ! grid.goal: candidates [ n for n in grid.neighbor_list(*current) if potential.get(n, float(inf)) potential.get(current, float(inf)) ] if not candidates: break current min(candidates, keylambda n: potential[n]) path.append(current) return path这里有个边界情况如果起点被障碍物围死或者地图不连通起点的势能永远为无穷大也就提取不出路径。需要在迭代后判断一下。CA在动态障碍物场景下有个巨大的优势障碍物变化时不需要重新从零开始算。因为在原来的势能场上局部重新迭代几轮就能把障碍物影响冲刷到整个地图。相比之下A*的动态重规划需要整棵搜索树重建GA和ACO需要重新迭代种群。这也是我在动态场景测试中CA表现最亮眼的原因。7. 四算法同场景对比路径长度、耗时与稳定性7.1 同一地图四个算法的原始数据实验条件六边形网格尺寸30×30随机种子固定障碍物比例15%按格子数计算起点(2, 2)目标(27, 20)。每个算法独立运行30次取平均。算法平均路径长度平均规划耗时成功率特点A*28.3格8ms100%理论最优稳定快速遗传算法31.7格1.8s93%耗时高路径偶有抖动蚁群优化29.6格3.2s96%接近最优参数敏感元胞自动机28.3格12ms100%路径最优重规划成本低这个结果在预期之中。A作为完备算法在静态无障碍物场景下最优且稳定。CA的波前传播本质上等价于Dijkstra所以路径长度和A一致只是计算方式不同。GA和ACO属于启发式搜索它们不保证全局最优而且收敛时间明显更长但在更大的搜索空间或者需要多解的场景下它们仍然是值得保留的选项。7.2 参数敏感性分析与选型建议参数敏感性实验我用的是单参数扰动法每次只改一个参数其他保持不变看路径质量和收敛时间的变化。对A*来说唯一值得调的是权重系数。权重为1时路径最优权重1.2时搜索速度提升约40%但路径长度最多增加5%。动态场景建议开1.1到1.2静态场景就用1.0。对GA来说最关键的参数是种群大小和变异率。种群太小20容易早熟种群太大100收敛时间成倍增加。我实测30×30地图上种群50、迭代上限200是比较均衡的配置。对ACO来说alpha和beta的比值关系比绝对值更重要。alpha1、beta5时蚂蚁偏理性路径质量更好但容易陷入局部alpha2、beta3时探索性更强但收敛变慢。想快速收敛就用前者。选型建议一句话总结静态场景无脑A*动态场景且地图规模中等以下用CA需要同时输出多条备选路径选ACO地图特别大且对实时性要求不高的复杂约束场景选GA。8. 最后一公里的经验清单8.1 路径后处理把折线路径变成可执行轨迹四个算法输出的都是一串六边形格子坐标是离散的路径。实际执行时不能直接拿这串坐标去控制机器人或无人机因为转角处会剧——六边形的60度转向在物理世界就是一次急转弯。我通常做的后处理是三次样条平滑。把路径节点作为控制点生成一条C2连续的曲线然后在每个格子中心做碰撞检测如果平滑后的曲线穿过障碍物就把那段局部权重加大重新拟合。这一步是最耗时间的但也是从算法能跑到项目能交付之间必须跨越的鸿沟。8.2 六边形网格可视化调试的几个技巧调试六边形网格比调试正方形网格要麻烦因为坐标到像素的映射不是简单的乘一个格子尺寸就完事。我用的渲染映射是def hex_to_pixel(q, r, size): x size * (3.0 / 2.0 * q) y size * (sqrt(3.0) / 2.0 * q sqrt(3.0) * r) return x, y这个公式是轴向坐标转像素坐标的标准形式。一个简单的验证方法是把坐标(0,0)、(1,0)、(0,1)打出来肉眼确认这三个格子构成一个倒三角而不是一条直线。另外强烈建议在调试阶段把每个格子的势能值和f值直接渲染到网格上。不然你会陷入一种尴尬境地算法明明在按预期工作但你不知道它在哪一步偏离了直觉。我调试元胞自动机时就是靠把势能值可视化才一眼看出某个方向的波前没有正确穿过窄通道。还有一个不算技巧但很实用的经验跑实验时一定要固定随机种子。GA和ACO自身的随机性波动非常大不固定种子你根本分不清算法的差异是真实差异还是随机噪声。我在最终对比实验时所有算法都用同一个随机种子每轮跑30次取平均才得出了那组有说服力的数据。那次项目之后我的路径规划工具箱里就常驻了这四套算法的Python实现。虽然现在深度学习端到端路径规划很火但经典算法在可解释性、稳定性和资源占用上的优势短期内仍然无法替代。六边形网格这个底层地图表达也在越来越多的无人机、机器人项目中成为首选框架。把这四种算法在这种网格上吃透后面不管遇到什么样的路径规划需求你都至少有一个不会错的大方向。