2
\$\begingroup\$

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:

Map of a D&D 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?

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ This is something I tried previously. The main problem is that this is inefficient. I want a map of 100x100 with possibly half of that being obstacles, which would give me 20000 edges to check per line. \$\endgroup\$ – user41258 Oct 22 '17 at 18:17
  • \$\begingroup\$ @user41258 In its optimized form it doesn't even take a single millisecond to go through all 1280000 collision tests. If one of them returns a collision, then you can even stop halfway through. If you really want to speed it up, then only check against the squares, that are inside the line's bounding box \$\endgroup\$ – Bálint Oct 22 '17 at 18:26
  • \$\begingroup\$ First start with a rasterization check using bresenham's. That's super fast and will give you the cells you need to check. Then you map the cells to the edges to test against. You don't need to compute it every time, right? Only when a player makes an attack. \$\endgroup\$ – mklingen Oct 27 '17 at 17:22
  • \$\begingroup\$ @mklingen Thank you. I'll try that. I need to compute it not just when a player makes an attack but also to see what enemies the player can attack, and worse, during the AI turn, where should the AI move so that the AI unit is the most well-positioned (which would mean testing many tiles as possible source points). \$\endgroup\$ – user41258 Nov 4 '17 at 3:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.