I've designed and coded an algorithm to solve visibility of cells in 2D maps, from the perspective of a single point. It's probably not new, but it was fun to make.

Characteristics and potential

It's not symmetric, because the camera has a single point, and tests corners of target cells. However, it sees through small gaps for maximum potential visibility, and uses relevant angular ranges rather than speculative raycasting.

It's reasonably efficient, and has a couple of inbuilt optimisations for clear areas near the player, and radius beyond whole-arc shadow.

It can be modified to record angular visibility for each cell, and calculate whether the camera can see an object of known size and position.

Algorithm overview

We start with a complete circle that denotes full visibility around the player. We expand that circle, partitioning it with every obstruction. As we expand the circle, it provides a simple test for cells further away.

It should have complexity O(n) for the traversal, and O(log n) for the preparation, where n is the number of cells. It occupies some memory for a list of pointers to cells, and the visibility arc data.

I'll call this algorithm "partitioned expanding visibility arc", but it probably has precedents.

.

Steps

1. Build a list of map cells, distance-ordered, holding: `{ [min, max] heading (angle), distance}`. This might be expensive, as `atan2()` calculations of all cells, which could be cached or optimized.
2. Start with a circle. Call this the 'visibility arc'
3. Find first obstacle in the distance-ordered list.
4. Mark as visible, all cells with radius up to that cell, in the distance-ordered list.

5. For an obstacle cell, mark visible if its angular range has visibility in the visibility arc, and split the visibility arc to exclude that range, using an exclusion range of the edges of the obstructing block. We can modify the cached angles to account for rogue-visible diagonals.
6. Continuing down the distance list, for any further non-obstructing cells, test if they fall in the visibility arc.
7. If the visibility arc is ever empty, then all remaining cells are not visible. It's best to 'mark visible with the current scan number', so that you don't need to touch cells to mark them as not-visible.

Optional improvements:

• Tag as visible = set to current scan number (increments with each new situation).
• Optional: Where there's vertical obscuring, or probabilitic obscuring, e.g. enemy, mark the cell as 'partial' and continue subdividing (not optimal for the subset of cells, unless we cache hashes in each arc partition?).
• Optional: Store partial visibility of squares behind an obstruction, using proportion of angular range that's visible. Store in a format that you can test against, for seeing smaller objects in the cell.
• Provide alternative angular range for a cell, for rogue corners, pillars, or other non-square features.