[gameprogrammer] Re: Calculating Line-Of-Sight
- From: Olof Bjarnason <olof.bjarnason@xxxxxxxxx>
- To: gameprogrammer@xxxxxxxxxxxxx
- Date: Sun, 6 Nov 2005 21:42:46 +0100
On 11/6/05, Jake Briggs <jacob_briggs@xxxxxxxxxxxxxxx> wrote:
> I would google for "line intersect plane", the line being the line of
> sight. Maybe read up on some simple ray tracer examples, I can't
> remember any specifics of the math behind it :)
>
> This is "2 1/2 D" like doom was yes? So you want to test each
> interesting plane for an intersection. The planes are the edges of your
> cubes, the cubes that are walls. Because its a doom like engine, you
> could probably make some assumptions that will speed this up, but don't
> do that until youve got it working :)
>
> You work out the vector between player one and player two (this is the
> line of sight), then test that vector against each plane in your map
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". 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. 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
Other related posts:
