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

Please log in or register to post a reply.

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

when i replyed I didnt saw your post@v71

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.

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)

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.

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

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.

- Upcoming Multiplatform Game Program...
- Our first game - looking for feedbacks
- Network Emulation Tool
- Trouble with accessing GLSL array
- Fiction
- Game Programming Patterns: Bytecode
- Interactive WebGL Water Demo
- Skeletal Animation Tutorial with GP...
- Unreal Engine 4
- Microsoft xbox one selling poorly

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