Optimize Field Of Vision Algorithm In A Grid Tiled Map

I am trying to implement Field of View algorithm in my game and I followed the great tutorial here : sight-and-light and here is what I got so far : As you can see it works fine f

Solution 1:

What you are doing can be optimized a great deal. First there's not point in using all the vertices and no need to do any intersection tests.

Take each polygon. For each vertex figure out if it's an inversion point. That is take the ray from the origin/eye and check if the neighbor are on the same side. Figure out which direction goes towards the origin and follow it until you find another inversion point. The segment in between these point are the ones facing the origin/eye. If you have a convex shape there's only 2 of them, for more complex ones there can be more.

Next convert all the inversion point to polar coordinates and sort them by the angle. Now you should have a bunch of possibly overlapping intervals (take care about the warparound 360->0). If you scene is simple the intervals are non overlapping, so you only need to follow your polygons with the light (no tests needed). If you have encounter an overlap, take the inversion point and the current edge from the existing interval and see if the inversion point is on the same side as the origin/eye. If so then you can intersect the ray to the inversion point with the current edge to get the far point and link it with the inversion point which will now replace as the current edge. If there's an interval that doesn't belong to any polygon the rays will go to infinity (there's nothing to see for all rays in that polygon).

This works for all non-overlapping polygons.

So in your case you will get only 9*2 inversion points (your polygons are simple) and you need to do very few edge * ray intersections because their layout is fairly sparse and the algorithm is quick to discard obvious non-intersecting cases.

If this is for some real-time application you can optimize it further by taking advantage of the fact that the inversion points mostly remain the same, and if they change they travel along the polygon usually one edge (could be more if the polygon is small the the move distance is large).