Author Topic: Trigonometry help needed!  (Read 1526 times)

InCreator

  • Posts: 3,168
  • Useless since 2003
    • I can help with AGS tutoring
    • I can help with animation
    • I can help with backgrounds
    • I can help with play testing
Trigonometry help needed!
« on: 20 Feb 2012, 07:19 »
Making a top-down car game (with Game Maker).
What I totally suck at, is physics/trigonometry.

Let the picture explain:


So, both cars are simple rectangular sprites (let's say 32x64px) and rotated about center point (origin) (xy on image).
At some point they collide. Not important which way, which point or what angle are they at. On picture, there's just a random example.
How to return this precise location where collision occurs?

Here's something to simplify this: Both cars have 4 corner points, and collision happening point is always at one of those 8 points.
T-shaped or otherwise full edge-to-edge collisions do not count, or at least they are not important to me. All I need is at least one colliding point.

I imagine it can be solved by dividing them into triangles and using phytagoras' theorem or something, or it's some kind of newtonian physics that makes it simple, but I have no clear idea how.

Any kind of pseudocode or formula should do... can anyone help?
« Last Edit: 20 Feb 2012, 09:34 by InCreator »

Wyz

  • Posts: 1,279
  • anno 1986
    • I can help with making music
    • I can help with story design
    • I can help with translating
    • I can help with voice acting
    • I can help with web design
Re: Trigonometry help needed!
« Reply #1 on: 20 Feb 2012, 14:30 »
I try to solve everything these days with congruence since it is 100 times faster then using trigonometric functions.
I might have an idea how to do this but I'm not sure if it will be correct but it's worth the try.
Since you already know the two objects collide you only need to find the closest point to the collision area. This you can do with vectors.

First you'd need the vector of the collision itself:
Code: Adventure Game Studio
  1. col.xy = car2.xy - car1.xy
  2.  

Then you calculate the vectors for the corner points
Code: Adventure Game Studio
  1. car1.c1 = car1.w/2 , car1.h/2
  2. car1.c2 = -car1.w/2 , car1.h/2
  3. car1.c3 = -car1.w/2 , -car1.h/2
  4. car1.c4 = car1.w/2 , -car1.h/2
  5.  

We can use the dot products of two vector to get a score how much they are alike:
Code: Adventure Game Studio
  1. function normalize(v)
  2. {
  3.   var n = sqrt(v.x*v.x + v.y*v.y)
  4.   return v / n
  5. }
  6.  
  7. function compare(v1,v2)
  8. {
  9.   v1 = normalize(v1)
  10.   v2 = normalize(v2)
  11.   var dot = v1.x*v2.x + v1.y*v2.y
  12.   return abs(dot)
  13. }
  14.  

Now we compare every corner, first for car1:
Code: Adventure Game Studio
  1. s1c1 = compare(col, car1c1);
  2. s1c2 = compare(col, car1c2);
  3. s1c3 = compare(col, car1c3);
  4. s1c4 = compare(col, car1c4);
  5.  

For car two we have to flip the collision vector:
Code: Adventure Game Studio
  1. s2c1 = compare(-col, car2c1);
  2. s2c2 = compare(-col, car2c2);
  3. s2c3 = compare(-col, car2c3);
  4. s2c4 = compare(-col, car2c4);
  5.  


Find the sXcY value that is the smallest and if my method works that will give you the colliding corner.

There are a few things that can be optimized: you don't have to recalculate the corner vectors because they don't change, already use normalized vectors everywhere so you don't have to recalculate that for each compare, and keep and keep track of the minimum so far when comparing vectors. Let em know if it works. :)
« Last Edit: 20 Feb 2012, 17:40 by Wyz »
Life is like an adventure without the pixel hunts.

InCreator

  • Posts: 3,168
  • Useless since 2003
    • I can help with AGS tutoring
    • I can help with animation
    • I can help with backgrounds
    • I can help with play testing
Re: Trigonometry help needed!
« Reply #2 on: 20 Feb 2012, 16:22 »
Quote
car1.c1 = car1.w/2 , car1.h/2

Hm, you're treating variable here like it could have two values I guess? Like c1 = 4,3?
I'll need to undo this first. Actually, I do have corner point coordinates kept in separate variables anyway.

Or maybe it's something waaaay out of my league :/

Quote
function normalize(v)
{
  var n = sqrt(v.x*v.x + v.y*v.y)
  return v / v
}

it returns... 1?
« Last Edit: 20 Feb 2012, 16:27 by InCreator »

Snarky

  • Global Moderator
  • Posts: 6,750
  • Private Insultant
    • I can help with proof reading
    • I can help with translating
Re: Trigonometry help needed!
« Reply #3 on: 20 Feb 2012, 16:34 »
Quote
function normalize(v)
{
  var n = sqrt(v.x*v.x + v.y*v.y)
  return v / v
}

it returns... 1?

It should be:

Code: Adventure Game Studio
  1. return v / n;

(The semi-colon key break on your keyboard, Wyz?)

Wyz

  • Posts: 1,279
  • anno 1986
    • I can help with making music
    • I can help with story design
    • I can help with translating
    • I can help with voice acting
    • I can help with web design
Re: Trigonometry help needed!
« Reply #4 on: 20 Feb 2012, 17:42 »
oh geez how did that happen?  ::)

