Line of sight math

Game Mechanics
#1

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

http://dl.dropbox.com/u/18809996/LOSMathProblem.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 been thinking along the lines of gradients, using floor and ceiling to isolate / determine spaces, or simply stepping along the line’s direction vector by a fixed amount.

#2

It’s late night for me so my math brain isn’t very active. I don’t know if there is a better way to just check a grid position randomly, but if you want to march along the line, try looking into http://en.wikipedia.org/wiki/Bresenham’s_line_algorithm

It basically does what you need to, but in terms of finding pixels to render when drawing a line. Of course it should be an easy modification to line of site in this case.

#3

I think this is what you want?

There’s a solution somewhere in that thread

#4

surely all you need to do is get the equation of the line and then step though one axis’s ordinates? e.g.

so in your example

the equation of the line is y = (3.5-1.45)/(3.4-0.7) * (x-0.7) + 1.45

and thus iterating x from 0.7 to 3.4 in steps of 1 should give you the co-ordinates to test in your map for intersections.

i.e.



float y;
for (float x = 0.7 ; x<3.4;x+=1.0f)
{
y= (3.5-1.45)/(3.4-0.7) * (x-0.7) + 1.45;

if (map[(int)x,(int)y] == WALL_TYPE)
{
      // draw wall
      break;
}
#5

The standard Bresenham’s line algorithm is NOT applicable in this case. It would simply miss certain tiles. It can however be modified to connect he line properly and avoid this.

The idea is to instead of looping over tile centers (x = 0.5, 1.5, 2.5…) we loop over tile borders (0.0, 1.0, 2.0, 3.0). Start by checking the tile the unit is standing on. Then branch depending on if dx or dy is the biggest (to handle all cases instead of just to the right). In OP’s case he’ll also want to check for negative dx and dy, leading to 4 branches since he needs to check from the unit and out and can’t swap the target with unit for handling cases where the target is to the left or over the unit. Then you do Bresenham’s as usual but doing the collision check on tile borders instead. When the floating point delta variable exceeds 0.5 or gets under -0.5, you also do an additional collision test to avoid missing a tile.

Sorry, I know this explanation is complete crap, but give me a little time and I’ll post code instead.

#6

Thanks for the responses. I made the post a couple of minutes before I had to leave for work.

Moogie: that method won’t work (it was the first that I sketched on my piece of paper) because it can skip over grid spaces along the line.

counterp: I haven’t read the thread yet, but thanks. That opening diagram looks very promising.

lhkbob: I’ll read that too :slight_smile:

theagentdd: thanks, much appreciated - again. :slight_smile:

I think I have the solution in mind, I just need to sketch it out and code it to see if it works.

#7

My implementation in the thread counterp posted, does as moogie suggests, but adds some special cases for the missed grid spaces. It works and should be faster than other approaches I can think of.

Start reading from here http://www.java-gaming.org/topics/line-logic/24593/msg/207942/view.html#msg207942, if you want some explanations.

#8

yep, that was left as an exercise :stuck_out_tongue: but all you need to do is record the last ‘y’ position and then iterate over all the y ordinates between the last ‘y’ and the current ‘y’.

i.e. some thing similar to this.



float y;
float lastY = 1.45;
out:
for (float x = 0.7 +1.0f ; x<3.4;x+=1.0f)
{
y= (3.5-1.45)/(3.4-0.7) * (x-0.7) + 1.45;

for (float currY=lastY;currY<y-1;currY+=1.0f)
{
if (map[(int)x-1,(int)currY] == WALL_TYPE)
{
      // draw wall
      break out;
}

lastY=y;
}
#9

you shoul cicle also for X, or aligned on y line will break your math