2d Visibility

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. Show 24 lights added to the map.

The roguelike community has collected several algorithms^[1], especially for grids. See this overview^[2] for how grid algorithms handle situations differently. Also see Albert Ford’s interactive tutorial about the recursive shadowcasting algorithm^[3] (wayback archive^[4] if the main link doesn’t work). Gridbugs has another nice explanation^[5].

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#

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.

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.

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.

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

Playground#

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 trailer for Dynamite Jack^[6] 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

Grenades thrown into purple areas will successfully hit a player. Orange 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^[7] 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 (used for the demos on this page); mostly readable.
• Javascript^[8] 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^[9].
• Alex Hall has a GDscript version^[10].
• R. Trabski has a Python version^[11].

Wade Tritschler suggests porting by hand^[12] 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.

Warning: my implementation is mediocre. It is missing optimizations and it has numerical robustness issues. It generates superfluous empty triangles in the output. This page^[13] is worth a read, and take a look at this library^[14] which implements robust algorithms. Another reference is Shewchuk’s^[15]. Thash posted in the comments a C++ version^[16] that also handles the tricky cases.

There’s a similar algorithm in CGAL^[17] (C++). See Rotational_sweep_visibility^[18]. There’s a Python version in SciKit^[19].

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. Also consider a 1D shadow map (here^[20], or here^[21]).

References#

1. Asano, Tetsuo. “An efficient algorithm for finding the visibility polygon for a polygonal region with holes.”^[22] IEICE TRANSACTIONS (1976-1990) 68.9 (1985): 557-559. This is a sweep algorithm^[23] like I’m using on this page, applied to polar coordinates instead of cartesian coordinates. This seems to be the paper that introduced the algorithm but I can’t find the paper online.
2. Bungiu, Francisc, et al. “Efficient computation of visibility polygons.”^[24] 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. The faster algorithm is implemented in CGAL^[25], which measured it as 50X faster than the rotational sweep algorithm I have on this page. This fast algorithm may be related to this beamcasting approach^[26], which was published in 2010 on a blog.

Related#

Nicky Case’s Sight and Light^[27] uses the same algorithm to solve the visibility problem. Sundaram Ramaswamy’s page^[28] covers visibility with arcs instead of circles, and includes a detailed explanation of the algorithm and implementation. My blog post^[29] has more links to projects like this. Munificent covers visibility algorithms optimized for grids^[30], with interactive diagrams and sample code. Kevin Zuniga has a divide-and-conquer approach^[31] with a parallel implementation in CUDA. The Skyline Problem^[32] is similar to 2d visibility, except it’s in cartesian coordinates instead of polar coordinates. There’s also the art gallery problem^[33] about placing multiple guards in the environment so that they can see the every area of the map. I’m making a list on Notion of possible future updates to this page^[34].