ENIGMA Forums

Contributing to ENIGMA => Function Peer Review => Topic started by: RetroX on December 31, 2010, 12:09:58 am

Title: move_contact functions optimised for bbox
Post by: RetroX on December 31, 2010, 12:09:58 am
Code: [Select]
int move_contact(double direction, double max_distance, bool solid_only)
{
  enigma::object_collisions* const inst1 = ((enigma::object_collisions*)enigma::instance_event_iterator->inst);
  double max_x = lengthdir_x(direction, max_distance);
  double max_y = lengthdir_y(direction, max_distance);
  for (enigma::inst_iter *it = enigma::fetch_inst_iter_by_int(all); 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 (max_x > 0)
    {
      const double x1 = inst1->x + max_x, x2 = inst2->x + inst2->bbox_left;
      if (x2 < x1)
      {
        max_x = x2 - inst1->x;
      }
    }
    else if (max_x < 0)
    {
      const double x1 = inst1->x + max_x, x2 = inst2->x + inst2->bbox_right;
      if (x2 > x1)
      {
        max_x = x2 - inst1->x;
      }
    }
   
    if (max_y > 0)
    {
      const double y1 = inst1->y + max_y, y2 = inst2->y + inst2->bbox_top;
      if (y2 < y1)
      {
        max_y = y2 - inst1->y;
      }
    }
    else if (max_y < 0)
    {
      const double y1 = inst1->y + max_y, y2 = inst2->y + inst2->bbox_bottom;
      if (y2 > y1)
      {
        max_y = y2 - inst1->y;
      }
    }
  }
  inst1->x += max_x;
  inst1->y += max_y;
 
  return 0;
}

inline int move_contact_solid(double direction, double speed) { return move_contact(direction, speed, true); }
inline int move_contact_all(double direction, double speed)   { return move_contact(direction, speed, false); }

Haven't tested it yet, but this should work.  Also am going under the assumption that objects don't collide when they share an edge.
Title: Re: move_contact functions optimised for bbox
Post by: RetroX on December 31, 2010, 12:42:19 am
Confirmed not working.  I know why, though.
Title: Re: move_contact functions optimised for bbox
Post by: RetroX on January 01, 2011, 07:27:59 pm
Wow, I can't get this to work.

Here's my code, and if anyone wants to see if they can fix it, go ahead:

Code: [Select]
#define EPSILON 1e-14

int move_contact(double direction, double max_distance, bool solid_only)
{
  enigma::object_collisions* inst1 = ((enigma::object_collisions*)enigma::instance_event_iterator->inst);
  const double left1  = inst1->x + inst1->bbox_left,  top1    = inst1->y + inst1->bbox_top,
               right1 = inst1->x + inst1->bbox_right, bottom1 = inst1->y + inst1->bbox_bottom;
  double max_x = lengthdir_x(max_distance, direction);
  double max_y = lengthdir_y(max_distance, direction);
  double moving_x = inst1->x + max_x;
  double moving_y = inst1->y + max_y;
  for (enigma::inst_iter *it = enigma::fetch_inst_iter_by_int(all); 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;
    const double left2  = inst2->x + inst2->bbox_left,  top2    = inst2->y + inst2->bbox_top,
                 right2 = inst2->x + inst2->bbox_right, bottom2 = inst2->y + inst2->bbox_bottom;
    const double x_moving = inst1->x + max_x;
    if (inst1->y < bottom2 && inst1->y > top2)
    {
      if (max_x > EPSILON)
      {
        if (left2 < moving_x)
        {
          max_x    = left2 - inst1->x;
          moving_x = inst1->x + max_x;
        }
      }
      else if (max_x < -EPSILON)
      {
        if (right2 > moving_x)
        {
          max_x    = right2 - inst1->x;
          moving_x = inst1->x + max_x;
        }
      }
    }

    if (inst1->x < right2 && inst1->x > left2)
    {
      if (max_y > EPSILON)
      {
        if (top2 < moving_y)
        {
          max_y    = left2 - inst1->y;
          moving_y = inst1->y + max_y;
        }
      }
      else if (max_y < -EPSILON)
      {
        if (bottom2 > moving_y)
        {
          max_y    = bottom2 - inst1->y;
          moving_y = inst1->y + max_y;
        }
      }
    }
  }

  inst1->x = moving_x;
  inst1->y = moving_y;

  return 0;
}

inline int move_contact_solid(double direction, double speed) { return move_contact(direction, speed, true); }
inline int move_contact_all(double direction, double speed)   { return move_contact(direction, speed, false); }
Title: Re: move_contact functions optimised for bbox
Post by: IsmAvatar on January 01, 2011, 09:29:49 pm
I like these lines of code:

  const double left1  = inst1->x + inst1->bbox_left,  top1    = inst1->x + inst1->bbox_top,
               right1 = inst1->x + inst1->bbox_right, bottom1 = inst1->x + inst1->bbox_bottom;

    const double left2  = inst2->x + inst2->bbox_left,  top2    = inst2->x + inst2->bbox_top,
                 right2 = inst2->x + inst2->bbox_right, bottom2 = inst2->x + inst2->bbox_bottom;
Title: Re: move_contact functions optimised for bbox
Post by: RetroX on January 01, 2011, 09:33:15 pm
Code: [Select]
#define EPSILON 1e-14

int move_contact(double direction, double max_distance, bool solid_only)
{
  enigma::object_collisions* inst1 = ((enigma::object_collisions*)enigma::instance_event_iterator->inst);
  const double left1  = inst1->x + inst1->bbox_left,  top1    = inst1->y + inst1->bbox_top,
               right1 = inst1->x + inst1->bbox_right, bottom1 = inst1->y + inst1->bbox_bottom;
  double max_x = lengthdir_x(max_distance, direction);
  double max_y = lengthdir_y(max_distance, direction);
  double moving_x = inst1->x + max_x;
  double moving_y = inst1->y + max_y;
  for (enigma::inst_iter *it = enigma::fetch_inst_iter_by_int(all); 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;
    const double left2  = inst2->x + inst2->bbox_left,  top2    = inst2->y + inst2->bbox_top,
                 right2 = inst2->x + inst2->bbox_right, bottom2 = inst2->y + inst2->bbox_bottom;
    const double x_moving = inst1->x + max_x;
    if (inst1->y < bottom2 && inst1->y > top2)
    {
      if (max_x > EPSILON)
      {
        if (left2 < moving_x)
        {
          max_x    = left2 - inst1->x;
          moving_x = inst1->x + max_x;
        }
      }
      else if (max_x < -EPSILON)
      {
        if (right2 > moving_x)
        {
          max_x    = right2 - inst1->x;
          moving_x = inst1->x + max_x;
        }
      }
    }

    if (inst1->x < right2 && inst1->x > left2)
    {
      if (max_y > EPSILON)
      {
        if (top2 < moving_y)
        {
          max_y    = top2 - inst1->y;
          moving_y = inst1->y + max_y;
        }
      }
      else if (max_y < -EPSILON)
      {
        if (bottom2 > moving_y)
        {
          max_y    = bottom2 - inst1->y;
          moving_y = inst1->y + max_y;
        }
      }
    }
  }

  inst1->x = moving_x;
  inst1->y = moving_y;

  return 0;
}

inline int move_contact_solid(double direction, double speed) { return move_contact(direction, speed, true); }
inline int move_contact_all(double direction, double speed)   { return move_contact(direction, speed, false); }
I know why this doesn't work, but I'm working on something else atm.  Will fix later; bug me on the IRC if I don't.
Title: Re: move_contact functions optimised for bbox
Post by: RetroX on January 02, 2011, 06:50:32 pm
Code: [Select]
#define EPSILON 1e-14

int move_contact(double direction, double max_distance, int object, bool solid_only)
{
  enigma::object_collisions* inst1 = ((enigma::object_collisions*)enigma::instance_event_iterator->inst);
  const double left1  = inst1->x + inst1->bbox_left,  top1    = inst1->x + inst1->bbox_top,
               right1 = inst1->x + inst1->bbox_right, bottom1 = inst1->x + inst1->bbox_bottom;
  double max_x = lengthdir_x(max_distance, direction);
  double max_y = lengthdir_y(max_distance, direction);
  double moving_left1  = left1  + max_x, moving_top1    = top1    + max_y,
         moving_right1 = right1 + max_x, moving_bottom1 = bottom1 + max_y;
  for (enigma::inst_iter *it = enigma::fetch_inst_iter_by_int(all); 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;
    const double left2  = inst2->x + inst2->bbox_left,  top2    = inst2->x + inst2->bbox_top,
                 right2 = inst2->x + inst2->bbox_right, bottom2 = inst2->x + inst2->bbox_bottom;
    if (top1 < bottom2 && bottom1 > top2)
    {
      if (max_x > EPSILON)
      {
        if (left2 < moving_right1)
        {
          max_x         = left2 - moving_right1;
          moving_left1  = left1  + max_x;
          moving_right1 = right1 + max_x;
        }
      }
      else if (max_x < -EPSILON)
      {
        if (right2 > moving_left1)
        {
          max_x         = right2 - moving_left1;
          moving_left1  = left1  + max_x;
          moving_right1 = right1 + max_x;
        }
      }
    }

    if (left1 < right2 && right1 > left2)
    {
      if (max_y > EPSILON)
      {
        if (top2 < moving_top1)
        {
          max_y          = top2 - moving_bottom1;
          moving_top1    = top1    + max_y;
          moving_bottom1 = bottom1 + max_y;
        }
      }
      else if (max_y < -EPSILON)
      {
        if (bottom2 > moving_bottom1)
        {
          max_y          = bottom2 - moving_top1;
          moving_top1    = top1    + max_y;
          moving_bottom1 = bottom1 + max_y;
        }
      }
    }
  }

  inst1->x += max_x;
  inst1->y += max_y;

  return 0;
}

inline int move_contact_solid(double direction, double speed)              { return move_contact(direction, speed, all, true); }
inline int move_contact_all(double direction, double speed)                { return move_contact(direction, speed, all, false); }
inline int move_contact_object(double direction, double speed, int object) { return move_contact(direction, speed, object, false); }

Now, I don't know why this is spazzing all over the place.  Will figure out later, or someone else can do it.
Title: Re: move_contact functions optimised for bbox
Post by: RetroX on January 02, 2011, 07:41:55 pm
lol:
Code: [Select]
#define EPSILON 1e-14

int move_contact(double direction, double max_distance, int object, bool solid_only)
{
  enigma::object_collisions* inst1 = ((enigma::object_collisions*)enigma::instance_event_iterator->inst);
  const double left1  = inst1->x + inst1->bbox_left,  top1    = inst1->y + inst1->bbox_top,
               right1 = inst1->x + inst1->bbox_right, bottom1 = inst1->y + inst1->bbox_bottom;
  double max_x = lengthdir_x(max_distance, direction);
  double max_y = lengthdir_y(max_distance, direction);
  double moving_left1  = left1  + max_x, moving_top1    = top1    + max_y,
         moving_right1 = right1 + max_x, moving_bottom1 = bottom1 + max_y;
  for (enigma::inst_iter *it = enigma::fetch_inst_iter_by_int(all); 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;
    const double left2  = inst2->x + inst2->bbox_left,  top2    = inst2->y + inst2->bbox_top,
                 right2 = inst2->x + inst2->bbox_right, bottom2 = inst2->y + inst2->bbox_bottom;
    if (top1 < bottom2 && bottom1 > top2)
    {
      if (max_x > EPSILON)
      {
        if (left2 < moving_right1)
        {
          max_x         = left2 - moving_right1;
          moving_left1  = left1  + max_x;
          moving_right1 = right1 + max_x;
        }
      }
      else if (max_x < -EPSILON)
      {
        if (right2 > moving_left1)
        {
          max_x         = right2 - moving_left1;
          moving_left1  = left1  + max_x;
          moving_right1 = right1 + max_x;
        }
      }
    }

    if (left1 < right2 && right1 > left2)
    {
      if (max_y > EPSILON)
      {
        if (top2 < moving_top1)
        {
          max_y          = top2 - moving_bottom1;
          moving_top1    = top1    + max_y;
          moving_bottom1 = bottom1 + max_y;
        }
      }
      else if (max_y < -EPSILON)
      {
        if (bottom2 > moving_bottom1)
        {
          max_y          = bottom2 - moving_top1;
          moving_top1    = top1    + max_y;
          moving_bottom1 = bottom1 + max_y;
        }
      }
    }
  }

  inst1->x += max_x;
  inst1->y += max_y;

  return 0;
}

inline int move_contact_solid(double direction, double speed)              { return move_contact(direction, speed, all, true); }
inline int move_contact_all(double direction, double speed)                { return move_contact(direction, speed, all, false); }
inline int move_contact_object(double direction, double speed, int object) { return move_contact(direction, speed, object, false); }
still doesn't work.
Title: Re: move_contact functions optimised for bbox
Post by: polygone on January 02, 2011, 08:54:34 pm
I think you wanted this:

Code: [Select]
    if (top1 < bottom2 && bottom1 > top2)
    {
      if (max_x > EPSILON)
      {
        if (moving_right1 > left2)
        {
          max_x         = left2 - moving_right1;
          moving_left1  = left1  + max_x;
          moving_right1 = right1 + max_x;
        }
      }
      else if (max_x < -EPSILON)
      {
        if (moving_left1 < right2)
        {
          max_x         = right2 - moving_left1;
          moving_left1  = left1  + max_x;
          moving_right1 = right1 + max_x;
        }
      }
    }

    if (left1 < right2 && right1 > left2)
    {
      if (max_y > EPSILON)
      {
        if (moving_bottom1 > top2)
        {
          max_y          = top2 - moving_bottom1;
          moving_top1    = top1    + max_y;
          moving_bottom1 = bottom1 + max_y;
        }
      }
      else if (max_y < -EPSILON)
      {
        if (moving_top1 < bottom2)
        {
          max_y          = bottom2 - moving_top1;
          moving_top1    = top1    + max_y;
          moving_bottom1 = bottom1 + max_y;
        }
      }
    }

But after actually reading the code for the first time I have a number of issues with this method anyway.

1. You can collide into an object from a position where neither this (top1 < bottom2 && bottom1 > top2) or (left1 < right2 && right1 > left2) is satisfied.
2. The max_x, max_y variables are not actually set to the correct values for moving to the position where the collision occurs.
3. You can 'skip' right through objects if the distance is set large enough, which is contrary to what move_contact should do.
4. It doesn't allow for precise collision checks only bbox checks.

Although this method is often faster, I don't think it is exactly correct to use. I would suggest writing a more precise method using place_meeting.
Title: Re: move_contact functions optimised for bbox
Post by: RetroX on January 02, 2011, 08:57:14 pm
I would suggest writing a more precise method using place_meeting.
The point of this was to avoid using a massive, inefficient for loop. (that)

I've basically given up at this point, so, anyone else can either fix mine or toss it and make a new one.
Title: Re: move_contact functions optimised for bbox
Post by: polygone on January 02, 2011, 09:06:15 pm
I know the point is to make it more efficient, but without doing an "inefficient loop" it's not exact going to be doing it's job.
Title: Re: move_contact functions optimised for bbox
Post by: RetroX on January 02, 2011, 09:56:05 pm
I know the point is to make it more efficient, but without doing an inefficient loop it's not exact going to be doing it's job.
It can be done.  It's just that I'm doing it incorrectly.
Title: Re: move_contact functions optimised for bbox
Post by: Josh @ Dreamland on January 02, 2011, 11:59:33 pm
A for loop is unnecessary with bboxes.
1) Calculate furthest bbox point when translated from the untranslated position.
i.     If your bottom-left corner is at (0,0) and you are 32x32 pixels, and you are checking 10px at 45 degrees, the coordinate you want is 10*cos(45 deg) + 32, 10*sin(45 deg) + 32
2) Loop, looking for solid objects that collide with box from the two furthest points ((0,0) and (10*cos(45 deg) + 32, 10*sin(45 deg) + 32) in our example)
3) Check untranslated rectangle for collisions; if you're colliding with it initially, we obviously can't move any closer, so break.ass
4) Switch the quadrant of our angle (wrap(angle,360) / 90). This code assumes inst is the current instance and inst1 is the instance we're looping through. Neither are translated from their original position. It assumes a variable representing total displacement, dt. distSquared is parameter dist * parameter dist.
Code: (C++) [Select]
case 0: // Quadrant 0; horizontal up to nearly vertical
  const int dx = inst2->bbox_left - inst->bbox_right; // Get horizontal distance
  const int tdt = (dx >= 0)?dx/cos(45) : (inst2->bbox_bottom - inst->bbox_top)*sin(45);
  if (tdt < td)
    td = tdt;

I lack time to do the other three quadrants. You can do them and debug, or I will later. Peace.
Title: Re: move_contact functions optimised for bbox
Post by: polygone on January 03, 2011, 06:27:35 am
You can't easily check for 'solid objects that collide with box from the two furthest points' when only using one reference point on the bbox. I have wrote it instead using two reference points on the bbox (at opposite ends) then you can easily check objects that will collide via the angles. Here is working code in gml:

Code: (EDL) [Select]
//move_contact_bbox(angle, distance, object)
var angle, dist;
angle = argument0;  dist = argument1;

with (argument2)
{
  if (bbox_right >= other.bbox_left && bbox_bottom >= other.bbox_top && bbox_left <= other.bbox_right && bbox_top <= other.bbox_bottom)
  {
    dist = 0;
    break;
  }

  switch (wrap(angle, 360) div 90)
  {
    case 0:
      if ((bbox_left > other.bbox_right || other.bbox_top > bbox_bottom) &&
      angle_difference(point_direction(other.bbox_right, other.bbox_bottom, bbox_left, bbox_top), angle) >= 0  &&
      angle_difference(point_direction(other.bbox_left, other.bbox_top, bbox_right, bbox_bottom), angle) <= 0)
      {
        if (angle_difference(point_direction(other.bbox_right, other.bbox_top, bbox_left, bbox_bottom), angle) > 0)
        {
          dist = min(dist, (other.bbox_top - bbox_bottom - 1)/sin(degtorad(angle)));
        }
        else
        {
          dist = min(dist, (bbox_left - other.bbox_right - 1)/cos(degtorad(angle)));
        }
      }
    break;

    case 1:
      if ((other.bbox_left > bbox_right || other.bbox_top > bbox_bottom) &&
      angle_difference(point_direction(other.bbox_left, other.bbox_bottom, bbox_right, bbox_top), angle) <= 0  &&
      angle_difference(point_direction(other.bbox_right, other.bbox_top, bbox_left, bbox_bottom), angle) >= 0)
      {
        if (angle_difference(point_direction(other.bbox_left, other.bbox_top, bbox_right, bbox_bottom), angle) > 0)
        {
          dist = min(dist, (bbox_right - other.bbox_left + 1)/cos(degtorad(angle)));
        }
        else
        {
          dist = min(dist, (other.bbox_top - bbox_bottom - 1)/sin(degtorad(angle)));
        }
      }
    break;

    case 2:
      if ((other.bbox_left > bbox_right || bbox_top > other.bbox_bottom) &&
      angle_difference(point_direction(other.bbox_right, other.bbox_bottom, bbox_left, bbox_top), angle) <= 0  &&
      angle_difference(point_direction(other.bbox_left, other.bbox_top, bbox_right, bbox_bottom), angle) >= 0)
      {
        if (angle_difference(point_direction(other.bbox_left, other.bbox_bottom, bbox_right, bbox_top), angle) > 0)
        {
          dist = min(dist, (other.bbox_bottom - bbox_top + 1)/sin(degtorad(angle)));
        }
        else
        {
          dist = min(dist, (bbox_right - other.bbox_left + 1)/cos(degtorad(angle)));
        }
      }
    break;

    case 3:
      if ((bbox_left > other.bbox_right || bbox_top > other.bbox_bottom) &&
      angle_difference(point_direction(other.bbox_right, other.bbox_top, bbox_left, bbox_bottom), angle) <= 0  &&
      angle_difference(point_direction(other.bbox_left, other.bbox_bottom, bbox_right, bbox_top), angle) >= 0)
      {
        if (angle_difference(point_direction(other.bbox_right, other.bbox_bottom, bbox_left, bbox_top), angle) > 0)
        {
          dist = min(dist, (bbox_left - other.bbox_right - 1)/cos(degtorad(angle)));
        }
        else
        {
          dist = min(dist, (other.bbox_bottom - bbox_top + 1)/sin(degtorad(angle)));
        }
      }
    break;
  }
}

x += cos(degtorad(angle))*dist;  y -= sin(degtorad(angle))*dist;
Here is the example file I was working with if anyone wants to check that it works:
http://www.box.net/shared/popdzld7rp (GM8 gmk)

Press M to move_contact, press Space to change the movement direction, Press R to move the instance back to it's starting position.

I will attempt a write of it in C++ at some point.
Title: Re: move_contact functions optimised for bbox
Post by: Josh @ Dreamland on January 03, 2011, 12:22:31 pm
>You can't easily check for 'solid objects that collide with box from the two furthest points' when only using one reference point on the bbox.

Yes, you can. That's why I broke it into quadrants. I didn't have time to sketch up my idea yesterday (or even to draft it fully), but today, I do.

http://dl.dropbox.com/u/1052740/MoveBboxSolid.png

Code: (C++) [Select]
case 0: // Quadrant 0; horizontal up to nearly vertical
  const int dx = inst2->bbox_left - inst->bbox_right, dy = inst2->bbox_bottom - inst->bbox_top; // Get horizontal distance
  const int tdt = (dx > dy)?  dx/cos(dir) : dy*sin(dir);
  if (tdt < td and /*a rectangle that is our translated rectangle with a 1px border collides with our inst2->bbox*/ true)
    td = tdt;
Title: Re: move_contact functions optimised for bbox
Post by: polygone on January 03, 2011, 12:25:19 pm
I don't exactly get what you're doing, I'll wait till I see it finished...

EDIT: OK I see that with this code:

Code: (C++) [Select]
const int dx = inst2->bbox_left - inst->bbox_right, dy = inst2->bbox_bottom - inst->bbox_top
const int tdt = (dx > dy)?  dx/cos(dir) : dy*sin(dir);
  if (tdt < td)
    td = tdt;
You are trying to do the exact same thing as I did with this code:

Code: (EDL) [Select]
        if (angle_difference(point_direction(other.bbox_right, other.bbox_top, bbox_left, bbox_bottom), angle) > 0)
        {
          dist = min(dist, (other.bbox_top - bbox_bottom - 1)/sin(degtorad(angle)));
        }
        else
        {
          dist = min(dist, (bbox_left - other.bbox_right - 1)/cos(degtorad(angle)));
        }
I do not think what you used works though, I believe you have to check the angle against the dir in order to determine the correct colliding side with the instance.

I think the method I have used is actually the same method as the one in your head, but I don't see how you can work it without checking the angles.

EDIT 2: Let me make an image, it might be easier to explain:
http://img403.imageshack.us/img403/5790/bboxmovement.png

The red arrows represent two different directions the object could move in from the same position, each direction will result in a different side being collided yet dx, dy are exactly the same. Can you see why I decided to check the angle then instead?
Title: Re: move_contact functions optimised for bbox
Post by: IsmAvatar on January 03, 2011, 06:32:49 pm
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.
Title: Re: move_contact functions optimised for bbox
Post by: polygone on January 03, 2011, 11:02:43 pm
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
Title: Re: move_contact functions optimised for bbox
Post by: RetroX on January 04, 2011, 04:34:25 pm
One random thing to mention, but:
(http://dl.dropbox.com/u/6125077/images/other/theultimatetest.png)

In this case, the box should move-collide with the corner exactly.  If it's not a good method, it won't.
Title: Re: move_contact functions optimised for bbox
Post by: Josh @ Dreamland on January 04, 2011, 08:01:45 pm
Oh, does it do so in GM? That would mean a change in algorithm (this one stops as soon as it hits a wall).
Title: Re: move_contact functions optimised for bbox
Post by: RetroX on January 04, 2011, 10:04:46 pm
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.
Title: Re: move_contact functions optimised for bbox
Post by: polygone on January 05, 2011, 07:38:49 am
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.
Title: Re: move_contact functions optimised for bbox
Post by: Josh @ Dreamland on January 05, 2011, 09:37:34 am
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.
Title: Re: move_contact functions optimised for bbox
Post by: polygone on January 05, 2011, 12:56:32 pm
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.
Title: Re: move_contact functions optimised for bbox
Post by: polygone on January 27, 2011, 01:17:34 pm
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);
}
Title: Re: move_contact functions optimised for bbox
Post by: Josh @ Dreamland on January 28, 2011, 12:41:44 am
Someone verify that and then bug me or Ism about it.