画流程图的时候连线有三种常见画法直线、曲线、直角折线。前两种好写两点一连或者算两个控制点就完事。直角折线也叫正交连线是流程图里最常用的也是最难写对的线要横平竖直要绕开中间的节点还不能拐得像迷宫。forxi.cn 的流程图默认连线就是这种直角折线。这篇不讲任何产品里的实现只从零写一个能跑的正交路由130 行原生 JSnode直接运行然后用实测数据说明一个参数的影响拐弯惩罚。测试环境Apple M2、Node v25.8.0。文中代码都是为这篇文章单独写的示意实现。为什么不能直接在像素网格上跑 A*最直觉的做法是把画布切成 1px 或 10px 的格子在格子上跑 A*。问题有两个格子太多。一个 1600×900 的画布10px 一格也有 14400 个点每拖动一下节点就要重算所有连线太慢。路径很丑。细网格上最短路径往往是一堆锯齿台阶还得再做一次平滑。实际常用的是稀疏网格也叫 orthogonal visibility graph 的简化版只在有意义的坐标上取点。思路只在有意义的坐标上建图哪些坐标有意义每个节点外扩一圈安全距离后的四条边线要么贴着这些边走要么在它们之间走起点、终点端口伸出去的那个点相邻两条边之间的中线线从两个节点中间穿过时走中线最好看。把所有候选 x 和所有候选 y 做笛卡尔积去掉落在节点内部的点就是图上的顶点。相邻顶点同一行或同一列之间只要线段不穿过节点就连一条边。十几个节点的图候选坐标通常只有几十个顶点几百个比像素网格小两三个数量级。关键状态里要带方向普通 A* 的状态是当前在哪个点。正交路由不够用因为我们想惩罚拐弯而这一步算不算拐弯取决于上一步是从哪个方向来的。所以状态要变成(点, 进入方向)代价是代价 走过的曼哈顿长度 拐弯次数 × BEND_COST启发函数仍然用到终点的曼哈顿距离它不会高估拐弯惩罚只加不减A* 的最优性还在。另外两个细节起点方向固定。从节点右边伸出的线第一段必须往右走否则线会贴着节点边往回折。禁止掉头。180° 回头在正交连线里永远不是好路径直接剪掉能省不少搜索。完整代码// 正交连线路由稀疏网格 带拐弯惩罚的 A*// 示意实现只依赖原生 JS可直接 node 运行constMARGIN16// 连线离节点的最小距离constBEND_COST40// 每拐一次弯的额外代价越大越倾向少拐弯functioninflate(r,m){return{x:r.x-m,y:r.y-m,w:r.w2*m,h:r.h2*m}}// 点是否严格在矩形内部边界上不算线可以贴着走functioninside(px,py,r){returnpxr.xpxr.xr.wpyr.ypyr.yr.h}// 水平或竖直线段是否穿过矩形内部functionsegHits(x1,y1,x2,y2,r){if(y1y2){if(y1r.y||y1r.yr.h)returnfalsereturnMath.max(x1,x2)r.xMath.min(x1,x2)r.xr.w}if(x1r.x||x1r.xr.w)returnfalsereturnMath.max(y1,y2)r.yMath.min(y1,y2)r.yr.h}// 从节点某一侧的中点伸出一小段作为连线真正的起止点functionport(rect,side){constcxrect.xrect.w/2,cyrect.yrect.h/2constp{top:{x:cx,y:rect.y,dx:0,dy:-1},bottom:{x:cx,y:rect.yrect.h,dx:0,dy:1},left:{x:rect.x,y:cy,dx:-1,dy:0},right:{x:rect.xrect.w,y:cy,dx:1,dy:0},}[side]return{...p,ox:p.xp.dx*MARGIN,oy:p.yp.dy*MARGIN}}functionroute(nodes,from,to){constobstaclesnodes.map(ninflate(n,MARGIN))constsport(from.rect,from.side)consttport(to.rect,to.side)// 1. 候选坐标障碍物边界 端口 相邻障碍物之间的中线constxsnewSet([s.ox,t.ox]),ysnewSet([s.oy,t.oy])for(constoofobstacles){xs.add(o.x);xs.add(o.xo.w)ys.add(o.y);ys.add(o.yo.h)}constaddMidset{constarr[...set].sort((a,b)a-b)for(leti0;iarr.length-1;i)set.add((arr[i]arr[i1])/2)}addMid(xs);addMid(ys)constX[...xs].sort((a,b)a-b)constY[...ys].sort((a,b)a-b)// 2. 网格点去掉落在障碍物内部的constkey(i,j)i*Y.lengthjconstfreenewSet()for(leti0;iX.length;i)for(letj0;jY.length;j)if(!obstacles.some(oinside(X[i],Y[j],o)))free.add(key(i,j))constsiX.indexOf(s.ox),sjY.indexOf(s.oy)consttiX.indexOf(t.ox),tjY.indexOf(t.oy)// 3. A*状态 (网格点, 进入方向)代价 长度 拐弯惩罚constDIRS[[1,0],[-1,0],[0,1],[0,-1]]consth(i,j)Math.abs(X[i]-X[ti])Math.abs(Y[j]-Y[tj])conststartDirDIRS.findIndex(dd[0]s.dxd[1]s.dy)constopen[{i:si,j:sj,d:startDir,g:0,f:h(si,sj),prev:null}]constbestnewMap()while(open.length){open.sort((a,b)a.f-b.f)// 节点不多排序代替堆够用constcuropen.shift()constskkey(cur.i,cur.j)*4cur.dif(best.has(sk)best.get(sk)cur.g)continuebest.set(sk,cur.g)if(cur.iticur.jtj){constpts[]for(letncur;n;nn.prev)pts.unshift({x:X[n.i],y:Y[n.j]})returnsimplify([{x:s.x,y:s.y},...pts,{x:t.x,y:t.y}])}DIRS.forEach(([di,dj],d){if(cur.d0di-DIRS[cur.d][0]dj-DIRS[cur.d][1])return// 不走回头路constnicur.idi,njcur.jdjif(ni0||nj0||niX.length||njY.length)returnif(!free.has(key(ni,nj)))returnif(obstacles.some(osegHits(X[cur.i],Y[cur.j],X[ni],Y[nj],o)))returnconstlenMath.abs(X[ni]-X[cur.i])Math.abs(Y[nj]-Y[cur.j])constbendcur.d0cur.d!d?BEND_COST:0constgcur.glenbend open.push({i:ni,j:nj,d,g,f:gh(ni,nj),prev:cur})})}returnnull// 没有路通常是节点把端口完全围住了}// 去掉共线的中间点只留拐点functionsimplify(pts){constout[pts[0]]for(letk1;kpts.length-1;k){constaout[out.length-1],bpts[k],cpts[k1]constcollinear(a.xb.xb.xc.x)||(a.yb.yb.yc.y)if(!collinear)out.push(b)}out.push(pts[pts.length-1])returnout.filter((p,k,arr)k0||p.x!arr[k-1].x||p.y!arr[k-1].y)}functiontoSvgPath(pts){returnpts.map((p,k)${k?L:M}${p.x},${p.y}).join( )}module.exports{route,toSvgPath}if(require.mainmodule){// 开始 → 判断 → 结束中间挡着一个「处理」节点conststart{x:40,y:40,w:120,h:50}constblock{x:220,y:30,w:120,h:180}constend{x:420,y:150,w:120,h:50}constnodes[start,block,end]constptsroute(nodes,{rect:start,side:right},{rect:end,side:left})console.log(pts)console.log(toSvgPath(pts))console.log(bends:,pts.length-2)}跑一下$ node ortho.js [ { x: 160, y: 65 }, { x: 204, y: 65 }, { x: 204, y: 226 }, { x: 404, y: 226 }, { x: 404, y: 175 }, { x: 420, y: 175 } ] M160,65 L204,65 L204,226 L404,226 L404,175 L420,175 bends: 4「开始」和「结束」中间横着一个高高的节点线从它下方绕了过去返回的点数组可以直接转成 SVGpath。拐弯惩罚到底有多大作用同一组 6 个节点从「开始」底部连到「结束」左侧只改BEND_COST左边只算长度拐了 5 次右边每拐一次加 40只拐 1 次。两条线的总长完全一样都是 712px。这就是只算长度的问题在曼哈顿距离下从左上到右下有大量等长的路径台阶形和 L 形长度一样A* 选中哪一条取决于展开顺序基本是随机的。加一个拐弯惩罚等于告诉算法长度一样的时候挑拐弯少的。为了不只看一个例子我随机生成了 200 个布局每个布局 12 个互不重叠的节点端口方向轮换分别用四档惩罚跑一遍BEND_COST平均拐弯次数平均长度平均耗时04.57597px4.39ms203.51597px6.37ms403.43600px8.30ms803.35604px11.91ms几点观察从 0 到 20 收益最大平均少拐一次多长度一点没变。20 之后收益迅速变小40 到 80 只少了 0.08 次拐弯长度开始往上涨为了少拐弯宁可绕远。耗时随惩罚上升惩罚越大启发函数只算距离和真实代价差得越远A* 需要展开更多状态。80 的耗时接近 0 的三倍。我自己的取法是惩罚设成节点间距的五分之一左右这组数据里就是 20~40 之间。这个实现没解决的事写到这里只能算能用离一个成熟的流程图编辑器还差不少说几个我知道的多条线会重叠。每条线独立计算两条线很可能挤在同一条中线上并排走看起来像一条。常见做法是算完之后做通道分配把同一段上的多条线平移错开这一步比路由本身还麻烦。没有处理线与线的交叉。代价里只算了长度和拐弯没算穿过别的线的次数。加进去不难但每一步都要查已有线段复杂度会明显上去。排序代替堆。open.sort在几百个状态时没问题节点上百之后要换成二叉堆。节点完全被围住时直接返回 null。实际产品里总得画点什么一般退化成一条直线再提示用户。拖动时的性能。随机布局 12 个节点平均 8ms 左右单条线够快但拖一个节点可能牵动十几条线要么只重算相连的线要么拖动过程中先画直线、松手后再算折线。小结正交连线的核心就三件事稀疏网格建图、状态里带方向、代价里加拐弯惩罚。第三点最容易被忽略也最影响观感实测一个 20~40 的惩罚就能把平均拐弯从 4.6 次降到 3.5 次左右长度几乎不变。如果只是想画个流程图不想自己写可以直接用 forxi.cn 上的流程图工具连线默认就是直角折线也能切成直线或曲线。
