Figuring out where a projectile will go

Started by
17 comments, last by alvaro 8 years, 1 month ago
I have an old school space game during a game jam and want to turn it into a full game, only issue I'm having is making an AI that can A) Hit things accurately and B) realize when projectiles are coming towards them and avoid them. What makes it difficult is the projectiles have wonky paths because they're affected by a crude approximation of gravity:
craziness.png

Now how the projectiles move is the star in this picture has a component called Gravity Source on it, and it supplies the force calculations:
using UnityEngine;
using System.Collections;
 
public class GravitySource : MonoBehaviour
{
    public Vector3 ForceAtPoint(Vector3 xyz)
    {
        var newForce = transform.position - xyz;
 
        if (newForce.sqrMagnitude > 0.0f)
        {
            newForce = (newForce / newForce.sqrMagnitude) * 5000.0f;
        }
 
        return newForce;
    }
}
and the missiles & player have a Gravity Receiver, the missiles having a 10x multiplier and players 1x


using UnityEngine;
using System.Collections;
 
public class GravityReciever : MonoBehaviour {
    public float gravityMultiplier = 1.0f;
    public GravitySource gravitySource;
    Rigidbody rb;
 
    void Start()
    {
        rb = GetComponent<Rigidbody>();
    }
 
void FixedUpdate () {
        rb.AddForce(gravitySource.ForceAtPoint(transform.position) * Time.fixedDeltaTime * gravityMultiplier, ForceMode.Acceleration);
    }
}

Now my question is, how do I calculate where a projectile is going so I can have my AI make decent shots as well as dodging incoming fire?



https://dl.dropboxusercontent.com/u/168938/Games/Space%20Melee/OrbitProjectileExample.zip (a copy of the physics code with all the assets removed to play around with/make examples)
Advertisement
This is a pretty tricky problem. The approach I would take would be to pick a direction and velocity, then calculate the path iteratively meaning you simulate the game forwards in time applying gravity and updating the projectile velocity etc. Do this for a few random directions then pick the one that is the best shot. You could then keep track of the best know shot from frame to frame then each frame, do the same thing but with slightly modified versions of the best current shot. If a slightly modified version improves the shot, then store that as the best shot.

You will determine the best shot based on a score. I would score it based on how close it comes to the target, and for moving targets, how much time it would take for impact. Further away shots wont score as high since it would be more likely for the target to move.

This would be a genetic algorithm approach. You could refine it by coming up with another method that can give a good initial direction and velocity, this would make it converge faster. You will also have to fine tune how much to modify the inputs each iteration. You will also need to set a max maximum time you will simulate out to.

Once you have a way to score your shots, you can set a threshold for the score. Once a shot score exceeds a threshold you take the shot. The threshold could slowly drop down each frame to ensure that the enemy eventually shoots, and once the enemy does shoot, you raise the threshold.

I may be over complicating this, but the nice thing about this approach is it pretty flexible. You could add multiple bodies with gravity and it would handle it just fine. You could also simulate moving targets assuming you could accurately predict their future position. The way you score a shot also gives you some flexibility. You could check for collision with things you don't want to hit as part of the score.

You could also reuse the same path predictor to determine if a projectile will hit the AI's ship.
My current game project Platform RPG

You could also try recording positions of each projectile every T seconds, and then use previous positions to approximate a parabola. Usually projectiles will travel in roughly a parabola (see: parabola from 3 points). An even simpler version of this is to just take the current position/velocity and raycast forward just a little ways (see: tangent line approximation).

If you don't like either of these and want more exact results an iterative finder will work. This can get quite complex and expensive to compute.

For incoming projectiles, you can do a "look ahead". Assuming that the physics update step is fixed, you can step a simulation ahead several frames. So... when the bullet is first initially fired, you do several computations on that one node, and generate a path to each simulation. Then you let the game "play" the "recorded" physics frames, while with each update step, it simply adds another step onto the physics projectile path.

The Ai will be aware of these paths and will try to steer clear of them within certain time frames. The projectiles simulation will continue to run, till the actual projectile it's self has been destroyed or the path leads into a celestial body.

For the AI to accurately aim... you'll want to think of this on a more realistic level. With multiple celestial bodies pulling on the object, it's not quite possible to know the exact route that will be taken.

