图形库提供了线条绘制例程，有时带有抗锯齿[1]和可变宽度。在网格地图上，线条绘制对于可视性、箭头/子弹的路径以及敌方AI非常有用。我有时看到人们将Bresenham线条绘制算法适配到网格上（特别是对于类roguelike游戏），但我更喜欢一个_简单_得多的算法，它运行得同样快。我将展示我使用的算法。
这是代码。第一部分将解释它是如何工作的，以及辅助函数 round_point 和 lerp_point 和 diagonal_distance （这些都是简短的），然后其他部分将描述算法的变体。
function line(p0, p1) { let points = []; let N = diagonal_distance(p0, p1); for (let step = 0; step <= N; step++) { let t = N === 0? 0.0 : step / N; points.push(round_point(lerp_point(p0, p1, t))); } return points; }
此演示展示了如果在两个点之间绘制一条线，应该标记哪些网格位置。尝试移动端点。
我发现找到这些点的最简单方法是使用 线性插值。让我们看看这是如何工作的。
1.1
插值数字
这里有一个我将使用的简单（Javascript）辅助函数：
function lerp(start, end, t) { return start (1.0 - t) + end t; }
线性插值（“lerp”）给你两个数字之间的一个数字。当 t = 0.0 时，你得到起点；当 t = 1.0 时，你得到终点。尝试设置 t，即 lerp() 的第三个参数：
lerp( 0, 1, ) = lerp( 0, 100, ) = lerp( 3, 5, ) = lerp( 5, 3, ) =
1.2
插值点
我们可以将插值的概念扩展到点上，通过插值 x 和 y 坐标。 尝试改变 t = :
以下是找到点 x,y 在点 p0 = (x0,y0) 和点 p1 = (x1,y1) 之间的代码:
function lerppoint(p0, p1, t) { return new Point(lerp(p0.x, p1.x, t), lerp(p0.y, p1.y, t));}
让我们把这条线分成相等的线段：
这里是找到那些点的代码：
let points = []; for (let step = 0; step <= N; step++) { let t = step / N; points.push(lerp_point(p0, p1, t));}
变体：我们可以开始让步长 = 1，并在步长 < N 时停止，如果我们想排除两个端点。变体：我们可以用另一个条件替换步长 <= N，例如在墙壁或地图边缘停止。
1.3
对齐到网格
接下来我们需要弄清楚那些点位于哪个 网格方块 中。我们可以将 x 和 y 四舍五入到最接近的整数，以找到网格瓦片:
我们还需要决定包含多少个点。太少的话，线条会有空洞。太多的话，线条会重叠。我们需要多少个点？正确的数量是端点之间的 对角距离，在这种情况下是 。
调整 N = 以查看线条如何填充。
就这样！
- 将 N 设置为起点和终点之间的对角距离。
- 选择 N+1 个均匀间隔的插值点。
- 将这些点四舍五入到最近的网格瓦片。
这是最终代码：
function line(p0, p1) { let points = ; let N = diagonaldistance(p0, p1); for (let step = 0; step <= N; step++) { let t = N === 0? 0.0 : step / N; points.push(roundpoint(lerppoint(p0, p1, t))); } return points; }
这是我所知道的最简单的线条绘制算法。以下是辅助函数，您可能已经实现过：
function diagonaldistance(p0, p1) { let dx = p1.x - p0.x, dy = p1.y - p0.y; return Math.max(Math.abs(dx), Math.abs(dy)); } function roundpoint(p) { return new Point(Math.round(p.x), Math.round(p.y)); } function lerppoint(p0, p1, t) { return new Point(lerp(p0.x, p1.x, t), lerp(p0.y, p1.y, t)); } function lerp(start, end, t) { return start * (1.0 - t) + t * end; }
1.4
插值其他类型
我定义了 lerp 函数来在两个 数字 之间进行插值，然后我定义了 lerp_point 来处理两个 点。其他类型 T 呢？我们需要这些操作来定义插值：
附加
b = a + d 其中 a: T, b: T, 和 d: ΔT. 对于点，b.x = a.x + d.x; b.y = a.y + d.y
减法
d = a - b 其中 a: T, b: T, d: ΔT. 对于点，d.x = a.x - b.x; d.y = a.y - b.y
标量乘法
e = k * d 其中 d: ΔT, e: ΔT, k: number. 对于点，e.x = k * d.x; e.y = k * d.y
我们可以在任何 向量空间[2] 上进行插值。 T 可以是一个数字、一个二维点、一个三维点、一个角度、一个时间、一个颜色或其他东西。我的 六边形网格指南[3] 使用插值在六边形网格上绘制线条。请注意，T 和 ΔT 可能是相同类型，但有时它们是不同的。例如，T 可能是一个时间戳，而 ΔT 可能是一个时间差，或者 T 可能是一个方向，而 ΔT 可能是一个旋转。当 T 和 ΔT 是相同类型时，d = a - b 可以实现为 d = a + (-1 * b)。
1.5
美学
线性插值是计算一个位置然后进行四舍五入。当值恰好为0.5时会发生什么？四舍五入规则各不相同[4]。这一点，加上浮点精度，使得线性插值并不总是以保持与旋转、反转和其他对称性一致的方式选择点。
我认为应该做的事情是通过 epsilon 来“推动”初始点。然而，我还没有在方形网格上探索过这个。我已经在六边形网格上使用过它。
1.6
代码优化
您可以通过以下步骤优化常规线条绘制算法；它将变成DDA算法[5]:
内联函数调用
您的编译器可能会这样做，但您可以通过自己先这样做来发现额外的优化机会。
展开插值
而不是每次循环中计算 t，然后 x = (b.x-a.x)t (a 减去并乘以)，你可以在循环外计算 Δx = (b.x-a.x)Δt，然后使用 x += Δx。y 也是如此。这将用加法替代乘法。
展开循环
你可以通过保持四对 x 和 y 来展开循环，然后使用 t += 4*Δt。这会允许使用 SSE 指令吗？我不知道。
单独案例
Δx 或 Δy 将是 ±1。您可能想为每种情况准备一个单独的版本。对于对角线，两者都是 ±1。对于正交线，两个中的一个将是 0。如果这些情况很常见，请为它们编写一个单独的例程。
四舍五入
比较 rint()、nearestint()、floor() 和 round() 的性能，因为其中一个可能更快（但要注意舍入模式，因为它们可能会改变结果）。
浮点数与定点数
如果你分析后发现 Math.round() 的开销很大，可以切换到定点算术，并用位移替代舍入。在 x86 上，可以考虑使用 fist / fistp 指令，或者使用 SSE 的 cvtsd2si（我还没有在优化上走到这一步）。
在优化之前，分析并确保线性插值是你的瓶颈。在我的项目中，这种情况很少发生，所以我没有费心去实现这些优化。这里有一个示例（大致的 C# 语法，用于显示类型）关于内联 + 展开 lerp，但没有应用其他优化：
List<Point> line(Point p0, Point p1) { List<Point> = new List<Point>(); int dx = p1.x - p0.x; int dy = p1.y - p0.y; int N = Math.Max(Math.Abs(dx), Math.Abs(dy)); double divN = (N == 0)? 0.0 : 1.0 / N; double xstep = dx * divN; double ystep = dy * divN; double x = p0.x, y = p0.y; for (int step = 0; step <= N; step++, x += xstep, y += ystep) { points.Add(new Point(Math.Round(x), Math.Round(y))); } return points; }
插值是简单而通用的，但没有考虑网格的属性。另一种绘制线条的方法是逐步进行。这种移动方式还允许 在边缘放置墙壁，以便墙壁可以阻挡视线或移动。