Hello, everyone!
Today I'm going to introduce you DAYU.
Overview
In the previous version, the simple connection is in some complex scenes, especially when there are many levels and the connection crosses many levels, the line will pass through the rectangle. This is the basis for optimizing the connection. line.
Scene analysis
In the following situations, the simple version of the drawing method is no longer able to avoid obstacle nodes.
In this case, due to the simple version, we only added 2 inflection points to the entire path. In this way of drawing, when the above situation occurs, the line will be blocked by B. For actual needs, we have to avoid this kind of node and go around open.
It should be the following situation:
The more complicated scenario is as follows
At this time, 2 nodes are blocked. All we have to do is to bypass the nodes as shown in the diagram.
Thinking analysis
Observation and analysis, if we want to bypass some obstacle nodes, we need to know which nodes will be blocked before we can bypass them. There are two clear data that we know the coordinates of the nodes of each layer, the starting point is p1, and the end point is p6. We can simulate this process:
a) If the line where p1 is located is not blocked by the nearest next layer, that is, the nodes D, E, and F in the figure are blocked, it means that the starting point can be drawn to p2 first
b) After drawing to p2, continue to judge the third-level node. Since node B will block the vertical line drawn from p2, it bypasses node B. Since the end point of P6 is on the left side of p2, look for it on the left side of B A blank space, namely p3
c) Now it's time to draw to p3. At this time, the starting point is to program p3, and the problem is converted to the scene of drawing p1
d) Keep looping until you reach the end point, and record all the turning points on this path, which is our path
Implementation
function drawLine(startX, startY, endX, endY, color, sourceNodeName, targetNodeName, endLayer, startLayer, lineNodes) {
var points = []; // save points on the path
var sx = startX;
var ex = endX;
for (var layer = startLayer + 1; layer <endLayer; layer++) {
// Determine whether the current layer is blocked by nodes
var coverRectIndex = -1;
for(var i = 0; i <lineNodes[layer].length; i++){
if(lineNodes[layer][i].x <sx && (sx-lineNodes[layer][i].x) <config.rect.width){
coverRectIndex = i;
break;
}
}
if(coverRectIndex === -1){
// If it is not blocked, check the next layer
continue;
}else{
// If it is blocked, you need to decide whether to wind to the left or to the back according to the relative position of the starting point and the target node
var midY = lineNodes[layer][coverRectIndex].y-40;
// Calculate whether it is the gap on the left or the gap on the right
var midX = lineNodes[layer][coverRectIndex].x;
midX += sx> ex? -(config.rect.space / 2 + config.rect.width): (config.rect.space / 2 + config.rect.width);
while (true) {
var flag = false;
if (nodeLines[layer]) {
for (var i = 0; i <nodeLines[layer].length; i++) {
var line = nodeLines[layer][i];
if (line.startY === midY) {
if (checkCross(sx, midX, line.startX, line.endX)) {
flag = true;
}
}
if (flag) break;
}
} else {
nodeLines[layer] = [];
}
if (!flag) break;
midY -= lineDis;
}
if (sx !== midX) {
nodeLines[layer].push({
startX: sx,
startY: midY,
endX: midX,
endY: midY })
}
// Point on the storage path
points.push({ x: sx, y: midY });
points.push({ x: midX, y: midY });
sx = midX;
}
}
// Process the scene of the last layer separately
var midY = lineNodes[endLayer][0].y-40;
while (true) {
var flag = false;
if (nodeLines[endLayer]) {
for (var i = 0; i <nodeLines[endLayer].length; i++) {
var line = nodeLines[endLayer][i];
if (line.startY === midY) {
if (checkCross(sx, ex, line.startX, line.endX)) {
flag = true;
}
}
if (flag) break;
}
} else {
nodeLines[endLayer] = [];
}
if (!flag) break;
midY -= lineDis;
}
if (sx !== ex) {
nodeLines[layer].push({
startX: sx,
startY: midY,
endX: ex,
endY: midY })
}
points.push({ x: sx, y: midY });
points.push({ x: ex, y: midY });
return points;}to sum up
This is optimized on the original basis and realizes the function of avoiding obstacle nodes. At the beginning, I thought that the A* algorithm was used to search, but there were too many pixels, and the complexity of the algorithm could not be held. Later, I was stuck in the link of shrinking. After the guidance of my colleagues, the current optimization was realized. Learn more, sum up more!
