[gameprogrammer] Re: Calculating Line-Of-Sight

On 11/8/05, Jake Briggs <jacob_briggs@xxxxxxxxxxxxxxx> wrote:
>
>
> Olof Bjarnason wrote:
>
> >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!).
> >
> >
> Yes, but how do you know which walls are on the line?
Look here, when you draw a line, you automatically know which points
are on that line. Google "line drawing" or "bresenhams line segment
algorithm".

>
> >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.
> >
> >
> So the x,y position is the point at which the line intersects the wall?
No, the x,y position is one of the candidate coordinates on the grid.
So when you got the x,y coordinate on the grid, check if it is a wall
(very fast), then if it is, do the more time-consuming cube-ray
intersection test.

To be super-clear about this, I could recap :

One could say the line-of-sight algorithm has two points A and B as
input (floating point values). Then, we could say the algorithm
proceeds in two "levels":

1. The "upper" level just figures out what integer grid locations
(x,y) could POSSIBLY contain a wall in the line between A and B. This
is the so-called "line-drawing" part of the algorithm. For every wall
found by this step, step 2 is performed
2. We know there is a wall at (x,y) which potentionally blocks the
line-of-sight between A and B from step 1. Do the maths here
(cube-line intersection test). If the test determines the line segment
between A and B intersects the cube, return "A does not have a clear
sight to B", otherwise continue with 1.

Once all candidate walls/grid locations have been tested and none of
them returned "A does not have a clear sight to B", we can conclude
that there is a clear line of sight from A to B, since we've tested
every wall that could possibly block the sight between them.

/Olof

>
> >/Olof
> >
> >
>
> --
> 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: