Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I've been staring at this problem for a few days now. I rigged up this graphic to help me visualise the issue:

http://i.stack.imgur.com/HxyP9.png

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

share|improve this question
    
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
add comment

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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