Need a formula for figuring out what squares in a grid are hit by a line spanning between 2 coordinates

Question

Example image: http://ericsartor.ca/Untitled2.gif

I'm making a game based on a grid system. For the battle system, I'm trying to figure out if a shot is blocked by checking all the squares in it's path to see if they are considered "obstacles". I'd need to be able to provide a start and end x,y coordinate, then loop through all the squares that the line between those points would pass through, as in the image. The formula would need to return x,y coordinates for each square in the path. I could iterate over it multiple times if necessary. I've been trying really hard to figure it out on my own, but I can't identify a clear pattern or consistency that I could use to make a formula. Could someone help? Thanks :)

Answer 1

I believe I have a solution for you. Suppose the grid is defined by all lines parallel to the $y$-axis through the points $\{x_k = a + k\Delta x\,:\,k \in \mathbb{Z}\}$ and all lines parallel to the $x$-axis through the points $\{y_j = b + j\Delta y\,:\,j\in\mathbb{Z}\}$. Further suppose the line extends from $(x_s,y_s)$ to $(x_e,y_e)$. The following pseudocode outlines the algorithm. At its conclusion the array $P$ contains a list of index pairs $(k,j)$ that index the bottom left corner of the rectangle with vertices $(x_k,y_j)$, $(x_k,y_j + \Delta y)$, $(x_k + \Delta x, y_j)$, $(x_k+\Delta x,y_j + \Delta y)$ that contains a portion of the line.

rtol = macheps
atol = 1e-14
k = floor((xs - a)/dx)
j = floor((ys - b)/dy)
ke = floor((xe - a)/dx)
je = floor((ye - b)/dy)
x = a + k*dx
y = a + j*dy
tcurr = 0
Add the pair (k,j) to an empty array P
while (k does not equal ke or j does not equal je) do 
    tmin = 2
    if (xe does not equal xs) then
        tol = rtol*|x| + atol
        t = (x + dx + tol - xs)/(xe - xs)
        if (tcurr < t and t <= 1) then
            tmin = min(tmin, t)
        end
        t = (x - xs - tol)/(xe - xs)
        if (tcurr < t and t <= 1) then
            tmin = min(tmin, t)
        end
    end
    if (ye does not equal ys) then
        tol = rtol*|y| + atol
        t = (y + dy + tol - ys)/(ye - ys)
        if (tcurr < t and t <= 1) then
            tmin = min(tmin, t)
        end
        t = (y - ys - tol)/(ye - ys)
        if (tcurr < t and t <= 1) then
            tmin = min(tmin, t)
        end
    end
    if (tmin is 2) then // should only be possible at the end of the line
        Add the pair (ke,je) to the array P
        break from the loop
    end
    tcurr = tmin
    k = floor((xs + tmin*(xe - xs) - a)/dx)
    j = floor((ys + tmin*(ye - ys) - b)/dy)
    Add the pair (k,j) to the array P
    x = a + k*dx
    y = b + j*dy
end

This algorithm may have to be tweaked depending on how you want to handle edge cases such as when the line passes through grid points.