Partial Occlusion Field-of-View

It seems like there are problems that I have to solve over and over again. Pathfinding is one of them. Another is visibility determination.

When you need to know if there’s an unobstructed line of sight between point A and point B you typically just cast a ray from A to B and see if it hits something. The set of all points that can be reached with an unobstructed line from A are referred to as A’s Field of View. Calculating it accurately would require an unlimited amount of rays, so you typically sacrifice accuracy by partitioning space in some discrete data structure. Grids, Trees, Pixels, Voxels… that kind of thing.

In this post I’ll focus on FoV calculations on square grids. Using a low resolution square grid is a pretty huge abstraction, and the whole point of this article is to show how to get some accuracy back without losing too much performance! But let’s start simple…

Calculate Field of View with Raycasting

As long as you only care for a Boolean result (is a square B visible from square A in the center) it’s straight forward to calculate using raycasting.
First of all consider how many rays you need: Just enough so that every field that could potentially be part of the Field of View is passed by at least one ray. So better define a max range or you would still have to cast an unlimited number of rays despite working on a low resolution square grid. Now select fields at maximum range so that those fields completely enclose your center. Draw lines to them and all closer fields are automatically tested too!

Raycasting only towards fields at max-range reduces the algorithms complexity from O(n³) to O(n²). Thtat’s a huge difference! Imagine how the illustration would look like if all cells would be target of  a raycast…

For line-drawing you can just use Bresenham’s Line Algorithm. All clear fields covered by the line are part of the field of view. As soon as you hit an opaque field abort the raycast. It’s not part of the field of view and all other fields that follow along the direction of the ray are occluded by it.

There’s room for improvement

When I tried to use the raycasting approach to implement dynamic lighting for an isometric 2D game engine I found that I would have to find an improved algorithm to make it look great.

Consider an opaque field casting a shadow. A lot of fields will neither be fully lit nor fully in shadow. From light source’s point of view those fields are partially occluded! So I wanted my fields to specify their membership in the Field of View as a percentage (0 – 100%) and not just a Boolean (true or false).

The other limitation I hoped to overcome were integer coordinates. It didn’t suffice to say a light-source is on Field (x,y) – I wanted to specify the exact position on the field the light would come from. So I needed to be able to precisely define the center of my Field of View by using non-integer coordinates.

The Mission

I hope I managed to convey an idea of what problem the algorithm I’m about to present is trying to solve. To be sure let’s sum up the situation:

• We operate on a square grid that partitions a 2D plane in equally sized fields.
• Some squares are clear (will allow light to pass through) while others are opaque (will block light).
• We define a point for which we want to calculate the Field of View.
• We want to know the degree of occlusion for each square closer then the max range.

My research didn’t yield any established solution so I accepted the challenge to find a new one (or reinvent the wheel, who knows). Here’s a demonstration of my solution in action:

The full source of the demo is available under the MIT license. However, deducting an algorithm from poorly documented AS3 source code might be a little inconvenient if you want to understand the principles behind it. So I conclude the post with a explanation of the algorithm.

Partial Occlusion Field of View

It helps to think of center of the Field of View as a light source from which light is spreading equally in all directions. The spreading light will exit a square on the edges facing away from the light source and enter a neighbouring square. So for each square you can clearly identify one or two neighbouring cells that all the light is coming from.

Now all you have to do to know how much light is going through a particular square is to ask the relevant neighbours to describe their contribution. If a neighbouring square is opaque it will contribute no light. Otherwise it will contribute a portion of the light it itself received – which can be anything between zero and the width of the shared edge.

Circular sectors to represent beams of light

A simple way to express the “portion of light” is a circular sector. With the center known we just have to store two angles to define such a sector.

This illustration shows how the light passing between two occluders can be described by specifying two angles: Alpha and Theta.

Due to the nature of the grid one sector (e.g. two angles) per neighbour is enough to describe it’s contribution! This is because occluders are always one square in size and thus the shadows they cast can’t be smaller then one square. With this method of describing lightbeams it’s easy to form unions and intersections of lightbeams, too. Unions, when we want to combine the light coming from two different neighbouring squares and Intersections when we constrain the result to the size of our current square.

The Algorithm

The algorithm can be summed up as follows:

FOR EACH non-blocking square:
	1: Identify all neighbours that are not opaque 
	   AND share an edge AND are closer to the center.
	2: Store the contribution from the first neighbour 
	   as circular sector A.
	3: IF a second neighbour exists: store the contribution 
	   from the second neighbour as circular sector B.
	4: Calculate a circular sector C that describes the maximum 
	   amount of light that could possibly pass the current square.
	5: Form the UNION of A and B and INTERSECT with C to receive D. 
	   D describes the amount of light actually passing the current square.
	   The smaller the ratio of D to C the bigger the occlusion.

The following illustration demonstrates the process on a square that happens to be half occluded. Only one neighbour contributes light, while the other is opaque.

This animated illustration shows how to calculate the occlusion of a square based on the occlusion of the two of it’s neighbours closer to the center.

Calculating a Squares circular Sector

But how to calculate a circular sector that describes the maximum width light beam that could go through a particular square (labeled ‘C’ in the above illustration)?
To find it you simply calculate alpha for all four corners of the square and pick the largest and the smallest angle to form the circular sector. The resulting sector will enclose the full square.

The illustration shows that there’s a distinct pattern in what corners you would have to pick. So you don’t have to calculate four values and then discard two. Instead you can evaluate the sign of the x and y component of the vector pointing from lightsource to the square and to predict the correct ones. And if you’re going through the sourcecode of my reference implementation and notice these weird looking lines now you know what they do! dx and dy describe the position of the square in relation to the center and (x1, y1) and (x2, y2) are the corner’s that define the sector.

var sx:Number = (dx == 0) ? 0 : (dx < 0) ? -1 : 1;
var sy:Number = (dy == 0) ? 0 : (dy < 0) ? -1 : 1;
var ox:Number = (sy == 0) ? sx : 0
var oy:Number = (sx == 0) ? sy : 0
var x1:Number = x + 0.5 * (1 - sy + ox);
var y1:Number = y + 0.5 * (1 + sx + oy);
var x2:Number = x + 0.5 * (1 + sy + ox);
var y2:Number = y + 0.5 * (1 - sx + oy);

Recursion vs Iteration

Another difficulty worth mentioning is that to calculate a particular square’s occlusion the occlusion of it’s relevant neighbours must be known first. How can we make sure they are already calculated?

The obvious approach would be to use recursion, which means that whenever we query the sector of a cell that hasn’t yet been evaluated it’s sector will be calculated before the query returns the correct value. To calculate the FoV (e.g. the degree of occlusion of all squares within max-range of the center) using recursion, trigger the evaluation in the four corners of the bounding rectangle. All squares enclosed by the rectangle will be visited before the calls return. There’s just no other way for the recursion to terminate than by reaching the center tile for which the occlusion is always known. This is when the evaluation-method ceases to calling itself on neighboring cells and begins to return values. It’s a good idea to implement it so that each cell is only calculated the first time it is queried and cache the result. That way subsequent queries don’t incur an unnecessary reevaluation.

There’s nothing wrong with that approach as long the stack space suffices. But if this could be a problem it’s also possible to devise an iterator pattern that will visit squares in such an order that all relevant neighbours have already been calculated.

The demonstration I’ve linked implements both the recursive and the iterator based version of the algorithm as well as some raycasting based FoV as a reference. Here’s the source code of the demo! It’s released under the MIT License and includes all relevant dependencies. I hope you enjoyed the lengthy read, feel free to post questions or comments!