9 replies to this topic

[destiny]

Hi there
I work on a function who tell me if Point A can see Point B in a 2D koordinate system (a koordinate can be blocked - black - or open - white)

How can i test if green can see red? Or not like in this example.
All Infos i have are:
both points green: 3,1; red:5,5
blocked fields: 4,2; 4,3; 4,4
and if necessary the side length of 1 field (it should work without that, not?)

I know there was something I learned at school, but I cant remember.

Can you help me with a bit pseudocode or a link or something?

thx alot!
destiny

[alphadog]

Google for line of sight algorithms. There more than you want to know...

[v71]

there are 2 different ways you can explore , the first is to use the brhesenham ( sp?? ) algorithm basically you trace a line between a and b and check if the square is black or not, if its black, then you can exit early with a non visibility flag, because the sight is blocked, or , you can compute the intersection point between the line and the box geometrically, if there is intersection then the line of sight is blocked

[destiny]

If I understand that right LOS make a line between both points and checks every pixel of this line (or every 4th pixel, or whatever u want). If the pixel is in something that blocks then return false, else continue. If u are at the other point the first point can see it.

right?

thx for the keyword

[destiny]

when i replyed I didnt saw your post

v71 said:

you can compute the intersection point between the line and the box geometrically, if there is intersection then the line of sight is blocked

thats what i had in mind from school. There was something with vectors hitting a point or a line. But i cant remember. And i dont know if thats good to do that this way or better with the linetrace. When i have 100 boxes on the map and each box have 4 lines to check, then thats much calculation.

[.oisyn]

Bresenham will only work if you allow diagonals. For example

A  X
 \X 
 X\
X  B

You may want to actually trace the line from beginning to end, and see which of the 4 boundaries it crosses on every grid point (similar to ray casting in wolfenstein 3D)

[v71]

Destiny, this is a classic problem and there are classic ways to solve, you could partition your search space using a quad tree or a regular grid or a bsp tree, but the complexity is higher.
If i had 100 boxes to check i would use a regular grid subdivision and i would trace a line beetween all this boxes and the observer, this is a pretty fast algorithm and its implementation isn't terribly difficult.
Note that you don't have to check all for boxes, if you detect a first intersection you can skip to the next block becasue just one intersection is sufficient to flag the block as visible.
A method is also to reduce the number of test, just like a collision detection procedure, compute the nearest and the fartest (sp??) points which belongs to the box respect the line and classify those points against the line with an halfspace function.

[fireside]

A simple way not totally accurate is to use your astar algorithm and if it hits a block, it can't be seen.

[alphadog]

destiny said:

If I understand that right LOS make a line between both points and checks every pixel of this line (or every 4th pixel, or whatever u want). If the pixel is in something that blocks then return false, else continue. If u are at the other point the first point can see it.

Yes. In your 2D-grid example, you have the two endpoints, and the line between them (meaning getting the squares that are on the line) is given by Bresenham's algorithm. Once you have those squares, you "walk" the list of squares hit by the line, and if something is in it, you determine if it blocks view or not. (Actually, you visit each square as you get the list, and end early if you hit a block.)

The potential problem with Bresenham's is that it can move diagonally via the vertex, so depending on the requirements of the game, this may translate into a "view around a corner" issue or other oddity in the game.

One approach to solve that could be to "anti-alias" the line. You'd have to adapt Xiaolin Wu's algo instead, and you can get more squares to what you'd get with Bresenham's. You'll note in the wikipedia's article that, in the function plot(x, y, c), the value of c (where 0 ≤ c ≤ 1) could be used as an indicator of levels of partial or variable visibility.

[.oisyn]

Actually, in case of diagonals, I think what I said made more sense (the wolfenstein raycasting remark). The points where you intersect the horizontal grid boundary lines are evenly spaced, and where you intersect the vertical lines as well. You can simply calculate those distances (dx/dy for one, dy/dx for the other), and how much you need to "move" for the first intersection in x or y - these are you two counters. At every point, the lowest of the two represents which you cross first. As soon as you hit an intersection, you reset it to the new distance.