Pages: 1 [2]
  Print  
Author Topic: move_contact functions optimised for bbox  (Read 6005 times)
Offline (Female) IsmAvatar
Reply #15 Posted on: January 03, 2011, 06:32:49 PM

LateralGM Developer
LGM Developer
Location: Pennsylvania/USA
Joined: Apr 2008
Posts: 891

View Profile Email
polygone, you may want to re-familiarize yourself with geometry.

First, there's two ways your statement "yet dx, dy are exactly the same" could be interpreted:
* dx1 = dy1 and dx2 = dy2
* dx1 = dx2 and dy1 = dy2

The first only occurs when the delta is at a slope of -/+ 1, so 45 degrees or 135 degrees. Since both line segments in the image have a positive slope, this could only occur if they both had an angle of 45 degrees, however this is clearly not the case. To further emphasize this, both segments begin from the same point, meaning they'd both overlap for the entirety of the travel of the shorter of the segments (or the entirety of the travel of both segments if the vectors are equal in magnitude).

The latter would imply that both segments are equivalent, but I'll spare you the proof, because it can visible be dismissed. If it were the case that dx1 = dx2 and dy1 = dy2, it would also be the case that dx1 = dx2. Since both segments begin from the same point, we know there is no vector displacement skewing. If we completely ignore the change in y coordinates of the two line segments, and only focus on the x coordinates, we can clearly see that one ends to the left of the other. Thus, dx1 < dx2 (or vice versa, depending on which one you decide is d1 and which is d2), but never dx1 = dx2.
« Last Edit: January 03, 2011, 06:34:58 PM by IsmAvatar » Logged
Offline (Male) polygone
Reply #16 Posted on: January 03, 2011, 11:02:43 PM

Contributor
Location: England
Joined: Mar 2009
Posts: 809

View Profile
Quote
First, there's two ways your statement "yet dx, dy are exactly the same" could be interpreted:
I didn't mean to suggest they were equal to each other (perhaps bad English), I was trying to say that dx and dy were constant, independent of the direction that the object travelled in. Thus they cannot be used to determine which side the object collides with.

But Josh said on IRC that his image was covering this case in the 3rd picture and was suggesting to use 'double collision' to resolve it, I don't wtf he means but regardless now anyway Josh has realised that the method I am using is the same as the one he was suggesting (which he didn't see before due to lack of sleep, he thought I was rewriting Retro's method) and since my code is working (I hope) it's fine to use (once written in C++).

EDIT:
Wait after actually reading what you put properly (I should really start doing that more), I think you have misinterpreted what I was referring to as dx, dy (since dx2 and dy2 don't exist  :D). I was not using them to represent displacement of the object, I was referring to the dx, dy variables Josh used in his code:

Code: (C) [Select]
const int dx = inst2->bbox_left - inst->bbox_right, dy = inst2->bbox_bottom - inst->bbox_top
« Last Edit: January 03, 2011, 11:26:32 PM by polygone » Logged
I honestly don't know wtf I'm talking about but hopefully I can muddle my way through.
Offline (Male) RetroX
Reply #17 Posted on: January 04, 2011, 04:34:25 PM

Master of all things Linux
Contributor
Location: US
Joined: Apr 2008
Posts: 1055
MSN Messenger - classixretrox@gmail.com
View Profile Email
One random thing to mention, but:


In this case, the box should move-collide with the corner exactly.  If it's not a good method, it won't.
« Last Edit: January 04, 2011, 04:37:26 PM by RetroX » Logged
My Box: Phenom II 3.4GHz X4 | ASUS ATI RadeonHD 5770, 1GB GDDR5 RAM | 1x4GB DDR3 SRAM | Arch Linux, x86_64 (Cube) / Windows 7 x64 (Blob)
Quote from: Fede-lasse
Why do all the pro-Microsoft people have troll avatars? :(
Offline (Male) Josh @ Dreamland
Reply #18 Posted on: January 04, 2011, 08:01:45 PM

Prince of all Goldfish
Developer
Location: Ohio, United States
Joined: Feb 2008
Posts: 2946

View Profile Email
Oh, does it do so in GM? That would mean a change in algorithm (this one stops as soon as it hits a wall).
Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
Offline (Male) RetroX
Reply #19 Posted on: January 04, 2011, 10:04:46 PM

Master of all things Linux
Contributor
Location: US
Joined: Apr 2008
Posts: 1055
MSN Messenger - classixretrox@gmail.com
View Profile Email
It actually probably does what you described in GM.  But it makes sense that it should be this way.  Someone should test it

If it works the other way in GM, I'd say have the crappy GM method, but also have the correct method.
Logged
My Box: Phenom II 3.4GHz X4 | ASUS ATI RadeonHD 5770, 1GB GDDR5 RAM | 1x4GB DDR3 SRAM | Arch Linux, x86_64 (Cube) / Windows 7 x64 (Blob)
Quote from: Fede-lasse
Why do all the pro-Microsoft people have troll avatars? :(
Offline (Male) polygone
Reply #20 Posted on: January 05, 2011, 07:38:49 AM

Contributor
Location: England
Joined: Mar 2009
Posts: 809

View Profile
No it doesn't do it in Game Maker. I don't think the move_contact function should do that either, the definition is to move the instance until it comes into contact with another object. What you're describing would be a whole other function, though probably a good one to implement. It shouldn't be hard to do, I believe you can just do another move_contact using the remaining momentum. What would be interesting (and highly useful) is doing a non-precise version of that function.

Note that we're going to need the GM method of move_contact as well anyway since it uses precise collisions and this one is only bbox. GM's method even works inside hollow objects, clearly the bbox method does nothing.
« Last Edit: January 05, 2011, 07:57:02 AM by polygone » Logged
I honestly don't know wtf I'm talking about but hopefully I can muddle my way through.
Offline (Male) Josh @ Dreamland
Reply #21 Posted on: January 05, 2011, 09:37:34 AM

Prince of all Goldfish
Developer
Location: Ohio, United States
Joined: Feb 2008
Posts: 2946

View Profile Email
Assuming you calculated the normal and took (distance-used_distance)*sin(dirdif(normal,dir)), then performed the second iteration perpendicular to that normal, it' work fine. Until, of course, you want us to check a third corner and so on. Then our algorithm becomes O(ND) as we have to keep iterating so long as there is yet any distance left to be iterated, not to mention it wouldn't look quite how the user would envision it in his ideal dream world. To get it to keep navigating around objects nicely, we would have to make our recursive calls to the function use no more of our remaining distance than it takes to move, in your drawing, inst1->bbox_left past inst2->bbox_right. Fortunately, with bboxes, all of this is insanely easy to calculate. Polygons and 3D meshes will not make this task quite so easy, and though it's well within the realm of possibility, my fear is, as always, efficiency.

The method may require a different subroutine to call that behaves like move_contact() but returns the distance it was able to travel before collision. That returned distance would then be subtracted from our remaining distance (we'd min() the distance required against the distance remaining before we ever invoked the subroutine to ensure this value will keep our remainder >= 0), and then the current function would be re-invoked.

It'd probably be useful and save memory to just return the distance traveled in the original move_contact. It's not like it won't already be in a register; returning it would probably just tell the compiler to keep it in eax.
Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
Offline (Male) polygone
Reply #22 Posted on: January 05, 2011, 12:56:32 PM

Contributor
Location: England
Joined: Mar 2009
Posts: 809

View Profile
Assuming you calculated the normal and took (distance-used_distance)*sin(dirdif(normal,dir)), then performed the second iteration perpendicular to that normal, it' work fine.
That's what I was thinking. It's highly easy with bbox checks.

Quote
Until, of course, you want us to check a third corner and so on. Then our algorithm becomes O(ND) as we have to keep iterating so long as there is yet any distance left to be iterated.
Yes, but then I don't think you are likely to hit that many instances when moving. The problem I envisaged though is doing this against concave slopes..

Quote
Polygons and 3D meshes will not make this task quite so easy, and though it's well within the realm of possibility, my fear is, as always, efficiency.
The thing is I advise making a function for this (or some other movement function) because then you can make it efficient and accurate. This will hopefully prevent most users making all sorts of bad collision systems and give them something easy to work with. The collision systems used in GM games are perhaps the most common area done badly.

I haven't actually thought much on how to go about it yet.
« Last Edit: January 05, 2011, 01:14:11 PM by polygone » Logged
I honestly don't know wtf I'm talking about but hopefully I can muddle my way through.
Offline (Male) polygone
Reply #23 Posted on: January 27, 2011, 01:17:34 PM

Contributor
Location: England
Joined: Mar 2009
Posts: 809

View Profile
OK wrote it in C++ now. I've let it return the distance the instance moved, maybe it should return the instance it collides with though (but that would make it less efficient).

Code: (C) [Select]
double move_contact_object(double angle, double dist, const int object, const bool precise = false, const bool solid_only = false)
{
  const double contact_distance = ((precise) ? 0.000001 : 1);
  dist = abs(dist);
  angle = ((angle mod 360) + 360) mod 360;
  enigma::object_collisions* const inst1 = ((enigma::object_collisions*)enigma::instance_event_iterator->inst);
  const int quad = int(angle/90.0);
  for (enigma::inst_iter *it = enigma::fetch_inst_iter_by_int(object); it != NULL; it = it->next)
  {
    const enigma::object_collisions* inst2 = (enigma::object_collisions*)it->inst;
    if (inst2->id == inst1->id || solid_only && !inst2->solid) {continue;}

    if (inst2->x + inst2->bbox_right >= inst1->x + inst1->bbox_left && inst2->y + inst2->bbox_bottom >= inst1->y + inst1->bbox_top && inst2->x + inst2->bbox_left <= inst1->x + inst1->bbox_right && inst2->y + inst2->bbox_top <= inst1->y + inst1->bbox_bottom)
    {
      dist = 0;
      break;
    }
   
    switch (quad)
    {
      case 0:
        if ((inst2->x + inst2->bbox_left > inst1->x + inst1->bbox_right || inst1->y + inst1->bbox_top > inst2->y + inst2->bbox_bottom) &&
        direction_difference(angle, point_direction(inst1->x + inst1->bbox_right, inst1->y + inst1->bbox_bottom, inst2->x + inst2->bbox_left, inst2->y + inst2->bbox_top)) >= 0  &&
        direction_difference(angle, point_direction(inst1->x + inst1->bbox_left, inst1->y + inst1->bbox_top, inst2->x + inst2->bbox_right, inst2->y + inst2->bbox_bottom)) <= 0)
        {
          if (direction_difference(angle, point_direction(inst1->x + inst1->bbox_right, inst1->y + inst1->bbox_top, inst2->x + inst2->bbox_left, inst2->y + inst2->bbox_bottom)) > 0)
          {
            dist = min(dist, (inst1->y + inst1->bbox_top - (inst2->y + inst2->bbox_bottom) - contact_distance)/sin(degtorad(angle)));
          }
          else
          {
            dist = min(dist, (inst2->x + inst2->bbox_left - (inst1->x + inst1->bbox_right) - contact_distance)/cos(degtorad(angle)));
          }
        }
      break;
      case 1:
        if ((inst1->x + inst1->bbox_left > inst2->x + inst2->bbox_right || inst1->y + inst1->bbox_top > inst2->y + inst2->bbox_bottom) &&
        direction_difference(angle, point_direction(inst1->x + inst1->bbox_left, inst1->y + inst1->bbox_bottom, inst2->x + inst2->bbox_right, inst2->y + inst2->bbox_top)) <= 0  &&
        direction_difference(angle, point_direction(inst1->x + inst1->bbox_right, inst1->y + inst1->bbox_top, inst2->x + inst2->bbox_left, inst2->y + inst2->bbox_bottom)) >= 0)
        {
          if (direction_difference(angle, point_direction(inst1->x + inst1->bbox_left, inst1->y + inst1->bbox_top, inst2->x + inst2->bbox_right, inst2->y + inst2->bbox_bottom)) > 0)
          {
            dist = min(dist, (inst2->x + inst2->bbox_right - (inst1->x + inst1->bbox_left) + contact_distance)/cos(degtorad(angle)));
          }
          else
          {
            dist = min(dist, (inst1->y + inst1->bbox_top - (inst2->y + inst2->bbox_bottom) - contact_distance)/sin(degtorad(angle)));
          }
        }
      break;
      case 2:
        if ((inst1->x + inst1->bbox_left > inst2->x + inst2->bbox_right || inst2->y + inst2->bbox_top > inst1->y + inst1->bbox_bottom) &&
        direction_difference(angle, point_direction(inst1->x + inst1->bbox_right, inst1->y + inst1->bbox_bottom, inst2->x + inst2->bbox_left, inst2->y + inst2->bbox_top)) <= 0  &&
        direction_difference(angle, point_direction(inst1->x + inst1->bbox_left, inst1->y + inst1->bbox_top, inst2->x + inst2->bbox_right, inst2->y + inst2->bbox_bottom)) >= 0)
        {
          if (direction_difference(angle, point_direction(inst1->x + inst1->bbox_left, inst1->y + inst1->bbox_bottom, inst2->x + inst2->bbox_right, inst2->y + inst2->bbox_top)) > 0)
          {
            dist = min(dist, (inst1->y + inst1->bbox_bottom - (inst2->y + inst2->bbox_top) + contact_distance)/sin(degtorad(angle)));
          }
          else
          {
            dist = min(dist, (inst2->x + inst2->bbox_right - (inst1->x + inst1->bbox_left) + contact_distance)/cos(degtorad(angle)));
          }
        }
      break;
      case 3:
        if ((inst2->x + inst2->bbox_left > inst1->x + inst1->bbox_right || inst2->y + inst2->bbox_top > inst1->y + inst1->bbox_bottom) &&
        direction_difference(angle, point_direction(inst1->x + inst1->bbox_right, inst1->y + inst1->bbox_top, inst2->x + inst2->bbox_left, inst2->y + inst2->bbox_bottom)) <= 0  &&
        direction_difference(angle, point_direction(inst1->x + inst1->bbox_left, inst1->y + inst1->bbox_bottom, inst2->x + inst2->bbox_right, inst2->y + inst2->bbox_top)) >= 0)
        {
          if (direction_difference(angle, point_direction(inst1->x + inst1->bbox_right, inst1->y + inst1->bbox_bottom, inst2->x + inst2->bbox_left, inst2->y + inst2->bbox_top)) > 0)
          {
            dist = min(dist, (inst2->x + inst2->bbox_left - (inst1->x + inst1->bbox_right) - contact_distance)/cos(degtorad(angle)));
          }
          else
          {
             dist = min(dist, (inst1->y + inst1->bbox_bottom - (inst2->y + inst2->bbox_top) + contact_distance)/sin(degtorad(angle)));
          }
        }
      break;
    }
  }
  inst1->x += cos(degtorad(angle))*dist;
  inst1->y -= sin(degtorad(angle))*dist;
  return dist;
}

inline int move_contact_all(const double direction, const double speed, const bool precise = false)
{
  return move_contact_object(direction, speed, all, precise);
}

inline int move_contact_solid(const double direction, const double speed, const bool precise = false)
{
  return move_contact_object(direction, speed, all, precise, true);
}

inline int move_contact(const double direction, const double speed, const bool precise = false)
{
  return move_contact_object(direction, speed, all, precise);
}
« Last Edit: July 17, 2011, 10:34:00 AM by polygone » Logged
I honestly don't know wtf I'm talking about but hopefully I can muddle my way through.
Offline (Male) Josh @ Dreamland
Reply #24 Posted on: January 28, 2011, 12:41:44 AM

Prince of all Goldfish
Developer
Location: Ohio, United States
Joined: Feb 2008
Posts: 2946

View Profile Email
Someone verify that and then bug me or Ism about it.
Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
Pages: 1 [2]
  Print