How to implement D&D 4e's line of sight algorithm?

Question

D&D 4th Edition (the tabletop game) has combat on a 2D map with square tiles. A creature occupies an entire single tile.

The attacker has clear sight on the defender if lines can be drawn from one corner of the attacker's square to all four corners of the defender's square and none of these lines are blocked.

The rules are as follows:

To determine if a target has cover, choose a corner of your square and trace imaginary lines from that corner to every corner of the target's square. If one or two of those lines are blocked by an obstacle, the target has cover. (A line isn’t blocked if it runs along the edge of an obstacle’s or an enemy’s square.) If three or four of those lines are blocked but you have line of effect, the target has superior cover.

So, in the following situation:

• A can fully see B, but C has superior cover from A (the unblocked line is from topright corner of A to topright corner of C), and A cannot see D at all.
• B can fully see A, C and D.

How can I implement this?

Over the years, I have tried several solutions: some forms of Bresenham's line, testing for walls pixel by pixel, giving some tolerance around corners, and even dividing the map into line segments and comparing rays from the attacker to these line segments using a line-intersection formula. But everything either wasn't sufficiently rules-accurate or was too computationally expensive.

Can this line-of-sight algorithm be implemented efficiently (enough so that hundreds of checks may be performed for maps of 100x100 tiles per second) and accurately, and if so, how?

Answer 1

We can check if a square and a line segment intersects by dividing the square into 4 line segments, then using the following formula from here:

s = (1/d)  ((x00 - x10) y01 - (y00 - y10) x01)
t = (1/d) -(-(x00 - x10) y11 + (y00 - y10) x11)

(x00, y00) are the first segment's first point, (x01, y01) are the first segment's second point and similarly (x10, y10) and (x11, y11) are the second segment's first and second point respectively.

If both of these values are in the range [0, 1], then the line segments intersect.

First of all, you should extract the cover squares from the map, then when you need to check for visibility, then you take the 4 points of the square the current player is standing on, for each of them create a line segment with the four points of the square the enemy is standing on (that's 16 line segments), then try intersecting them with the edges of every cover square.

If you're wondering, that's 64 * of collision checks, which considering how simple the formula is, isn't much

Answer 2

TLDR: Walk the geometry of the grid by following the slope of the line. Provide the computer the instructions you'd follow tracing the line yourself with a ruler.

Below I will share an unoptimized C# implementation. The core challenge here is determining which grid cells the traced line will pass through between two corners. Some additional complication is added by the 4e rule about handling line of effect along edges, and so edge pairs are also returned. Those can be tested to see if the cells on both sides of the line are blocked to prevent line of effect from going perpendicularly through a wall.

The function calls itself with swapped parameters to reduce the number of cases. I assume GridCellsBetweenCorners is O(n) where n = the line's length, but maybe someone still in university can confirm.

    public static (List<Vector2I> coveredCells, List<Tuple<Vector2I, Vector2I>> edgePairs) GridCellsBetweenCorners(Vector2I origin, Vector2I target) {
        //origin and destination points are specified by indicating the coordinates of the grid cell that has that point as the top-left corner
        List<Vector2I> coveredCells = [];
        List<Tuple<Vector2I, Vector2I>> edgePairs = [];
        Vector2I diff = target - origin;
        Vector2I diffSign = diff.Sign();
        if(diffSign.X < 0) {
            return GridCellsBetweenCorners(target, origin);
        }
        if(origin == target) {
            //no covered cells
        } else if(diff.X == 0 || diff.Y == 0) {
            //parallel to the x or y axis
            //edges don't count as intersections, but they need to be checked to see if both sides of an edge are blocked
            if(diffSign.Y < 0) {
                return GridCellsBetweenCorners(target, origin);
            }
            Vector2I walk = diff.Sign();
            Vector2I edgeCheckOffset = diff.X == 0 ? Vector2I.Left : Vector2I.Up;
            int distance = Math.Max(diff.X, diff.Y);
            for(int i = 0; i < distance; i++) {
                Vector2I posEdge = origin + (walk * i);
                edgePairs.Add(Tuple.Create(posEdge, posEdge + edgeCheckOffset));
            }
        } else if(Math.Abs(diff.X) == Math.Abs(diff.Y)) {
            //slope of 1 or -1
            Vector2I walk = diffSign;
            Vector2I offset = diff.Y < 0 ? Vector2I.Up : Vector2I.Zero;
            offset += diff.X < 0 ? Vector2I.Left : Vector2I.Zero;
            int distance = Math.Abs(diff.X);
            for(int i = 0; i < distance; i++) {
                coveredCells.Add(origin + offset + (walk * i));
            }
        } else {
            int prime = Math.Abs(diff.X) > Math.Abs(diff.Y) ? 0 : 1; //axis index
            int aux = prime == 1 ? 0 : 1; //axis index
            int distance = Math.Abs(target[prime] - origin[prime]);
            bool isSlopePositive = diffSign.X == diffSign.Y;
            Vector2I walk = Vector2I.Zero;
            Vector2I offset = isSlopePositive ? Vector2I.Zero : Vector2I.Up;
            for(int i = 0; i < distance; i++) {
                coveredCells.Add(origin + walk + offset);
                if(Math.Abs((i + 1) * diff[aux] / diff[prime]) != Math.Abs(walk[aux])) {
                    walk[aux] += (isSlopePositive || prime == 1) ? 1 : -1;
                    if(i + 1 != distance && diff[prime] % diff[aux] != 0) {
                        coveredCells.Add(origin + walk + offset);
                    }
                }
                walk[prime] += (isSlopePositive || prime == 0) ? 1 : -1;
            }
        }
        return (coveredCells, edgePairs);
    }

Assuming you want to implement the 4e line of effect rules, you'll have to call it 16 times and remove the cells the units are standing in...

    public static (List<List<Vector2I>> cells, List<List<Tuple<Vector2I, Vector2I>>> edgePairs) TraceSightLines(Vector2I originCell, Vector2I targetCell) {
        List<List<Vector2I>> result = [];
        List<List<Tuple<Vector2I, Vector2I>>> result2 = [];
        Vector2I[] offsets = [Vector2I.Zero, Vector2I.Right, Vector2I.Down, Vector2I.One];
        for(int i = 0; i < offsets.Length; i++) {
            for(int j = 0; j < offsets.Length; j++) {
                (List<Vector2I> cells, List<Tuple<Vector2I, Vector2I>> edgePairs) = GridCellsBetweenCorners(originCell + offsets[i], targetCell + offsets[j]);
                cells.Remove(originCell);
                cells.Remove(targetCell);
                result.Add(cells);
                List<Tuple<Vector2I, Vector2I>> edgesPairsToKeep = [];
                foreach(Tuple<Vector2I, Vector2I> pair in edgePairs) {
                    if(pair.Item1 != originCell && pair.Item2 != originCell
                    && pair.Item1 != targetCell && pair.Item2 != targetCell) {
                        edgesPairsToKeep.Add(pair);
                    }
                }
                result2.Add(edgesPairsToKeep);
            }
        }
        return (result, result2);
    }

...then test against the grid data and select the most favorable vertex to trace from with regards to cover.

            var (lines, edgePairs) = TraceSightLines(_activeUnit.Cell, newCell);
            bool _isLineBlocked(List<Vector2I> line) {
                foreach(Vector2I cell in line) {
                    if(IsBlocked(cell)) {
                        return true;
                    }
                }
                return false;
            }
            bool _isEdgeBlocked(List<Tuple<Vector2I, Vector2I>> pairs) {
                foreach(var pair in pairs) {
                    if(IsBlocked(pair.Item1) && IsBlocked(pair.Item2)) {
                        return true;
                    }
                }
                return false;
            }
            Vector2 traceOrigin = CalcCornerMapPositions(_activeUnit.Cell)[0];
            int countMin = int.MaxValue;
            Color[] coverColors = new Color[4];
            for(int i = 0; i < lines.Count;) {
                bool tL = _isLineBlocked(lines[i]) || _isEdgeBlocked(edgePairs[i]); i++;
                bool tR = _isLineBlocked(lines[i]) || _isEdgeBlocked(edgePairs[i]); i++;
                bool bL = _isLineBlocked(lines[i]) || _isEdgeBlocked(edgePairs[i]); i++;
                bool bR = _isLineBlocked(lines[i]) || _isEdgeBlocked(edgePairs[i]); i++;
                int count = (tL ? 1 : 0) + (tR ? 1 : 0) + (bL ? 1 : 0) + (bR ? 1 : 0);
                if(count < countMin) {
                    countMin = count;
                    traceOrigin = CalcCornerMapPositions(_activeUnit.Cell)[(i - 4) / 4];
                    coverColors[0] = tL ? Colors.Red : Colors.Green;
                    coverColors[1] = tR ? Colors.Red : Colors.Green;
                    coverColors[2] = bL ? Colors.Red : Colors.Green;
                    coverColors[3] = bR ? Colors.Red : Colors.Green;
                }
            }
            _unitPath.PaintPath([], traceOrigin, CalcCornerMapPositions(newCell), coverColors);