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