legends2k / 2d-fov

Field of View and Line of Sight in 2D

Field of View and Line of Sight in 2D

View it in action in your browser!

The idea is to find the field of view from a given point in a 2D world which has buildings. Many resources on the web doing 360° FoV exists; these have their FoV's distance and angle unbound. This is simpler to design; arriving at a fast implementation is easier since -- if rightly done -- there would be no intersection queries every iteration of the loop to eat up performance. However, the FoV here is different; it's limited both by angle and distance. Care is taken to have an optimised solution that avoids unnecessary intersection tests so that it's usable in a game where multiple agents would need their FoV computed every frame.

This implementation is done in HTML5 Canvas/JavaScript for easy viewing but the idea is mathematical and can be implemented in any language. The only library it uses is glMatrix for vector calculations. The code is heavily commented and includes references to articles and books for someone to learn from it.

The design document has all the gory details, again with references for further study.

2d-fov's Issues

incorrect hit point intersection, when segment.center x is the same as polygon edge

Hi! I really liked your article and the source codes for that 2d-fov. I've found a bug in your code, I spend 2 days finding and fix, but I can't find a solution. Please help.
A test scene is:

scene = {
         polygons: [
             { coords: [ 96,72,120,72,120,96,96,96 ],
               colour: "128, 128, 128",
               stroke: 1,
               fill: true },

        ],
         observer: { loc: vec2.fromValues(50, 96),
                     dir: vec2.fromValues(-0.707106781186, 0.707106781186),
                     colour: observerColour },
         target: { loc: vec2.fromValues(500, 100),
                   dir: vec2.fromValues(-1, 0),
                   colour: targetColour }
     };

As you see, fov calculation is incorrect

Any field of view greater than 180° fails to render properly

Not sure if you're actually interested in this anymore, but thought I'd bring it up just in case. I'm actually trying to do something similar to what you already have, but with a full 360° range. I could use your code directly and just run it twice for those cases where the total FoV is greater than 180° (splitting the range between the two runs) and union the polygons, but that's likely way more inefficient than it could be with a real solution.