move_contact functions optimised for bbox

[RetroX]

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.

[RetroX]

Confirmed not working.  I know why, though.

[RetroX]

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); }

[IsmAvatar]

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;

[RetroX]

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.

[RetroX]

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.

[RetroX]

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.

[polygone]

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.

[RetroX]

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.

[polygone]

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.

[RetroX]

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.

[Josh @ Dreamland]

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.

[polygone]

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.

[Josh @ Dreamland]

>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;


[polygone]

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?