11
\$\begingroup\$

I've been staring at this problem for a few days now. I rigged up this graphic to help me visualise the issue: enter image description here (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.

\$\endgroup\$
2

2 Answers 2

6
\$\begingroup\$

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 :)

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Suds
    Nov 23, 2011 at 9:28
  • \$\begingroup\$ @JustSuds: Check for update in post. \$\endgroup\$
    – zacharmarz
    Nov 23, 2011 at 9:47
  • \$\begingroup\$ Hey hey! that almost directly matches what I have on my whiteboard! Thanks, my system is now implemented and working. :-) \$\endgroup\$
    – Suds
    Nov 24, 2011 at 1:26
  • \$\begingroup\$ 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. \$\endgroup\$
    – zenith
    Feb 23, 2016 at 5:05
2
\$\begingroup\$

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

grid line intersection

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();
}
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .