[gameprogrammer] Re: Calculating Line-Of-Sight

On 11/7/05, Jake Briggs <jacob_briggs@xxxxxxxxxxxxxxx> wrote:
>
>
> 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 :)

The problem with the original approach was that it could *miss* walls,
even if we decrease the "interval length" (which would of course make
the algorithm slower also) added at each step.

The line-drawing approach I am talking about, fills every wall on the
line, very much like a line-drawing algorithm from point A to point B
in a painting program would (thus the name!).

When you have such an algorithm from drawing lines on Stephen's grid,
it is easily modified to instead of drawing a "pixel" at location
(x,y), doing the test I mentioned earlier. That's where my x and y
comes from.

/Olof

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


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

Other related posts: