Collision point of 2 curves in a 3d-room_问答_开发者

i am programming a small game for quite some time. We started coding a small FPS-Shooter inside of a project at school to get a bit experience using directX. I dont know why, but i couldnt stop the project and started programming at home aswell. At the moment i am trying to create some small AI. Of cause thats definatlly not easy, but thats my personal goal anyways. The topic could prolly fill multiple books hehe. I've got the walking part of my bots done so far. They walk along a scriped path. I am not working on the "aiming" of the bots. While programming that i hit on some math problem i couldnt solve yet. I hope of your input on this to help me get further. Concepts, ideas and everything else are highly appreciated.

Problem: Calculate the position (D3DXVECTOR3) where the curve of the projectile (depends on gravity, speed), hit the curved of the enemys walking path (depends on speed). We assume that the enemy walks in a constant line.

Known variables:

float projectilSpeed = 2000 m/s //speed of the projectile per second
float gravitation = 9.81 m/s^2 //of cause the gravity lol
D3DXVECTOR3 targetPosition //position of the target stored in a vector (x,y,z)
D3DXVECTOR3 projectilePosition //position of the projectile
D3DXVECTOR3 targetSpeed //stores the change of the targets position in the last second

Variabledefi开发者_运维百科nition

ProjectilePosition at time of collision = ProjectilePos_t
TargetPosition at time of collision = TargetPos_t
ProjectilePosition at time 0, now = ProjectilePos_0
TargetPosition at time 0, now = TargetPos_0
Time to impact = t
Aim-angle = theta

My try: Found a formular to calculate "drop" (Drop of the projectile based on the gravity) on Wikipedia:

float drop = 0.5f * gravity * t * t

The speed of the projectile has a horizontal and a vertical part.. Found a formular for that on wikipedia aswell:

ProjectilVelocity.x = projectilSpeed * cos(theta)
ProjectilVelocity.y = projectilSpeed * sin(theta)

So i would assume this is true for the projectile curve:

ProjectilePos_t.x = ProjectilePos_0.x + ProjectileSpeed * t
ProjectilePos_t.y = ProjectilePos_0.y + ProjectileSpeed * t + 0.5f * gravity * t * t
ProjectilePos_t.z = ProjectilePos_0.z + ProjectileSpeed * t

The target walk with a constant speed, so we can determine his curve by this:

TargetPos_t = TargetPos_0 + TargetSpeed * D3DXVECTOR3(t, t, t)

Now i dont know how to continue. I have to solve it somehow to get a hold on the time to impact somehow. As a basic formular i could use:

float time = distanz / projectileSpeed

But that wouldnt be truly correct as it would assume a linear "Trajectory". We just find this behaivor when using a rocket.

I hope i was able to explain the problem as much as possible. If there are questions left, feel free to ask me!

Greets from germany, Frank

Edit:

The main problem is that i cant calculate the enemies position at collision time as i dont have the time passed until the collision occurs.. And on the other hand i cant calculate the time without knowing the enemies location at impact time. Maybe an iterative method solves this.

curve enemy:

pos(t).x = pos(0).x + speed.x * time
pos(t).y = pos(0).y + speed.y * time
pos(t).z = pos(0).z + speed.z * time

curve projectile: pos(t).y = pos(0).y + sin(theta) * speed + 0.5 * gravity * time * time

pos(t).x and pos(t).z not sure how to calculate in (x and z) define the forward direction basically.. not just x..

cant calculate the enemy without knowing the time.. and i cant calculate the time without knowing the angles (theta, pitch/yaw) and the distance it will be to the "future" impact point

Not a complete solution but how I would approach this from a mathemtical point of view.

You have two objects that you want to meet. The three unknowns you need to find are time at which the hit occurs, vertical angle of shot and horizontal angle of shot.

You know the position of the target at any time t just by saying

position = initial position + t*velocity

(in vectors here).

The position of the projectile will be:

position = initial position + t*(initial velocity) + 0.5*acceleration*t^2

(again vectors so the initial velocity here will be dependant on the two angles of the shot)

When we get a hit obviously these two positions will be the same so we can equate these two positions.

We know have a vector equation with three unknowns effectively. If we then split it into its component vectors then each of those equations holds for just the x, y and z components of the vectors (note that acceleration only has a component in the z direction).

We then get three equations with three unknowns that will be solved simultaneously. The main reason I am going to leave the rest to you is because I have no idea how I'd represent the algebra in my answer in a nice way. :)

Sorry this isn't more complete but hopefully may give you a new way of looking at things and you might be able to work through the maths yourself to solve the equations yourself (not hard but at the same time not that easy...)

first of all, as you're going with C++, it's really worth using the overloaded arithmetic operators and thus vector operations extensively. Your formulae are going to look much cleaner and closer to the mathematical definitions. You're rarely going to ever need explicit .x, .y assignments at all.

So now to your question:

The main problem is that i cant calculate the enemies position at collision time as i dont have the time passed until the collision occurs

Yes, time is the way to go.

Imagine you shoot in every possible direction at the same time. All projectiles will form an expanding sphere somewhere in the air at any given time. You can now intersect this spheres with the path of the target and get times when a hit can occur. Maths for this is just a bit tricky (solving polynomial equations of degree four), but it works well with approximation.

As you're German, you should definitely take a look at this german article that covers the topic nicely!

If the enemy is walking at a constant velocity (ie. in a straight line), the simplest way is to change variables so that you write everything in the moving frame of the enemy. Then, you have a quadratic equation to solve.

But in the real world, there are many enemies, and when you shoot, you have to test whether your bullet at time t intersects some enemy shape (enemies are not points). So you fire your bullet, simulate its trajectory with fast ODE solver: Runge Kutta 4th order is commonly used I think, not for its accuracy (you have no easy control of the error, and you don't need physical accuracy: only realism. Don't use RK4 for solving ODEs except in video games) but because you can take relatively large time steps without being too off.

Actually, simulating the physics of the game (players and enemies physics and IA, bullets, ...) requires you to keep track of time. You then iterate over the bullets and test for their intersection with various objects of the game (mainly enemies).

At each time, the typical way to compute intersections is to use an octree to keep track of where the objects are. At a given time, this device enables you to locate easily (log n) the enemies which lie in the same region of space as the bullet. Now, you can use:

Bounding elementary shapes (boxes, spheres) for the enemy which deal with a lot of the cases when the bullet hits or hits not the enemy: put boxes outside the enemy shape, and inside.
When bounding boxes tell you nothing (you pass through one outer box, but do not intersect any inner box), you have to work out the intersection of a small straight line (between t and t + dt, with dt not that small) with the enemy shape.