Line of sight

I have been fighting with line of sight over the past couple of days. I picked up my old algorithm and reworked it but it proved too heavy an inefficient for my needs. It attempts to calculate how much of the view was blocked by walls and give a % of the target square that was visible. While it gives a good approximation it always carried some strange artefacts that gave strange FOV results when rendered.

So I went back to basics. I wanted an algorithm that would be efficient. accurate and work on integers only for speed. I first considered the Bresenham’s line algorithm but this has issues in how it steps along the line, shown below in the first image. As you can see it actually misses a few squares along the projection, the ones highlighted in the second image in green.

The Bresenham algorithm also uses real numbers which means using float, double or decimals in C#, all of which have issues. Float and doubles are limited precision so you end up requiring tolerance checking when you want to compare values and decimals are just too costly in time.

I found an algorithm that would walk the line matching the second image all in integers but this was flawed when projecting the line diagonally, say (0, 0) -> (4, 4) in that it would step strangely and give an asymmetric line of sight depending on if you were tracing (0, 0) -> (4, 4) or (4, 4) -> (0, 0). This was quickly fixed up such that a trace of (0, 0) -> (4, 4) would yield (0, 0) (1, 1) (2, 2) (3, 3) (4, 4). This leaves the dilemma, does (0, 1) block line of sight or not as the line really touches the corner but does not enter the square, I decided not to include off the line in these situations.

The result is the following, a function that produces an enumerable list of the squares you must check between two points. It is a lazy generator so will only produce the trace while you consume it.

public static IEnumerable CastRay(
    this Vector start, Vector end, bool includeStart, bool includeEnd)
{
    var delta = (start - end).Abs();

    var current = start;

    var xIncrement = (end.X > start.X) ? 1 : -1;
    var yIncrement = (end.Y > start.Y) ? 1 : -1;

    var error = delta.X - delta.Y;
    var errorCorrect = delta * 2;

    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);
        }
    }
}

This is the building block that all my line of sight code is based on from determining if actor 1 can see actor 2 through to building a field of view projection for the player so the render engine knows what is visible to the player. It would have been nice to remove the need for the loop but limitation in tail recursion in C# means that a recursive solution is not really viable.

Determining if a target is visible to the player become trivial as shown below.

public static bool CanSee(
    this Vector location, Vector target, 
    Func<Vector, bool> blocksLineOfSight)
{
    return CastRay(location, target, false, false)
        .All(x => !blocksLineOfSight(x));
}

All we need to do is walk the line and ensure that none of the squares block the line of sight. The Func<Vector, bool> is used to test if a square blocks the line of sight making the code map agnostic so it is easy to use in any 2D grid based world no matter how it is stored.

Calculation of the map area visible to the player is also based off the same ray casting building block. It simply calculates all the locations around the edge of the area you want to test, cast a ray to each and then walks the ray until a blocking square is located. While this is not quite as efficient as techniques like shadow casting it provides a far better representation with no strange artefacts.

The final code is all available Here.