我最早接触六边形网格路径规划是因为在做一个策略类游戏的原型。正方形网格一横一竖四个方向走起来总觉得太“直角”换成六边形之后六个方向等距移动距离的计算也统一了地图上的走法一下子就自然了很多。后来做无人机在栅格化地图上的航线搜索发现六边形网格在城市低空走廊建模里同样有优势。于是就有了这个项目把A*、遗传算法、蚁群优化和元胞自动机这四种经典算法全部放进六边形网格这个统一地图模型里分别跑通四种不同特点的路径规划场景并用Python把完整代码落地。这篇文章我会把整个研究过程中最核心的东西讲清楚六边形网格的坐标系统怎么选、四种算法在这个地图模型上分别怎么建模、四种场景为什么这样划分、代码里哪些细节不能写错、以及我实际调试时踩过的坑。无论你是做游戏AI、机器人导航还是纯粹想找一份能直接改来用的六边形网格路径规划代码这篇文章应该都比你自己从零摸索要省力得多。1. 为什么是六边形网格它解决了正方形网格解决不了的问题1.1 正方形网格的“距离”是分裂的正方形网格看起来简单但你只要认真做一次路径规划就会发现问题一个格子走上下左右步长是1走对角线步长是根号2。这意味着在地图上移动时两个邻居格子看似“相邻”真实代价却不一致。为了让A*这样的算法正常工作你得额外区分对角和对边移动启发函数也要跟着调。六边形网格没有这个问题。每个格子周围恰好有6个邻居从中心到任何一个邻居的距离完全相等一步的代价永远是1。距离度量天然统一路径规划的核心“代价计算”就变得非常干净。这也是《文明》系列战棋地图偏爱六边形的原因——玩家无论朝哪个方向走消耗的行动力都是等值的。1.2 坐标系统选型立方体坐标是最优选做六边形网格第一个难关就是坐标表示。网上能搜到三种方案偏移坐标offset、轴向坐标axial、立方体坐标cube。偏移坐标最容易理解像正方形网格一样用(row, col)表示但奇数行和偶数行相邻格子的位置要偏移半个格子邻居计算必须判断奇偶分支。这个分支逻辑写起来不复杂却特别容易出bug我第一版代码就栽在“奇数行向上还是向下偏移”搞反了。轴向坐标把六边形压缩成(q, r)两个轴两个轴夹角60度比偏移坐标简洁但距离公式记起来仍有点绕。立方体坐标最优雅把一个点在二维平面上的六边形网格映射到三维空间里满足xyz0的平面上方向数组变成固定的六个三维向量距离计算变成两个立方体坐标差的绝对值的最大值。我最终的方案是内部存储和算法计算全部用cube坐标只有在最后绘制地图时转换回offset坐标。这样既保证了计算简单又方便出图。# 立方体坐标下六个邻居方向 CUBE_DIRECTIONS [ (1, -1, 0), (1, 0, -1), (0, 1, -1), (-1, 1, 0), (-1, 0, 1), (0, -1, 1) ] def cube_neighbor(hex_pos, direction_index): dx, dy, dz CUBE_DIRECTIONS[direction_index] x, y, z hex_pos return (x dx, y dy, z dz) def cube_distance(a, b): return max(abs(a[0] - b[0]), abs(a[1] - b[1]), abs(a[2] - b[2]))1.3 网格转坐标与取整一个极其隐蔽的坑六边形网格坐标还有一个绕不过去的环节当你从屏幕像素点反算格子坐标或者从offset坐标转回cube坐标时浮点数运算会产生误差。如果直接把浮点结果四舍五入到最近的整数坐标可能落到错误的格子上。正确的做法是做一个“立方体坐标取整”操作先四舍五入得到临时坐标然后计算与原始浮点坐标的偏差把偏差最大的那个分量修正掉因为cube坐标必须满足xyz0这个约束。def cube_round(frac): x, y, z frac rx round(x) ry round(y) rz round(z) dx abs(rx - x) dy abs(ry - y) dz abs(rz - z) if dx dy and dx dz: rx -ry - rz elif dy dz: ry -rx - rz else: rz -rx - ry return (rx, ry, rz)这个取整函数是所有六边形网格程序的基石。后来我把整个项目翻新时发现路径突然绕远、A*搜索卡死这类诡异问题八成都是这里出了问题。2. 四种算法在六边形网格上的建模差异2.1 A*启发函数必须是可采纳的A在六边形网格上的实现和正方形网格没有本质区别核心差异全部集中在启发函数。如果用曼哈顿距离做启发值会严重高估到目标的真实距离导致启发函数“不可采纳”A会退化成类似贪心搜索的东西找出来的路径不是最短的。在cube坐标下两个六边形格子之间的距离就是三点差绝对值的最大值即 max(|dx|, |dy|, |dz|)。这个距离公式既是一致且可采纳的启发函数也是精确的实际步长所以A*在六边形网格上可以直接拿它同时当“启发值”和“路径代价”。我用的开放表是Python的heapq每次从堆里弹出代价最小的节点生成六个邻居后分别计算g值和f值记录父节点最后回溯路径。import heapq def a_star(start, goal, obstacles, max_iterations100000): open_heap [(0, start)] g_score {start: 0} came_from {} closed set() while open_heap and len(closed) max_iterations: f_current, current heapq.heappop(open_heap) if current in closed: continue if current goal: path [] while current in came_from: path.append(current) current came_from[current] path.append(start) return path[::-1] closed.add(current) for direction_index in range(6): neighbor cube_neighbor(current, direction_index) if neighbor in obstacles or neighbor in closed: continue tentative_g g_score[current] 1 if tentative_g g_score.get(neighbor, float(inf)): came_from[neighbor] current g_score[neighbor] tentative_g h cube_distance(neighbor, goal) heapq.heappush(open_heap, (tentative_g h, neighbor)) return None2.2 遗传算法编码方式决定算法上限把遗传算法用在六边形网格路径规划上第一件事是决定染色体怎么编码。常见的做法有三种定长格子ID序列、方向序列、关键点序列。我最终用的是“关键点序列 路径修补”的编码方式染色体是一串格子坐标每个坐标代表路径必须经过的关键点实际路径由这些关键点用A*逐段连接而成。这样做的好处是染色体长度固定、交叉操作简单坏的个体不会因为出现非法路径直接废掉。适应度函数由三部分组成路径总代价核心目标、路径经过障碍物的惩罚、绕路冗余惩罚。交叉算子我用的是单点交叉两个父代染色体从随机位置切开交换后半段。变异算子有两种随机替换某个关键点的位置或者随机插入/删除一个关键点。在六边形网格上交叉后两个片段拼接处往往不在同一个连通区域所以每轮进化后都要调用一个“修复函数”把断开的路径重新连起来。这是遗传算法在这个项目中比方形网格更容易出现的问题。2.3 蚁群优化信息素矩阵怎么设计蚁群优化ACO在六边形网格上做路径规划最关键的是信息素矩阵的组织方式。一般是对每个可通行格点存储一个信息素浓度值蚂蚁在格点之间移动时根据信息素浓度和启发信息计算转移概率。状态转移概率公式是当前格点i选择邻居j的概率等于 (tau_ij^alpha) * (eta_ij^beta) 的归一化结果。tau_ij是格点上的信息素浓度eta_ij是启发信息通常取1/distance_to_goal。alpha和beta分别控制信息素和启发信息的权重。每一轮迭代后所有蚂蚁走过的路径都会释放信息素同时全图信息素按挥发系数rho衰减。我用的信息素更新方式是“蚂蚁周模型”——先等一轮蚂蚁全部走完再用本轮最优路径统一更新信息素矩阵。给一个核心片段参考def transition_probability(current, neighbors, pheromone, goal, alpha, beta): total 0.0 probabilities [] for n in neighbors: eta 1.0 / (cube_distance(n, goal) 1e-6) p (pheromone[n] ** alpha) * (eta ** beta) probabilities.append(p) total p return [p / total for p in probabilities]蚁群算法在这里有个先天优势信息素会挥发所以当障碍物或代价变化时旧路径上的信息素会逐渐消退蚂蚁能重新探索出新路线。这是它比其他算法更适合动态重规划场景的根本原因。2.4 元胞自动机用局部规则“涌现”出路径行为元胞自动机CA严格说起来不是寻路算法它没有起点到目标点的全局搜索过程而是通过每个格子根据局部邻居状态反复更新从整体上涌现出某种空间行为。在路径规划里它最适合被用在多智能体协同、交通流模拟、路径平滑这类“局部规则决定性很强”的任务上。在六边形网格上每个元胞有6个邻居状态可以定义为空闲、障碍、被智能体占用、目标点。更新规则的设计决定了一切。我采用了一套类似双向行人流的规则每个智能体根据邻居状态判断是否有障碍冲突若前方被占用则选择代价最小的空闲邻居绕行同时用随机扰动避免所有智能体挤向同一个格子。核心更新循环大致是这样def cell_automaton_update(grid, agents, target): # 先根据目标方向计算每个格子的偏好方向 preference {} for cell in grid.all_cells(): preference[cell] cube_direction_to_target(cell, target) new_positions {} for agent in agents: candidates [cube_neighbor(agent.pos, i) for i in range(6)] candidates [c for c in candidates if grid.is_passable(c) and c not in new_positions] candidates.sort(keylambda c: cube_distance(c, target) random.uniform(0, 0.5)) if candidates: new_positions[agent.pos] candidates[0] return new_positions这里有个很关键的认识CA不适合单独用来做全局最短路径搜索但它是四种算法里对网格几何形状最不敏感的一个因为它只依赖“邻居关系”不依赖精确的距离度量。所以在我的项目里CA主要负责多智能体局部避碰和路径细化而不是从零找路。3. 四种场景的划分逻辑让算法去它最擅长的地方3.1 场景划分总览很多人做多种算法对比时喜欢把四种算法丢到同一个静态地图上直接比谁找的路径短、谁跑得快。但这样其实没有发挥出这四种算法的差异优势。我做的划分思路是不同算法对应不同场景特性静态精确搜索、组合优化、动态重规划、多智能体局部协同四种需求分别匹配最合适的算法。整个场景划分如下表场景匹配算法场景特点核心验证指标场景一A*地图完全静态单智能体寻路解的最优性、搜索时间场景二遗传算法多目标点遍历带组合优化约束总路径长度、收敛代数场景三蚁群优化障碍物或通行代价动态变化重规划耗时、路径质量场景四元胞自动机多智能体同图移动需要局部避碰冲突次数、整体流量3.2 为什么A*放在静态精确场景A*是唯一能保证在启发函数可采纳时找到最短路径的算法。静态地图上地图信息完整、代价不变这个“最优性”优势可以被完全释放。我让它在场景一里负责单智能体从起点到终点的精确最短路径验证标准就是解的最优性。3.3 遗传算法放在多点遍历场景多点遍历本质上是组合优化问题访问顺序不同总路径长度差异巨大。遗传算法对这类问题的编码和适应度设计非常自然。我把场景二设计成机器人需要依次访问多个指定目标点最后返回终点路径顺序就是染色体的排列编码。遗传算法一批一批地进化出更好的访问顺序和旅行商问题TSP的处理思路一致。3.4 蚁群算法放在动态重规划场景动态环境是蚁群算法的表演舞台。场景三里地图中央会周期性出现随机障碍物蚂蚁从起点出发需要不断适应变化。信息素的挥发机制让旧路线逐渐失去吸引力正反馈机制又让新路线被更早发现的蚂蚁快速强化这种“遗忘强化”的动态平衡是A和遗传算法不具备的。而A遇到障碍变化就必须完全重跑一遍开销大很多。3.5 元胞自动机放在多智能体协同场景场景四设计成一个多智能体同时从不同位置出发走向各自目标的任务。这种场景下全局寻路只是第一步智能体之间的局部冲突才是主要矛盾。元胞自动机通过同步更新所有格点状态让每个智能体每次移动都参考周围邻居的最新状态用极其简单的局部规则实现了避碰行为整体流量非常平滑。这个场景不适合用集中式A*因为智能体数量增加后状态空间会指数爆炸。4. Python实现细节从网格类到四个算法的主干代码4.1 六边形网格基类在做任何算法之前先封装一个HexGrid类。它负责管理地图尺寸、障碍物集合、坐标转换和邻居查询。这样后续四个算法都不需要直接关心六边形几何细节。我建议把这个类写稳后面所有算法都建立在它上面一旦坐标系统有错四个算法会一起爆掉。class HexGrid: def __init__(self, size, obstacles()): self.size size self.obstacles set(obstacles) self.cells [self.cube_offset_to_cube(x, y) for x in range(size) for y in range(size)] def in_bounds(self, hex_pos): x, y, z hex_pos return -(self.size // 2) x self.size // 2 and \ -(self.size // 2) y self.size // 2 and \ -(self.size // 2) z self.size // 2 def is_passable(self, hex_pos): return self.in_bounds(hex_pos) and hex_pos not in self.obstacles def get_neighbors(self, hex_pos): return [cube_neighbor(hex_pos, i) for i in range(6) if self.is_passable(cube_neighbor(hex_pos, i))]4.2 A*的实现注意点A*的代码前面已经给过主干。实际项目里我在三个地方做了加强一是用了heapq的元组比较需要注意如果f值相同会继续比较后面两个元素如果直接把hex_pos元组放进去元组也是可以比较的没有问题二是加了一个最大迭代次数作为兜底防止地图不可达时无限循环三是把单步移动代价统一设为1因为六边形网格所有邻居等距这是这个项目能保持简洁的基础。调试时我还验证过一个细节closed集合里存放的是已经确定最优代价的节点如果从堆里弹出时发现该节点已经在closed中直接跳过。这个判断放在循环开头避免同一节点被重复扩展。4.3 遗传算法的交叉和变异实现遗传算法代码中比较关键的是交叉后的路径修复。我写了一个repair_path函数当交叉产生的关键点序列无法通过A*连通时自动在断裂处插入中间关键点如果仍然无法连通就丢弃这段染色体重新生成一个随机个体参与竞争。变异操作和修复是配套的。我的变异率设为0.15变异方式有三种等概率触发随机移动某个关键点到它的任意邻居格子、删除一个关键点、插入一个随机关键点。做完变异后同样要执行连通性检测。def repair_path(individual, grid): # 把不连通的关键点列表修复为连通路径 repaired [individual[0]] for i in range(len(individual) - 1): segment a_star(individual[i], individual[i 1], grid.obstacles) if segment is None: return None # 无法修复淘汰 repaired.extend(segment[1:]) return repaired有了这个修复函数交叉算子就可以大胆地做单点交换而不用担心生成大量非法个体。这也让遗传算法在这个项目里的收敛速度比我想象的快很多基本在第50代左右就稳定了。4.4 蚁群算法的信息素更新蚁群的信息素更新分成两步挥发和沉积。挥发是所有格点的信息素统一乘以(1 - rho)沉积是在本轮最优路径经过的所有格点上增加Q / path_length的信息素。为了避免信息素无限累积我还设置了一个上下限最小0.01最大5.0超过这个范围就截断。转移概率的alpha和beta分别是1.0和2.0这个比例是我试了几个组合之后觉得效果最稳的。alpha太高会让蚂蚁过早收敛到一条不一定好的路线上beta太高又会让蚂蚁过于贪心、忽略信息素变成强化版贪心搜索。这些参数敏感性测试在第5章详细讲。def update_pheromone(pheromone, best_path, rho, Q): for cell in pheromone: pheromone[cell] * (1 - rho) for cell in best_path: pheromone[cell] Q / len(best_path)4.5 元胞自动机的同步更新规则CA的代码最容易出错的地方是更新顺序。如果用逐智能体更新前面的智能体移动会影响后面智能体的判断产生“先手优势”。我采用的是同步更新先根据当前帧所有格点状态计算每个智能体的目标位置全部算完后再统一写入下一帧状态。这样每个智能体的决策都基于同一时刻的地图快照公平且无偏。具体实现时维护了两份网格状态一份是当前帧的occupancy_map一份是下一帧的new_occupancy_map。计算完所有智能体的move决定后一次性把new_occupancy_map覆盖回occupancy_map。这个做法的另一个好处是天然支持并行计算后面如果想用numpy向量化加速只需要把状态矩阵抽出来批量更新。5. 实验结果与参数调优实测数据和踩坑记录5.1 四种算法在各自场景下的实测对比我用了25x25大小的六边形网格地图障碍物比例约25%。每个场景跑30次取平均主要结果如下场景算法平均路径长度平均寻路耗时成功率静态单目标A*21.36ms100%多点遍历遗传算法78.51.2s93%动态重规划蚁群优化27.8最终14ms/帧89%多智能体协同元胞自动机108总路径2ms/帧97%A*在静态场景下的表现没有悬念又快又准。遗传算法初始随机解质量很差总路径能到130以上进化50代之后稳定在80左右说明进化策略在多目标点遍历上确实有效。蚁群在动态场景里比较有意思前几帧的路径因为信息素还没形成质量不高但大约10帧后逐渐稳定到接近静态最优的水平而且障碍物突然出现时它只需要2到3帧就能绕过。元胞自动机牺牲了一点路径最优性但换来了极低的冲突次数整体流量非常平稳。5.2 参数调优里最关键的几个坑遗传算法的早熟现象是我遇到的最大问题。当种群多样性不足时所有个体快速收敛到同一个局部最优解交叉算子再怎么交叉也产生不了新结构。我在代码里加了“种群多样性阈值”每轮统计所有个体的路径长度标准差如果标准差低于阈值就触发“移民”——随机生成10%的新个体加入种群打乱节奏。蚁群算法的信息素初始值也很关键。刚开始我图省事把所有格子初始信息素设为1.0结果前几轮蚂蚁几乎完全按照启发信息贪心移动信息素的正反馈完全不起作用。后来我把初始信息素设成一个较小的值让启发信息的权重一开始略占上风但随着信息素累积逐渐把搜索引向优质路径效果好很多。A在六边形网格上最容易踩的坑是启发函数不可采纳。如果你在xxl网格上直接用曼哈顿距离路径会比最优长10%左右。最典型的症状是路径上会出现不必要的绕行而且直觉上很难发现。我的排查方法是把A结果和BFS结果在同一个地图上对比一旦发现长度不一致就基本确定启发函数出了问题。5.3 坐标系相关的调试心得我复盘整个项目时发现七八成bug都出在坐标转换上而不是算法本身。这里分享两个排错技巧第一单元测试优先测邻居关系。在六边形网格上跑一圈从一个格子出发的所有邻居用距离公式验证每个邻居距离为1同时验证方向数组的对称性。这个测试能在一分钟内发现方向向量写错的问题。第二渲染可视化时在格子中心打印坐标。我曾经以为offset转cube的公式写对了结果渲染出来地图上的格子排列是乱的最后发现是取整函数里的约束条件写反了。打印坐标后这种问题基本一眼就能定位。调试这类代码一定要分阶段验证先验证坐标系统再验证邻居和距离最后才进算法。四个算法同时出错时问题几乎一定在公共的网格类里而不是在算法本身。6. 可以顺带扩展的方向做完这个项目之后我自己同时有两点体会一是这四种算法不是非此即彼的竞争关系而是可以组合的——比如用A*生成遗传算法的初始种群可以大幅加速收敛用蚁群算法在动态环境里先跑出信息素场再给元胞自动机提供局部避碰参考方向协同效果非常明显。另一点是六边形网格路径规划并不只属于游戏AI。城市低空配送航线规划、无人机覆盖巡检、无线传感器网络的路由选择凡是移动代价各向同性的场景六边形网格都是一个比正方形网格更贴合真实世界的建模基础。如果你现在正卡在某个六边形网格的路径规划项目里希望这套实现和这些踩坑记录能帮你少走点弯路。