An Introduction to Cross Shaped FOV

This article is also available on GitHub.

Cross shaped field of view casts four rays in cardinal directions. All rays have a unified width, but the maximum range of each ray can be defined separately. It suits well if your dungeon is filled with narrow corridors and your field of view is asymmetric. I implement the algorithm with Godot script language (see CrossShapedFOV.gd) in One More Level. In the latest version (0.3.0), it is used in Railgun. Below is a screenshot.

If you want to use CrossShapedFOV.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_CrossShapedFOV := preload("res://library/CrossShapedFOV.gd").new()

The script has two public functions. Call set_rectangular_sight() 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(center_x: int, center_y: int,
        face_x: int, face_y: int, half_width: int,
        front_range: int, right_range: int,
        back_range: int, left_range: int,
        func_host: Object, is_obstacle_func: String,
        opt_arg: Array) -> void

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

In set_rectangular_sight(), center_x and center_y is the source position. [face_x, face_y] should be either [0, y] or [x, 0]. They represent the front direction. Other directions, right, back and left, are defined relatively. The width of a ray is half_width * 2 + 1. The function also requires a function (is_obstacle_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.

If your field of view is somewhat symmetric, you can use set_t_shaped_sight() or set_symmetric_sight() instead of set_rectangular_sight().

set_t_shaped_sight(center_x: int, center_y: int,
        face_x: int, face_y: int, half_width: int,
        front_range: int, side_range: int,
        func_host: Object, is_obstacle_func: String,
        opt_arg: Array) -> void

set_symmetric_sight(center_x: int, center_y: int,
        half_width: int, max_range: int,
        func_host: Object, is_obstacle_func: String,
        opt_arg: Array) -> void:

See RailgunPCAction.gd about how to use the fov script.

Next I will explain how does the algorithm work. In set_rectangular_sight(), we cast four rays in four directions. These rays stop when they encounter an obstacle or when they are out of range. Thus we can draw a rectangle that limits the field of view. We use four private variables to record the position of the rectangle: _max_x, _max_y, _min_x and _min_y.

          ^
          | left
          |
<- back - @ - front ->
          |
          | right
          v

In is_in_sight(), we check if a given position is inside the rectangle and is close enough to an axis.

func is_in_sight(x: int, y: int) -> bool:
    if (x < _min_x) or (x > _max_x) or (y < _min_y) or (y > _max_y):
        return false
    elif (abs(x - _center_x) > _half_width) \
            and (abs(y - _center_y) > _half_width):
        return false
    return true

Now let’s go back to implement set_rectangular_sight(). The core part is casting four rays in a loop and updating the position of the rectangule.

func set_rectangular_sight(...) -> void:
    for i in ...:
        end_point = _cast_ray(...)
        _update_min_max(end_point[0], end_point[1])

The function _cast_ray() returns the coordinates of the farthest grid a ray can reach. It requires at least three groups of arguments: the starting point, the maximum distance a ray can cover if not blocked, and a way to decided whether a grid blocks the ray. We can hard wire the verification logic into the fov script, pass a function as an argument to _cast_ray(), pass an object that implements an interface, or in Godot script, pass a function reference. The detail does not matter. Let’s suppose that _cast_ray() accpets a function _ray_is_blocked() that returns a Boolean value.

func _cast_ray(start_x: int, start_y: int, shift_x: int, shift_y: int,
        max_range: int, ...) -> Array:
    var x: int = start_x
    var y: int = start_y

    for _i in range(max_range):
        x += shift_x
        y += shift_y
        if not _is_inside_dungeon(x, y):
            x -= shift_x
            y -= shift_y
            break
        elif _ray_is_blocked(x, y):
            break
    return [x, y]

Note that _cast_ray() also requires shift_x and shift_y as inputs because we need to cast four rays in four directions and we’d prefer to let the caller decide the direction.

The function _update_min_max() resets private variables if necessary.

func _update_min_max(x: int, y: int) -> void:
    if x > _max_x:
        _max_x = x
    elif x < _min_x:
        _min_x = x

    if y > _max_y:
        _max_y = y
    elif y < _min_y:
        _min_y = y

In set_rectangular_sight(), we need to pass four sets of arguments to _cast_ray(). Suppose we have aleardy processed face_x and face_y so that one of them is 0 and the other is either 1 or -1. We define an array of arguments like this:

func set_rectangular_sight(center_x: int, center_y: int,
        face_x: int, face_y: int, half_width: int,
        front_range: int, right_range: int,
        back_range: int, left_range: int, ...) -> void:
    ...

    if face_x == 0:
        cast_ray_arg = [
            [face_x, face_y, front_range],
            [face_x, -face_y, back_range],
            [face_y, face_x, right_range],
            [-face_y, face_x, left_range],
        ]
    else:
        cast_ray_arg = [
            [face_x, face_y, front_range],
            [-face_x, face_y, back_range],
            [face_y, -face_x, right_range],
            [face_y, face_x, left_range],
        ]

    for i in cast_ray_arg:
        end_point = _cast_ray(center_x, center_y, i[0], i[1], i[2], ...)
        _update_min_max(end_point[0], end_point[1])

Thus we have implement cross shaped field of view.