# Finding which tiles are intersected by a line, without looping through all of them or skipping any

I've been staring at this problem for a few days now. I rigged up this graphic to help me visualise the issue: (from the graph, we know that the line intersects [1, 1], [1, 2], [2, 2], [2, 3], ending in [3,3])

I want to step along the line to each grid space and check to see if the material of the grid space is solid. I feel like I already know the math involved, but I haven't been able to string it together yet. I'm using this to test line of sight and eliminate nodes after a path is found via my pathfinding algorithms - my agents cant see through a solid block, therefore they cant move through one, therefore the node is not eliminated from the path because it is required to navigate a corner.

So, I need an algorithm that will step along the line to each grid space that it intersects. Any ideas?

I've taken a look at a lot of common algorithms, like Bresenham's, and one that steps at predefined intervals along the line (unfortunately, this method skips tiles if they're intersecting with a smaller wedge than the step size).

I'm populating my whiteboard now with a mass of floor() and ceil() functions - but its getting overly complicated and I'm afraid it might cause a slowdown.

-
You already know how to test the actual line-box intersection, right? Just asking, cause this is relevant to the answer. – TravisG Nov 23 '11 at 9:47
possible duplicate of How do I generalise Bresenham's line algorithm to floating-point endpoints? (the question isn’t actually about Bresenham) – sam hocevar May 16 '15 at 22:13

If you know starting block (you know point X and you dind't include block [0,1] in block list, so I suppose you know also the starting block), I think you should surely use Bresenham's algorithm. You wrote, you looked at it.

It's suitable algorithm for this problem. It can be also written in a way, it computes only with integers. You can find a lot of implementations out there on the web.

EDIT:

I'm sorry, I haven't realized that Bresenham won't find all blocks. So I found better solution. There is also code written in C++, but I think it shouldn't be hard to understand :)

-
The reason I looked past the Bresenham algorithm was purely because of the image on Wikipedia. (en.wikipedia.org/wiki/File:Bresenham.svg) You can see that the line intercepts some unshaded squares, albeit barely. I need something that will detect every tile, regardless of how infinitely small the slice is. Edit: It appears that I have misunderstood bresenham's anyway. I need to reverse it - I have the first and last point, and I need the tiles that it intersects - rather than the line that would be best to plot. – Suds Nov 23 '11 at 9:28
@JustSuds: Check for update in post. – zacharmarz Nov 23 '11 at 9:47
Hey hey! that almost directly matches what I have on my whiteboard! Thanks, my system is now implemented and working. :-) – Suds Nov 24 '11 at 1:26
Can you remove the part about Bresenham's algorithm as it doesn't answer the question? Don't worry, it will stay in your answer's edit history. – zenith Feb 23 at 5:05