连接所有点的线算法，没有对角线

Question

只有这样的线条：

存储这些动作，我有一个Queue实施（FIFO），将这些动作存储为

Integer

s.

s。

UP:    0
RIGHT: 1
DOWN:  2
LEFT:  3

我有敌人的X和y位置，我有X和Y位置。我想制作一条线，所有点都连接（没有对角线），从我到敌人，并将方向编号存储在我的

Queue

.

中。

如何生成此类行的方法是什么？

我假设您想要这样的结果：

Answer 1

可以通过从源细胞移动到目标细胞来实现这一目标，例如一次和下一个单元，并根据从理想线到网格单元中心点的垂直距离来决定每个步骤：

如果是网格单元的大小的一半，而

α是理想线的斜率，那么从中心点到理想线的阈值垂直距离为

X。（1 -tan（α））。如果距离小于此，则水平移动，如果比这大，则垂直移动。 您也可以这样看：如果理想线仅通过当前单元格的左侧和右边缘，则水平移动；如果它穿过当前单元格的顶部/底部边缘，请向上/向下移动。 如果理想线比水平（切线> 1）更垂直，但使用类似的方法，但转到90°：测量从单元中心到理想线的水平距离，并以较小的距离进行垂直移动，并以更大的距离进行水平移动。 this JavaScript代码片段显示了主要水平线的算法，例如在示例中，以及主要垂直线的等效方法，使用cotangent：

function tronPath(a, b) {
    var path = [a];
    var x = a.x, y = a.y;                         // starting cell
    var dx = a.x == b.x ? 0 : b.x > a.x ? 1 : -1; // right or left
    var dy = a.y == b.y ? 0 : b.y > a.y ? 1 : -1; // up or down
    if (dx == 0 || dy == 0) {
        // STRAIGHT LINE ...
    }
    else if (Math.abs(b.x - a.x) > Math.abs(b.y - a.y)) {
        // MAINLY HORIZONTAL
        var tan = (b.y - a.y) / (b.x - a.x);      // tangent
        var max = (1 - Math.abs(tan)) / 2;        // distance threshold
        while (x != b.x || y != b.y) {            // while target not reached
            var ideal = a.y + (x - a.x) * tan;    // y of ideal line at x
            if ((ideal - y) * dy >= max) y += dy; // move vertically
            else x += dx;                         // move horizontally
            path.push({x:x, y:y});                // add cell to path
        }
    }
    else {
        // MAINLY VERTICAL
        var cotan = (b.x - a.x) / (b.y - a.y);    // cotangent
        var max = (1 - Math.abs(cotan)) / 2;      // distance threshold
        while (x != b.x || y != b.y) {            // while target not reached
            var ideal = a.x + (y - a.y) * cotan;  // x of ideal line at y
            if ((ideal - x) * dx >= max) x += dx; // move horizontally
            else y += dy;                         // move vertically
            path.push({x:x, y:y});                // add cell to path
        }
    }
    return path;
}
var a = {x:1, y:1}, b = {x:11, y:5};
var path = tronPath(a, b);
document.write(JSON.stringify(path));

---

有一种优雅的方法：只需沿着直线乘

n

+1均等的点，其中

N

+1是将包含在生产线中的网格单元的数量，然后找到包含每个点的网格单元。 事实证明，只要您包含一个小的“轻推”偏移以防止点精确地降落在网格线上，这些点最终都会以不同的网格单元格的形式结束。轻推朝向

的垂直方向

对于带有和没有对角线的绘制线路的绘制线正确，您只需要在每种情况下正确计算线长度

n

：

当不允许对角线时，

n

Answer 2

当允许对角线时，

n是两个端点之间向量的均匀标准（即最大绝对值）。 另一个答案给出了一个JavaScript示例，我也会使用它：

function line(x1, y1, x2, y2, allowDiagonals) {
    const dx = x2 - x1,
        dy = y2 - y1,
        absDX = Math.abs(dx),
        absDY = Math.abs(dy),
        nudgeX = 1e-10 * dy,
        nudgeY = -1e-10 * dx,
        n = allowDiagonals ? Math.max(absDX, absDY) : absDX + absDY;
    
    const points = [];
    for(let i = 0; i <= n; ++i) {
        const t = i / n;
        points.push({
            x: Math.round(x1 + dx * t + nudgeX),
            y: Math.round(y1 + dy * t + nudgeY),
        });
    }
    return points;
}

demo：将鼠标悬停在线上。

function line(x1, y1, x2, y2, allowDiagonals) {
    const dx = x2 - x1,
        dy = y2 - y1,
        absDX = Math.abs(dx),
        absDY = Math.abs(dy),
        nudgeX = 1e-10 * dy,
        nudgeY = -1e-10 * dx,
        n = allowDiagonals ? Math.max(absDX, absDY) : absDX + absDY;

    const points = [];
    for(let i = 0; i <= n; ++i) {
        const t = i / n;
        points.push({
            x: Math.round(x1 + dx * t + nudgeX),
            y: Math.round(y1 + dy * t + nudgeY),
        });
    }
    return points;
}

const checkbox = document.getElementById('diagonals'),
    canvas = document.getElementById('canvas'),
    ctx = canvas.getContext('2d');

let mouseX = 0, mouseY = 0;
function draw() {
    ctx.clearRect(0, 0,  400, 400);
    ctx.fillStyle = 'black';
    const points = line(10, 10, mouseX, mouseY, checkbox.checked);
    for(const point of points) {
        ctx.fillRect(20 * point.x, 20 * point.y, 20, 20);
    }
    window.requestAnimationFrame(draw);
}
draw();

canvas.addEventListener('mousemove', e => {
    mouseX = Math.floor(e.offsetX / 20);
    mouseY = Math.floor(e.offsetY / 20);
});

• <input id="diagonals" type="checkbox"><label for="diagonals">Allow diagonals</label><br>
  <canvas id="canvas" width="400" height="400"></canvas>