共计 15002 个字符，预计需要花费 38 分钟才能阅读完成。
如果你用过流程图绘制工具，那么可能会好奇节点之间的连接线是如何计算出来的：
不要走开，追随本文一起来探索一下吧。
最终成果预览：https://wanglin2.github.io/AssociationLineDemo/
根本构造
先应用 Vue3 搭建一下页面的根本构造，为了简化 canvas 操作，咱们应用 konvajs 库来绘制图形。
页面模板局部，提供一个容器即可：
<div class="container" ref="container"></div>js局部，次要是应用 konvajs 来创立两个可拖拽的矩形元素及一个连接线元素，当然目前连接线并没有顶点数据：
import {onMounted, ref} from "vue";
import Konva from "konva";
const container = ref(null);
// 创立两个矩形、一个折线元素
let layer, rect1, rect2, line;
// 矩形挪动事件
const onDragMove = () => {
// 获取矩形实时地位
console.log(rect1.x(), rect1.y(), rect2.x(), rect2.y());
};
// 初始化图形
const init = () => {const { width, height} = container.value.getBoundingClientRect();
// 创立舞台
let stage = new Konva.Stage({
container: container.value,
width,
height,
});
// 创立图层
layer = new Konva.Layer();
// 创立两个矩形
rect1 = new Konva.Rect({
x: 400,
y: 200,
width: 100,
height: 100,
fill: "#fbfbfb",
stroke: "black",
strokeWidth: 4,
draggable: true,// 图形容许拖拽
});
rect2 = new Konva.Rect({
x: 800,
y: 600,
width: 100,
height: 100,
fill: "#fbfbfb",
stroke: "black",
strokeWidth: 4,
draggable: true,
});
// 监听进行拖拽事件
rect1.on("dragmove", onDragMove);
rect2.on("dragmove", onDragMove);
// 矩形增加到图层
layer.add(rect1);
layer.add(rect2);
// 创立折线元素
line = new Konva.Line({points: [],// 以后它的顶点数据是空的，所以你还看不见这个元素
stroke: "green",
strokeWidth: 2,
lineJoin: "round",
});
// 折线增加到图层
layer.add(line);
// 图层增加到舞台
stage.add(layer);
// 绘制
layer.draw();};
onMounted(() => {init();
});成果如下：
接下来咱们只有在图形拖拽时实时计算出关联线的顶点而后更新到折线元素里就能够绘制出这条连接线。
计算出关联线最有可能通过的点
整个画布上所有的点其实都是可能通过的点，然而咱们的连接线是【横平竖直】的，且要尽可能是最短路线，所以思考所有的点没有必要，咱们能够依照肯定规定放大范畴，而后再从中计算出最优路线。
首先终点和起点两个点必定是必不可少的，以下图为例，假如咱们要从左上角的矩形顶部两头地位连贯到右下角的矩形顶部两头地位：
接下来咱们定两个准则：
1. 连接线尽量不能和图形的边重叠
2. 连接线尽量不能穿过元素
为什么说尽量呢，因为当两个元素间隔过近或有重叠的话这些都是无奈防止的。
联合下面两个准则咱们能够规定元素四周肯定间隔内都不容许线通过（当然除了连贯起起点的线段），这样就相当于给元素里面套了个矩形的突围框：
通过起起点且垂直于起起点所在边的直线与突围框的交点肯定是会通过的，并且这两个点是惟一能间接和起起点相连的点，所以咱们能够把这两个点当做是“终点 ” 和 ” 起点”，这样在计算的时候能够少计算两个点：
在矩形挪动事件里进行点的计算，首先缓存一下矩形的地位和尺寸信息，而后定义终点和起点的坐标，最初定义一个数组用来寄存所有可能通过的点：
// 矩形挪动事件
const onDragMove = () => {computedProbablyPoints();
};
// 计算所有可能通过的点
let rect1X, rect1Y, rect1W, rect1H, rect2X, rect2Y, rect2W, rect2H;
let startPoint = null, endPoint = null;
const computedProbablyPoints = () => {
// 保留矩形的尺寸、地位信息
rect1X = rect1.x();
rect1Y = rect1.y();
rect1W = rect1.width();
rect1H = rect1.height();
rect2X = rect2.x();
rect2Y = rect2.y();
rect2W = rect2.width();
rect2H = rect2.height();
// 起起点
startPoint = [rect1X + rect1W / 2, rect1Y];
endPoint = [rect2X + rect2W / 2, rect2Y];
// 保留所有可能通过的点
let points = [];}因为起起点能够在矩形的任一方向，所以咱们写个办法来获取伪终点和伪起点，并将它们增加到数组里：
const computedProbablyPoints = () => {
// ...
// 伪终点：通过终点且垂直于终点所在边的线与突围框线的交点
let fakeStartPoint = findStartNextOrEndPrePoint(rect1, startPoint);
points.push(fakeStartPoint);
// 伪起点：通过起点且垂直于起点所在边的线与突围框线的交点
let fakeEndPoint = findStartNextOrEndPrePoint(rect2, endPoint);
points.push(fakeEndPoint);
}
// 找出终点的下一个点或起点的前一个点
const MIN_DISTANCE = 30;
const findStartNextOrEndPrePoint = (rect, point) => {
// 终点或起点在右边
if (point[0] === rect.x()) {return [rect.x() - MIN_DISTANCE, rect.y() + rect.height() / 2];
} else if (point[1] === rect.y()) {
// 终点或起点在上边
return [rect.x() + rect.width() / 2, rect.y() - MIN_DISTANCE];
} else if (point[0] === rect.x() + rect.width()) {
// 终点或起点在左边
return [rect.x() + rect.width() + MIN_DISTANCE,
rect.y() + rect.height() / 2,
];
} else if (point[1] === rect.y() + rect.height()) {
// 终点或起点在下边
return [rect.x() + rect.width() / 2,
rect.y() + rect.height() + MIN_DISTANCE,
];
}
};伪终点和伪起点会造成一个矩形，这个矩形和终点元素突围框能够组成一个更大的矩形，这个矩形的四个角是连接线有可能通过的点：
将这几个点增加到数组里，有一个点和伪起点反复了，不过没关系，咱们最初再去重即可：
const computedProbablyPoints = () => {
// ...
// 伪终点和伪起点造成的矩形 和 终点元素突围框 组成一个大矩形 的四个顶点
points.push(
...getBoundingBox([
// 伪终点起点
fakeStartPoint,
fakeEndPoint,
// 终点元素突围框
[rect1X - MIN_DISTANCE, rect1Y - MIN_DISTANCE], // 左上顶点
[rect1X + rect1W + MIN_DISTANCE, rect1Y + rect1H + MIN_DISTANCE], // 右下顶点
])
);
}
// 计算出给定点能够造成的最大的矩形的四个顶点
const getBoundingBox = (points) => {let boundingBoxXList = [];
let boundingBoxYList = [];
points.forEach((item) => {boundingBoxXList.push(item[0]);
boundingBoxYList.push(item[1]);
});
let minBoundingBoxX = Math.min(...boundingBoxXList);
let minBoundingBoxY = Math.min(...boundingBoxYList);
let maxBoundingBoxX = Math.max(...boundingBoxXList);
let maxBoundingBoxY = Math.max(...boundingBoxYList);
return [[minBoundingBoxX, minBoundingBoxY],
[maxBoundingBoxX, minBoundingBoxY],
[minBoundingBoxX, maxBoundingBoxY],
[maxBoundingBoxX, maxBoundingBoxY],
];
};
从图上能够看进去，关联线要么从左边连过来，要么从右边连过来。
同样，伪终点和伪起点造成的矩形也会和起点元素突围框造成一个更大的矩形，这个矩形的四个顶点也是有可能会通过的，这当起点元素位于终点元素上方时会通过：
// 伪终点和伪起点造成的矩形 和 起点元素突围框 组成一个大矩形 的四个顶点
points.push(
...getBoundingBox([
// 伪终点起点
fakeStartPoint,
fakeEndPoint,
// 起点元素突围框
[rect2X - MIN_DISTANCE, rect2Y - MIN_DISTANCE], // 左上顶点
[rect2X + rect2W + MIN_DISTANCE, rect2Y + rect2H + MIN_DISTANCE], // 右下顶点
])
);
以上这些点根本能满足起起点都在元素上方的状况，然而对于上面这种终点在下面起点在右边状况就不行了：
很显著看到如果存在上面这个点就能够了：
这其实就是后面所说的通过起起点且垂直于起起点所在边的两条线的交点，求交点能够先依据两个点计算出直线方程，再联立两个方程计算交点，然而咱们的线都是横平竖直的，所以没必要这么麻烦，两条线要么是平行的，要么是一条程度一条垂直，很容易列举完所有状况：
// 计算两条线段的交点
const getIntersection = (seg1, seg2) => {
// 两条垂直线不会相交
if (seg1[0][0] === seg1[1][0] && seg2[0][0] === seg2[1][0]) {return null;}
// 两条水平线不会相交
if (seg1[0][1] === seg1[1][1] && seg2[0][1] === seg2[1][1]) {return null;}
// seg1 是水平线、seg2 是垂直线
if (seg1[0][1] === seg1[1][1] && seg2[0][0] === seg2[1][0]) {return [seg2[0][0], seg1[0][1]];
}
// seg1 是垂直线、seg2 是水平线
if (seg1[0][0] === seg1[1][0] && seg2[0][1] === seg2[1][1]) {return [seg1[0][0], seg2[0][1]];
}
};有了这个办法咱们就能够把这个交点增加到数组里：
const computedProbablyPoints = () => {
// ...
// 通过终点且垂直于终点所在边的线 与 通过起点且垂直于起点所在边的线 的交点
let startEndPointVerticalLineIntersection = getIntersection([startPoint, fakeStartPoint], [endPoint, fakeEndPoint]);
startEndPointVerticalLineIntersection && points.push(startEndPointVerticalLineIntersection);
}
到这里计算出来的点能满足大部分状况了，然而还有一种状况满足不了，当起起点绝对时：
所以当后面计算的 startEndPointVerticalLineIntersection 点不存在的时候咱们就计算通过伪终点和伪起点的一条垂直线和一条水平线的交点（黄色的两个点）：
const computedProbablyPoints = () => {
// ...
// 当 通过终点且垂直于终点所在边的线 与 通过起点且垂直于起点所在边的线 平行时，计算一条垂直线与通过另一个点的伪点的水平线 的节点
if (!startEndPointVerticalLineIntersection) {
let p1 = getIntersection([startPoint, fakeStartPoint],// 假如通过终点的垂直线是垂直的
[fakeEndPoint, [fakeEndPoint[0] + 10, fakeEndPoint[1]]]// 那么就要计算通过伪起点的水平线。水平线上的点 y 坐标雷同，所以 x 坐标轻易加减多少数值都能够
);
p1 && points.push(p1);
let p2 = getIntersection([startPoint, fakeStartPoint],// 假如通过终点的垂直线是程度的
[fakeEndPoint, [fakeEndPoint[0], fakeEndPoint[1] + 10]]// 那么就要计算通过伪起点的垂直线。);
p2 && points.push(p2);
// 上面同上
let p3 = getIntersection([endPoint, fakeEndPoint],
[fakeStartPoint, [fakeStartPoint[0] + 10, fakeStartPoint[1]]]
);
p3 && points.push(p3);
let p4 = getIntersection([endPoint, fakeEndPoint],
[fakeStartPoint, [fakeStartPoint[0], fakeStartPoint[1] + 10]]
);
p4 && points.push(p4);
}
}
到这里可能通过的点就找的差不多了，一共有：
接下来进行去重以及导出相干的数据：
const computedProbablyPoints = () => {
// ...
// 去重
points = removeDuplicatePoint(points);
return {
startPoint,
endPoint,
fakeStartPoint,
fakeEndPoint,
points,
};
}
// 去重
const removeDuplicatePoint = (points) => {let res = [];
let cache = {};
points.forEach(([x, y]) => {if (cache[x + "-" + y]) {return;} else {cache[x + "-" + y] = true;
res.push([x, y]);
}
});
return res;
};
暴力求解：回溯算法
如果不思考效率和最短距离，咱们能够间接应用广度优先搜寻或者说是回溯算法，也就是从终点开始，挨个尝试终点周边的点，到下一个点又挨个尝试下一个点周边所有的点，如果遇到起点，那么完结，把所通过的点连接起来就是一条门路，接下来咱们尝试一下。
在开始算法之前须要先实现如何找出一个点周边的点，如果是在网格中，那么很简略，一个点周边的点就是 x、y 坐标加 1 或减 1，然而咱们这些点彼此之间的间隔是不确定的，所以只能依据坐标进行搜寻，比方要找一个点左边最近的点，那么依据该点的y 坐标进行搜寻，看有没有 y 坐标雷同的点，有的话再找出其中最近的，当然，还要检测找出的这个点和指标点的连线是否会穿过起起点元素，是的话这个点也要跳过：
// 找出一个点周边的点
const getNextPoints = (point, points) => {let [x, y] = point;
let xSamePoints = [];
let ySamePoints = [];
// 找出 x 或 y 坐标雷同的点
points.forEach((item) => {
// 跳过指标点
if (checkIsSamePoint(point, item)) {return;}
if (item[0] === x) {xSamePoints.push(item);
}
if (item[1] === y) {ySamePoints.push(item);
}
});
// 找出 x 方向最近的点
let xNextPoints = getNextPoint(x, y, ySamePoints, "x");
// 找出 y 方向最近的点
let yNextPoints = getNextPoint(x, y, xSamePoints, "y");
return [...xNextPoints, ...yNextPoints];
};
// 检测是否为同一个点
const checkIsSamePoint = (a, b) => {if (!a || !b) {return false;}
return a[0] === b[0] && a[1] === b[1];
};接下来就是 getNextPoint 办法的实现：
// 找出程度或垂直方向上最近的点
const getNextPoint = (x, y, list, dir) => {
let index = dir === "x" ? 0 : 1;// 求程度方向上最近的点，那么它们 y 坐标都是雷同的，要比拟 x 坐标，反之亦然
let value = dir === "x" ? x : y;
let nextLeftTopPoint = null;
let nextRIghtBottomPoint = null;
for (let i = 0; i < list.length; i++) {let cur = list[i];
// 查看以后点和指标点的连线是否穿过起起点元素
if (checkLineThroughElements([x, y], cur)) {continue;}
// 左侧或上方最近的点
if (cur[index] < value) {if (nextLeftTopPoint) {if (cur[index] > nextLeftTopPoint[index]) {nextLeftTopPoint = cur;}
} else {nextLeftTopPoint = cur;}
}
// 右侧或下方最近的点
if (cur[index] > value) {if (nextRIghtBottomPoint) {if (cur[index] < nextRIghtBottomPoint[index]) {nextRIghtBottomPoint = cur;}
} else {nextRIghtBottomPoint = cur;}
}
}
return [nextLeftTopPoint, nextRIghtBottomPoint].filter((point) => {return !!point;});
};checkLineThroughElements办法用来判断一条线段是否穿过或和起起点元素有重叠，也是一个简略的比拟逻辑：
// 查看两个点组成的线段是否穿过起起点元素
const checkLineThroughElements = (a, b) => {let rects = [rect1, rect2];
let minX = Math.min(a[0], b[0]);
let maxX = Math.max(a[0], b[0]);
let minY = Math.min(a[1], b[1]);
let maxY = Math.max(a[1], b[1]);
// 水平线
if (a[1] === b[1]) {for (let i = 0; i < rects.length; i++) {let rect = rects[i];
if (minY >= rect.y() &&
minY <= rect.y() + rect.height() &&
minX <= rect.x() + rect.width() &&
maxX >= rect.x()) {return true;}
}
} else if (a[0] === b[0]) {
// 垂直线
for (let i = 0; i < rects.length; i++) {let rect = rects[i];
if (minX >= rect.x() &&
minX <= rect.x() + rect.width() &&
minY <= rect.y() + rect.height() &&
maxY >= rect.y()) {return true;}
}
}
return false;
};接下来就能够应用回溯算法来找出其中的一条门路，回溯算法很简略，因为不是本文的重点，所以就不具体介绍了，有趣味的能够浏览回溯（DFS）算法解题套路框架。
计算出坐标点后再更新连线元素，记得要把咱们真正的终点和起点坐标加上去：
// 矩形挪动事件
const onDragMove = () => {
// 计算出所有可能的点
let {startPoint, endPoint, fakeStartPoint, fakeEndPoint, points} =
computedProbablyPoints();
// 应用回溯算法找出其中一条门路
const routes = useDFS(fakeStartPoint, fakeEndPoint, points);
// 更新连线元素
line.points(
// 加上真正的终点和起点
(routes.length > 0 ? [startPoint, ...routes, endPoint] : []).reduce((path, cur) => {path.push(cur[0], cur[1]);
return path;
},
[])
);
};
// 应用回溯算法寻找门路
const useDFS = (startPoint, endPoint, points) => {let res = [];
let used = {};
let track = (path, selects) => {for (let i = 0; i < selects.length; i++) {let cur = selects[i];
// 达到起点了
if (checkIsSamePoint(cur, endPoint)) {res = [...path, cur];
break;
}
let key = cur[0] + "-" + cur[1];
// 该点曾经被抉择过了
if (used[key]) {continue;}
used[key] = true;
track([...path, cur], getNextPoints(cur, points));
used[key] = false;
}
};
track([], [startPoint]);
return res;
};成果如下：
能够看到的确计算出了一条连接线门路，然而显然不是最短门路，并且回溯算法是一种暴力算法，点多了可能会存在性能问题。
应用 A * 算法联合曼哈顿门路计算最短门路
后面咱们应用回溯算法找出了其中一条关联线门路，然而很多状况下计算出来的门路都不是最短的，接下来咱们就应用 A* 算法来找出最短门路。
A*算法和回溯算法有点类似，然而不是自觉的挨个遍历一个点四周的点，而是会从中找出最有可能的点优先进行尝试，残缺的算法过程形容如下：
1. 创立两个数组，
openList寄存待遍历的点，closeList寄存曾经遍历的点；2. 将终点放入
openList中；3. 如果
openList不为空，那么从中选取优先级最高的点，假如为n：
- 3.1. 如果
n为起点，那么完结循环，从n登程，顺次向前找出父节点，也就是最短门路；3.2. 如果
n不为起点，那么：
- 3.2.1. 将
n从openList中删除，增加到closeList中；3.2.2. 遍历
n四周的点：
- 3.2.2.1. 如果该点在
closeList中，那么跳过该点；3.2.2.2. 如果该点也不在
openList中，那么：
- 3.2.2.2.1. 设置
n为该点的父节点；- 3.2.2.2.2. 计算该点的代价，代价越高，优先级越低，反之越高；
- 3.3.3.3.3. 将该点增加到
openList；- 3.2.3. 持续 3 的循环过程，直到找到起点，或
openList为空，没有后果；
依据以上过程，咱们创立一个 A* 类：
// A* 算法类
class AStar {constructor() {
this.startPoint = null;
this.endPoint = null;
this.pointList = [];
// 寄存待遍历的点
this.openList = [];
// 寄存曾经遍历的点
this.closeList = [];}
// 算法主流程
start(startPoint, endPoint, pointList) {
this.startPoint = startPoint;
this.endPoint = endPoint;
this.pointList = pointList;
this.openList = [
{
point: this.startPoint, // 终点退出 openList
cost: 0, // 代价
parent: null, // 父节点
},
];
this.closeList = [];
while (this.openList.length) {
// 在 openList 中找出优先级最高的点
let point = this.getBestPoint();
// point 为起点，那么算法完结，输入最短门路
if (checkIsSamePoint(point.point, this.endPoint)) {return this.getRoutes(point);
} else {
// 将 point 从 openList 中删除
this.removeFromOpenList(point);
// 将 point 增加到 closeList 中
this.closeList.push(point);
// 遍历 point 四周的点
let nextPoints = getNextPoints(point.point, this.pointList);
for (let i = 0; i < nextPoints.length; i++) {let cur = nextPoints[i];
// 如果该点在 closeList 中，那么跳过该点
if (this.checkIsInList(cur, this.closeList)) {continue;} else if (!this.checkIsInList(cur, this.openList)) {
// 如果该点也不在 openList 中
let pointObj = {
point: cur,
parent: point,// 设置 point 为以后点的父节点
cost: 0,
};
// 计算以后点的代价
this.computeCost(pointObj);
// 增加到 openList 中
this.openList.push(pointObj);
}
}
}
}
return []}
// 获取 openList 中优先级最高的点，也就是代价最小的点
getBestPoint() {
let min = Infinity;
let point = null;
this.openList.forEach((item) => {if (item.cost < min) {
point = item;
min = item.cost;
}
});
return point;
}
// 从 point 登程，找出其所有祖宗节点，也就是最短门路
getRoutes(point) {let res = [point];
let par = point.parent;
while (par) {res.unshift(par);
par = par.parent;
}
return res.map((item) => {return item.point;});
}
// 将点从 openList 中删除
removeFromOpenList(point) {let index = this.openList.findIndex((item) => {return checkIsSamePoint(point.point, item.point);
});
this.openList.splice(index, 1);
}
// 检查点是否在列表中
checkIsInList(point, list) {return list.find((item) => {return checkIsSamePoint(item.point, point);
});
}
// 计算一个点的代价
computeCost(point) {// TODO}
}代码有点长，然而逻辑很简略，start办法根本就是对后面的算法过程进行还原，其余就是一些辅助工具办法，只有一个 computeCost 办法临时没有实现，这个办法也就是 A* 算法的外围。
A*算法的所说的节点优先级是由两局部决定的：
f(n) = g(n) + h(n)g(n)代表节点 n 间隔终点的代价。
f(n)代表节点 n 到起点的代价，当然这个代价只是预估的。
f(n)为 g(n) 加上 h(n)，就代表节点n 的综合代价，也就是优先级，代价越低，当然优先级越高，批改一下 computeCost 办法，拆解成两个办法：
// 计算一个点的优先级
computePriority(point) {point.cost = this.computedGCost(point) + this.computedHCost(point);
}g(n)的计算很简略，把它所有先人节点的代价累加起来即可：
// 计算代价 g(n)
computedGCost(point) {
let res = 0;
let par = point.parent;
while (par) {
res += par.cost;
par = par.parent;
}
return res;
}而 h(n) 的计算就会用到曼哈顿间隔，两个点的曼哈顿间隔指的就是这两个点的程度和垂直方向的间隔加起来的总间隔：
对于咱们的计算，也就是以后节点到起点的曼哈顿间隔：
// 计算代价 h(n)
computedHCost(point) {
return (Math.abs(this.endPoint[0] - point.point[0]) +
Math.abs(this.endPoint[1] - point.point[1])
);
}接下来实例化一个 AStar 类，而后应用它来计算最短门路：
const aStar = new AStar();
const onDragMove = () => {let { startPoint, endPoint, fakeStartPoint, fakeEndPoint, points} =
computedProbablyPoints(startPos.value, endPos.value);
const routes = aStar.start(fakeStartPoint, fakeEndPoint, points);
// 更新连线元素
// ...
}
能够看到不会呈现回溯算法计算出来的超长门路。
优化
到上一节曾经根本能够找出最短门路，然而会存在几个问题，本大节来试着优化一下。
1. 连接线冲破了突围框
如上图所示，垂直局部的连接线显然离元素过近，尽管还没有和元素重叠，然而曾经冲破了突围框，更好的连接点应该是左边两个，下图的状况也是相似的：
解决办法也很简略，后面咱们实现了一个判断线段是否穿过或和起起点元素重叠的办法，咱们批改一下比拟条件，把比拟对象由元素自身改成元素的突围框：
export const checkLineThroughElements = (a, b) => {
// ...
// 水平线
if (a[1] === b[1]) {for (let i = 0; i < rects.length; i++) {let rect = rects[i];
if (minY > rect.y() - MIN_DISTANCE &&// 减少或减去 MIN_DISTANCE 来将比拟指标由元素改成元素的突围框
minY < rect.y() + rect.height() + MIN_DISTANCE &&
minX < rect.x() + rect.width() + MIN_DISTANCE &&
maxX > rect.x() - MIN_DISTANCE) {return true;}
}
} else if (a[0] === b[0]) {
// 垂直线
for (let i = 0; i < rects.length; i++) {let rect = rects[i];
if (minX > rect.x() - MIN_DISTANCE &&
minX < rect.x() + rect.width() + MIN_DISTANCE &&
minY < rect.y() + rect.height() + MIN_DISTANCE &&
maxY > rect.y() - MIN_DISTANCE) {return true;}
}
}
return false;
};成果如下：
2. 间隔太近没有连接线
目前咱们的逻辑如果当两个元素太近了，那么是计算不进去符合要求的点的，天然就没有线了：
解决办法也很简略，当第一次门路计算没有后果时咱们假如是因为间隔很近导致的，而后咱们再以宽松模式计算一次，所谓宽松模式就是去掉是否穿过或和元素有穿插的判断，也就是跳过 checkLineThroughElements 这个办法，另外真正的终点和起点也要退出点列表里加入计算，并且计算的终点和起点也不再应用伪终点和伪起点，而是应用真正的终点和起点，不然会呈现如下的状况：
首先批改一下 onDragMove 办法，将门路计算独自提成一个办法，不便复用：
const onDragMove = () => {
// 计算点和门路提取成一个办法
let {startPoint, endPoint, routes} = computeRoutes();
// 如果没有计算出来门路，那么就以宽松模式再计算一次可能的点，也就是容许和元素穿插
if (routes.length <= 0) {let res = computeRoutes(true);
routes = res.routes;
}
// 更新连线元素
updateLine((routes.length > 0 ? [startPoint, ...routes, endPoint] : []).reduce((path, cur) => {path.push(cur[0], cur[1]);
return path;
},
[])
);
};
// 计算门路
const computeRoutes = (easy) => {
// 计算出所有可能的点
let {startPoint, endPoint, fakeStartPoint, fakeEndPoint, points} =
computedProbablyPoints(startPos.value, endPos.value, easy);
// 应用 A * 算法
let routes = = aStar.start(
easy ? startPoint : fakeStartPoint,// 如果是宽松模式则应用真正的终点和起点
easy ? endPoint : fakeEndPoint,
points
);
return {
startPoint,
endPoint,
routes,
};
};而后批改一下 computedProbablyPoints 办法，减少一个 easy 参数，当该参数为 true 时就将真正的终点和起点退出点列表中：
const computedProbablyPoints = (startPos, endPos, easy) => {
// ...
// 是否是宽松模式
easyMode = easy;
// 保留所有可能通过的点
let points = [];
// 宽松模式则把真正的终点和起点退出点列表中
if (easy) {points.push(startPoint, endPoint);
}
// ...
}最初再批改一下计算一个点周边的点的办法，去掉是否穿过或和元素穿插的检测：
const getNextPoint = (x, y, list, dir) => {
// ...
for (let i = 0; i < list.length; i++) {let cur = list[i];
// 查看以后点和指标点的连线是否穿过起起点元素，宽松模式下间接跳过该检测
if (!easyMode && checkLineThroughElements([x, y], cur)) {continue;}
}
}最终成果如下：
总结
本文尝试通过 A* 算法实现了寻找节点的关联线门路，本来认为难点在于算法，没想到在实现过程中发现最难之处在于找点，如果有更好的找点形式欢送评论区留言。
源码地址：https://github.com/wanglin2/AssociationLineDemo。
参考文章
门路布局之 A* 算法
LogicFlow 边的绘制与交互