How to Implement Recursive Shadow Casting FOV with Godot Script

This article is also available on GitHub.

Recursive shadow casting field of view algorithm is explained in detail in this RogueBasin article. It is available in libtcod and rot.js. In order to use it in my own project One More Level, I implement the algorithm with Godot script, see ShadowCastFOV.gd. In the latest version (0.3.0), there are five dungeons that use shadow casting fov: Balloon, Desert, Frog, Knight and Mirror. Below is a screenshot.

If you want to use ShadowCastFOV.gd in your own Godot project, first you need to set dungeon width and height in the script:

const DUNGEON_WIDTH: int = 21
const DUNGEON_HEIGHT: int = 15

Then load and initialize the script:

var _new_ShadowCastFOV := preload("res://library/ShadowCastFOV.gd").new()

The script has two public functions. Call set_field_of_view() to set internal data, then call is_in_sight() to check if a given position is in sight. Their signatures are as follows:

set_field_of_view(x: int, y: int, max_range: int,
        func_host: Object, block_ray_func: String, opt_arg: Array) -> void

is_in_sight(x: int, y: int) -> bool

The function set_field_of_view() requires a function (block_ray_func(x: int, y: int, opt_arg: Array)) to verify is a grid blocks line of sight, which is hosted in func_host. See FuncRef in Godot manual for more information. See PCActionTemplate.gd about how to use the fov script.

If you want to implement the algorithm in another language, here are some tips. According to the original RogueBasin article, the whole dungeon is rendered in four steps:

• Step 1: Select a center point and divide the dungeon into eight regions.
• Step 2: Select a region.
• Step 3: Render the region.
• Step 4: Render other regions in a similar way.

Step 1 is straightforward. Usually we select PC’s position as the center point and divide the map as required. However, which region shall we render first? Are there any easy to miss details in the rendering process? How to repeat the process in other regions?

  \ 5 | 6 /
   \  |  /
  4 \ | / 7
------@------>
  3 / | \ 0
   /  |  \
  / 2 | 1 \
      |
      v

Let’s start from Step 4. Suppose _set_octant() renders region 0, what to do next? In region 0, as x grows, we scan the region column by column. However in region 1, as y grows, we scan the region row by row. The scanning process is the same. The only difference lies in coordinates. More specifically, if the origin of coordinates is PC’s position, there is a relation between coordinates in region 0 and 1:

x_2 = y_1
y_2 = x_1

If the origin of coordinates is on the top left corner of the screen, the equations above can be rewritten as:

x_2 - pc_x = y_1 - pc_y
y_2 - pc_y = x_1 - pc_x

Therefore:

x_2 = (y_1 - pc_y) + pc_x
y_2 = (x_1 - pc_x) + pc_y

If we convert x_1 and y_1 to x_2 and y_2 somewhere in _set_octant(), the function can render both region 0 and 1. In fact, the same conversion applies to all regions. See _convert_coord() (below) for more information.

Next let’s consider Step 2. Which region to render first? Any region will suffice, but it would be better if both x and y are positive and the slope does not grow to infinity. If we define right and down as positive directions for x and y axis, both coordinates are positive in region 0 and 1. If we define the slope as (y_2 - y_1) / (x_2 - x_1), it grows to infinite in region 1. This leaves region 0 as our only candidate.

Every grid in the dungeon should have a Boolean value to tell whether it is in PC’s sight. Suppose _dungeon is a private variable that functions like a 2D array, we can implement is_in_sight() like this:

func is_in_sight(x: int, y: int) -> bool:
    return _dungeon[x][y]

In set_field_of_view(), first we need to reset every grid in _dungeon to false, then call _set_octant() for every region:

func set_field_of_view(...) -> void
    _reset_dungeon()

    # i = 0, 1, 2, ..., 7
    for i in range(0, 8):
        _set_octant(i, ...)

Finally, let’s focus on _set_octant() that renders a single region. Suppose we only need to scan region 0, therefore the function contains 2 loops: as x grows, scan every column decreasingly:

_set_octant(...) -> void
    for x in range(source_x + 1, max_x, 1):
        end_loop = true

        for y in range(max_y, min_y, -1):
            ...
            _set_octant(...)
            ...
            if ...:
                end_loop = false
            ...

        if end_loop:
            break

