tl;dr: Use planes, maths explained below. There's a canvas example at the bottom.
Given that all of your cells are axis-aligned bounding boxes, you could use the plane equation to find the intersection of your line with the edges.
Planes
You can think of your box as a set of four geometric planes. Each plane has a normal, or a vector of length one, indicating which direction is the "front" of the plane. The normals for the planes that make up your cell's sides would be:
top = {x: 0, y: -1};
bottom = {x: 0, y: 1};
left = {x: -1, y: 0};
right = {x: 1, y: 0};
Given a point on the plane, the plane has the equation:
distance = (normal.x * point.x) + (normal.y * point.y)
You can use this equation to calculate the distance of the plane. In this case, you know the top-left corner of your box (let's say x is 10 and y is 100) is on the top plane, so you can do:
distance = (0 * 10) + (-1 * 100)
distance = -100
Checking a point against a plane
Once you have the distance, you can reuse the equation to check where any point is, relative to the plane. For a random point p (where x is -50 and y is 90), you can do:
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
There are two possible results:
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
}
Checking a line against a plane
You can check both endpoints of a line from a to b in this way:
result1 = (normal.x * a.x) + (normal.y * a.y) - distance
result2 = (normal.x * b.x) + (normal.y * b.y) - distance
There are four possible results:
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
}
When the line intersects the plane, you want to find the point of intersection. It helps to think of a line in vector terms:
a + t * (b - a)
If t == 0, you are at the start of the line, and t == 1 is the end of the line. In this context, you can calculate the point of intersection as:
time = result1 / (result1 - result2)
And the point of intersection as:
hit.x = a.x + (b.x - a.x) * time
hit.y = a.y + (b.y - a.y) * time
Checking a line against the box
With that math, you can figure out the lines of intersection with your box. You just need to test the endpoints of your line against each plane, and find the minimum and maximum values of time.
Because your box is a convex polygon, there is an early out in this check: if the line is completely in front of any one plane in your box, it cannot intersect with your box. You can skip checking the rest of the planes.
In JavaScript, your result might look something like this:
/**
* 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
}
};
}
If this is still too slow, you can also do broadphase culling by dividing the world up into big rects, and assigning lines to those rects. If your line and cell aren't in the same rect, they don't collide.
I've uploaded a canvas example of this.
