[gameprogrammer] Re: Calculating Line-Of-Sight

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


Other related posts: