H-World - Docs - Field of View

Shadowcasting

H-World uses shadowcasting to determine which squares are visible from a given point. It does this by determining the shadowed angles caused by sight blocking squares and checking which squares are inside the shadowed angles.

The image below shows the shadow of one blocking square. The blocking square is marked in black. The visitor is placed on the center of the square down left.

One blocking square

There are fully shadowed grids inside the shadow angle, and partly shadowed grids. The fully shadowed squares are displayed in dark brown, the party shadowed squares are displayed in light brown.

The next image shows two blocking squares. Their shadows overlap, causing a bigger area to be shadowed.

Two blocking squares with overlapping shadows

The shadowcasting implementation of H-World works fairly simple. It traverses the octant from left to right, and each column from bottom to top and performs the following calculations:

1. For each square, two angles are determined, the top-left angle, and the bottom-right angle. If the square is a blocking square those angles are the lower and upper bounds of the shadowed angle interval.
2. If a blocking square is found, the shadowed interval is stored in a list. If the interval overlaps with another interval already stored in the list, the intervals get merged.
3. If a non-blocking square is found, it gets checked if is fully or partly inside a shadowed angle interval. Fully shadowed means it's own shadowed angle interval is a sub-interval of a shadowed interval from the shadow list. Partly shadowed means that its shadowed interval overlaps with a shadowed interval from the shadow list.

You can use the same code to perform the calculation for all octants by mapping the octants onto each other, using affine transformations.

This approach has the benefit, that each square is only visited once. Another benefit is that it can calculate shadows of things smaller than a full square as well, even if the things are not centered on the square. Just the angles must be calculated correctly for the objects size and position.

Its drawback is that if many intervals need to be stored in the shadow list, the checks for 'fully shadowed', 'partly shadowed' and merging new intervals into the list get slow. In addition calculating the angles might be slow (but you can use a lookup table for this). Also, angles are usually stored as floating point numbers, which are usually bigger in memory and slower to compute than integer numbers.

If you want or need to use integers only you can use the x/y quotient instead of angles.

The implementation used in H-World can calculate visibility information of a area of 59x59 squares in less than 6 ms, often in less than 2 ms on a 400MHz AMD K6/2 processor. The time depends on the number of shadow intervals, but usually the intervals merge well, so that the list only contains a few intervals.

Was this article interesting to you? Did you find mistakes or want to make suggestions?
Feedback (good or bad) is always welcome!
You can reach me by e-mail: Send feedback.