Math question (2d trig)
Michael Weiss

I have a bit of a tricky math problem and I was wondering if anyone could provide insight.

Its about trigonometry and systems of equations.

This is all in 2D.

It is trivial to have an enemy shoot a bullet at the player. Simple trig.

But I want to have an enemy shoot a bullet, not at where the player is, but where they will be.
(assuming the player does not change velocity or direction)

My inputs are:
the player's position: px, py
the player's movement: pxinc, pyinc

the origin of the bullet: bx, by
the speed of the bullet: bspeed

What I want for an output is the angle of the bullet to ensure a collision
(or bxinc, byinc which I could calculate from angle)

Every method I can think of involves brute force, iterating through angles until I find a solution

There must be an more elegant solution.

I am trying to think of it as where two lines intersect...
But each line has a different velocity, so the line length are related to time...and speed?

Can anyone of you smart people help point me in the right direction?

DanielH

You need to find out at what time(t) will they collide.

Basic position function: S(t) = S(0) + v(t) * t + 1/2 * a(t) * t^2

S(0) = starting position
v(t) = velocity at time t (constant in your case)
a(t) = acceleration at time t (zero if velocity is constant)
t = time

S(t) = S(0) + v(t)t

Can be broken into x,y components:
Sx(t) = Sx(0) + v(t)t
Sy(t) = Sy(0) + v(t)t

What are the player's and bullet's positions?

Player:
Px(t) = px + pxinc * t
Py(t) = py + pyinc * t

Bullet:
Bx(t) = bx + bxinc * t
By(t) = by + byinc * t

this creates a triangle
{"name":"613141","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/6\/66721966b91c1742b7df294159bc4344.png","w":322,"h":372,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/6\/66721966b91c1742b7df294159bc4344"}613141

You can either use x or y

Px(t) = Bx(t) or Py(t) = By(t)

px + pxinc*t = bx + bxinc*t
px - bx = pxinc*t + bxinc*t
px - bx = t(pxinc - bxinc)
t = (px - bx)/(pxinc - bxinc)

You can use original formula to then solve for x and y of final position:
x(t) = px + pxinc*t = bx + bxinc*t
y(t) = py + pyinc*t = by + byinc*t

float findPosition(float &x, float &y, 
                  float px, float py, float pxinc, float pyinc,
                  float bx, float by, float bxinc, float byinc)
{
    float t = (px - bx)/(pxinc - bxinc);


    x = px + pxinc * t;
    y = py + pyinc * t;

    return t;
}

It's a mess. Hopefully I didn't miss anything.

Michael Weiss

Thank you for that. I am working on implementing it.
Time was the key. At what time will they collide?

UPDATE

Unfortunately I was unable to make your method work.

All I have for b is initial position and speed.
I do not have bxinc or byinc or the angle.
That is what I am trying to find.

The way I figured out how to do it was:

iterate on frame (time period) in a loop

for each frame find
- where we guess the player will be
- the distance from that position to the bullet origin
- find out how far the bullet could travel in the same amount of time

When those distances are equal (or close) that is where the will collide.
From the frame number that occurred at, I get the players position
That is where I shoot the bullet.

#SelectExpand
1void fire_enemy_bulletb(int EN, int bullet_ans, int p) 2{ 3 al_fixed bx = Efi[EN][0]; 4 al_fixed by = Efi[EN][1]; 5 al_fixed bspeed = Efi[EN][7]; 6 7 al_fixed px = players[p].PX; 8 al_fixed py = players[p].PY; 9 al_fixed pxi = players[p].xinc; 10 al_fixed pyi = players[p].yinc; 11 12 for (int i=1; i<100; i++) 13 { 14 px+=pxi; 15 py+=pyi; 16 17 // calc distance from player's new pos to bullet origin 18 al_fixed xlen = px - bx; // get the x distance between enemy and player 19 al_fixed ylen = py - by; // get the y distance between enemy and player 20 al_fixed hy_dist = al_fixhypot(xlen, ylen); // hypotenuse distance 21 22 // get distance that bullet would travel in same amount of time 23 al_fixed bd = bspeed * i; 24 25 // if they are close enough pull the trigger 26 al_fixed bdif = hy_dist-bd; 27 28 al_fixed ltol = al_ftofix(-5); 29 al_fixed utol = al_ftofix(5); 30 31 if ((bdif < utol) && (bdif > ltol)) 32 { 33 i = 100; // break out of loop 34 35 al_fixed speed = Efi[EN][7]; // speed 36 al_fixed scaler = al_fixdiv(hy_dist, speed); // get scaler 37 38 al_fixed xinc = al_fixdiv(xlen, scaler); // calc xinc 39 al_fixed yinc = al_fixdiv(ylen, scaler); // calc yinc 40 41 for (int z=0; z<50; z++) // find empty e_bullet 42 if (!e_bullet_active[z]) 43 { 44 e_bullet_active[z] = 1; 45 e_bullet_shape[z] = 1000 + bullet_ans; 46 e_bullet_fx[z] = Efi[EN][0]; 47 e_bullet_fy[z] = Efi[EN][1]; 48 e_bullet_fxinc[z] = xinc; 49 e_bullet_fyinc[z] = yinc; 50 z=50; 51 } 52 } 53 } 54}

This actually works, but I am sure there is a much better way of doing it.

UPDATE

This is the equation I have come up with:

https://d1cxvcw9gjxu2x.cloudfront.net/attachments/613142

Now the fun part!

Solve for t.

My skills are not up to the task...

Edgar Reynaldo

t and angle are related. If you change one, you change the other. You'll have to make an initial guess and hope it's efficient.

Michael Weiss

I had a method where I just increased time until I found a close enough solution.
That took a lot of iterations.
And if I wanted it more accurate, I would have to step time even slower, which meant even more iterations

I found a method where I search for t in large steps.
Then when I overshoot it, I reverse direction and decrease the step size...
I keep doing this until I get close enough.
This greatly reduces the amount of values of t I need to test.

#SelectExpand
1al_fixed get_distance(al_fixed px, al_fixed py, al_fixed pxinc, al_fixed pyinc, 2 al_fixed bx, al_fixed by, al_fixed b_speed, al_fixed t) 3{ 4 al_fixed px1 = px + al_fixmul(pxinc, t); // get the p position at time t 5 al_fixed py1 = py + al_fixmul(pyinc, t); 6 al_fixed p_distance_to_b = al_fixhypot(px1-bx, py1-by); // distance from p to b 7 al_fixed b_distance = al_fixmul(b_speed, t); // how far will b travel in time t 8 return (p_distance_to_b - b_distance); // difference between distances 9} 10 11void fire_enemy_bulleta(int EN, int bullet_ans, int p) 12{ 13 al_fixed bx = Efi[EN][0]; 14 al_fixed by = Efi[EN][1]; 15 al_fixed bspeed = Efi[EN][7]; 16 17 al_fixed px = players[p].PX; 18 al_fixed py = players[p].PY; 19 al_fixed pxi = players[p].xinc; 20 al_fixed pyi = players[p].yinc; 21 22 al_fixed f0 = al_itofix(0); // the number zero in fixed format 23 al_fixed t = f0; // start time 24 al_fixed tinc = al_itofix(20); // initial time step 25 al_fixed bdif = f0; 26 27 int tries = 0; 28 int done = 0; 29 while (!done) 30 { 31 t+=tinc; 32 bdif = get_distance(px, py, pxi, pyi, bx, by, bspeed, t); 33 if (( bdif < al_itofix(1)) && (bdif > al_itofix(-1))) done = 1; // is the difference with the threshold? 34 35 if (((tinc > f0) && (bdif < f0)) || // overshot while t increasing 36 ((tinc < f0) && (bdif > f0))) // overshot while t decreasing 37 tinc = al_fixdiv(tinc, al_itofix(-2)); // half the increment and reverse direction 38 39 if (tries++ > 100) done = 1; // break out in case something goes wrong 40 } 41 al_fixed px1 = px + al_fixmul(pxi, t); // get player target position based on t 42 al_fixed py1 = py + al_fixmul(pyi, t); 43 fire_enemy_bulletz(EN, bullet_ans, px1, py1); 44}

However I consider this entire approach an inelegant brute force method.

I can't help but think there is a better way of doing this.

My whole approach can be condensed to:

Find the time when the player's future position has an equal distance to the bullet origin as the distance the bullet will travel in the same amount of time.

Then it is trivial to get the player's future x and y position from the time.

I came up with an equation to describe that, but I don't know if it is possible to isolate t on one side (solve for t)
https://www.allegro.cc/files/attachment/613143

DanielH

Find the time when the player's future position has an equal distance to the bullet origin as the time the bullet will travel in the same amount of time.

Then it is trivial to get the player's future x and y position from the time.

That's what this function does. Returns time. Sets x and y as postion of collision.

float findPosition(float &x, float &y, 
                  float px, float py, float pxinc, float pyinc,
                  float bx, float by, float bxinc, float byinc)
{
    float t = (px - bx)/(pxinc - bxinc);


    x = px + pxinc * t;
    y = py + pyinc * t;

    return t;
}

If you only have bullet position and speed, we can calculate the angle and velocities

// bx,by bullet position
// x, y collision point
float findAngle(float bx, float by, float x, float y)
{
    return atan2(by - y, bx - x);
}

// you said you know the speed. get velocity from that
void calculateBulletVelocity(float &bxinc, floast &byinc, float angle, float speed)
{
    bxinc = speed * cos(angle);
    byinc = speed * sin(angle);
}

What was this about stepping time?

Let's say it take 2.47s seconds to collision, but your logic is only accurate to the tenth of a second. There might be a collision miss. Take the 0.07s difference and give the bullet a nudge in the direction.

Michael Weiss

I don't understand...

Your function 'findPosition' needs bxinc and byinc as an input.
I don't have those, that is what I am trying to find.

Then you say:

"If you only have bullet position and speed, we can calculate the angle and velocities"

In your function 'findAngle' where do you get x and y?
That is also what I am looking for, where the collision takes place.
If I knew that, the rest is trivial...

Its kind of like a chicken and egg thing here.

If I know exactly when the collision happens, I can figure out the rest.
If I know exactly where the collision happens, I can figure out the rest.

Am I missing something in your explanation? I cannot see how it would work.

DanielH

You're right. Chicken and egg.

I'll get back to you.

Edgar Reynaldo

Like I said, t and angle are related. You have to guess for one, and then solve for the other. You don't need to iterate anything.

The question (and answer) are actually more complicated than either of you are thinking. Solving for t involves solving a quadratic equation.

{"name":"613146","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/7\/9\/79dc84ef8bb6bdae06f90f2d63794299.png","w":3072,"h":2275,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/7\/9\/79dc84ef8bb6bdae06f90f2d63794299"}613146

I think what you really want though is to set a time of intercept, and solve for the angle necessary to hit the target. That's beyond me for the moment.

DanielH

a = distance bullet to collision
b = distance player to collision
c = distance bullet to player
A = angle at player
B = angle at bullet
C = angle at collision

1. make a line the player is travelling

// point 1 = px, py
// point 2 = px + pxinc, py + pyinc

// pick any x and give corresponding y
float getY(float x1, float y1, float x2, float y2, float x)
{
    // m = rise / run
    float m = (y2 - y1) / (x2 - x1);

    // y = mx + b, b = y - mx 
    float b = y1 - m * x1;

    return (m * x + b);
}

now pick any point on that line ax, ay

float ax = 100f;
float ay = getY(px, py, px + pxinc, py + pyinc, ax);

1. calculate number of iterations of pxinc, pyinc to get to point (k)
2. calculate number of iterations of bxinc, byinx to get to point (l)

What is ratio?

float pspeed = sqrt(pxinc^2 + pyinc^2);
// already have bullet speed
float k = (sqrt((px - ax)^2 + (py - ay)^2)))/pspeed;
float l = (sqrt((bx - ax)^2 + (by - ay)^2)))/bspeed;
float ratio = l/k;
// save for later

calculate angle between 2 lines
cos(angle) = dotproduct(v1,v2) / (magnitude(v1)*magnitude(v2))
v1 = <bx - px, by - py>
v2 = <bx - ax, by - ay>

#SelectExpand
1// line 1 - 1 to 2 2// line 2 - 3 to 2 3// point 2 is the shared point 4float calcAngle(float x1, float y1, float x2, float y2, float x3, float y3) 5{ 6 float vx = x1 - x2; 7 float vy = y1 - y2; 8 float zx = x3 - x2; 9 float zy = y3 - y2; 10 11 float dot = vx * zx + vy * zy; 12 float magv = sqrt(vx^2 + vy^2); 13 float magz = sqrt(zx^2 + zy^2); 14 15 return dot/(magv * magz); 16} 17 18// first calculate angle at player 19float angleA = calcAngle(pxinc, pyinc, px, py, bx, by); 20 21// calculate ratioed angle of temp point and divide by ration to get full angle 22float angleB = calcAngle(ax, ay, bx, by, px, py) / ratio; 23 24// difference is angle C 25float angleC = 180.0f - (angleA + angleB);

Use law of sines to calculate the rest

sin(C)/c = sin(A)/a = sin(B)/b

we know c
a = csin(A)/sin(C)
b = csin(B)/sin(C)

!!!!WARNING!!!!
this may all be wrong as I have no way of verifying at the moment.

Michael Weiss

Edgar, I can't just set a time and figure out the angle.

Well maybe I could if I could adjust the speed of the bullet.
But I can't, that is fixed.

There is a solution (actually two).

An exact time when the bullet fired will hit where the player will be be.

I can easily find the solution, my code works perfectly.

The equation that I posted earlier describes the conditions accurately.

I just don't have the mathematical skill to solve it for t.

So I have to try different values of t until I get close enough.

I don't claim that my solution is the only one. (or even a good one)
But I know that it works.

My math skills are limited, maybe that equation I posted does not have any easy way to isolate t.

Or maybe there is a completely different approach that I have not even thought of.

I just don't see how I can pick a value for t and then figure out the angle.

EDIT

OK maybe there is some misunderstanding here.
By time, I mean how long it will take the fired bullet to collide.

The time that the bullet is fired is always t=0, the speed is constant,
we know where the bullet originates...
All that is needed is what direction to fire to ensure a collision.

Edgar Reynaldo

Michael, assuming your theory and your math is correct, I solved for t. You'll still have to apply the quadratic equation to solve it though.

 t^2(pvx^2 + pvy^2 - bv^2)
+t^1(2pxpvx + 2pypvy - 2bxpvx - 2bypvy)
+t^0(px^2 + bx^2 + py^2 + by^2 - 2bxpx - 2bypy)

Just apply the quadratic equation now, and you have your values for t.

I'm going to work on finding angle from t. My approach would be to set a time (like say a few seconds) and then find the angle necessary to hit that time.

Peter Hull

I came up with a quadratic but not quite the same as ER's. It cuts down on the maths chores if you set the origin to be where the bullet starts, and have the player relative to that, ie. work with x = px - bx and y = py - by instead of (px,py) and (bx,by).

The position of the player at time t is (x + pxinc *t, y + pyinc * t) and the bullet is (bxinc*t, byinc*t). Equate the x-coords and y-coords separately, that's three unknowns, bxinc, byinc and t, with two equations - now add third equation bxinc^2 + byinc^2 = bspeed^2.

bxinc*t = x + pxinc*t (1)
byinc*t = y + pyinc*t (2)
bxinc^2 + byinc^2 = bspeed^2 (3)

I found it easiest to rewrite (3) as
bxinc^2 * t^2 + byinc^2 * t^2 = bspeed^2 * t^2 (4)

Square (1) and (2), substitute them in the LHS of (4)
(x + pxinc*t)^2 + (y + pyinc*t)^2 = bspeed^2 * t^2 (5)

Now you can expand the brackets and it's a quadratic in t. There are 2 solutions usually and you have to take the bigger (I don't know why or what the other one means!)
[edit] OK actually it should be the smallest one that is >= 0. If both are negative then the shot is impossible.

When you have t then work out dx = x + pxinc*t and dy = y + pyinc*t (displacement to where the ship will be)
then bxinc = dx/sqrt(dx*dx+dy*dy)*bspeed and byinc = dy/sqrt(dx*dx+dy*dy)*bspeed

Example code

#SelectExpand
1#include <allegro5/allegro.h> 2#include <allegro5/allegro_primitives.h> 3#include <math.h> 4#include <random> 5 6#define W 800 7#define H 600 8 9static const float bullet_speed = 5.0f; 10 11struct thing { 12 float x; 13 float y; 14 float dx; 15 float dy; 16 float radius; 17 ALLEGRO_COLOR color; 18 float speed; 19 bool active; 20 thing(ALLEGRO_COLOR c, float r, float s) 21 : color(c), radius(r), speed(s), active(true) {} 22 void move() { 23 if (active) { 24 x += dx; 25 y += dy; 26 while (x < 0.0f) 27 x += float(W); 28 while (x >= float(W)) 29 x -= float(W); 30 while (y < 0.0f) 31 y += float(H); 32 while (y >= float(H)) 33 y -= float(H); 34 } 35 } 36 void draw() { 37 if (active) 38 al_draw_circle(x, y, radius, color, 1.0f); 39 } 40 void setup() { 41 static std::minstd_rand engine; 42 double theta; 43 x = std::uniform_real_distribution<float>(0.0f, float(W))(engine); 44 y = std::uniform_real_distribution<float>(0.0f, float(H))(engine); 45 theta = std::uniform_real_distribution<>(-1.0, 1.0)(engine); 46 switch (std::uniform_int_distribution<>(0, 3)(engine)) { 47 case 0: // top 48 theta += M_PI / 2.0; 49 y = 20.0f; 50 break; 51 case 1: // right 52 theta += M_PI; 53 x = float(W - 20); 54 break; 55 case 2: // bottom 56 theta -= M_PI / 2.0; 57 y = float(H - 20); 58 break; 59 case 3: // left 60 default: // can't happen 61 x = 20.0f; 62 break; 63 } 64 dx = float(cos(theta)) * speed; 65 dy = float(sin(theta)) * speed; 66 active = true; 67 } 68}; 69 70thing fire(const thing &from, const thing &to) { 71 float x = to.x - from.x; 72 float y = to.y - from.y; 73 float r2 = x * x + y * y; 74 75 thing bullet(al_map_rgb(128, 128, 128), 2.0f, bullet_speed); 76 float A = to.dx * to.dx + to.dy * to.dy - bullet_speed * bullet_speed; 77 float B = x * to.dx + y * to.dy; 78 float rt = B * B - A * r2; 79 if (rt >= 0.0f) { 80 float t = (sqrt(rt) - B) / A; 81 float t_alt = (-sqrt(rt) - B) / A; 82 if (t < 0.0f) { 83 t = t_alt; 84 } else { 85 if (t_alt >= 0.0f) { 86 t = std::min(t, t_alt); 87 } 88 } 89 if (t >= 0.0f) { 90 float vx = x + to.dx * t; 91 float vy = y + to.dy * t; 92 float v = sqrt(vx * vx + vy * vy) / bullet_speed; 93 bullet.dx = vx / v; 94 bullet.dy = vy / v; 95 bullet.x = from.x; 96 bullet.y = from.y; 97 return bullet; 98 } 99 } 100 // Bullet can't reach the target 101 bullet.active = false; 102 return bullet; 103} 104 105bool collide(const thing &a, const thing &b) { 106 float r2 = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); 107 return r2 < a.radius + b.radius; 108} 109 110int main(int, char *[]) { 111 al_init(); 112 al_init_primitives_addon(); 113 ALLEGRO_DISPLAY *display = al_create_display(W, H); 114 ALLEGRO_TIMER *timer = al_create_timer(1.0 / 30.0); 115 ALLEGRO_EVENT_QUEUE *queue = al_create_event_queue(); 116 al_register_event_source(queue, al_get_display_event_source(display)); 117 al_register_event_source(queue, al_get_timer_event_source(timer)); 118 bool running = true; 119 bool advance = true; 120 thing ship(al_map_rgb(255, 128, 128), 10.0f, 1.0f); 121 thing ufo(al_map_rgb(128, 255, 128), 10.0f, 2.0f); 122 thing bullet(al_map_rgb(128, 128, 128), 2.0f, 5.0f); 123 ship.setup(); 124 ufo.setup(); 125 bullet.active = false; 126 al_start_timer(timer); 127 while (running) { 128 ALLEGRO_EVENT event; 129 al_wait_for_event(queue, nullptr); 130 while (al_get_next_event(queue, &event)) { 131 if (event.type == ALLEGRO_EVENT_DISPLAY_CLOSE) { 132 running = false; 133 } else if (event.type == ALLEGRO_EVENT_TIMER) { 134 advance = true; 135 } 136 if (advance) { 137 al_clear_to_color(al_map_rgb(0, 0, 0)); 138 ufo.draw(); 139 bullet.draw(); 140 ship.draw(); 141 al_flip_display(); 142 ufo.move(); 143 bullet.move(); 144 ship.move(); 145 if (!bullet.active) { 146 bullet = fire(ufo, ship); 147 } else { 148 if (collide(bullet, ship)) { 149 ship.active = bullet.active = false; 150 } 151 } 152 if (!ship.active) 153 ship.setup(); 154 } 155 } 156 } 157 return 0; 158}

The fire function is the important bit, all the rest is fluff to provide a runnable demo

Michael Weiss

Wow!

Thanks to all you guys for your help and insights.

I am going to try to work through them, but it will take some time.

I spent a few hours adding a page to my documentation where I describe my approach in great detail.

https://mweiss001.github.io/bullets.html

I hope to understand the answers I have gotten from you guys and update my bullet page. (with credits due to all who helped)

Thanks again!

I am in awe of the level of technical knowledge here!

UPDATE

I tried Edgar's solution and it worked perfectly...
I guess my math skills are not what they could be.

Thank you Edgar! You are so smart and helpful.
Sorry I didn't understand your answer when you first posted it.

Here is how I patched it into my code.
(for testing only, later I will redo it with fixed numbers)

#SelectExpand
1void fire_enemy_bulleta(int EN, int bullet_ans, int p) 2{ 3 float bx = Efi[EN][0]; 4 float by = Efi[EN][1]; 5 float bv = Efi[EN][7]; 6 float px = players[p].PX; 7 float py = players[p].PY; 8 float pvx = players[p].xinc; 9 float pvy = players[p].yinc; 10 11 float A = (pvx*pvx) + (pvy*pvy) - (bv*bv); 12 float B = 2*(px*pvx) + 2*(py*pvy) -2*(bx*pvx) -2*(by*pvy); 13 float C = (px*px) + (bx*bx) + (py*py) + (by*by) - 2*(bx*px) -2*(by*py); 14 float t = ( -B - sqrt((B*B) - 4*(A*C)) ) / (2 * A); 15 16 al_fixed px1 = px + al_fixmul(pvx, al_ftofix(t)); // get player target position based on t 17 al_fixed py1 = py + al_fixmul(pvy, al_ftofix(t)); 18 fire_enemy_bulletz(EN, bullet_ans, px1, py1); 19}

Peter Hull

Good stuff. If you take your final equation, square both sides and substitute x = px - bx and y = py - by then it's the same as my equation (5) so I think we agree. Which is a relief!

Michael Weiss

Peter, I worked through your solution and it works just the same.
Like you said, the math is slightly simpler.

Thank you for all the time and effort you put into helping me.

EDIT

I have fully implemented this new bullet firing strategy.
And updated my documentation at:
https://mweiss001.github.io/purple_martians/bullets

Edgar Reynaldo

You will have to check your code for division by A=0 and for a negative B^2 - 4AC discriminant.

I am coming up with a different, more general solution. I'll let you know when it's done.

It's taken me about a week to get the math right but I think I have it. t from theta and theta from t.

{"name":"613155","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/d\/8d3e173992e3fdfc9e2b91ce552c5926.png","w":3072,"h":4096,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/d\/8d3e173992e3fdfc9e2b91ce552c5926"}613155

So everything is derived from Dx(t) and Dy(t), the x and y distance between the player and the projectile based on time.

(0a) DX(t) = dx + pvx*t - bvz*t*cos(theta) = 0
(0b) DY(t) = dy + pvy*t - bvz*t*sin(theta) = 0

dx and dy are the starting distance between the player and the launcher. pvx and pvy are the x and y velocity of the player. bvz is the magnitude of the velocity of the projectile. t is time and theta is the angle of the launcher's aim.

Since we need the x and y distance between the projectile and the player to be 0 we can set them equal to zero and henceforth equal to each other. Then it is a matter of separating t and theta depending on which we want to solve for.

The base equation is thus :

(1) bvz*t*(cos(theta) - sin(theta)) = (pvy - pvx)*t + (dy - dx)

Solve 0b for sin(theta) and cos(theta) and then form tan(theta) using the two as sin(theta) / cos(theta). Then take the arctangent (2) of both sides and you have the angle necessary. You can also solve for t in one and substitute in the other.

UPDATE
So the formulas for the angle at time t are as follows :

(I wish Matthew would fix those darn MathML thingies or Latex or w/e it was.)

sin(theta) = (dy + pvy*t)/bvz*t

cos(theta) = (dx + pvx*t)/bvz*t

tan(theta) = ((dy/bvz*t + pvy/bvz) / (dx/bvz*t + pvx/bvz)) = DY/DX

Just send that mess to atan2 as atan2(DY,DX);.

And then similarly you can also solve for t from a given angle to aim at and it will tell you if it is possible or not.

I think the equation is this : (I've been staring at this all week)

t^2 * (pvx-pvy)^2 - bvz^2 * (1 - sin(2*theta)) +
t^1 * 2*(pvy-pvy)(dx-dy) +
t^0 * (dx - dy)^2

Then you have another quadratic equation.
\frac{-B +/-sqrt(B^2 - 4AC)}{2*A}

I will try to explain better later. Don't want the thread to lock.

DanielH

If player is headed directly to or directly away, the following won't work

Take your 3 points and make a triangle

{"name":"613158","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/7\/a7bdfc4beef455bda1d9bdcb5684873a.png","w":615,"h":355,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/7\/a7bdfc4beef455bda1d9bdcb5684873a"}613158

point p = player
point b = bullet
point x = collision (unknown)

side a = p to x, distance = t * pv
side b = b to x, distance = t * bv
side c = p to x, distance we can calculate = sqrt((bx - px)^2 + (by - py)^2)

divide all 3 by time (t) to make it easier later on

a = pv, which we know
b = bv, which we know
c = sqrt((bx - px)^2 + (by - py)^2)/t

angles
B = we can calculate using "angle between two vectors" formula

v1 = (bx - px, by - py)
v2 = (pvx, pvy)

cos(angle) = (v1 . v2)/(||v1||||v2||) // dot product divided by magnitudes

dot product:
(v1 . v2) = v1.x * v2.x + v1.y * v2.y

magnitude:
||v1|| = sqrt(v1.x^2 + v1.y^2)
||v2|| = sqrt(v2.x^2 + v2.y^2)

Law of Sines
sin(B)/b = sin(A)/a = sin(C)/c

sin(B)/b = sin(A)/a
rearrange
sin(A) = asin(B)/b
A = arcsin(asin(B)/b)

we know B, b and a so calculate A

Use to A and B to calculate final angle C

C = pi - A - B (or 180deg - A - B)

Law of cosines
c^2 = a^2 + b^2 - 2abcos(C)

((bx - px)^2 + (by - py)^2)/t^2 = pv^2 + bv^2 - 2*pv*bv*cos(C)

t^2 = ((bx - px)^2 + (by - py)^2) / (pv^2 + bv^2 - 2*pv*bv*cos(C))

t = sqrt(((bx - px)^2 + (by - py)^2) / (pv^2 + bv^2 - 2*pv*bv*cos(C)))

My head hurts!

Edgar Reynaldo

DanielH
I'm trying to follow your math. Yeah, it makes me dizzy too. ;p

I'm writing a simple game to test my theories. Don't want the thread to lock! :X

DanielH

This is what I was referring to.

{"name":"613172","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/6\/a60603168a8cc3dee45134ec2332f6df.png","w":616,"h":574,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/6\/a60603168a8cc3dee45134ec2332f6df"}613172

***** this graph only works if bullet is to the right of player, Would need alteration otherwise, bullet speed must also not be too low or will never reach player ******

What you can adjust:
A is angle relative to B (not absolute)
p1 is player
p2 is bullet start
v1 is player speed
v2 is bullet speed

Other stuff below that:
j = horizontal difference bullet to player
k = vertical difference bullet to player
l = distance bullet to player
F = angle relative to x axes
B = bullet angle from player to collision
C = collision angle from player to bullet
c = distance using speed (player and bullet) alone
t = actual distance / speed distance = number of iterations until collision
p3 and p4 is the point of collision using absolute angles from p1 and p2 respectively

Edgar Reynaldo

I've been trying to solve this myself and I just can't get it right. I come up with something different every time, and even when I plug in the equation I came up with for Michael Weiss it still doesn't work. My times are negative always.

DanielH

Sometimes I struggled with these problems as well. Then something clicked.

Edgar Reynaldo

I know this part is right.

(0a) DX(t) = dx + pvx*t - bvz*t*cos(theta) = 0
(0b) DY(t) = dy + pvy*t - bvz*t*sin(theta) = 0

sin(theta) = (dy + pvy*t)/bvz*t

cos(theta) = (dx + pvx*t)/bvz*t

tan(theta) = ((dy/bvz*t + pvy/bvz) / (dx/bvz*t + pvx/bvz)) = DY/DX

This is the angle at time t. But t is still unknown.

So go back to 0a and 0b. Solve for t. I did that, like 5 times. I came up with something different like three times. Grr. I've got a little demo setup that has a plane and a tank and the tank shoots at the plane, but t is negative.

Now, next (just now) I read carefully through your last explanation. I follow most of it, but how can you possibly calculate v2.x and v2.y??? You don't know the angle to shoot at! So that leaves B undefined and the whole mess falls apart.

After that I visited your link. Neat tutorial. Neat diagram. How do they calculate A? Do they define theta (the angle the bullet travels) ? That's v2.x and v2.y, which is unknown.

I'm missing something.

:-[

DanielH

Similar triangles

Assumptions: bullet speed should be known even if we don't know direction. Normally a constant.

Small triangle sides:
a = known = player speed
b = known = bullet speed - direction unknown but irrelevant at this point
c = unknown

Small triangle angles:
A = known
B = unknown
C = unknown

Big triangle sides:
a = t * player speed
b = t * bullet speed
c = distance p to b

Using small triangle, solve the rest.

Law of Sines:
sin(A)/a = sin(B)/b = sin(C)/c

Since we know b, use it to solve for B.
B = arcsin(b * sin(A) / a)

Solve C
C = 180 - A - B

Law of cosines:
c^2 = a^2 + b^2 - 2ab*cos(C)
c = sqrt(a^2 + b^2 - 2ab*cos(C))

Time t is the ratio of c from large triangle to c from small triangle.

t = large c / small c

The angles are relative to each and not absolute to the x/y axes. In my example, I added the offset.

Edgar Reynaldo

I mostly understand your code, but I don't know where you are getting bv.x and bv.y from for your cos angle trick.

Bump so the thread doesn't close. >:(

DanielH

Here is the link again.

Going down the list line by line:

1 through 5 are adjustable. You can manually change or drag the points around.

1. p1 is player position
2. p2 is bullet position
3. A is angle player is traveling (relative to the line p1 to p2 not the x axis)
4. v1 is player speed
5. v2 is bullet speed

make an imaginary triangle
6. j is horizontal distance p2 to p1
7. k is vertical distance p2 to p1
8. l is absolute distance p2 to p1

9. F is angle from x axis to the line p2 to p1

10 I meant to remove (it is duplicated at line 18)

11. calculate B - using the similar triangle method I described earlier (law of sines)
12. calculate C
13. calculate c of smaller similar triangle where a = pv and b = bv and using C (law of cosines)
14. calculate time t based of the two similar c's, where l is c from big triangle

Next 2 lines 15 and 16 I calculate collision point using both A and B
(A + F) is absolute angle to x axis of player to collision
(180 - B + F) is absolute angle to x axis of bullet to collision
I have 90 + 90 - (B - F) so I could visualize it in my head while I was doing it. Starting at 90 how much to add 90 - (B - F).

{"name":"613192","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/0\/e07b47d697607193b4119438b8663fd2.png","w":576,"h":538,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/0\/e07b47d697607193b4119438b8663fd2"}613192

15. calculate point p3 = player + time * speed * angle
16. calculate point p4 = bullet + time * speed * angle

this part of that is where we get bv.x and bv.y
bv.x = bv * cos(180 - B + F)
bv.y = bv * sin(180 - B + F)

p4.x = bullet.x + time * bv.x
p4.y = bullet.y + time * bv.y

17, 18 and 19 are lines drawn between the points with limits put in

Edgar Reynaldo

I don't see which triangles are similar. Can you let me know?

I finally gave up and tried the equation I provided to Michael based on his formula and it works perfectly. I now have a little tank shooting down an airplane. I don't know if I'll develop it further, but at least now I have proof of concept.

DanielH

2 triangles.

The "big" triangle has 3 sides.

Side a is a vector where start is player and end is collision
Length a = time * player speed

Side b is a vector where start is bullet and end is also collision.
Length b = time * bullet speed

Side c is a vector where start is player and end is bullet

We don't know time so we can't calculate a or b. We can calculate c with distance formula.

"Small" triangle is a similar triangle where all sides lengths are divided by time
a = player speed
b = bullet speed
c = unknown

In my example I used trig to calculate small c. Then take ratio of big c to little c to calculate time.

Michael Weiss

Wow! I have been away for a while and I come back to find all this cool discussion.

When I have time I will see if I can wrap my head around these new concepts.

Thank you all for working on my little math problem.
I find the discussion fascinating....

I was pretty sure there were multiple ways to get the answer.

Thread #618631. Printed from Allegro.cc