Finding which tiles are intersected by a line, without looping through all of them or skipping any
- by JustSuds
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.
