• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
zqf

Enemies Leading their shots

9 posts in this topic

I've tried looking this up but couldn't find anything basic enough for my beginner maths skills to understand.
Isn't much more than what's in the Topic title, would like monsters to be able to shoot at where a player is moving to rather than just directly at them.
0

Share this post


Link to post
Share on other sites
Assuming you're comfortable with basic algebra and at least rudimentary vector arithmetic:

[list][*]Compute the distance between the player and the enemy[*]Divide the distance by the speed of the projectile to determine how long it will take for the shot to reach the player[*]Take the player's current velocity vector[*]Scale the velocity vector by the time taken for the shot to arrive[*]Sum this vector with the player's current position[*]This gives you the target location you should aim at[/list]
0

Share this post


Link to post
Share on other sites
It's actually a bit more complicated than that in truth, as you aren't trying to calculate the time to get to where the player is currently at, but rather the time where the player will be when the bullet hits. This resolves to a quadratic equation.

Assume the shooter is at position Gun and is stationary, the target is at position TargetStart and is moving along the velocity vector TargetVel . Gun shoots a bullet that travels at BulletSpeed, that starts at Gun and moves along the vector BulletVec to strike the target at the impact point, called Bullet. Okay?

The time, t, denotes the time it takes for the bullet to strike the target. So at time t, the bullet will have traveled a distance of t*BulletSpeed and the Target will have moved a distance t*TargetSpeed. The impact point will be at a distance t*BulletSpeed from Gun and t*TargetSpeed from TargetStart, where TargetSpeed is the speed component, or length, of TargetVel. Armed with this knowledge, we can begin deriving some equations.

1) Impact will be at a distance of t*BulletSpeed from Gun, so that suggests the equation for the projectile as a parametric circle centered at Gun. Recall that a circle, of course, is all points that are a given distance from the center. In this case, all points that are t*BulletSpeed distance from center:
[code]
(Bullet.X - Gun.X) * (Bullet.X - Gun.X) + (Bullet.Y - Gun.Y) * (Bullet.Y - Gun.Y) = (t * BulletSpeed) * (t * BulletSpeed)
[/code]

2) In the time, t, that it takes the bullet to reach the impact point, Bullet, the target is also moving a distance equal to t*TargetSpeed. So the location that the target will be at at time t can be calculated as:
[code]
Target.X = TargetStart.X + TargetVel.X * t;
Target.Y = TargetStart.Y + TargetVel.Y * t;
[/code]

3) The impact point is where the target is the same distance from Gun as the projectile is at time t.
[code]
(Target.X - Gun.X) * (Target.X - Gun.X) + (Target.Y - Gun.Y) * (Target.Y - Gun.Y) = (Bullet.X - Gun.X) * (Bullet.X - Gun.X) + (Bullet.Y - Gun.Y) * (Bullet.Y - Gun.Y)
[/code]

4) Armed with these expressions, we can do substitute the equations for Target.X and Target.Y from (2) into (3)
[code]
((TargetStart.X + TargetVel.X*t) - Gun.X) * ((TargetStart.X + TargetVel.X*t) - Gun.X) + ((TargetStart.Y +TargetVel.Y * t) - Gun.Y) * ((TargetStart.Y + TargetVel.Y * t) - Gun.Y) = (Bullet.X - Gun.X) * (Bullet.X - Gun.X) + (Bullet.Y - Gun.Y) * (Bullet.Y - Gun.Y)
[/code]

5) Now, for the other side of the equation, we can substitute in (1) to get rid of the unknowns, Bullet.X and Bullet.Y:
[code]
((TargetStart.X + TargetVel.X*t) - Gun.X) * ((TargetStart.X + TargetVel.X*t) - Gun.X) + ((TargetStart.Y +TargetVel.Y * t) - Gun.Y) * ((TargetStart.Y + TargetVel.Y * t) - Gun.Y) = (t * BulletSpeed) * (t * BulletSpeed)
[/code]

6) Re-arrange and simplify the expression:
[code]
((TargetVel.X * TargetVel.X) + (TargetVel.Y * TargetVel.Y) - (BulletSpeed * BulletSpeed)) * t*t + 2*(TargetVel.X * (TargetStart.X - Gun.X) + TargetVel.Y * (TargetStart.Y - Gun.Y)) * t + ((TargetStart.X - Gun.X) * (TargetStart.X - Gun.X)) + ((TargetStart.Y - Gun.Y) * (TargetStart.Y - Gun.Y) = 0
[/code]

7) (6) Looks a bit ugly, and I glossed over a bit of simplification, but if you look at it what you have is a quadratic equation. Recall that a quadratic equation is of the form a*t*t + b*t + c = 0. The above equation follows this form, with values for a,b,c as follows:

[code]
a = ((TargetVel.X * TargetVel.X) + (TargetVel.Y * TargetVel.Y) - (BulletSpeed * BulletSpeed))
b = 2*(TargetVel.X * (TargetStart.X - Gun.X) + TargetVel.Y * (TargetStart.Y - Gun.Y))
c = ((TargetStart.X - Gun.X) * (TargetStart.X - Gun.X)) + ((TargetStart.Y - Gun.Y) * (TargetStart.Y - Gun.Y)
[/code]

You can find the solution of a quadratic equation by
[code]
t = (-b (+ or -) sqrt(b*b - 4 * a * c)) / (2 * a)
[/code]

8) 7 can have either 0, 1 or 2 possible solutions. Cases in which there are 0 solutions include instances where the projectile could not possibly hit the target in any given amount of time, given the target position and velocity and the bullet velocity. ie, the target moves out of range too fast, was never in range to start with, etc... Cases where there are 2 solutions include solutions with a -t value, or time-traveling bullets that can go back in time to hit the target where it was back then. Which would be kind of awesome if you think about it, but I bet they'd be way overpowered.

Bear in mind the above was taken from some rather chicken-scratch notes I had made a long time ago when I was deriving this solution, so I'm not actually 100% sure it's all correct, but it seems right. It's not an extremely complicated problem, but it does take a bit of figuring.
1

Share this post


Link to post
Share on other sites
The method I described is certainly approximate, but it goes a long way towards preventing your enemies from being impossibly hard to dodge. It's also a lot simpler to calculate, which IMO makes it advantageous for a beginner.

You are absolutely correct that it is not perfect, though!


(Of course you can always go super-overkill and compute the actual equation that includes the acceleration and velocity of both the player and the enemy, includes windage effects, etc. etc., but the calculus gets a bit hairy.)
0

Share this post


Link to post
Share on other sites
I am planning to release a paper which can explain how to make any type of projectile (instance-fire, straight rockets, grenades, wavy alien guns, etc.) hit any target as long as its path is not interrupted by player input.
That is, the target can just fall and accelerate, or it could land on the ground and stop, or bounce off a wall, etc. Since all of these can be predicted and measured, an AI can account for them while taking aim.

While some of these resolve to quartic functions, and if you want to account for the target hitting walls or floors you will need to have a collision-detection routine handy, but I will also present a fairly intuitive and straight-forward method that handles every gun type and target-motion type. If you don't have the ability to account for hitting walls etc., you can still use the method (without accounting for every type of target motion) and it is simple to implement.

Unfortunately you will have to wait a while. I am very busy these days.


L. Spiro
-1

Share this post


Link to post
Thanks for the replies! I briefly tried ApochPiQ's technique...it didn't seem to work until I tried multiplying the time up at which point the leading seemed to start having an effect. I don't know if at this point I'm just scaling up the player's velocity by a random amount that happens to be about right and aiming at that though

However the game in question is a horde based shooter and I was mainly looking for a way to prevent circling monsters from rendering them harmless. This actually seems to be close to what I need as the bit of inaccuracy only increases the apparent chaos around the player, which is great :)

I'm interested in looking into it further...though I don't really understand FLeBlanc right now. I need to read over that again :E
0

Share this post


Link to post
Share on other sites
I realize that I omitted one important detail, assuming it would be clear enough, but that may not be the case: when you scale the player's velocity by the estimated impact time, you should first normalize the velocity [i]then[/i] multiply by the time factor. Although honestly unless your world units are at a very different order of magnitude than I usually use, that should result in [i]overcorrection[/i] instead of what you describe, so... maybe it's something else :-)

Any chance you could post the aiming code for examination? Shouldn't be more than 15-20 lines worth of stuff, ideally, so no big deal for us to help check your math :-)
0

Share this post


Link to post
Share on other sites
Here's my code (AS3). I'm multiplying the time by the player's speed.

[code]//Compute the distance between the player and the enemy
var v1:Vector2D = new Vector2D(newBullet.position.x - player.position.x, newBullet.position.y - player.position.y);
var dist:Number = Math.sqrt(v1.a * v1.a + v1.b * v1.b);

//Divide the distance by the speed of the projectile to determine how long it will take for the shot to reach the player
var time:Number = dist / Monsters.trooperRangedSpeed; // RangedSpeed = 6
//Take the player's current velocity vector
var v2:Vector2D = new Vector2D(player.movement.a, player.movement.b);

//Scale the velocity vector by the time taken for the shot to arrive
v2.a = v2.a / v2.magnitude;
v2.b = v2.b / v2.magnitude;

v2.a *= time * 4; // <--- scaling time by player velocity seems to give closer results
v2.b *= time * 4;

//Sum this vector with the player's current position
v2.a += player.position.x;
v2.b += player.position.y;
//This gives you the target location you should aim at
// Shoot[/code]

Hope I've not done anything too dumb :unsure:
0

Share this post


Link to post
Share on other sites
Here is a drop-in implementation of the algorithm I posted earlier:

[code]
bool calcInterceptTrajectory(vec2 &gun, vec2 &targetstart, vec2 &targetvel, float bulletspeed, vec2 &impactpoint, vec2 &bullettrajectory)
{
// The coefficients of the quadratic equation:
// a = ((TargetVel.X * TargetVel.X) + (TargetVel.Y * TargetVel.Y) - (BulletSpeed * BulletSpeed))
// b = 2*(TargetVel.X * (TargetStart.X - Gun.X) + TargetVel.Y * (TargetStart.Y - Gun.Y))
// c = ((TargetStart.X - Gun.X) * (TargetStart.X - Gun.X)) + ((TargetStart.Y - Gun.Y) * (TargetStart.Y - Gun.Y)

float a = ((targetvel.x * targetvel.x) + (targetvel.y * targetvel.y) - (bulletspeed * bulletspeed));
float b = 2.0f * (targetvel.x * (targetstart.x - gun.x) + targetvel.y * (targetstart.y - gun.y));
float c = ((targetstart.x - gun.x) * (targetstart.x - gun.x)) + ((targetstart.y - gun.y) * (targetstart.y - gun.y));

// First, calculate the discriminant to see if we can even make the shot
float disc = b*b - 4.0f*a*c;

// If the discriminant is <0, there is no chance of hitting the target. Just not gonna happen, not in this universe of real numbers
if (disc < 0.0f) return false;

if (a==0.0f) return false; // Avoid the case of a divide-by-zero

// Calculate the possible solutions
float t1 = (-b + sqrt(disc)) / (2.0f * a);
float t2 = (-b - sqrt(disc)) / (2.0f * a);

float t = std::max(t1, t2);
if (t < 0.0f) return false; // Time-traveling bullets are, sadly, not allowed

// We get here, we have a valid time. Use it to extrapolate the target's position at time t, or the impact point

impactpoint=vec2(targetstart.x + t * targetvel.x, targetstart.y + t*targetvel.y);

// And subtract to obtain the vector along which to shoot
bullettrajectory = vec2(impactpoint.x - gun.x, impactpoint.y - gun.y);

// Normalize it to unit length
float len=sqrt(bullettrajectory.x * bullettrajectory.x + bullettrajectory.y * bullettrajectory.y);
bullettrajectory.x /= len;
bullettrajectory.y /= len;
return true;

}
[/code]

To use the above, pass in the gun location, the target starting location, the target velocity vector and the bullet speed. The function will return false if the shot can not be made, and will calculate impact and bullettrajectory then return true if the shot can be made. I just now tested it in a quick and dirty SFML app and it seems to work fine.

Note that as others noted, this is a linear simplification of general-case trajectory calculation. It doesn't take into account curved target trajectories, accel/decel, etc... So in your use-case of shooting at an opponent circling around you, this method would be little better than an approximation, since the target's trajectory is always changing. Target prediction that takes into account accel/decel and also the possibilities of a target randomly changing direction, even if the constraints of the target's possible movement (maximum acceleration and deceleration, turn radius, etc..) are known, is a god-awful ugly problem that may be ultimately unsolvable in many cases, and probably outside of your requirements. Sure, the Navy might need to know exactly where and when to put their torpedo in the water, but shit son, this is video games.
1

Share this post


Link to post
Share on other sites
I feel a bit like a moron now, but your math should actually do the right thing. (You of course have to take the player's actual velocity into account, because failing to do this will result in pointing in the correct general direction but not the right spot in time, if that makes sense. A good technique for checking your math is to try extreme cases; so compare the results of a player moving 1 pixel per hour to 100 pixels per second; in the latter case, it's pretty obvious that you have to multiply by the player velocity to get to the right target point. So your solution looks fine.)

Only possible mistake I see is the use of v2.magnitude in the middle of changing the components of v2; depending on how magnitude is computed, you might get bad answers when adjusting v2.b because the vector is already partially scaled the second time you ask for its magnitude. If nothing else, I would change this to store v2.magnitude in a temporary variable and divide a and b by that instead, just to make things clear in the code.
0

Share this post


Link to post
Share on other sites
An outside the box solution, which may not be what you are looking for, is to have an enemy that paths differently than other enemies. Performing flanking behavior essentially. That removes circling the enemies and creates some cool emergent behavior including the semblance of AI that has teamwork, even though the ai isn't really working together.

You could do something as simple as the way the pacman ghosts work. One ghost sets his navigation target to the player's position, one sets his target to a position behind the player, and one sets his target to a position in front of the player.

If you look at geometry wars enemies you'll get a good idea of how this effect works. With just the blue diamonds (enemies that just follow the player) you can easily fly in circles around the flock. Introducing the green squares (enemies that follow the player and are faster than the player, but avoid the player's bullets) the player now has to juggle the flocking behavior of two enemies. Then you add enemies who just wonder around aimlessly and now the player has to keep moving to avoid blue diamonds, keep herding the green squares to keep them from catching him, and dodge random floating pinwheels.

Your solution is just as viable, just making sure you account for other possible solutions that might also make your game interesting.
2

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0