Algorithm to construct a parabola that hits a given target and avoids given boundaries

Question

I'm working on a video game and I'm struggling with the math behind one of the enemies. The enemy is a grenade launcher mounted on a vertical rail, which can slide up and down, and lob a grenade at any angle with any amount of force. The grenade's path will be a parabola which must hit the player, but there are line segment boundaries in the way represented by their two endpoints which the parabola must avoid.

Here is a drawing:

What I'd like to do is calculate the equation for the parabola of the grenade which hits a target and misses all of the boundaries, from which I can figure out the position, angle, and force for the launcher to use. The parabola must be subject to these three constraints:

1. The parabola must pass through the target point $(x_T, y_T)$
2. The parabola must pass through the line segment $\overline{RS}$
3. For each boundary $\overline{EF}$, if the parabola passes through the segment, it must not happen between the line $\overline{RS}$ and the target point.

Depending on where the target is, there may be no solution, in which case I'd like it to return that information. If there is any solution there will be multiple; I would only need one.

What I've tried so far:

We can represent the parabola as $y-y_T=A(x-x_T)^2+B(x-x_T)$, which takes care of the first constraint, and means we need to find values for $A$ and $B$ that satisfy the other two constraints (we know $A$ must be negative because of the direction of gravity). Then for each boundary $\overline{EF}$ on the map, with endpoints $(x_E,y_E)$ and $(x_F,y_F)$, we can represent the boundary line as $(y_E-y_F)x+(x_F-x_E)y+(x_E y_F-x_F y_E)=0$. From that I can find the points of intersection between the line and the parabola, and make sure that for every boundary, the x-values of the points are either not between $x_E$ and $x_F$, or they are not between $x_S$ and $x_T$. This quickly becomes a nasty quadratic equation, which then creates a system of linear inequalities that I don't know how to solve. Can anyone think of a better way to approach the problem?

Answer 1

Consider an endpoint $(x_E,y_E)$ of an obstacle line segment. I'm going to assume for simplicity that if the projectile goes exactly through $(x_E,y_E)$, this is a legal trajectory, i.e., it's OK for a projectile to "just graze" the obstacle. (If that's not OK, it is easy to adjust the solution below to just miss the corner by a tiny amount $\epsilon$, or it is easy to adjust the size of each obstacle by $\epsilon$ in each direction.)

Let's define a "grazing constraint" as one of the following possibilities:

• If the point $E$ is a vertex of an obstacle (i.e., an endpoint of an obstacle line segment) or is $R$ or $S$, then "The parabola must go through $E$" is a grazing constraint.

• If $EF$ is an obstacle line segment, then "The parabola intersects $EF$ and is tangent to it" is a grazing constraint.

In this way, given $n$ obstacle line segments, we obtain $2n+2$ possible grazing constraints.

Now I make two claims:

Claim 1: Any two grazing constraints uniquely determine the parabola.

Proof: If both grazing constraints are of the "must go through E" type, then together with the target $T$, we have three points, and any three points uniquely define a parabola, i.e., given three points, there is a unique parabola that goes through those three points. A similar argument can be made if one or both of the grazing constraints are of the "tangent" type.

Claim 2: If there is any solution to your problem, there is a solution that satisfies two of the possible grazing constraints listed above.

(I don't have a proof for this claim.)

This immediately suggests a simple algorithm: enumerate over all pairs of grazing constraints, find the unique parabola that satisfies those two grazing constraints and goes through the target $T$, and check whether this parabola avoids all obstacles and intersects the starting line segment RS. You can check whether it avoids all obstacles by iterating over all obstacle line segments, and for each, finding the intersection using the method you described. If there is a valid solution to your problem, this method will find it.

The running time of this method will be something like $O(n^3)$, where $n$ is the number of obstacle line segments. I don't know if there is a more efficient method. There might well be.