tl; dr：使用飞机，数学解释如下。底部有一个画布示例。
鉴于您的所有单元格都是轴对齐的边界框，您可以使用平面方程来找到您的线与边缘的交点。
飞机
你可以把你的盒子想象成一组四个几何平面。每个平面都有一个法线或长度为 1 的向量，指示哪个方向是平面的“正面”。构成细胞侧面的平面的法线为：
top = {x: 0, y: -1};
bottom = {x: 0, y: 1};
left = {x: -1, y: 0};
right = {x: 1, y: 0};
给定平面上的一个点，平面有以下方程：
distance = (normal.x * point.x) + (normal.y * point.y)
您可以使用此等式来计算平面的距离。在这种情况下，您知道框的左上角（假设 x 为 10，y 为 100）位于顶部平面上，因此您可以执行以下操作：
distance = (0 * 10) + (-1 * 100)
distance = -100
根据平面检查点
获得距离后，您可以重新使用该方程来检查任何点相对于平面的位置。对于随机点p（其中 x 为 -50，y 为 90），您可以执行以下操作：
result = (normal.x * p.x) + (normal.y * p.y) - distance
result = (0 * -50) + (-1 * 90) - (-100)
result = 0 + (-90) - (-100)
result = -90 + 100
result = 10
有两种可能的结果：
if (result >= 0) {
// point is in front of the plane, or coplanar.
// zero means it is coplanar, but we don't need to distinguish.
} else {
// point is behind the plane
}
对照平面检查一条线
您可以通过以下方式检查一条线的两个端点 from ato b：
result1 = (normal.x * a.x) + (normal.y * a.y) - distance
result2 = (normal.x * b.x) + (normal.y * b.y) - distance
有四种可能的结果：
if (result1 >= 0 && result2 >= 0) {
// the line is completely in front of the plane
} else if (result1 < 0 && result2 < 0) {
// the line is completely behind the plane
} else if (result1 >= 0 && result2 < 0) {
// a is in front, but b is behind, line is entering the plane
} else if (result1 < 0 && result2 >= 0) {
// a is behind, but b is in front, line is exiting the plane
}
当直线与平面相交时，您想要找到交点。用矢量术语来思考一条线会有所帮助：
a + t * (b - a)
如果t == 0，您在行首，并且t == 1是行尾。在这种情况下，您可以将交点计算为：
time = result1 / (result1 - result2)
交点为：
hit.x = a.x + (b.x - a.x) * time
hit.y = a.y + (b.y - a.y) * time
对照方框检查一条线
有了这个数学，你可以找出你的盒子的相交线。您只需要针对每个平面测试线的端点，并找到时间的最小值和最大值。
因为你的盒子是一个凸多边形，所以这个检查有一个早期的结果：如果这条线完全在你盒子里的任何一个平面的前面，它就不能与你的盒子相交。您可以跳过检查其余飞机。
在 JavaScript 中，您的结果可能如下所示：
/**
* Find the points where a line intersects a box.
*
* @param a Start point for the line.
* @param b End point for the line.
* @param tl Top left of the box.
* @param br Bottom right of the box.
* @return Object {nearTime, farTime, nearHit, farHit}, or false.
*/
function intersectLineBox(a, b, tl, br) {
var nearestTime = -Infinity;
var furthestTime = Infinity;
var planes = [
{nx: 0, ny: -1, dist: -tl.y}, // top
{nx: 0, ny: 1, dist: br.y}, // bottom
{nx: -1, ny: 0, dist: -tl.x}, // left
{nx: 1, ny: 0, dist: br.x} // right
];
for (var i = 0; i < 4; ++i) {
var plane = planes[i];
var nearDist = (plane.nx * a.x + plane.ny * a.y) - plane.dist;
var farDist = (plane.nx * b.x + plane.ny * b.y) - plane.dist;
if (nearDist >= 0 && farDist >= 0) {
// both are in front of the plane, line doesn't hit box
return false;
} else if (nearDist < 0 && farDist < 0) {
// both are behind the plane
continue;
} else {
var time = nearDist / (nearDist - farDist);
if (nearDist >= farDist) {
// entering the plane
if (time > nearestTime) {
nearestTime = time;
}
} else {
// exiting the plane
if (time < furthestTime) {
furthestTime = time;
}
}
}
}
if (furthestTime < nearestTime) {
return false;
}
return {
nearTime: nearestTime,
farTime: furthestTime,
nearHit: {
x: a.x + (b.x - a.x) * nearestTime,
y: a.y + (b.y - a.y) * nearestTime
},
farHit: {
x: a.x + (b.x - a.x) * furthestTime,
y: a.y + (b.y - a.y) * furthestTime
}
};
}
如果这仍然太慢，您还可以通过将世界划分为大矩形并将线条分配给这些矩形来进行广泛相位剔除。如果您的线和单元格不在同一个矩形中，则它们不会发生碰撞。
我已经上传了一个画布示例。