Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

In my 2D game I have AI turrets that should assist the player by automatically firing towards enemies. I would like to make them fire intelligently and lead their target instead of just targeting an enemy's current position. So, given the (always constant) velocity and position vector of both the enemy and the turret's projectile, how can I find a vector that represents the actual position the turret must target in order for the projectile to intersect (and hit) the enemy?

Any links to articles that describe the math, algorithms, etc. would be appreciated!

share|improve this question
    
    
Thanks for the links! However I feel the solutions are a little hard to read, maybe I can muster up a clear visual answer to this question using the links you provided, to help any others that are stuck with the same problem. –  Larolaro Oct 19 '12 at 22:25
    
@Larolaro I've added a graphical demonstration to my answer so you can understand it a little better. –  jmacedo Oct 22 '12 at 22:48
    
I describe the approach I take in this answer gamedev.stackexchange.com/a/28582/6588 –  jhocking Mar 4 '14 at 15:31

3 Answers 3

up vote 5 down vote accepted

This question on GameDev, and this question on StackOverflow should provide you with the answer you're looking for. :)

share|improve this answer
1  
thanks :) I was able to implement a solution using the code from the second link –  Kryptic Nov 2 '10 at 16:31

I'm not gonna give you an answer I'm sure is useful or even correct, but here it goes:
After playing with mathematica a little more (check the end of the answer for notebook /published notebook) files, this solution appears to be correct, even thought it might not be the best one in terms of efficiency.

I wrote this in mathematica which corresponds to your problem. Basically it solves the equations / inequalities in order to the OA variable which is what we need to find out. The output is gonna give us the possible solutions that OA can have and the conditions that need to verify for each solution to be valid:

Reduce[{BPx, BPy} + t*{BVx, BVy} == {OPx, OPy} + t*OV*{Cos[OA], Sin[OA]} && t != 0 && OV != 0, {OA}]
  • {BPx,BPy} is blue's current position

  • {BVx,BVy} is blue's velocity vector

  • {OPx,OPy} is orange's bullet position

  • OV is the norm of orange's bullet velocity vector (total speed)

  • OA is orange's bullet angle (angle of velocity vector)

  • t is the time needed for the bullet to hit blue

I tried putting t>0 && OV>0 in the conditions but mathematica would take forever so I just used t!= 0 && OV != 0. So the solutions I'm gonna give here just work when blue is not in the exact same position as orange and when the orange's bullet really moves (instead of staying still)

The output is gigantic: http://freetexthost.com/xzhhpr5e2w

However if we extract the OA == _ parts, we get this:

http://freetexthost.com/iyrhqoymfo

Those are the values OA can have (each one requiring different conditions to be valid).

With some further analysis taking out the solutions that require OV to be negative which we don't want, I got this:

http://freetexthost.com/iy4wxepeb6

So these are the possible solutions to the problem, each one requiring different conditions to be valid. In order for a certain angle OA to be a valid solution, the following conditions must meet:

Reduce[{BPx, BPy} + t*{BVx, BVy} == {OPx, OPy} + t*OV*{Cos[OA], Sin[OA]} && t != 0 && OV != 0, {t}]

Output:

(BVy - OV Sin[OA] != 0 && BPx == (BPy BVx + BVy OPx - BVx OPy - BPy OV Cos[OA] + OPy OV Cos[OA] - OPx OV Sin[OA])/(BVy - OV Sin[OA]) && t == (-BPy + OPy)/(BVy - OV Sin[OA]) &&  BPy OV - OPy OV != 0) || 
(BVy == OV Sin[OA] && BPy == OPy && BVx - OV Cos[OA] != 0 && t == (-BPx + OPx)/(BVx - OV Cos[OA]) && BPx OV - OPx OV != 0) || 
(BVy == OV Sin[OA] && BVx == OV Cos[OA] && BPy == OPy && BPx == OPx && OV t != 0)

So consider only the solutions where that verifies (you don't need to verify the t==_ parts. They are the ones that give you the time needed for the bullet to hit the vehicle if the other conditions are valid. Notice that if t results in a negative value, you cannot consider a given OA as a valid solution, even if it verifies the other conditions (this is because we used t!= 0 instead of t>0 in reduce)).

It also might be a good idea to ask in http://math.stackexchange.com/ about this.

Edit

I've grown some interest for this question, so I've created a commented notebook with a graphical demonstration of everything I explained . Download it here:

http://www.2shared.com/file/pXhYyhN1/towerBullets.html
Or here: http://www.2shared.com/file/W01g4sST/towerBullets.html

(this is the published version, and you only need the mathematica player -which is free- to see it. If you don't have mathematica this is the way to go)

Screenshot:

share|improve this answer
    
I can provide the conditions and solutions with the multiplication sign (*) so it is easier for you to port them to your programming language (Then you would only need to replace the ArcTan[...],Sin[...],Cos[...],Sqrt[...] and eventually the power sign (^). –  jmacedo Oct 20 '12 at 17:41
    
Hah, forget about this solution. Now that this question has been merged, the first answer's links seam to contain better answers. –  jmacedo Oct 22 '12 at 23:43

This is a repeat answer from this thread Predictive firing (in a tile-based game)

Linear targeting

enter image description here

All successful targeting and shooting of enemies requires an algorithm to fire bullets at the place where you predict that an enemy will be at a future point in time. This algorithm can be used for linear, circular, and oscillating predictive targeting. And if you have a function that returns the position of the enemy at a future point in time, you can use the algorithm to calculate the impact point, the firing angle, the impact position, and the impact time.

This algorithm implements the secant method to numerically solve the impact time. Once this impact time is known, our predictive function obtains the impact position. Then we fire at that position.

The Intercept class shown in Listing 1 assumes that the enemy is traveling in a straight line from its current position at its current velocity.

Listing 1. Using the Intercept class

public class Intercept {

    public Coordinate impactPoint = new Coordinate(0, 0);
    public double bulletHeading_deg;

    protected Coordinate bulletStartingPoint = new Coordinate();
    protected Coordinate targetStartingPoint = new Coordinate();
    public double targetHeading;
    public double targetVelocity;
    public double bulletPower;
    public double angleThreshold;
    public double distance;

    protected double impactTime;
    protected double angularVelocity_rad_per_sec;

    public void calculate(
            // Initial bullet position x coordinate 
            double xb,
            // Initial bullet position y coordinate
            double yb,
            // Initial target position x coordinate
            double xt,
            // Initial target position y coordinate
            double yt,
            // Target heading
            double tHeading,
            // Target velocity
            double vt,
            // Power of the bullet that we will be firing
            double bPower,
            // Angular velocity of the target
            double angularVelocity_deg_per_sec
    ) {
        angularVelocity_rad_per_sec
                = Math.toRadians(angularVelocity_deg_per_sec);

        bulletStartingPoint.set(xb, yb);
        targetStartingPoint.set(xt, yt);

        targetHeading = tHeading;
        targetVelocity = vt;
        bulletPower = bPower;
        double vb = 20 - 3 * bulletPower;

        double dX, dY;

// Start with initial guesses at 10 and 20 ticks
        impactTime = getImpactTime(10, 20, 0.01);
        impactPoint = getEstimatedPosition(impactTime);

        dX = (impactPoint.x - bulletStartingPoint.x);
        dY = (impactPoint.y - bulletStartingPoint.y);

        distance = Math.sqrt(dX * dX + dY * dY);

        bulletHeading_deg = Math.toDegrees(Math.atan2(dX, dY));
        angleThreshold = Math.toDegrees(Math.atan(ROBOT_RADIUS / distance));
    }

    protected Coordinate getEstimatedPosition(double time) {

        double x = targetStartingPoint.x
                + targetVelocity * time * Math.sin(Math.toRadians(targetHeading));
        double y = targetStartingPoint.y
                + targetVelocity * time * Math.cos(Math.toRadians(targetHeading));
        return new Coordinate(x, y);
    }

    private double f(double time) {

        double vb = 20 - 3 * bulletPower;

        Coordinate targetPosition = getEstimatedPosition(time);
        double dX = (targetPosition.x - bulletStartingPoint.x);
        double dY = (targetPosition.y - bulletStartingPoint.y);

        return Math.sqrt(dX * dX + dY * dY) - vb * time;
    }

    private double getImpactTime(double t0,
            double t1, double accuracy) {

        double X = t1;
        double lastX = t0;
        int iterationCount = 0;
        double lastfX = f(lastX);

        while ((Math.abs(X - lastX) >= accuracy)
                && (iterationCount < 15)) {

            iterationCount++;
            double fX = f(X);

            if ((fX - lastfX) == 0.0) {
                break;
            }

            double nextX = X - fX * (X - lastX) / (fX - lastfX);
            lastX = X;
            X = nextX;
            lastfX = fX;
        }

        return X;
    }

}

Circular targeting

enter image description here

The great thing about the Intercept class is that it can be easily reused to calculate the firing angle for circular motion. To do this, write a CircularIntercept class that inherits from the Intercept class, and overwrite the getEstimatedPosition() method. Listing 2 shows the code for the CircularIntercept class:

Listing 2. CircularIntercept class

public class CircularIntercept extends Intercept {

    protected Coordinate getEstimatedPosition(double time) {
        if (Math.abs(angularVelocity_rad_per_sec)
                <= Math.toRadians(0.1)) {
            return super.getEstimatedPosition(time);
        }

        double initialTargetHeading = Math.toRadians(targetHeading);
        double finalTargetHeading = initialTargetHeading
                + angularVelocity_rad_per_sec * time;
        double x = targetStartingPoint.x - targetVelocity
                / angularVelocity_rad_per_sec * (Math.cos(finalTargetHeading)
                - Math.cos(initialTargetHeading));
        double y = targetStartingPoint.y - targetVelocity
                / angularVelocity_rad_per_sec
                * (Math.sin(initialTargetHeading)
                - Math.sin(finalTargetHeading));
        return new Coordinate(x, y);
    }

}

Example

Listing 3 shows an example of using the Intercept class. It assumes that we calculated the current position, heading, and velocity of the target, as well as the power of the bullet that we will be firing.

Listing 3. Using the Intercept class

Intercept intercept = new Intercept();

intercept.calculate (
        ourRobotPositionX,
        ourRobotPositionY,
        currentTargetPositionX,
        currentTargetPositionY,
        curentTargetHeading_deg,
        currentTargetVelocity,
        bulletPower,
        0 // Angular velocity
);

// Helper function that converts any angle into  
// an angle between +180 and -180 degrees.
    double turnAngle = normalRelativeAngle(intercept.bulletHeading_deg - robot.getGunHeading());

// Move gun to target angle
    robot.setTurnGunRight (turnAngle);

    if (Math.abs (turnAngle) 
        <= intercept.angleThreshold) {
  // Ensure that the gun is pointing at the correct angle
  if ((intercept.impactPoint.x > 0)
                && (intercept.impactPoint.x < getBattleFieldWidth())
                && (intercept.impactPoint.y > 0)
                && (intercept.impactPoint.y < getBattleFieldHeight())) {
    // Ensure that the predicted impact point is within 
            // the battlefield
            fire(bulletPower);
        }
    }
}

This firing strategy has proven very successful. Encapsulating the intercept in its own class and subclassing it for different prediction algorithms allows variability in targeting schemes.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.