# 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.

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 '16 at 5:05

The code in the example that the accepted answer links to needs some adjustment for perfectly diagonal lines. Here's a complete demo application written with Qt (C++ and QML).

Relevant C++ code:

void rayCast()
{
if (!isComponentComplete())
return;

mTiles.clear();
mTiles.fill(QColor::fromRgb(255, 222, 173), mSizeInTiles.width() * mSizeInTiles.height());

const QPoint startTile = startTilePos();
const QPoint endTile = endTilePos();
// http://playtechs.blogspot.com/2007/03/raytracing-on-grid.html
int x0 = startTile.x();
int y0 = startTile.y();
int x1 = endTile.x();
int y1 = endTile.y();

int dx = abs(x1 - x0);
int dy = abs(y1 - y0);
int x = x0;
int y = y0;
int n = 1 + dx + dy;
int x_inc = (x1 > x0) ? 1 : -1;
int y_inc = (y1 > y0) ? 1 : -1;
int error = dx - dy;
dx *= 2;
dy *= 2;

for (; n > 0; --n)
{
visit(x, y);

if (error > 0)
{
x += x_inc;
error -= dy;
}
else if (error < 0)
{
y += y_inc;
error += dx;
}
else if (error == 0) {
// Ensure that perfectly diagonal lines don't take up more tiles than necessary.
// http://playtechs.blogspot.com/2007/03/raytracing-on-grid.html?showComment=1281448902099#c3785285092830049685
x += x_inc;
y += y_inc;
error -= dy;
error += dx;
--n;
}
}

update();
}