[gameprogrammer] Re: Calculating Line-Of-Sight

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

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

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

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

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


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

Other related posts: