# Predictive firing (in a tile-based game)

I have a (turn-based) tile-based game, in which you can shoot at entities.

You can move around with mouse and keyboard, it's all tile-based, except that bullets move "freely".

I've got it all working just fine except that when I move, and the creatures shoot towards the player, they shoot towards the previous tiles.. resulting in ugly looking "miss hits" or lag.

I think I need to implement some kind of predictive firing based on the bullet speed and the distance, but I don't quite know how to implement such a thing...

Here's a simplified snip of my firing code.

``````class Weapon {

public void fire(int x, int y) {
...
...
...
Creature owner = getOwner();
Tile targetTile = Zone.getTileAt(x, y);

float dist = Vector.distance(owner.getCenterPosition(), targetTile.getCenterPosition());

Bullet b = new Bullet();
b.setPosition(owner.getCenterPosition());

// Take dist into account in the duration to get constant speed regardless of distance
float duration = dist / 600f;

// Moves the bullet to the centre of the target tile in the given amount of time (in seconds)
b.moveTo(targetTile.getCenterPosition(), duration);

// This is what I'm after
// Vector v = predict the position
// b.moveTo(v, duration);

Zone.add(bullet); // Now the bullet gets "ticked" and moveTo will be implemented
}
}
``````

Movement of creatures is as simple as setting the position variable.

-
an alternative option would be to have it fire a burst shot sometimes, so that it will at least be firing one of the shots closer to you – TMP Sep 12 '12 at 15:42

At its core you are going to have to predict which tile the target will be on.

A simple solution would be to take the current velocity of the target, figure out where the target would be in the amount of time it would take the bullet to traverse to the player (to get a rough estimate you could use the current distance to the target), and then aim at that tile.

-
Some games cheat by altering (a diagonal offset) the instantaneous velocity of the bullet. One of them is Age of Empires (although not tile based), where a javelin was thrown and it followed a moving character till it hit almost dead on. It was annoying to see it, but at least one wouldn't complain that the arrow fell 3 meters back and then their unit died. – teodron Sep 12 '12 at 15:42
Your answer sounds like a nice and simple solution... but I must admit my math skills are, well... a bit rusty! A pseudo-code, or a more detailed explanation behind the - probably quite straightforward math - would be very helpful. Thanks for your time and answer! – TX-256 Sep 12 '12 at 20:45
Calculate distance from you to the player. You have the speed of the bullet, from that determine the time it'll take to reach the player (distance/speed). You have the velocity of the player. Predicted position = current player position + ( player velocity * time for bullet to hit player ). Aim at predicted position. – Tetrad Sep 12 '12 at 21:10
OK, I got it almost working now... one more silly question though, how do I actually calculate the velocity of the player for predicting to work correctly? I currently have a simple move(Direction)-method in my player class. The turn gets processed afterwards. The player moves Tile.SIZE at a time. I tried some things, off the top my head, but they didn't work quite right; the best result got the predicting to hit 1-4 tiles ahead of the wanted tile. The predicting itself should work now, though! – TX-256 Sep 13 '12 at 22:47
I dont think the shooting angle depends on the distance. It depends only on the velocities of bullet, player and the relative angle of player with respect to the enemy. – Shashwat Sep 14 '12 at 7:23

Sounds like `ballistics` technology in Age of Empires. You need to find the correct angle of fire.

``````         A
| \\
|  \ \
|   \  \
| vb \   \
|     \   \
|      \    \
D------ B--->C
vp

Here A = enemy
B = player current position
C = player future position
vb = speed of bullet
vp = speed of player
``````

Hope you understood the graph. If I got the problem correct, then your enemy is shooting at B, but you want it to shoot at C.

``````Let angle(DAB) = o
angle(DAC) = p
``````

Clearly,

``````vb*sin(o) + vp = vb*sin(p)
p = inv_sin( sin(o) + vp/vb )
``````

Here is the angle you needed to shoot.

NOTE

I does not depend on the distance between enemy and player

-

# Linear targeting

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);

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

protected double impactTime;

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 velocity
double vt,
// Power of the bullet that we will be firing
double bPower,
// Angular velocity of the target
double angularVelocity_deg_per_sec
) {

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

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

double dX, dY;

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);

}

protected Coordinate getEstimatedPosition(double time) {

double x = targetStartingPoint.x
double y = targetStartingPoint.y
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

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) {
return super.getEstimatedPosition(time);
}

double x = targetStartingPoint.x - targetVelocity
double y = targetStartingPoint.y - targetVelocity
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,
currentTargetVelocity,
bulletPower,
0 // Angular velocity
);

// Helper function that converts any angle into
// an angle between +180 and -180 degrees.

// 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.

-