Does Part of Line Cut Through Square

Question

I am working on a 2D game that involves square creatures and projectiles.

Each projectile moves several creature-lengths per game tick, so I can't just check for any creatures at the projectile's location every tick- this skips any creatures in-between the projectile's starting and ending positions.

Each tick, I have the location projectile_x and projectile_y, delta_time and speed of the projectile, which result in the distance_moved. I also have the direction of the projectile in radians. This allows me to get the trajectory lines starting and ending coordinates, (projectile_start_x,projectile_start_y) and (projectile_end_x,projectile_end_y).

For each creature with center (creature_x,creature_y) and square width creature_size. How can I find out whether a projectile's trajectory has intersected a creature?

Edit: I don't mind approximating to assume that creatures are in fact circles.

Edit Edit: Actually, squares seem simpler from these answers.

Answer 1

Basically, each frame, we have a line segment from $(p_x,p_y)$ (where those denote projectile_x and projectile_y) in direction $(\cos(\theta),\sin(\theta))$ (where $\theta$ is short for direction. $\theta=0$ refers to the right, horizontally) with length $d$ (which is, you guessed it, distance_moved).

If we are to make this a line opposed to only a line segment, then the following equality would describe its path:

$$(y-p_y)\cos(\theta)=(x-p_x)\sin(\theta)\tag{$*$}$$

We can view creatures as circles instead of squares if we know the direction of the line; a line with direction $\theta$ intersects the circle with center $(c_x,c_y)$ and radius

$$r=\frac s2\cdot ((\sqrt2-1)|\sin(2\theta)|+1)$$

if and only if it intersects a square with side lengths $s$ and center $(c_x,c_y)$.

So first, we find the candidates. What circles intersect the line described at $(*)$? Well, it only intersects a circle if the distance from the line to the center of the circle is less than or equal to the radius. The distance from $(c_x,c_y)$ to $(y-p_y)\cos(\theta)=(x-p_x)\sin(\theta)$ is exactly

$$\left|(c_x-p_x)\sin(\theta)-(c_y-p_y)\cos(\theta)\right|$$

So if this is less than or equal to $\frac{s}{\cos(\theta)}$ (where $s$ is creature_size), then the creature is on the line describing the projectile, but not necessarily on the line segment.

This is the next step. Checking whether or not it reaches the square representing the creature is luckily not very hard. First, note that the end points of the segment are at $(p_x,p_y)$ and $(p_x+d\cos(\theta),p_y+d\sin(\theta))$. Now we need to check:

\begin{align} \min(p_x,p_x+d\cos(\theta))&<c_x+\tfrac s2\\ \max(p_x,p_x+d\cos(\theta))&>c_x-\tfrac s2 \end{align} and \begin{align} \min(p_y,p_y+d\sin(\theta))&<c_y+\tfrac s2\\ \max(p_y,p_y+d\sin(\theta))&>c_y-\tfrac s2 \end{align}

If those are all true, then the square overlaps the line segment at some point.

---

To summarize, first check $$\left|(c_x-p_x)\sin(\theta)-(c_y-p_y)\cos(\theta)\right|\leq\frac s2\cdot ((\sqrt2-1)|\sin(2\theta)|+1)\tag{1}$$ and then check, if the previous expression was true, \begin{align} \min(p_x,p_x+d\cos(\theta))&<c_x+\tfrac s2\\ \max(p_x,p_x+d\cos(\theta))&>c_x-\tfrac s2\tag{2.1} \end{align} and if those are true, \begin{align} \min(p_y,p_y+d\sin(\theta))&<c_y+\tfrac s2\\ \max(p_y,p_y+d\sin(\theta))&>c_y-\tfrac s2\tag{2.2} \end{align} and if those last ones are true too, then your box collides with the line.

You could do these three checks in any order you like, however, since the first seems less computationally heavy, I'd go with my suggested order. A different order would be more efficient if you expect many of the creatures to be in the line the projectile is moving but not necessarily in range of the projectile.

Answer 2

There's a hit if the segment on the line $L$ traversed by the projectile meets an edge of the square.

Find the equation of $L$ in parametric form: $tV + (1-t)W$, where $V$ and $W$ are the starting and ending positions of the projectile.

The equation for each edge of the square looks like $sA + (1-s)B$, where $A$ and $B$ are adjacent corners. Find out where that line meets $L$ (it will unless $L$ is horizontal). If for any edge both $s$ and $t$ are between $0$ and $1$ then it's a hit.

This is tedious analytic geometry but not hard to program.

Answer 3

Here's the fastest way that I can come up with from the top of my head:

Write direction vector of the projectile as $(d_x, d_y)$, then you'll get an orthogonal vector via $v := (-d_y, d_x)$. Now, all the points $P$ on the trajectory of your projectile have one thing in common, namely that their inner product with v is $(v,P) = (v,A) = (v,B)$ where $A,B$ are the starting and ending point of the projectile (just trying to abbreviate notation here)

This trajectory divides the plane into two half-planes, and the projectile does NOT hit the creature if the square lies entirely in one of those two half-planes. In that case, all points $p$ of the square would have to satisfy either $(v,p) < (v,A)$ or $(v,p) > (v,A)$ (depending on which half-plane they are in). Note that it is sufficient to check this condition on the four corners of your square!

So what you'd have to do is the following:

1) Compute the direction vector of the projectile

2) Determine an orthogonal vector

3) Compute the inner product with either $A$ or $B$

4) Compute the inner products with the four corners of your square

5) Order those 5 numbers and see whether the number you obtained in 3) is either the largest or the smallest among them: In that case the projectile does NOT hit the creature. In case it is neither the largest nor the smallest, you're one creature down.

Answer 4

Here’s another approach.

First note that the intervals $[m,M]$ and $[n,N]$ overlap if and only if $m\le N$ and $n\le M$.

Using this test, determine whether or not the $x$-range of the projectile, $[\min(\text{projectile_start_x}),\max(\text{projectile_end_x})]$, overlaps with the $x$-range of the square.

If it doesn’t, there’s no intersection. If it does, determine in the same way if the $y$-range of the segment overlaps with the $y$-range of the square.

If it doesn’t, there’s no intersection. If there are overlaps in both coordinates, determine for each of $x$ and $y$, “when” the line extending the projectile’s segment is within each of the coordinate ranges of the square.

To do this, parameterize the projectile as moving during a time interval $t=0$ to $t=1$ as $$\text{position}(t)=\\(\text{projectile_start_x}+t(\text{projectile_end_x}-\text{projectile_start_x}),\\\text{projectile_start_y}+t(\text{projectile_end_y}-\text{projectile_start_y}))$$ and solve the four simple equations for when its $x$-coordinate equals the square’s left and right $x$-coordinate and when its $y$-coordinate is equal to the square’s bottom and top $y$-coordinate. (Be careful not to divide by zero if the projectile is moving horizontally or vertically, in which case the time intervals are either empty or $(-\infty,\infty)$.)

Now you have two time intervals, one for when the line the projectile lies in is within the square’s $x$-range and one for when it’s in the $y$-range.

See if those time intervals overlap. If so, the segment intersects the square. Otherwise, it doesn’t.

You might be tempted to skip the preliminary checks, but first of all, they are easy and eliminate many projectile-creature possibilities. Second of all, the time intervals could overlap outside the range $[0,1]$ (if the projectile is aimed toward the square but stops short), so you still have something else to check if the time intervals overlap. You don’t have to make this last check if you did the initial check.