I got nothing for how the AI can aim. Most games I see just have the AI aimlessly chase you, and shoot in bizzare ways.

as tangletail says, the calculations for aiming will be exceeding complex - more complex than norton bomb sight calculations.

an iterative "look ahead" approach as described by happycoder will likely be the best approach.

select a likely trajectory, run it for a few updates, check the range to target. adjust trajectory and try again. limit it to perhaps ten tries before shooting for real. sort of a "targeting computer".

Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php

If you want to go really crazy, you can look at NASA's GMAT, it's source code is available. Though that would seem to be overkill if you only have one planetary body.

There is also this matlab source code here, that seems to deal with just one planetary body. It's still more than you need, as it's calculating a variable mass rocket, but maybe you can pare it down.

I have a couple of friends that are really good at differential equations. I'll ask them if there's a simple analytic solution to this. I'll report back.

I have a couple of friends that are really good at differential equations. I'll ask them if there's a simple analytic solution to this. I'll report back.

It's a multivariable problem. There are multiple effectors, which generates an infinite vector field in space that models the influence.

I don't think differential equations wouldn't be too useful here. The purpose of a differential is to model the rate of change to a higher order function at some point x or y. It can't really be used to find a predictable path alone, but it can be used to find the changes in velocity, acceleration, and position.

Example: Let A be your acceleration. t be time.

y''(t) = A, is just a straight line for the entirety of t.
y'(t) = At + C, is now computing velocity at time of t with a constant of C.

y(t) = 1/2At^2 + Ct + k, is now a parabolic curve that computes the position of (x, y, or z) in space to a "ground place" being effected by a constant force. C and K are constants of anything. Which makes this equation an "ok" general solution for this linear equation. But not a perfect one.

Though taking the integral of those rate of change functions does transform it into something that measures something else with the slope of the differential effecting it's values, it won't exactly be an efficient way to go about predicting paths of functions with too much chaos.

Though there are non linear differential equations, we only know a few that have exact solutions.


Though that would seem to be overkill if you only have one planetary body.

i was assuming more than one gravity source. if you only have one gravity source and you're working in 2D, it may be directly solvable (but still somewhat complicated).

in fact, in 2d, with a single gravity influence, faking it should become easy. you start with a straight line shot, corrected for target motion. this gives you your initial trajectory if there was no gravity. then you simply apply a mod to the initial trajectory based on range and angle to the gravity source. the amount of mod is determined experimentally. it may be a linear relationship or perhaps exponential.

an iterative approach could also be used. at each step, the gravity source is simply an acceleration vector applied to the projectile.

Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php

I don't think differential equations wouldn't be too useful here. The purpose of a differential is to model the rate of change to a higher order function at some point x or y. It can't really be used to find a predictable path alone, but it can be used to find the changes in velocity, acceleration, and position.

Most if not all movement equations in physics are differential equations...besides, changes in position integrated over time is the path.

y(t) = 1/2At^2 + Ct + k, is now a parabolic curve that computes the position of (x, y, or z) in space to a "ground place" being effected by a constant force. C and K are constants of anything. Which makes this equation an "ok" general solution for this linear equation. But not a perfect one.

If you pose your problem correctly, i.e. prescribe position and velocity, C and K are not "anything", but uniquely defined. This is then the only solution to this equation.

By the way, most if not all problems in mechanics and engineering can be reduced to solving (partial or ordinary) differential equations. You grossly understate their utility.

Of course OPs problem can be formulated as a ODE using Newton's law as a well-enough approximation:

our gravitational potentials are of the form V_i(r) = - G * M / |r - r_i| (central potential), so the force at point r can be written (if I'm not mistaken) as F_i(r) = grad V_i(r) = -G * M (r - r_i) / |r - r_i|^3.

Given an initial position r_0 and initial velocity v_0, you have enough data to compute the exact path. Plug this into m*a(t) = F(t) and you obtain an ODE for your path. I don't think solving this exactly is easy (maybe not even possible). You can certainly solve this numerically with ODE step solvers, but OP is looking at the inverse problem, which is hard in itself already. I don't know if this can be solved without some heuristic "aim, guess resulting path, adjust aim" algorithm, unless the ODE can be solved exactly. Maybe I'm off on this one, who knows :D

This topic is closed to new replies.

Advertisement