Well it's fixed now.
(The semi-colon key break on your keyboard, Wyz?)
The pseudo code I use resembles ECMA script a lot, and that doesn't need semicolons when there are line breaks  ;)
Life is like an adventure without the pixel hunts.

Khris

  • Posts: 10,676
  • having to deal with what games are going through
    • Lifetime Achievement Award Winner
    • I can help with play testing
    • I can help with scripting
    • I can help with translating
    • Khris worked on a game that was nominated for an AGS Award!
Re: Trigonometry help needed!
« Reply #5 on: 20 Feb 2012, 19:04 »
Just out of curiosity, are you also looking for a collision detection algorithm? Or is GameMaker already handling this?

InCreator

  • Posts: 3,168
  • Useless since 2003
    • I can help with AGS tutoring
    • I can help with animation
    • I can help with backgrounds
    • I can help with play testing
Re: Trigonometry help needed!
« Reply #6 on: 20 Feb 2012, 21:57 »
It's already handled, with a wide range from bounding boxes to pixel-perfect. All it doesn't do is xy of collision point, not ever approximate.

InCreator

  • Posts: 3,168
  • Useless since 2003
    • I can help with AGS tutoring
    • I can help with animation
    • I can help with backgrounds
    • I can help with play testing
Re: Trigonometry help needed!
« Reply #7 on: 21 Feb 2012, 13:12 »
I'm rather unsure how to implement Wyz' suggestion and from what I've googled, Oriented-Bounding-Box intersection stuff is something people write papers about and get doctorates for, not something you can squeeze out in an afternoon.

To hell with this.

I'm going to simply define 8 points around car, and during collision, check which two points were closest, then divide the distance and drop some sparks there. Shouldn't be too hard. Sprites are rather tiny anyway.

Kweepa

  • Posts: 3,332
  • Mutated Guano Deviser
    • Best Innovation Award Winner 2009, for his modules and plugins
    • Kweepa worked on a game that was nominated for an AGS Award!
Re: Trigonometry help needed!
« Reply #8 on: 21 Feb 2012, 14:44 »
This is conceptually quite simple.
You just need the corner that is inside the bounding box of the other car.
Each side of car A can be used as a clip plane to reject a corner of car B. If a corner passes all four planes, it's inside.

Code: Adventure Game Studio
  1.  
  2. struct SCar
  3. {
  4.    float x, y, w, h, rot;
  5. };
  6.  
  7. SCar cars[2];
  8.  
  9. float GetCarCornerX(int a, int i)
  10. {
  11.    float x = cars[a].x;
  12.    float w = cars[a].w;
  13.    float h = cars[a].h;
  14.    float rot = cars[a].rot;
  15.    float c = Maths.Cos(rot);
  16.    float s = Maths.Sin(rot);
  17.    if (i == 0)
  18.    {
  19.       return x + w*c + h*s;
  20.    }
  21.    if (i == 1)
  22.    {
  23.       return x - w*c + h*s;
  24.    }
  25.    if (i == 2)
  26.    {
  27.       return x + w*c - h*s;
  28.    }
  29.    return x - w*c - h*s;
  30. }
  31.  
  32. float GetCarCornerY(int a, int i)
  33. {
  34.    float y = cars[a].y;
  35.    float w = cars[a].w;
  36.    float h = cars[a].h;
  37.    float rot = cars[a].rot;
  38.    float c = Maths.Cos(rot);
  39.    float s = Maths.Sin(rot);
  40.    if (i == 0)
  41.    {
  42.       return y - w*s + h*c;
  43.    }
  44.    if (i == 1)
  45.    {
  46.       return y + w*s + h*c;
  47.    }
  48.    if (i == 2)
  49.    {
  50.       return y - w*s - h*c;
  51.    }
  52.    return y + w*s - h*c;
  53. }
  54.  
  55. // returns the index of the colliding point
  56. int DoCarsCollide(int a, int b)
  57. {
  58.    int ci;
  59.    ci = 0;
  60.    while (ci < 4)
  61.    {
  62.       // get the corner, translated into B's space
  63.       float ax = GetCarCornerX(a, ci) - cars[b].x;
  64.       float ay = GetCarCornerY(a, ci) - cars[b].y;
  65.  
  66.       // plane normals
  67.       float nx = Maths.Sin(cars[b].rot);
  68.       float ny = Maths.Cos(cars[b].rot);   // EDIT: NOTE: I removed the negative sign!
  69.  
  70.       float xoff = nx*ax + ny*ay;
  71.       float yoff = ny*ax - nx*ay;
  72.  
  73.       if (xoff*xoff < bw*bw && yoff*yoff < bh*bh)
  74.       {
  75.          return ci;
  76.       }
  77.  
  78.       ci++;
  79.    }
  80.  
  81.    return -1;
  82. }
  83.  
  84. // and then to use
  85. int c = DoCarsCollide(0, 1);
  86. if (c >= 0)
  87. {
  88.    float cx = GetCarCornerX(0, c);
  89.    float cy = GetCarCornerY(0, c);
  90. }
  91. else
  92. {
  93.    c = DoCarsCollide(1, 0);
  94.    if (c >= 0)
  95.    {
  96.       float cx = GetCarCornerX(1, c);
  97.       float cy = GetCarCornerY(1, c);
  98.    }
  99. }
  100.  

(In 3d it's much more difficult and there are several approaches, but the one most like the 2d case would involve "trimming" one box with the planes of the other box, and if there's anything left, using the center of the remnants as a collision point.)
« Last Edit: 21 Feb 2012, 15:06 by Kweepa »
Still waiting for Purity of the Surf II

Wyz

  • Posts: 1,279
  • anno 1986
    • I can help with making music
    • I can help with story design
    • I can help with translating
    • I can help with voice acting
    • I can help with web design
Re: Trigonometry help needed!
« Reply #9 on: 21 Feb 2012, 15:11 »
I'm rather unsure how to implement Wyz' suggestion and from what I've googled, Oriented-Bounding-Box intersection stuff is something people write papers about and get doctorates for, not something you can squeeze out in an afternoon.

It's simple geometry. The reason why people write papers about really simple things is because it needs to be fast as hell in modern computing.
What do you not understand about my pseudo code?

When I write:
Code: Adventure Game Studio
  1. col.xy = car2.xy - car1.xy
  2. car1.c1 = car1.w/2 , car1.h/2
  3.  
you should read it as:
Code: Adventure Game Studio
  1. col.x = car2.x - car1.x
  2. col.y = car2.y - car1.y
  3.  
  4. car1.c1.x = car1.w/2
  5. car1.c1.y = car1.h/2
  6.  
Life is like an adventure without the pixel hunts.

Kweepa

  • Posts: 3,332
  • Mutated Guano Deviser
    • Best Innovation Award Winner 2009, for his modules and plugins
    • Kweepa worked on a game that was nominated for an AGS Award!
Re: Trigonometry help needed!
« Reply #10 on: 21 Feb 2012, 15:40 »
Wyz's technique is ingenious!
It's not 100% accurate (I don't think), but it's close enough for your needs, and it's simple to implement.
Still waiting for Purity of the Surf II