Having implemented DDA code a bunch of times, I find it easiest to think about it in lazy functional terms: it's like a takeWhile on a merge (or union) of infinite ordered streams of ray t-values.<p>In other words, decompose the problem into one of finding where the ray crosses the X grid lines and the Y grid lines, and the mental image is:<p><pre><code> +-------+-------+-------+ | | | | -------------------------
| | | ^ | | | | ^ | ^
| | | / | | | | / | /
| | | / | | | | / | /
+-------+-------+-*-----+ | | | / | ------------------*------
| | |/ | | | |/ | /
| | * | | | * | /
| | /| | | | /| | /
+-------+-----*-+-------+ = | | / | | U --------------*----------
| | / | | | | / | | /
| | / | | | | / | | /
| | / | | | | / | | /
+-------+-*-----+-------+ | | / | | ----------*--------------
| |/ | | | |/ | | /
| * | | | * | | /
| o| | | | o| | | o
+-------+-------+-------+ | | | | -------------------------
</code></pre>
Now, if our ray has origin o, and direction d, the position of any point along the ray for a t-value is:<p><pre><code> x' = o.x + t * d.x
y' = o.y + t * d.y.
</code></pre>
Where's the first grid intersection in X? Assuming d.x is positive, it'll be at ceil(o.x). So solve for t:<p><pre><code> ceil(o.x) = x' = o.x + t * d.x
t = (ceil(o.x) - o.x) / d.x.
</code></pre>
Then, since the grid lines are spaced 1 unit apart, every subsequent intersection will be 1/d.x further along in t. In other words, the ray t-values of all the grid crossing in X are stream generated by a simple linear function:<p><pre><code> ((ceil(o.x) - o.x)/d.x) + step * 1/d.x.
</code></pre>
And exactly the same thing applies in Y for the Y grid crossings.<p>So let's say that we have a ray with origin (0.8, 0.2) and a direction of (0.5, 0.25). Then we get:<p><pre><code> X-crossings = [0.4, 2.4, 4.4, 6.4, 8.4, 10.4, ...]
Y-crossings = [3.2, 7.2, 11.2, 15.2, ...]
</code></pre>
Then we merge those two infinite ordered streams:<p><pre><code> [0.4, 2.4, 3.2, 4.4, 6.4, 7.2, 8.4, 10.4, 11.2, ...]
X X Y X X Y X X Y ...
</code></pre>
and those are the t-values where we walk from one cell to another. Keeping track of which value came from which stream tells us whether the step is in X or in Y (it's always one or the other - a DDA never takes a diagonal step). Continue lazily generating and merging the stream this way until you run into something, run out of bounds, or just decide you've gone far enough to stop.<p>Obviously, there's some fiddliness when the direction has negative components or worse, zero, but it's not to hard to work out the adjustments for those cases. Likewise, you also want to be very careful about handling the case where the ray origin is <i>exactly</i> on a cell boundary. But again, focusing on just one dimension at a time helps when reasoning all that out.<p>Generalizing the concept to a DDA in 3D on a voxel grid isn't much harder, either: now you find the stream of Z-crossings as well and do a 3-way merge.<p>(If you ever want to vectorize grid traversal across multiple rays, there are some tricks to that in a 2006 SIGGRAPH paper that I worked on: <a href="https://www.sci.utah.edu/~wald/Publications/2006/CGT/grid.pdf" rel="nofollow">https://www.sci.utah.edu/~wald/Publications/2006/CGT/grid.pd...</a>)