Calculate visible points in grid in 2D game

Question

I have a game grid and I need to figure out which game grid points are not behind occupied grid point from players view. The visible points. I'd like to define a visible point first, because it can mean many things and I had to figure it out:

• I call a point visible point if lines from refference point's centre to two closest point's corners do not intersect with any occupied point. On image bellow, illustration shows invisible in orange, visible in green.
  

By this definition, we can make a map like this:

Legend:

• - visible pixel
• - partially visible pixel
• - occupied pixel
• - player

I'm not interested in partially visible pixels, but I need to find out which pixels are visible. I don't know where to start. My only idea was to loop angles, but that doesn't work on larger map, where one iteration skips many actual pixels.

How do I check the visible pixels, or ideally, only the furthest visible pixels, as on this map:

And looping through all pixels must be probably avoided, that would eat up too much performance.

Answer 1

The trick is to cast rays from the source point to the edges of occupied squares.

Then sort the rays by their angle. You then 'sweep' those angles and cull the pixels that are behind the intersection points. There are ways to optimize the algorithm by removing rays that have multiple intersections, as these rays will always be between rays that have only one intersection point.

See also my answer on a similar question: 2D - Smooth lighting with shadows for a tile-based game

And an example of the algorithm in a polygon environment: http://ncase.me/sight-and-light/ The theory is also easily applied to a grid, since that could be represented by bunch of square polygons.