Project Delve Part 5: Line of Sight

In Descent and many other games, units often must have what’s known as “line of sight” to their targets when performing various actions such as attacking, buffing an ally, teleporting, and more. Sometimes games differentiate between “line of sight” and “line of targeting,” the difference being between what a unit can see versus what a unit can target. However, for our game these are going to be the same for simplicity’s sake.

At the end of this post we’ll have a functional line-of-sight calculator, as well as a visual representation of what a unit can see and what it cannot.

---

The Script

We’ll start by adding a new Node2D to the Dungeon scene called “LineOfSight” and create a new script to attach to it. I named it line_of_sight.gd (super original, right?). Our script is going to have only a single public method: can_see(). This follows the single-responsibility principle, which states that functions, modules, and classes (or in our case scripts) should be responsible for only a single part of the larger program. I’m not always the best at following all of the principles I learned in school in every piece of code I write, but the goal is to always be striving to improve.

The basic idea of the function is this: take in two points and try to draw an (invisible) uninterrupted line between both of them (also known as a raycast). If the line is not blocked by anything we define to be a vision-blocking item, the target point is considered to be in the line of sight of the origin. Let’s start by defining the function signature.

func can_see(world_point_origin: Vector2, world_point_target: Vector2):
    pass

The simplest way to do the check is to use Godot’s raycaster.

get_world_2d().direct_space_state.intersect_ray(pointA, pointB)

The intersect_ray() function returns a dictionary object containing the information of the first intersection the ray makes from pointA to pointB. If there’s no obstruction, the dictionary will be empty. This is the state we’ll want to check for to make sure there’s line of sight from pointA to pointB.

Our simple function should look like this now.

func can_see(world_point_origin: Vector2, world_point_target: Vector2):
    var result = get_world_2d().direct_space_state.intersect_ray(world_point_origin, world_point_target)
    return result.empty()

The only caveat with using a raycaster is that it interacts with the physics system, which our game does not use. In order for the ray to collide with something, that “something” needs to have a collider attached, so we’ll need to set up colliders on our tileset. Those instructions can be found on the Godot docs.

Once you’ve set that up, select the Obstacles node in the Dungeon scene and enable the “Show collision” property in the inspector. You should see something like this if you’ve set it all up properly.

Now if we write some quick code in the dungeon.gd script we can check that our can_see() function is working like it should. If the two points are within line of sight of each other, the line color will be green. If not, it will be red.

---

Refining The Function

So now that we have a basic function to calculate line of sight, let’s look at the rules for how Descent determines line of sight.

In order for a figure to have line of sight to a space, a player must be able to trace an uninterrupted, straight line from any corner of that figure’s space to any corner of the target space.

Rulebook, pg. 12, “Line of Sight”

This approach to line of sight is known as the corner-to-corner method. The other most commonly used method (when dealing with a grid system) is the center-to-center approach. I like the corner-to-corner method because it allows for a much larger field of vision than center-to-center.

With this in mind, let’s update the function. We now want to do the same raycast from each of the origin point’s corners to each of the target point’s corners. If any of the raycasts are successful (meaning they didn’t collide with anything) then we can exit the function early without needing to do any more checks.

First of all, we need to ensure that the world point we pass to the can_see() function is the top-left corner of the tile that was clicked on. This is fairly simple since the origin point of our tiles are set to the top left, so we just need to get that point and then add Vector2.RIGHT * tile_size, Vector2.DOWN * tile_size, and Vector2.ONE * tile_size to it and we’ll have the four corners of the tile.

Let’s start by getting the position of the top left corner of the tile in world coordinates. Because the LineOfSight node is on the Dungeon, I think it makes sense for the dungeon.gd script to have a method that exposes the can_see() function, just so we don’t have to rely on the structure of the Dungeon scene tree to get the line_of_sight.gd script.

# dungeon.gd

func has_line_of_sight_to(from_world_point: Vector2, to_world_point: Vector2):
    # First we need the map coordinates for the given world coordinates.
    var origin_map_point = floors.world_to_map(from_world_point)
    var target_map_point = floors.world_to_map(to_world_point)

    # Then we need to convert those map coordinates back to
    # world coordinates. This will give us the top-left corner
    # of the tiles in world coordinates.
    var origin_world_point = floors.map_to_world(origin_map_point)
    var target_world_point = floors.map_to_world(target_map_point)

    # Then we just return the result of the can_see() function
    return $LineOfSight.can_see(origin_world_point, target_world_point)

Now let’s fix the can_see() function to check each corner of the origin point and target point.

# line_of_sight.gd

func can_see(world_point_origin: Vector2, world_point_target: Vector2):
    for from_world_point in _get_tile_corners(world_point_origin):
        for to_world_point in _get_tile_corners(world_point_target):
            if from_world_point == to_world_point or _has_LoS(from_world_point, to_world_point):
                return true

    return false

func _has_LoS(from_world_point: Vector2, to_world_point: Vector2):
    var result = get_world_2d().direct_space_state.intersect_ray(from_world_point, to_world_point)
    return result.empty()

func _get_tile_corners(point):
    return PoolVector2Array(
        [
            point,                              # top left
            point + Vector2.RIGHT * _tile_size, # top right
            point + Vector2.DOWN * _tile_size,  # bottom left
            point + Vector2.ONE * _tile_size    # bottom right
        ]
    )

The last variable we need is the tile_size, which the tilemap can give us in the dungeon.gd script. So when I said we’d only be surfacing a single function in the line_of_sight.gd script… I lied. Oops! But because this function will supplement the can_see() function I think it still follows the single-responsibility principle, so we’re in the clear.

# line_of_sight.gd

var _tile_size: Vector2

# Make sure to call this function from the dungeon.gd
# script at some point before calling can_see()
func set_tile_size(size: Vector2):
    _tile_size = size

Here’s a visual representation of how the algorithm behaves now.

---

What’s Left?

So it seems like we’re pretty much done, right? Well, almost. Our function currently only considers the tilemap obstacles for blocking line of sight (because that’s the only thing we’ve set up colliders for so far). But in the game, there are more things that can block line of sight than a static obstacle — units, for instance. Units of different types (meaning hero or monster) block line of sight for the opposite type, so we still need to account for that in our calculations.

As I said at the start of the post, I’d also like to have a visual indicator of what a unit can or cannot see. I originally thought it’d be cool to have all the tiles that are within line of sight of a unit highlighted, but running this function for every possible combination of tiles on the grid could get expensive, especially when you consider that the grid will most likely be much larger than our little demo dungeon here. I think instead I’ll settle for calculating line of sight only when needed, and only on hovered tiles (kind of like what’s happening when displaying the movement of a unit).

And of course lastly there’s bound to be bugs or inconsistencies that will come to light with further use. I actually discovered one bug while recording the above gif! It seems like when the line of sight would pass on the diagonal edge of an obstacle tile (but not through it) it counts it as being blocked. This is a case that’s specifically called out in the rulebook as being allowed, and I think it should be as well, so I’ll need to figure out the best way to handle that use case.

The code for this post can be found here.