What is a good rule for blocking projectiles on a square grid?

Question

Suppose we have a square grid, and each tile may or may not be occupied by an object. Some of those objects can be a unit that can launch a projectile at another unit. However, that projectile should be blocked if a third unit is "in the way" of the projectile path.

What I want is a rule for whether a projectile path is "blocked" from one tile to another, based on possible intermediate tiles blocked by an object. The blocking rule should satisfy the following criteria:

1) It should be based only on the information about the relative position on the grid of the two tiles, and the occupation of tiles by objects. Details such as which object is occupying a tile should not matter. Imagine the same rules would apply with placing stones on a Go board

2) It should be as obvious to the player as possible what the projectile blocking rules are. Imagine they could move a ranged unit to a tile to get a shot, and that movement is irreversible. If they later find out that the shot they wanted to make is blocked, they essentially got screwed over by a game mechanic. I don't want people to lose a game because of opaque mechanics. It should be as obvious as possible to the player that the shot they want to make form a tile is blocked before moving to that tile.

3) The rule should be generally applicable, not just a heuristic for a non-general set of possible scenarios. Given any two integer coordinates, {X1, Y1} and {X2, Y2} we should automatically be able to name the coordinates of all tiles that block those two coordinates.

4) The rule should be invariant to 4-way rotation, translation, and reflection along either axis.

Some rules would be obvious. For example, if your shot is completely horizontal/vertical (rook movement) or completely diagonal (bishop movement) and something is directly in that path, it should be blocked.

But there are cases that are not completely obvious to me, and different rules have been followed in different games. For example, what if the projectile launcher and target are separated by a knight's path? Is an object blocking the projectile if it lies on one of the two tiles that sit between the launcher and target along the long axis of separation? I have seen that being a valid block in the game Hero Academy, though it's not obvious to me that it should be.

EDIT: I realize that point #2 can be addressed with a nice UI that can inform the player of whether a path is blocked before they commit to their move. However, even if the UI does that, I still want it to be obvious to the player, independent of the UI. (If the player has to play a few games to learn how it works, that's fine, as long as it's easy to learn.) This aligns with my general philosophy that one should maximize the proportion of cognitive effort that goes towards strategic decision making, and minimize the proportion of cognitive effort that goes towards figuring out game mechanics on the spot.

Answer 1

First, let's look at a few examples.

White tiles represent the tiles that must be empty for line of sight. The grey tiles are allowed to be full. The black line is your attempted projectile path. Notice the red edges. These are all the edges the projectile must cross to get to its target. If the projectile hits the very corner, we act as if it must cross all edges that meet at that corner. So, we simply need to test a collision between the path and all these edges.

To do this, we can use the slope. Starting and ending at the centers of the start and target tiles, a slope greater than 1 would mean we first cross to the tile above, so we determine if that tile is clear. If the slope is less than one, we first check the tile to the right. If we are firing down or left, we do the same thing, but check if the slope is negative.

It is a litter tricky for the next tile, though. So instead let's look at our line. If we say the start point is the origin, then our line is y = mx where m is the slope. When x = 0.5, it should cross over to the tile to the right. If we solve for y by multiplying by the slope, we can see how many tiles up or down we've traveled before crossing the right. In the first example, when x = 0.5, y = 0.5 * 2 = 1. Since it is in the 0.5-1.5 range, we can conclude that it must have crossed the top edge first. If it was even higher, like between 1.5 and 2.5, then we would need to count two tiles above instead of one. If it is exactly .5, 1.5, etc., then it is at a corner, and we include all the tiles like in the second example. We can repeat the process, testing x = 1.5 next, and so forth, until we reach the destination.

Answer 2

Just viewing the problem from a mathematical standpoint:

If \$(x_0,y_0)\$ and \$(x_1,y_1)\$ are your two points, let's define \$\Delta x=x_1-x_0\$ and \$\Delta y = y_1-y_0\$.

As you've pointed out, some special cases are trivial:

1. If \$\Delta x=0\$, it's a vertical column of tiles
2. If \$\Delta y=0\$, it's a horizontal row of tiles
3. If \$\Delta x=\Delta y\$, it's a diagonal (and possibly adjacent tiles)

Leaving these aside, you can assume w.l.o.g. that \$x_0<x_1\$ and that \$\Delta x > \Delta y\$, otherwise just switch the roles of \$x\$ and \$y\$ and reverse the \$(x,y)\$-coordinates of the output tuples when you're done.

Your question is answered by looking at where the line \$f(x)=\frac{\Delta y}{\Delta x}(x-x_0) + y_0\$ which connects the original two points intersects the vertical grid lines between your tiles.

The set of "blocking" tiles should contain all pairs of integer tuples \$(i,j), (i+1,j)\$ for \$x_0 \leq i < x_1\$ where \$ j-\frac{1}{2}\leq f(i+\frac{1}{2})\leq j+\frac{1}{2}\$, as illustrated in the lazy drawing below.

Whether you choose strict inequalities in the last expression or not determines what happens when the line exactly passes through a point where two grid lines cross. I'd recommend against using strict inequalities since it would allow a projectile to slip through the "gap" between two diagonally aligned blocks, such as shooting from (0,0) to (1,1) when there are walls on (0,1) and (1,0).

Needless to say, if you were to implement it exactly this way you'd end up counting a lot of tiles twice, so there's still a bit of work to be done in translating this idea into an efficient algorithm.