Trigonometry help needed!

[InCreator]

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?

[Wyz]

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: ags

col.xy = car2.xy - car1.xy

Then you calculate the vectors for the corner points

Code: ags

car1.c1 = car1.w/2 , car1.h/2
car1.c2 = -car1.w/2 , car1.h/2
car1.c3 = -car1.w/2 , -car1.h/2
car1.c4 = car1.w/2 , -car1.h/2

We can use the dot products of two vector to get a score how much they are alike:

Code: ags

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

function compare(v1,v2)
{
  v1 = normalize(v1)
  v2 = normalize(v2)
  var dot = v1.x*v2.x + v1.y*v2.y
  return abs(dot)
}

Now we compare every corner, first for car1:

Code: ags

s1c1 = compare(col, car1c1);
s1c2 = compare(col, car1c2);
s1c3 = compare(col, car1c3);
s1c4 = compare(col, car1c4);

For car two we have to flip the collision vector:

Code: ags

s2c1 = compare(-col, car2c1);
s2c2 = compare(-col, car2c2);
s2c3 = compare(-col, car2c3);
s2c4 = compare(-col, car2c4);

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.

[InCreator]

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

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

it returns... 1?

[Snarky]

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

it returns... 1?

It should be:

Code: ags

return v / n;

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

[Wyz]

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 

[Khris]

Just out of curiosity, are you also looking for a collision detection algorithm? Or is GameMaker already handling this?

[InCreator]

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]

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]

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: ags

struct SCar
{
   float x, y, w, h, rot;
};

SCar cars[2];

float GetCarCornerX(int a, int i)
{
   float x = cars[a].x;
   float w = cars[a].w;
   float h = cars[a].h;
   float rot = cars[a].rot;
   float c = Maths.Cos(rot);
   float s = Maths.Sin(rot);
   if (i == 0)
   {
      return x + w*c + h*s;
   }
   if (i == 1)
   {
      return x - w*c + h*s;
   }
   if (i == 2)
   {
      return x + w*c - h*s;
   }
   return x - w*c - h*s;
}

float GetCarCornerY(int a, int i)
{
   float y = cars[a].y;
   float w = cars[a].w;
   float h = cars[a].h;
   float rot = cars[a].rot;
   float c = Maths.Cos(rot);
   float s = Maths.Sin(rot);
   if (i == 0)
   {
      return y - w*s + h*c;
   }
   if (i == 1)
   {
      return y + w*s + h*c;
   }
   if (i == 2)
   {
      return y - w*s - h*c;
   }
   return y + w*s - h*c;
}

// returns the index of the colliding point
int DoCarsCollide(int a, int b)
{
   int ci;
   ci = 0;
   while (ci < 4)
   {
      // get the corner, translated into B's space
      float ax = GetCarCornerX(a, ci) - cars[b].x;
      float ay = GetCarCornerY(a, ci) - cars[b].y;

      // plane normals
      float nx = Maths.Sin(cars[b].rot);
      float ny = Maths.Cos(cars[b].rot);   // EDIT: NOTE: I removed the negative sign!

      float xoff = nx*ax + ny*ay;
      float yoff = ny*ax - nx*ay;

      if (xoff*xoff < bw*bw && yoff*yoff < bh*bh)
      {
         return ci;
      }

      ci++;
   }

   return -1;
}

// and then to use
int c = DoCarsCollide(0, 1);
if (c >= 0)
{
   float cx = GetCarCornerX(0, c);
   float cy = GetCarCornerY(0, c);
}
else
{
   c = DoCarsCollide(1, 0);
   if (c >= 0)
   {
      float cx = GetCarCornerX(1, c);
      float cy = GetCarCornerY(1, c);
   }
}

(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.)

[Wyz]

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: ags

col.xy = car2.xy - car1.xy
car1.c1 = car1.w/2 , car1.h/2

you should read it as:

Code: ags

col.x = car2.x - car1.x
col.y = car2.y - car1.y

car1.c1.x = car1.w/2
car1.c1.y = car1.h/2

[Kweepa]

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.