There are three things worth mentioning in the snippet. Firstly, the function _set_octant() is recursive. Secondly, the start point [source_x, source_y] is excluded from region 0. That’s why we range from source_x + 1 to max_x. If we range from source_x to max_x, when we call _set_octant() recursively, we need to input new_x + 1 rather than new_x, because a recursive scan (in region 0) should start one column further from the current point. Lastly, only one column is scanned by default. Continue scanning the next column if and only if (quote from RogueBasin):

Ok, once a scan has reached it’s last cell the scan is finished and a new scan is started one row further away if, and only if, the last cell was a non-blocking cell.

Obviously _set_octant() requires source_x, source_y and max_x as inputs. Since we need to calculate min_y and max_y from slopes, the function also needs two slopes. So we can refine the code outside y loop like this:

_set_octant(source_x: int, source_y: int, max_x: int,
        left_slope: float, right_slope: float, ...) -> void
    for x in range(source_x + 1, max_x, 1):
        max_y = ceil(right_slope * (x - source_x) + source_y) as int
        min_y = floor(left_slope * (x - source_x) + source_y) as int
        min_y -= 1
        end_loop = true

        for y in range(max_y, min_y, -1):
            ...

Note that the down direction is positive for y axis and we define slope as delta_y / delta_x. If a ray passes through a gird, the grid is insight. Therefore max_y is the largest possible integer and min_y is the smallest possible integer. However, in Godot script, range(left_value, right_value) includes left_value but excludes right_value. In order to include min_y in the y loop, we need to minus min_y by 1. This is a Godot specific issue.

We render a single column in the y loop. Below is the backbone of the loop.

for y in range(max_y, min_y, -1):
    # Part 1.
    if not _is_inside_dungeon(x, y):
        continue
    _dungeon[x][y] = true

    # Part 2.
    if _ray_is_blocked(x, y):
        ...
        _set_octant(...)
    # Part 3.
    else:
        ...
        if _last_grid_is_not_blocked(y):
            end_loop = false

if end_loop:
    break

Part 1 is self-evident. In part 2, _ray_is_blocked() is a function that decides if the current grid blocks ray. The function can be implemented in various ways. You can hard wire it into the fov script, pass the function as an argument to set_field_of_view() and then _set_octant(), pass an object that implements an interface, or in Godot script, pass a function reference. The detail does not matter. Let’s suppose that _ray_is_blocked() returns a Boolean value. Call _set_octant() recursively if the current grid blocks ray and the last scanned grid does not block ray. We use two private variables, is_blocked and sub_y, for the second condition.

for x in range(source_x + 1, max_x, 1):
    ...
    is_blocked = false
    for y in range(max_y, min_y, -1):
        ...
        if _ray_is_blocked(x, y):
            # Continue if this is not the first blocked grid.
            if is_blocked:
                continue
            is_blocked = true
            # Step back 1 grid. Continue if the grid is outside region 0.
            sub_y = y + 1
            if sub_y > max_y:
                continue
            # Calculate a new left slope.
            sub_left_slope = _get_slope(source_x, source_y, x, sub_y)
            # Start a recursive call.
            _set_octant(x,              # No change.
                    sub_y,              # Has changed.
                    max_x,              # No change.
                    sub_left_slope,     # Has changed.
                    right_slope,        # No change.
                    ...)

In part 3, we need to calculate a new right_slope and decide whether to scan the next column.

else:
    # Set a new right slope after leaving a continuous column of blocks.
    if is_blocked:
        is_blocked = false
        right_slope = _get_slope(source_x, source_y, x, y)
    # Continue scanning if the last grid in the column is not blocked.
    if y == min_y + 1:
        end_loop = false

We have talked about coordinate conversion above. But when to do it? Convert a pair of coordinates to region 0 from another region only when we check if a grid is inside dungeon, set _dungeon to true or verify whether a grid blocks ray.

for y in range(max_y, min_y, -1):
    convert_x = _convert_coord(which_octant, x, y, true)
    convert_y = _convert_coord(which_octant, x, y, false)

    if not _is_inside_dungeon(convert_x, convert_y):
        continue
    _dungeon[convert_x][convert_y] = true

    if _ray_is_blocked(convert_x, convert_y):
        ...

The function _convert_coord() converts x and y in region which_octant to a new x or y based on the last argument. The variable which_octant is an argument of _set_octant().