10
\$\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\$
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\$
  • 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 '11 at 9:28
  • \$\begingroup\$ @JustSuds: Check for update in post. \$\endgroup\$ – zacharmarz Nov 23 '11 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 '11 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 '16 at 5:05
1
\$\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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.