Thin wall field of view

from Red Blob Games
14 Jul 2021

For my roguelike project this year I'm implementing "thin walls". The walls will be along edges instead of occupying a full tile. I had to build a new map generator to support this style of wall, and I also had to build a new field of view algorithm. I also have page about visibility with polygon obstacles.

I want to calculate which tiles are visible, with the walls blocking your vision:

I'm calculating this for one 90° sector at a time, as it simplifies the logic.

 1  Range expansion#

The main idea here is that the range will expand as we move away from the player:

Distance:

This comes from "similar triangles" in geometry class. Any subrange will expand the same way:

Distance:

That means we can start with the full range, then reduce it every time we see a wall:

Distance:

 2  Range subtraction#

One of the main ideas I wanted to pursue was maintaining an visible set of ranges, \((a_{1}, b_{1}), (a_{2}, b_{2}), …\), where \(a_{1} ≤ x ≤ b_{1}\) OR \(a_{2} ≤ x ≤ b_{2}\) OR …. These would be the horizontal green lines in the above diagrams.

On each horizontal edge, I subtract the set of walls \((p_{1}, q_{1}), …\) from the visible set.

Then to move to the next horizontal row down, I need to widen the visible set by multiplying each value by \((y+1) / y\). For example in the above diagram, the visible range is \(-0.5 ≤ x ≤ +0.5\) at \(y = 0.5\). Then moving up a row, it expands to \(-1.5 ≤ x ≤ +1.5\) at \(y = 1.5\).

What is the algorithm for range difference?

for (let shaded in wallSet) {
    visible = visible.flatMap(lit => subtract(lit, shaded));
}

function subtract(A, B) {
    return [
        {left: A.left, right: Math.min(A.right, B.left)},
        {left: Math.max(A.left, B.right), right: A.right}
    ].filter(range => range.left < range.right);
}

Test cases and visualizations for a single segment subtracted from a single segment:

Casea–b minus c–d
{{rule[0]}}{{format([rule[1]])}} \ {{format([rule[2]])}} = {{format(subtract(rule[1], rule[2]))}}

Also see https://www.ics.uci.edu/~alspaugh/cls/shr/allen.html[1]

 3  Horizontal walls#

TODO: this should be fairly simple, as I already have that diagram above, but I just haven't coded up the algorithm yet

As we walk down the rows, subtract out the range of the walls from the current visible range:

range-subtraction.png

 4  Vertical walls#

TODO: this is trickier

For the output, we need to evaluate the middle of each row. A vertical wall casts a shadow like this:

vertical-wall.png

So we need to know if the shadow triggers before or after the middle of the tile. I haven't worked out the details yet.

 5  Symmetry#

TODO: Like the albertford tutorial, I will make 4 copies of this using rotation to calculate the visibility in each direction

four-rotations.png

First take a coordinate and subtract (player.x, player.y). Then rotate (dx, dy) one of four ways: (dx, dy), (dy, -dx), (-dx, -dy), (-dy, dx). Then add back (player.x, player.y). Doing this for thin walls is slightly trickier but not hard.

 6  More#

Note that my algorithm is not recursive but seems to behave similarly to the recursive shadowcasting approaches.

Email me , or tweet @redblobgames, or comment: