June 2012

In a 2D top-down map it is sometimes useful to calculate which areas are visible from a given point. For example you might want to hide what’s not visible from the player’s location, or you might want to know what areas would be lit by a torch.

Drag the circle around to see what’s visible from the player’s location:

This algorithm can also calculate what areas are lit given a light source. Run once per light, we can build a light map showing which areas are lit up. What if we put 24 lights into the above maze?

The roguelike community has collected several algorithms, especially for grids (see this overview). Subtractive algorithms start with everything visible then subtract the hidden areas; additive algorithms start with nothing visible then add the visible areas. I’ll describe an additive algorithm that works with line segments, not only solid blocks or grids.

## #Ray casting

A simple approach is to cast rays from the center. It’s a reasonable first step to get an approximate answer:

To be smarter about it, let’s cast the rays only at angles where the walls begin or end. The triangles produced by these rays are the visible areas:

That’s it! The algorithm is:

1. Calculate the angles where walls begin or end.
2. Cast a ray from the center along each angle.
3. Fill in the triangles generated by those rays.

## #Wall tracking

We could stop there, especially if we have a fast ray-casting algorithm that uses a spatial hash to avoid intersecting with every wall. However, a more efficient approach is to combine the ray casting and wall intersection into a single algorithm. I’ll describe here an algorithm that sweeps a line around a circle, hitting all the points sorted by angle; it’s also possible to expand circles outwards, hitting all the points sorted by radius, but I haven’t tried that approach.

For the area between consecutive rays, we want to find the nearest wall. This wall is lit up; all others are hidden. Our strategy will be to sweep around 360° and process all of the wall endpoints. As we go, we’ll keep track of the walls that intersect the sweep line.

Press Play to see the sweep of the endpoints:

The next step is to keep track of which walls the sweep ray passes through. Only the nearest wall is visible. How do you figure out which wall is nearest? The simplest thing is to calculate the distance from the center to the wall. However, this approach doesn’t work well if the walls are of different sizes, so the demo uses a slightly more complicated approach, which I won’t explain here.

Press Play to see the sweep with the nearest wall drawn in white and the other walls drawn in black.

Whenever the nearest wall ends, or if a new wall is nearer than the others, we create a triangle showing a visible region. The union of these triangles is the area that is visible from the central point.

```var endpoints;   # list of endpoints, sorted by angle
var open = [];   # list of walls the sweep line intersects

loop over endpoints:
remember which wall is nearest
add any walls that BEGIN at this endpoint to 'walls'
remove any walls that END at this endpoint from 'walls'

figure out which wall is now nearest
if the nearest wall changed:
fill the current triangle and begin a new one```

Note that creating a triangle involves intersecting the previously active wall with the sweep ray. As a result, the new edge of the triangle may be longer or shorter than the sweep ray, and the far edge of the triangle may be shorter than the previously active wall.

## #Playground

Here’s a playground with more blocks. Drag blocks into the grid area. Press play/pause to see the algorithm in action, or drag the center point around to see what would be visible as the player walks around.

## #Combining outputs

We can use set operations to combine outputs of this algorithm in interesting ways. These are implemented either as boolean operations in algorithms that analyze the output, or as bitmap operations in algorithms that render the output.

### Player vision

The simplest operation is to limit the player’s vision by intersecting the output with the limit of visibility. For example, intersect the output of the algorithm with a circle to limit the radius you can see. Intersect with a gradient-filled circle to make the light fall off with distance. Intersect with a cone to build a “flashlight” effect that lets you see farther in front of you but not much behind you (see the trailed for Dynamite Jack for an example of this).

Player vision would also look better if it took into account both eyes instead of treating the player as a single point. I’d expect that you can take the union of the visibility output from each eye but I haven’t tried this.

### Map objects

Visibility can also be used for calculating what areas a torch lights up. The demo at the top of the page first takes the union of the areas lit up by each torch, then intersects that with the area the player can see. (Note that this algorithm produces hard shadows and you’ll have to post-process the output to get soft shadows.)

The same calculation could be used for determining what areas a security camera can see, what’s protected by a shield, or what’s magic objects are close enough to give you a bonus or curse.

### AI behaviors

Visibility can also be used to build AI behaviors.

For example, let’s suppose the enemy AI wants to throw a grenade to hit one of the players, but also wants to stand in a place where the players can’t shoot back. Grenades need to be close enough to hit the player, and also not behind an obstruction.

This diagram shows the map annotations an AI unit might calculate:

Grenades thrown into purple areas will successfully hit a player. Yellow and purple areas are dangerous to stand in; the player can shoot the AI unit from there. The AI needs to stand in a safe (dark blue) zone and throw a grenade into a purple zone, then take cover. How do you calculate cover? Run the visibility algorithm again from the place the AI plans to throw the grenade, making cabinets and tables block line of sight.

## Implementation

I have written a Haxe 3 implementation of this algorithm, open source under the Apache v2 license (similar to MIT and BSD, it can be used in commercial projects). Haxe code can be compiled into Javascript, Actionscript, C++, Java, C#, or PHP. I compiled it into Javascript for this web page and compiled it into Flash for some of my other projects. I’ve compiled it into these languages:

• Actionscript; readable, since Actionscript is not too different from Haxe
• Javascript ported by hand by Cyril Silverman; more readable than the one compiled from Haxe.
• Java; mildly readable but not great.
• C#; mildly readable but not great. Roy Triesscheijn has a better version here.

Wade Tritschler suggests porting by hand is going to generate cleaner results than using the Haxe output. I agree. You’ll also understand the algorithm better if you convert the code by hand.

Thash posted in the comments a C++ version that also handles the tricky cases.

Although the main part of the algorithm is CPU bound, the GPU could be used for triangle rendering to a bitmap and compositing operations for combining bitmap outputs. (A boolean AND operation becomes a bitmap multiply; a boolean OR becomes a bitmap add and clamp.) The performance hasn’t been enough of a problem in my projects so I haven’t built a GPU version. If your game is CPU bound, consider using a subtractive algorithm (instead of the additive one shown here), rendering the shadow of each line segment as a quad. It will increase the rendering load on the GPU but it doesn’t require sorting on the CPU. If fill rate is an issue, consider rendering a light bitmap that’s at a lower resolution than the game screen, and scaling it up.

## References

1. Bungiu, Francisc, et al. “Efficient computation of visibility polygons.” arXiv preprint arXiv:1403.3905 (2014). This paper covers several algorithms, including one that’s significantly faster than the one I’m using on this page. This paper came out after I wrote my page; I’d like to one day go back and try their algorithm.
2. Asano, Tetsuo. “An efficient algorithm for finding the visibility polygon for a polygonal region with holes.” IEICE TRANSACTIONS (1976-1990) 68.9 (1985): 557-559. This is a sweep algorithm like I’m using on this page, applied to polar coordinates instead of cartesian coordinates.

## Related

Sight and Light uses the same algorithm to solve the visibility problem. This page covers visibility with arcs instead of circles, and includes a detailed explanation of the algorithm and implementation. My blog post has more links to projects like this. Munificent covers visibility algorithms optimized for grids, with interactive diagrams and sample code. The Skyline Problem is similar to 2d visibility, except it’s in cartesian coordinates instead of polar coordinates. There’s also the art gallery problem about placing multiple guards in the environment so that they can see the every area of the map. I’m making a list on Trello of possible future updates to this page.