Elegant/Clean (special case) Straight-line Grid Traversal Algorithm?

Question

I'm dusting off an old project of mine. One of the things it had to do was -- given a Cartesian grid system, and two squares on the grid, find a list of all squares that a line joining the center of those two squares would pass through.

The special case here is that all start and end points are confined to the exact center of squares/cells.

Here are some examples -- with pairs of sample starting and ending points. The shaded squares are the ones that should be returned by the respective function call

removed dead ImageShack link - example

The starting and end points are referred to by the squares they are in. In the above picture, assuming that the bottom left is [1,1], the line on the bottom right would be identified as [6,2] to [9,5].

That is, from the (center of the) square on the sixth column from the left, on the second row from the bottom to the (center of the) square on the ninth column from the left, on the fifth row from the bottom

Which really doesn't seem that complicated. However, I somehow seemed to have found some complex algorithm online and implemented it.

I do recall that it was very, very fast. Like, optimized-for-a-hundreds-or-thousands-of-times-per-frames fast.

Basically, it jumped from border to border of the squares, along the line (the points where the line crosses the grid lines). It knew where the next crossing point was by seeing which crossing point was closer -- a horizontal one or a vertical one -- and moved to that next one.

Which is sort of okay in concept, but the actual implementation turned out to be pretty not-so-pretty, and I'm afraid that the level of optimization might be way too high for what I practically need (I'm calling this traversal algorithm maybe five or six times a minute).

Is there a simple, easy-to-understand, transparent straight-line grid traversal algorithm?

In programmatic terms:

def traverse(start_point,end_point)
  # returns a list of all squares that this line would pass through
end

where the given coordinates identify the squares themselves.

Some examples:

traverse([0,0],[0,4])
# => [0,0], [0,1], [0,2], [0,3], [0,4]
traverse([0,0],[3,2])
# => [0,0], [0,1], [1,1], [2,1], [2,2], [3,2]
traverse([0,0],[3,3])
# => [0,0], [1,1], [2,2], [3,3]

Note that lines that move directly through corners should not include squares on the "wing" of the line.

(Good ol' Bresenham's might work here, but it's a bit backwards from what I want. As far as I know, in order to use it, I'd basically have to apply it to the line and then scan every single square on the grid for true or false. Infeasible -- or at least inelegant -- for large grids)

(I am re-looking into Bresenham, and Bresenham-based algorithms, due to a misunderstanding of mine)

For clarification, one possible application of this would be, if I was storing all of my objects in a game inside zones (a grid), and I have a ray, and want to see which objects the ray touches. Using this algorithm, I could test the ray to only the objects that are within the given zones, instead of every object on the map.

The actual use of this in my application is that every tile has an effect associated with it, and an object moves through a given line segment every turn. At every turn, it is necessary to check to see which squares the object has traversed through, and therefore, which effects to apply to the object.

Note that, at this point, the current implementation I have does work. This question is mostly for curiosity's purpose. There has to be a simpler way...somehow...for such a simple problem.

What am I looking for exactly? Something conceptually/neat and clean. Also, I've realized that due to what I am exactly specifying, all start and end points are always going to be in the center of squares/cells; so perhaps something that takes advantage of that would be neat as well.

user_4910042 · Answer

Here is a simple implementation in Python, using numpy. However, what is used here is only 2D vectors and component by component operations which is rather common. The result looks quite elegant to me (~20 loc without comments).

This is not general as it assumes tiles are centered at integer coordinates, while separating lines appear at each integer plus one half (0.5, 1.5, 2.5, etc.). This allows to use rounding to get tile integer coordinates from world coordinate (which is not actually needed in your special case) and gives the magic number 0.5 to determine when we have reached the last tile.

Finally, note that this algorithm does not deal with point exactly crossing the grid at an intersection.

import numpy as np

def raytrace(v0, v1):
    # The equation of the ray is v = v0 + t*d
    d = v1 - v0
    inc = np.sign(d)  # Gives the quadrant in which the ray progress

    # Rounding coordinates give us the current tile
    tile = np.array(np.round(v0), dtype=int)
    tiles = [tile]
    v = v0
    endtile = np.array(np.round(v1), dtype=int)

    # Continue as long as we are not in the last tile
    while np.max(np.abs(endtile - v)) > 0.5:
        # L = (Lx, Ly) where Lx is the x coordinate of the next vertical
        # line and Ly the y coordinate of the next horizontal line
        L = tile + 0.5*inc

        # Solve the equation v + d*t == L for t, simultaneously for the next
        # horizontal line and vertical line
        t = (L - v)/d

        if t[0] < t[1]:  # The vertical line is intersected first
            tile[0] += inc[0]
            v += t[0]*d
        else:  # The horizontal line is intersected first
            tile[1] += inc[1]
            v += t[1]*d

        tiles.append(tile)

    return tiles

Elegant/Clean (special case) Straight-line Grid Traversal Algorithm?

4 Answers