John Valentine
PEVA visibility algorithm
 Date 27 March 2024

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.

Visibility highlighted from the algorithm.

## 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.