Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

In the Permissive Field of View algorithm, a destination square is visible from a source square if any unobstructed line can be drawn from the source square to the destination square. The algorithm works by defining a series of view fields (essentially, triangles) and checking if the destination square exists inside of a view field.

Unfortunately, the algorithm does not make available the actual line that it found between the source square and the destination square; it only tells you whether such a line is guaranteed to exist.

How can I find the line, presuming it is guaranteed to exist?

I've tried plotting lines between the edges of the source square to the edges of the destination square, but this apparently is just an approximation (it can fail to find the line).

share|improve this question
1  
There's also a page there that talks about DFOV, a similar algorithm with the advantage that it makes it easy to draw "target lines". Alternatively, you could just use a bare-bones line-of-sight algorithm once you know a particular target is visible. –  Geobits Jan 15 at 18:50

1 Answer 1

  1. Find all squares that are between the source and destination. (E.g. all squares that intersect a bounding box.)
  2. Do a 2d rotation of all the squares (including src & dest) so that a line that connects the source and destination is perpendicular to the x axis.
  3. Perform an orthographic projection of the squares into 1d space. I.e. squish them into intervals.
  4. Take the source interval, and subtract the intervals of all the other squares from it. (Perhaps using something like an interval tree.)
  5. The intersection of the subtracted source interval and the destination will give an interval of lines which connect the two squares. (Due to floating point imprecision after all these calculations, you may want to filter by a small epsilon.)
  6. Project the interval back into 2d space and rotate back into the original basis, and you have a set of lines which connect the two squares.

This should be able to calculate both if the destination is visible and the set of all lines that connect them.

share|improve this answer
    
Ok, on second thought this will only work if your src & dest squares have the same projection interval. You didn't specify, so this would be an invalid assumption in general. –  infogulch Jan 15 at 20:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.