[gameprogrammer] Re: Calculating Line-Of-Sight
- From: Jake Briggs <jacob_briggs@xxxxxxxxxxxxxxx>
- To: gameprogrammer@xxxxxxxxxxxxx
- Date: Tue, 08 Nov 2005 09:46:29 +1300
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:
