如何让走线不可见:ZigZag 针迹路由背后的 A* 网格搜索原理

原创2026-11-16 14:04:231,432 阅读

如何让走线不可见:ZigZag 针迹路由背后的 A* 网格搜索原理

ZigZag 是一款免费开源的刺绣软件,它的 Travel(走线)路由模块用网格 A* 搜索,在图形之间的空地上自动规划针脚的"隐形路线"——让连接走线藏在填充针迹之下或稍后覆盖的针迹之下,不再从边缘露出来。本文带你拆解这套针迹路由的原理。

ZigZag 刺绣软件工作室界面,展示走线路由后的填充与缎面设计

为什么走线必须"藏起来"

刺绣机缝完一个图形、移向下一个图形时,通常要剪断机针。剪开的线头会翘在背面,需要手工拉出;如果直接让针脚在表面横穿,成品上就会留下一条明晃晃的走线,观感非常业余。

ZigZag 的规划器更倾向于"不剪、藏住":让连接走线从正在缝的填充之下,或稍后覆盖上来的针迹之下穿过。源码开篇的注释点明了这个目标(src/route.rs):"Travel stitches that stay out of sight"——找一条藏在暗处的路,绕过孔洞、穿过窄口、贴着覆盖物走。

规划器会把每段走线归类为四种方式(src/design.rs 的 TravelHow):

  • Across:直接横穿填充内部
  • Edge:绕着填充轮廓内侧走一圈
  • Under:从对象自己尚未缝到的针迹之下、或稍后缝上来的针迹之下穿过
  • Open:在空白布料上以平针直接连接

前三种都属于"隐藏走线",而核心引擎就是本文主角:网格 A* 搜索。

把"隐形地面"变成网格:Zone

ZigZag 走线路由效果示例:山景刺绣徽章中的填充与轮廓走线

算法第一步是回答:哪些地方,走线穿过时不会被人看见? ZigZag 称这块隐形地面为 Zone,把它切成一张网格(src/route.rs)。构建过程分三步:

  1. 填充网格:用轮廓的交点扫描把区域切成格子。格子最小 0.25 mm,再按区域总面积自动放大,最多约 40 万个格子,保证绣框大小的区域也能快速搜索(src/route.rs);
  2. 标注离边距离:为每个格子标记它离区域边缘有多远,搜索会优先走离边缘至少 3 个格子的中央通道,避免走线从覆盖物边缘"露头";
  3. 连通分量:给每块连通区域编号,两个端点之间若不在同一块,一眼就知道无路可走,连搜索都省了。

离边标注正是"不露头"的关键:太靠近边缘的格子移动代价被放大 4 倍(NEAR_EDGE),路线自然会被推到中央走廊;只有空间太窄(如比安全距离还细的窄口)时,它才贴边走。

🧭 A* 搜索:寻路四步走

核心函数 Zone::route_from 在这张网格上做一次标准 A*(src/route.rs):

  • 代价 g:每走一步的代价 = 步长 × 权重,中央格子权重 1,近边格子 ×4;
  • 启发 h:到目标的直线距离,乘以贪心系数 GREED = 2.0——找到一条"足够好"的路线就提前收手,大量贴近边缘的格子(如抖色块)不必全部权衡,速度显著提升(src/route.rs);
  • 移动:支持 8 个方向,但禁止斜向"切角"钻进区域外部——路线绝不会切进孔洞;
  • 剪枝:g+h 估计超过预算(travel_route × 4)的格子直接放弃。

还有两个贴心细节:起点允许在区域外几个格子以内(拉力补偿会让针迹末端略超出轮廓),enter 会自动吸附到最近的可行格子(src/route.rs);搜索的工作数组在多次寻路之间复用,只靠一个"搜索编号"区分新旧,无需反复清零。

后处理:拉直路线,切分成针脚

A* 给出的格子路线是"台阶状"的,直接缝会很啰嗦。ZigZag 做了两步后处理(src/route.rs):

  1. 拉直:从每个拐点尽量把直线延伸——只要延伸后的直线代价不高于原路线(不会误切边缘),就合并成一段;
  2. 切分针脚:每段按最长 3.0 mm(STITCH = 30 units)切成针脚,保证每一针都在机器能力范围内;
  3. 终检:拉直后总长仍超预算,则放弃这条路,交给规划器换备选方案。

找不到路时的退路 ✂️

网格搜索可能一无所获,规划器按优先级依次回退:

  • 间隙极小(≤ max_jump_no_trim,默认 1 mm):直接跳过去,机器不剪线;
  • 间隙落在同一填充内部:直线横穿(Across);
  • 图形间的空白布料:平针连接(Open);
  • 勾选 over_sewn 时:实在没有隐藏路线,就允许在已有针迹之上走一条平针——少剪几次线,只留一条可见的线。

与此同时,质检模块 src/checks.rs 的 exposed_travel 会扫描所有"暴露在已缝针迹之上、横跨 8 针以上"的走线,逐条报告给编辑器和 AI agent,方便你精确定位问题所在。

ZigZag 深色模式工作室界面,展示针迹规划与线序面板

参数速查与相关模块

参数 默认值 含义
travel_route 500 units(约 50 mm) 隐藏走线的最大长度,超过则剪线
travel_inside 60 units(约 6 mm) 填充内部直线横穿的最大间隙
max_jump_no_trim 10 units(约 1 mm) 不剪线跳过的最大间隙
over_sewn 关闭 无隐藏路线时允许在针迹上走线

相关源码入口:

小结

ZigZag 的针迹路由用三步就让走线"消失"在成品里:把隐形地面切成网格、用 A* 搜索找到绕开孔洞和窄口的最短隐藏路线、再用边缘回避权重和拉直后处理保证走线绝不露头。下次打开一个设计,看看 Issues 面板——如果没有任何暴露走线的警告,说明这套隐藏路线已经帮你把该藏的线都藏好了 ✅

登录后查看全文
zigzag