Roguelike line of sight calculation

Calculating line of sight between two points is a fundamental building block for classic tile based roguelike games. It can be used to check if an NPC or player can see an an item, player, monster etc. It can also be used for for field of view and AI code.

The following is a line of sight engine that is detached from any specific tile map, the function used to detect if a given square blocks line of sight is supplied by the caller. This allows the code to be used no matter the complexity of the data structures your engine makes use of. It is written in C# but should be easy to port to any other language.

Line of sight in most roguelikes is a compromise, there are always some artifacts and strange behavior. I have been through a few iterations of this sort of logic over the years and this is my current favorite technique. For this I Initially looked at the Bresenham's line algorithm but I did not like the way that it stepped, it could result in being able to see through gaps that should block line of sight. It is also based around real numbers which I did not want to use given the grid based nature of roguelike maps. This is how the Bresenham's line algorithm steps.

This is based on that but with a modified walk and int based coordinates. The extra squares this pulls in are highlighted in green below.You can see the line just passes through the squares, which is why I wanted to pull them in.

I believe this results in a better projection in practice, the FOV projection also feels more logical but I will cover how FOV projection builds on top of this code in another piece.

The CastRay() function simply builds a list of coordinates between the start and end points, a ray cast projection. It can optionally including the start and end points in the projection. The list produced is lazy so each coordinate is only calculated as it is consumed, this is a nice optimization for a couple of reasons:

• No need to create storage for the list of coordinates.
• If the line of sight is blocked early on then you only calculate the coordinates until the line of sight is blocked, no more.

So lets jump right in with the CastRay() function:

public static IEnumerable<Vector> CastRay(
    this Vector start, Vector end, 
    bool includeStart, bool includeEnd)
{
    var xIncrement = (end.X > start.X) ? 1 : -1;
    var yIncrement = (end.Y > start.Y) ? 1 : -1;

    var delta = (start - end).Abs();
    var error = delta.X - delta.Y;
    var errorCorrect = delta * 2;

    var current = start;
    while (true)
    {
        if ((current == start && includeStart) ||
            (current == end && includeEnd) ||
            (current != start && current != end))
        {
            yield return current;
        }

        if (current == end)
        {
            yield break;
        }

        if (error > 0)
        {
            current = Vector.Create(current.X + xIncrement, current.Y);
            error -= errorCorrect.Y;
        }
        else if (error < 0)
        {
            current = Vector.Create(current.X, current.Y + yIncrement);
            error += errorCorrect.X;
        }
        else
        {
            current = Vector.Create(
                current.X + xIncrement,
                current.Y + yIncrement);
        }
    }
}

Simple enough, just walks between the two points spitting out the list of vectors for the ray.

To check if you can see a given square from another we simply walk the list checking that none of them block the line of sight. Job done :)

public static bool CanSee(
    this Vector location, Vector target, 
    Func<Vector, bool> blocksLineOfSight)
    => !CastRay(location, target, false, true).Any(blocksLineOfSight);

The blocksLineOfSight function can be as simple or complex as you like. Here is a simple example:

// Sample blocksLineOfSight
Func<Vector, bool> blocksLineOfSight = 
    vector => myGrid[vector.X, vector.Y].IsWall;

Nice simple code that only does the minimum work required required to get the result :)

The only thing left is the Vector object, this is a simple immutable struct with some helpers and operator overloads. It is geared around building roguelike engines.

public struct Vector : IEquatable<Vector>
{
    private Vector(int x, int y)
    {
        X = x;
        Y = y;
    }

    public static Vector Create(int x, int y) => new Vector(x, y);

    public int X {get;}
    public int Y {get;}

    public Vector Abs() => new Vector(Math.Abs(X), Math.Abs(Y));

    public double DistanceFrom(Vector target)
    {
        var diffX = Math.Abs(X - target.X);
        var diffY = Math.Abs(Y - target.Y);

        return Math.Sqrt((diffX * diffX) + (diffY * diffY));
    }

    public override bool Equals(object obj)
        => obj is Vector && Equals((Vector)obj);

    public bool Equals(Vector other)
        => X == other.Y && X == other.Y;

    public static bool operator ==(Vector vector1, Vector vector2)
        => vector1.Equals(vector2);

    public static bool operator !=(Vector vector1, Vector vector2)
        => !vector1.Equals(vector2);

    public static bool operator >(Vector vector1, Vector vector2)
        => vector1.X > vector2.X && vector1.Y > vector2.Y;

    public static bool operator <(Vector vector1, Vector vector2)
        => vector1.X < vector2.X && vector1.Y < vector2.Y;

    public static bool operator >=(Vector vector1, Vector vector2)
        => vector1.X >= vector2.X && vector1.Y >= vector2.Y;

    public static bool operator <=(Vector vector1, Vector vector2)
        => vector1.X <= vector2.X && vector1.Y <= vector2.Y;

    public static Vector operator +(Vector vector1, Vector vector2)
        => new Vector(vector1.X + vector2.X, vector1.Y + vector2.Y);

    public static Vector operator -(Vector vector1, Vector vector2)
        => new Vector(vector1.X - vector2.X, vector1.Y - vector2.Y);

    public static Vector operator *(Vector vector, int scale)
        => new Vector(vector.X * scale, vector.Y * scale);

    public override int GetHashCode()
    {
        unchecked
        {
            var hash = X.GetHashCode();
            hash = (hash * 397) ^ Y.GetHashCode();
            return hash;
        }
    }
}

Would you like me to cover FOV projection and A* pathfinding also?

Happy coding

Woz