[gameprogrammer] Re: Calculating Line-Of-Sight



Olof Bjarnason wrote:



I wouldn't recommend testing against *all* planes in your map -- just
the planes of the wall-cubes that are "candidates". How to find the
candidates? One simple idea is "drawing" a straight line from point A
to point B, testing all walls thus "painted".

How do you find out which walls are "painted", and which one are not without testing all the walls for an intersection? You would end up doing all the walls once, then re-testing the candidate walls.

You could cull the walls as an optimisation, getting rid of the test for all walls "behind" the player for example, but with only 6400 walls in the worst case I am not sure if it would be much of an optimisation. Maybe it would be, I dunno.... But you would have to find a better way to work out which walls are "behind" the player than testing for an intersection of the line of sight ray and the wall!
Also you could skip the whole test if the opposing player was "behind" the other.


You can draw the line
using Bresenhams classic algorithm, or just use some simple
floating-point algo, shouldn't really make any practical difference
since you are not "drawing" more than a very small amout of lines per
frame (one for each sniper-rifle shot? one for each enemy? never the
less an insignificant amount I would hazard .. ). Just make sure you
draw a wide enough "line": two may be too thin.


I suppose you could use 8 rays, one pointing at each corner of an invisible bounding box around the opposing player. The rays would start from one point on player one, and target the corners of the opposing player. This would mean 51,200 intersection tests in the worst case. The worst case being that all cells are ceiling cells, and that wouldn't be much fun to play :) But that is still a lot of tests.

A sniper rifle type weapon would only need one ray, but you would have to test it against each of the 6 planes of the aformentioned bounding box. You would only need to perform this test if the line of sight test was true though.

Try drawing the grid
on a piece of paper, putting A and B out NOT centered on a grid cell,
and figure it out.

Seems like a good place to read about drawing primitives:
http://www.brackeen.com/home/vga/shapes.html#shapes3.0

/Olof



(the walls or edges of your wall cubes, all 4 of them). If you find an
intersection, test the depth. If the intersection is not between player
one and player two, then there is clear line of sight. I think you could
actually stop once you have found the first intersection that is between
player one and player two, since this game is "2 1/2 D". Otherwise carry
on with the next intersection test.
You work out the vector once, then test it against the planes. You treat
one of the players as the origin, it probably doesnt matter which one.
For example, if you decide that player one is to be the origin, and you
find an intersection of the vector and a plane, then if the intersection
is further along the ray than player 2 is, then the plane in question
doesnt get in the way of line of sight, if the plane is closer than
player two, then you have no line of sight.

Even if you do this niavely, it should be faster than your current
algorithm, and it wont fail the edge cases (pun intended :) ), ie it
will be more accurate. As I said befor, I can't remember the math
specifics, but with the ray tracer it was faster to convert the vector
and the object to unit vectors and preform the intersection test rather
than try to do it with the real vector. This involves some simple matrix
multiplication. Keep us updated :)

Jake

Stephen wrote:



I have a 3D game that uses the following algorythm to work out of one
unit can see another (i.e. are there any walls in the way):-

(Note - the map of the game is a simple 40x40 array, and each cell can
be a wall or floor.  Unit positions are stored as floats, so they can
be anywhere, not just in the centre of a map square)

1) Work out a line from one unit to another
2) Move along the line, and at every interval, check whether the point
is part of a wall or a map.  If its a wall, the unit cannot see the
target.

This does work well in general, but if two units are close together
but round the corner from each other, it can sometimes return true
when in fact there is a corner in the way.  I could try increasing the
interval, but this obviously increases the time it takes the algorythm
to run.  Does anyone know a better method?

Thanks in advance,

Stephen





---------------------
To unsubscribe go to http://gameprogrammer.com/mailinglist.html






--
Jacob Briggs
Systems Engineer

Core Technology Limited
Level 1, NZX Centre
11 Cable Street
Wellington
Phone +64 4 499-1108

--

Named after its country of origin 'England', English is a little known dialect 
used by up to 1.5 billion non-Americans worldwide. Some interesting but 
obviously incorrect features of the language include:

- queues of people
- wonderful coloUrs
- the useful metal aluminIum
- the exotic herbs (h-urbs), basil (ba-zil) and oregano (o-re-gaa-no)
- specialiSed books called 'dictionaries' that tell you how to spell words 
correctly

Many people using this bizarre gutter speak also subscribe to the pagan belief 
that water freezes at 0 degrees and that distances should be measured in the 
forbidden mathematical system of base-10...



---------------------
To unsubscribe go to http://gameprogrammer.com/mailinglist.html







---------------------
To unsubscribe go to http://gameprogrammer.com/mailinglist.html







--
Jacob Briggs
Systems Engineer

Core Technology Limited
Level 1, NZX Centre
11 Cable Street
Wellington
Phone +64 4 499-1108

--

Named after its country of origin 'England', English is a little known dialect 
used by up to 1.5 billion non-Americans worldwide. Some interesting but 
obviously incorrect features of the language include:

- queues of people
- wonderful coloUrs
- the useful metal aluminIum
- the exotic herbs (h-urbs), basil (ba-zil) and oregano (o-re-gaa-no)
- specialiSed books called 'dictionaries' that tell you how to spell words 
correctly

Many people using this bizarre gutter speak also subscribe to the pagan belief 
that water freezes at 0 degrees and that distances should be measured in the 
forbidden mathematical system of base-10...



---------------------
To unsubscribe go to http://gameprogrammer.com/mailinglist.html


Other related posts: