If your AI has structured knowledge of the obstacles in the way (eg. it knows there is a wall in-between with a hole at vertical position holeY), then an analytic solution may be possible (ie. you drop your source, target, and gap coordinates into a function and get your launch velocity back out).
I'm going to assume that you need to solve a more general case though, where there could be arbitrary geometry in the way. As Arthur Wulf White has noted above, in this case your best bet is to search through a family of potential parabolic trajectories, testing each one for collisions with geometry, until you find one that works.
So, how do you describe this family of parabolas?
I wouldn't recommend parametrizing the family on the vertical velocity component. For each possible input, you'd have two possible trajectories (one that peaks before reaching the target, and hits the target before peaking). That means solving a quadratic every iteration of your search. For binary search we'd prefer a 1-to-1 mapping with simpler calculations each iteration, even if it means a little more work for setup.
When I've tackled this problem in past games, I've found it convenient to use the duration of the projectile's flight - call it T.
It may seem an odd choice, but for every choice of T there is a unique parabolic trajectory joining the source and target, and the math (though plenty ugly during set-up!) is neater per-iteration than using velocity directly.
It's also easy to map conceptually: T = 0 represents the infinite-velocity straight line ray from source to target. Greater values of T represent increasingly tall (and indirect) arcs.
So, defining our knowns & unknownns:
Unknown
T = the time of impact on our target, measured in seconds after launch
launchVelocity = the initial velocity of the projectile (vector)
Known
launchPosition = the initial position of the projectile (vector)
targetPosition = the position of the target at the time of firing (vector)
deltaP = targetPosition - launchPosition = the net travel of the projectile (vector)
acceleration = the net acceleration (due to gravity, wind, etc) (vector)
hMax = the ceiling height, we want to keep our projectile lower than this
deltaH = hMax - launchPosition.y = the headroom we have above our firing spot
Next we'll want to establish the range of our parameter T to search through:
Your minimum T is the shortest/most direct flight possible:
float b1 = dot(deltaP, acceleration) + vMax*vMax;
float discriminant = b1*b1 - dot(a, a) * dot(deltaP, deltaP);
float T_min = sqrt((b1 - sqrt(discriminant)) * 2 / dot(acceleration, acceleration));
If discriminant < 0, that means the target is out of range and you can skip out early: no trajectory within our allowable speed can reach it.
Your maximum T is the least direct flight possible, shooting way up at maximum speed, so that the projectile eventually falls onto the target
// Limit due to launch power
float T_max = sqrt((b1 + sqrt(discriminant)) * 2 / dot(acceleration, acceleration));
But we might hit the ceiling first, so we have to account for the latest impact time that keeps us under that obstacle:
// Limit due to obstacles above.
float b2 = g * (2 * yMax - deltaY);
float T_ceiling = sqrt((
(deltaP.y - 2.0f * deltaH)
+ 2.0f * sqrt(deltaH * (deltaH - deltaP.y))
) * 2.0f / acceleration.y);
T_max = min(T_max, T_ceiling); // Take the earlier / most limiting case.
One more T value that I've found useful is the lowest-energy trajectory (the one with the smallest initial velocity) - it has:
float T_lowEnergy = sqrt(sqrt(4.0 f * dot(deltaP, deltaP) / dot(acceleration, acceleration)));
This one's a good baseline for AI jumping. :)
Now in each iteration of your search, you'll pick a T value and test the resulting parabola. This step is much neater. Calculate your launch velocity from T using:
launchVelocity = deltaP/T - a * T/2.0f;
This works in any number of dimensions. In 2D, with a = (0, -gravity) it's equivalent to:
launchVelocity.x = (p_Target.x - pStart.x)/T - 0;
launchVelocity.y = (p_Target.y - pTarget.y)/T + gravity * T/2.0f;
For each trajectory in this range, you can test a set of line segments along the line...
$$\vec p(t) = \vec p_0 + \vec v_0 \cdot t + \frac {\vec a} 2 t^2$$
Vector position(float t) {
return startPosition + launchVelocity * t + a * t*t/2.0f;
}
...to see if it collides with your terrain.
Here's a gif of the different trajectories we can form this way, as the target moves, bracketing the range of possible solutions:
T_min = red, T_lowEnergy = yellow, T_max = green, ceiling = blue
If your terrain always consists of low obstacles and open sky, then as Arthur notes above you can use binary search on T between T_min and T_max until you find a viable (non-colliding) trajectory, or you hit an iteration limit and give up.
If you can have floating obstacles or a solid ceiling with stalactites, then you may do better to do a linear search - say starting at T_lowEnergy and expanding above & below in small steps until you hit T_max and T_min, respectively.
I hope that's useful, and that I haven't botched the math anywhere! :)
Here's a detailed derivation of these formulas:
First, we take our parametric equation for motion under constant acceleration, substitute \$t = T\$ so that our position is the target position \$\vec p_T\$, and rearrange to isolate our initial velocity \$\vec v_0\$:
$$ \begin{align}
\vec p(t) &= \vec p_0 + \vec v_0 \cdot t + \frac {\vec a} 2 \cdot t^2 \\
\vec p_T = \vec p(T) &= \vec p_0 + \vec v_0 \cdot T + \frac {\vec a} 2 \cdot T^2 \\
\vec v_0 &= \frac 1 T \left( \vec p_T - \vec p_0 - \frac {\vec a} 2 \cdot T^2 \right) \\
\vec v_0 &= \left( \frac{\vec {\Delta p}} T - \frac {\vec a} 2 \cdot T \right)
\end{align}$$
Next we apply our constraint: our initial speed \$ \begin{Vmatrix} \vec v_0 \end{Vmatrix}\$ mustn't exceed our max speed \$v_{max}\$. At the limiting cases, the two are exactly equal, so we'll start with that equality then substitute the expression above...
$$\begin{align}
\begin{Vmatrix}\vec v_0\end{Vmatrix} &= v_{max} \\
\vec v_0 \cdot \vec v_0 &= v_{max}^2 \\
\frac 1 {T^2} \left( \vec{\Delta p} - \frac {\vec a} 2 T^2 \right) \cdot \left( \vec{\Delta p} - \frac {\vec a} 2 T^2 \right) &= v_{max}^2 \\
\begin{Vmatrix}\vec {\Delta p}\end{Vmatrix}^2 - \left(\vec{\Delta p} \cdot \vec a \right) T^2 + \frac {\begin{Vmatrix} \vec a \end{Vmatrix}^2} 4 T^4 &= v_{max}^2 T^2
\end{align}$$
This may look hairy, what with the fourth powers and all, but if we substitute \$ u = T^2 \$ and rearrange, we get a familiar-looking quadratic we can solve by the quadratic formula. :)
$$ \begin{array}{c|l}
\frac {\begin{Vmatrix} \vec a \end{Vmatrix}^2} 4 u^2 + \left(-\vec{\Delta p} \cdot \vec a - v_{max}^2\right) u + \begin{Vmatrix}\vec {\Delta p}\end{Vmatrix}^2 = 0
&
A = \frac {\begin{Vmatrix} \vec a \end{Vmatrix}^2} 4 \\
\space &
B = - \left(\vec{\Delta p} \cdot \vec a + v_{max}^2\right) \\
\large {u = \frac {-B \pm \sqrt{B^2 - 4AC} } {2 A}}
&
C = \begin{Vmatrix}\vec {\Delta p}\end{Vmatrix}^2
\end{array}
$$
And since \$T\$ is non-negative by definition, we can express it as:
$$T = \sqrt{\frac 2 {\begin{Vmatrix}a\end{Vmatrix}^2} \left( \left( \vec{\Delta p} \cdot \vec a + v_{max}^2 \right) \pm \sqrt{\left( \vec{\Delta p} \cdot \vec a + v_{max}^2 \right)^2 - \begin{Vmatrix}\vec {\Delta p}\end{Vmatrix}^2 \begin{Vmatrix}\vec a\end{Vmatrix}^2} \right) }
$$
Here the inner negative gives us \$T_{min}\$ and the positive gives us \$T_{max}\$.
To find the limits due to our ceiling, \$ h_{max} \$, we find the peak of our parabola by isolating the y axis and taking the derivative...
$$\begin{align}
\vec p(t) &= \vec p_0 + \vec v_0 t + \frac {\vec a} 2 t^2 \\
p_y(t) &= p_{y_0} + v_{y_0} t + \frac {a_y} 2 t^2\\
\frac {\delta p_y(t)} {\delta t} &= v_{y_0} + a_y t
\end{align}$$
At the time it hits its peak \$t_*\$, the derivative is equal to zero (flight levels off before falling), so we can substitute this time in to solve for the peak height of the parabola.
$$ \begin{align}
\frac {d p_y(t_*)} {d t} = v_{y_0} + a_y t_* &= 0\\
t_* &= -\frac {v_{y_0}} {a_y}
\end{align} $$
$$\begin{align}
h_{max} &= p_y(t_*) \\
h_{max} &= p_{y_0} + v_{y_0} t_* + \frac {a_y} 2 t_*^2 \\
h_{max} &= p_{y_0} + v_{y_0}\left(-\frac{v_{y_0}}{a_y}\right) + \frac{a_y}2\left(-\frac{v_{y_0}}{a_y}\right)^2 \\
h_{max} - p_{y_0} &= -\frac{v_{y_0}^2}{a_y}+ \frac{v_{y_0}^2}{2a_y}\\
\Delta h &= -\frac {v_{y_0}^2} {2 a_y}
\end{align}
$$
Substituting our formula for \$v_0 = \frac{ \vec {\Delta p}} T - \frac a 2 T\$ lets us solve for the limiting time-to-target:
$$\begin{align}
-2a_y\Delta h & = \frac 1 {T^2} \left( \Delta p_y - \frac {a_y} 2 T^2 \right) \left( \Delta p_y - \frac {a_y} 2 T^2 \right) \\
-2a_y\Delta h T^2 &= \Delta p_y^2 - \Delta p_y a_y T^2 + \frac {a_y^2} 4 T^4 \\
\frac {a_y^2} 4 T^4 + a_y\left(2\Delta h - \Delta p_y \right) T^2 + \Delta p_y &= 0
\end{align}$$
Which we can solve again using the quadratic formula as before. This time, we care about only the inner positive case. The inner negative corresponds to a trajectory where we hit our target before we have a chance to hit the ceiling anyway. ;)
$$
T_{ceiling} = \sqrt{\frac 2 {a_y} \left( \left(\Delta p_y - 2\Delta h\ \right) + 2\sqrt{\Delta h^2 - \Delta h\Delta p_y }\right)}
$$
Lastly, to find the lowest-energy trajectory, we take the earlier expression for the square magnitude of the initial velocity as a function of \$T\$, and set its derivative equal to zero to locate its (unique) local minimum:
$$\begin{align}
\begin{Vmatrix}\vec v_0 \end{Vmatrix}^2 &= \frac {\begin{Vmatrix}\vec {\Delta p} \end{Vmatrix}^2} {T^2} - \left( \vec {\Delta p} \cdot \vec a \right) + \frac {\begin{Vmatrix}\vec a \end{Vmatrix}^2}4 T^2 \\
\frac { d \begin{Vmatrix}\vec v_0 \end{Vmatrix}^2}{d T} &= -2 \frac {\begin{Vmatrix}\vec {\Delta p} \end{Vmatrix}^2} {T^3} - 0 + \frac {\begin{Vmatrix}\vec a \end{Vmatrix}^2}2 T \\
0 &= -2 \frac {\begin{Vmatrix}\vec {\Delta p} \end{Vmatrix}^2} {T_{low}^3} + \frac {\begin{Vmatrix}\vec a \end{Vmatrix}^2}2 T_{low} \\
0 &= -2\begin{Vmatrix}\vec {\Delta p} \end{Vmatrix}^2 + \frac {\begin{Vmatrix}\vec a \end{Vmatrix}^2}2 T_{low}^4 \\
T_{low}^4 &= \frac{4\begin{Vmatrix}\vec {\Delta p} \end{Vmatrix}^2}{\begin{Vmatrix}\vec a \end{Vmatrix}^2} \\
T_{low} &= \sqrt[4]\frac{4\begin{Vmatrix}\vec {\Delta p} \end{Vmatrix}^2}{\begin{Vmatrix}\vec a \end{Vmatrix}^2}
\end{align}$$
Somewhat magically, the time to hit a target with the least energy doesn't vary with the direction to the target, only the ratio of its distance away to the force of gravity.
