[gameprogrammer] Re: Calculating Line-Of-Sight



Olof Bjarnason wrote:

On 11/6/05, Jake Briggs <jacob_briggs@xxxxxxxxxxxxxxx> wrote:


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.



Well, in the line-drawing inner-llop, instead of pixels[pitch*y + x] =
color; or whatever draw-pixel-code you have, you do
if(isWall(x,y))
RayCubeCollisionText(theRay, getCubeAt(x,y));



Where does the x,y value come from? Is that where the player is? Or is that an incrementing point along the line of sight? If its a point along the line of sight, then that algorithm is pretty much the same as the original one....
I think we are talking about different things here, and getting our signals crossed :)



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!


Well I didn't optimize that much, I just wanted to not have to test
*all* "wall-cubes" of the whole map.


Well we know where the player is, and which way the player is facing, I think that this would be a fast brute force culling technique. Then again, I don't know how Stephen's engine works.



Also you could skip the whole test if the opposing player was "behind"
the other.


Yep, that's an optimization. Just project the B-A vector on the
"forward" vector of the player (at A) and check if the result is
positive.


Indeed.





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.


I'm not sure I follow you here.



I was talking about 2 different things :) The first paragraph concerned the line of sight problem. The second paragraph diverted onto how to see if a weapon would hit the player, if that weapon was an instant hit one (machine gun and rail gun in quake3arena are instant hit weapons for example).

When you want to see if player one can see player two, you probably want to test the extremities of Player twos model. If you only use one ray pointed at the middle of player twos model, then player two would be "unseen", if they were not in full sight, the the middle of the model was occluded by a wall for example. The bounding box just makes this easier.

The weapon one is different. You would calculate the vector that describes the shot, then test for an intersection of that vector and the opposing player. Since the opposing player would be a model with a whole lot of polygons (say 100 for a crappy looking model) you don't really want to test all of those. So you use a bounding box, then you only have 6 intersection tests.
Once you've done that, you can move on to optimize it, or make it cooler. Maybe have 2 bounding boxes, one for the head and one for the rest of the body. Maybe 6, head, torso, and the limbs. I dunno.

--
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: