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?