Iterative Method

Intro

The Millington iterative method (often referred to as iterative targeting or iterative refinement in Ian Millington’s AI for Games or Game Physics Engine Development) is a technique used in game AI to solve for the necessary launch velocity or angle to hit a moving target with a projectile, while accounting for gravity. [1, 2]

Because a moving target shifts the required landing spot during the time of flight, the method uses an iterative approach to find the correct, non-linear firing solution. [3]

The Problem: Static vs. Moving Targets

• Static Method: If a target is stationary, a single formula, often based on the kinematic trajectory formula:

$y=x\tan \theta -\frac{g{x}^2}{2u^2{\cos }^2\theta }$

can determine the necessary launch parameters.

• The Iterative Problem: If the target moves, the time to hit it ($t$) changes. If the time changes, the target moves to a new position before the projectile arrives. [4, 5, 6, 7, 8]

The Millington Iterative Process

The technique involves refining the estimated time of impact, as outlined in Millington’s approaches to ballistic trajectories:

1. Initial Estimate: Calculate the time to intercept ($t_i$) assuming the target is currently at its present position (static target).
2. Predict Target Position: Use this initial time $t_i$ to calculate where the target will be when the projectile arrives: ${\vec{p}}_{new}={\vec{p}}_{old}+{\vec{v}}_{target}\times t_i$.
3. Refine Time: Re-calculate the time to intercept ($t_{new}$) using the new position of the target.
4. Loop: Repeat steps 2 and 3 until the change in time between iterations is negligible (i.e., the algorithm converges). [1, 4, 9, 10, 11]

Key Components of the Algorithm

• Targeting Equation: The core kinematic equation used for each step is ${\vec{p}}_t={\vec{p}}_0+\vec{u}t+\frac{1}{2}\vec{g}{t}^2$, where ${\vec{p}}_t$ is the target position, ${\vec{p}}_0$ is the source, $\vec{u}$ is the initial velocity, and $\vec{g}$ is gravity.

• Binary Search/Correction: In cases of high-speed targets or when drag is added, the algorithm may use a binary search to adjust the launch angle if the target is consistently over- or undershot.

• Convergence: The method converges quickly because it uses fixed-point iteration to find the unique positive solution for the target’s position. [1, 9, 12, 13, 14]

This method is popular in AI for games (like shooters) because it strikes a balance between physical accuracy and computational speed, providing a “good enough” hit against moving players. [2, 15, 16]

AI can make mistakes, so double-check responses

[1] https://www.cs.drexel.edu/~santi/teaching/2017/CS387/CS387-W2-Movement-part1.pdf [2] https://www.coursesidekick.com/computer-science/1581354 [3] https://hanspeterschaub.info/Papers/grads/PadraigLysandrou.pdf [4] https://www.coursehero.com/file/212558446/Notes-1txt/ [5] https://www.vedantu.com/jee-main/physics-derivation-of-equation-of-trajectory [6] https://www.scribd.com/document/959078570/2-Ballistic-Projectile-Static-Target-With-Gravity [7] https://askfilo.com/user-question-answers-smart-solutions/if-the-equation-of-a-projectile-is-y-3x-gx-2-2-then-the-3337323339303838 [8] https://www.reddit.com/r/Unity3D/comments/73z8bm/working_on_realistic_physics_missiles_what_do_you/ [9] https://jarnepeire.be/physicspredictions/ [10] https://www.reddit.com/r/gamedev/comments/sd3cva/homing_missile_with_trajectory_prediction_in/ [11] https://www.gamedeveloper.com/programming/predictive-aim-mathematics-for-ai-targeting [12] https://ndspacegrant.und.edu/_files/docs/meetings/2015/numerical-solutions-of-a-projectile-motion.pdf [13] https://www.vaia.com/en-us/textbooks/physics/essential-university-physics-global-edition-4-edition/chapter-3/problem-91-generalize-problem-90-to-find-an-expression-for-t/ [14] https://www.vedantu.com/question-answer/the-equation-of-motion-of-a-projectile-is-y-ax-class-11-physics-cbse-5fdf2e32aa2c940e6f576c32 [15] https://himnickson.medium.com/artificial-intelligence-alpha-beta-pruning-75f920a72891 [16] https://www.mdpi.com/2076-3417/15/4/1781

---

Based on the image provided, the mathematical expression shown is:

$u_{p0}=\frac{2\Delta -g_p{t}_c^2}{2s_p{t}_c}$

Breaking Down the Components While this specific formula can appear in various specialized engineering contexts, it bears a strong resemblance to kinematic equations rearranged to solve for an initial velocity ($u$). Comparing it to the standard kinematic equation for displacement: $\Delta x=v_{0}t+\frac{1}{2}a{t}^2$

If we solve for $v_0$ (initial velocity): $v_0=\frac{\Delta x-\frac{1}{2}a{t}^2}{t}=\frac{2\Delta x-a{t}^2}{2t}$

In your formula, the variables likely represent:

• : Initial velocity (often $u$ or $v_0$ in physics). • : Displacement or change in position. • : Acceleration (likely a specific “p” component of gravity or a generalized acceleration). • : A specific time interval (the “c” might denote “critical” or “cycle” time). • : This is often a scaling factor, a specific distance, or related to a slope/projected component in more complex dynamics (like ballistics or fluid flow).

Summary of the Relationship The formula calculates a required initial velocity ($u_{p0}$) needed to achieve a certain displacement ($\Delta$) over a specific time ($t_c$), accounting for a constant acceleration ($g_p$) and a scaling or sensitivity factor ($s_p$).

AI can make mistakes, so double-check responses