version 1

There are two quads – Mighty one (M) (wall, stone block, platform) and Weak one (W) ( creature, small item ). Weak quad will be pushed away from Mighty one and its position will change if M and W collide. Mighty one's position will not be modified.

first check if:

- 1. both quads sizes have to be positive and bigger than zero. Negative sizes of quads are not supported.
- 2. check if quads will ever touch or intersect by comparing their starting and ending positions. If M is to the left from W on start position and also on end position it means that there is no chance that they will intersect.
- 3.If quads are already intersecting in their starting position then I have to move W out from M quad. I'll select to move it in direction where there is shortest way to move it.

it looks like that quads will collide, so make some preparations:

- 4.Calculate quad delta movement for their start-to-end movement. Calculate their relative movement. If relative movement of quads is zero it means that the quads are either staying put, or they're moving together and both those possibilities mean that they won't intersect, and we can quit.
- 5.Calculate number of the 'steps' that quads will make in the movement in X and Y direction. Use largest number of steps so quads won't make movement greater than 1 pixel per frame.
- 6.Calculate movement delta of both quads per one frame (dw, dm) and initialize their starting positions (pw, pm)
- 7.Initialize [intersect] variables with state of intersection in X & Y directions. It will be used in detection of direction of intersection. They will be copied to [intersectprev] in start of the loop.

Now, lets start up the movement loop. What we want to do here is:

- 8. start the loop
- 9. move quads step by step
- 10. check if they intersect. If they don't then continue the cycle
- 11. If they do then find out how did they intersect and set flags according to direction from which it intersects, then continue
- 12. In case that quads got out of each other, and they movement indicates that they won't intersect in their movement then quit the loop

Did they intersect ?

- 13. In each loop step check if quads did intersect.
- 14. if they did then move the W back to the position where it was before, and move it by M's movement delta so it seems as M pushed W away
- 15. calculate W's movement in a way which would not collide with M. Make it move in direction where it does not intersect with M.
- 16. end of the loop

After the loop is finished:

- 17. Check if all steps were passed. If they were not, it means that loop was broken because quads won't intersect anymore, so just move the quads and do not calculate intersections.
- 18. Set the result and return result flags

*stepi*- counters for stepping through quad movement*steps*- number of the steps which have to be performed to move both quads from their start position to their end position*pw, pm, ppw*- position of quads while moving*dw, dm*- one-step movement-delta of quads*dwadd*- delta of weak quad which would never move W to collide with M*vm, vw*– delta movement of quads, delta from start to end position*vq*– delta of movement of quads relative to each other.*intersectx, intersecty, intersectprevx, intersectprevy*– variables indicating if quads are intersecting in X or Y direction. These variables help to decide in which direction collision was made and so in which direction W should be moved to be out of the quad and to 'slide' by the M.*intersect_direction*– holds information about direction of intersection

float CTeryGame::CollisionOfTwoQuads( s_collision_of_two_quads_spec& specs ) { // find out how the quads move compared each other s_xy_long vw, vm, vq; static s_collision_of_two_quads_spec* s; s = &specs; // clear flags s->collision = cf_none; *1 // quads have to have positive sizes if ( ! ( ( s->rmsize.x > 0 ) && ( s->rmsize.y > 0 ) && ( s->rwsize.x > 0 ) && ( s->rwsize.y > 0 ))) { assert( false ); return -1.0; } *2 // if their edge-axes won't move one through another they won't intersect // because movement is straightforward. if (( s->rms.x + s->rmsize.x < s->rws.x ) && ( s->rmc.x + s->rmsize.x < s->rwc.x )) return -2.0; if (( s->rms.x > s->rws.x + s->rwsize.x ) && ( s->rmc.x > s->rwc.x + s->rwsize.x )) return -2.0; if (( s->rms.y + s->rmsize.y < s->rws.y ) && ( s->rmc.y + s->rmsize.y < s->rwc.y )) return -2.0; if (( s->rms.y > s->rws.y + s->rwsize.y ) && ( s->rmc.y > s->rwc.y + s->rwsize.y )) return -2.0; // number of steps, counter int min, steps, stepi; // movement delta of both quads s_xy_float dw, dm; // delta of weak quad which would never collide with mighty one s_xy_float dwadd; // position of both quads while moving s_xy_float pw, pm; // position of weak quad in previous position s_xy_float ppw; s_xy_float rws2; // if quads are already intersecting in their starting position // I could move the weak quad out of the strong by shortest way.. // modify weak's starting position stored in [rws2] rws2 = s->rws; *3 if ( QuadIntersection( s->rms, s->rms + s->rmsize, s_xy_Copy( s->rws ), s_xy_Copy( s->rws ) + s->rwsize ) ) { s_space_around dist; int min; dist.l = ( s->rms.x - ( s->rws.x + s->rwsize.x )); dist.r = ( s->rws.x - ( s->rms.x + s->rmsize.x )); dist.u = ( s->rms.y - ( s->rws.y + s->rwsize.y )); dist.d = ( s->rws.y - ( s->rms.y + s->rmsize.y )); min = 0; // act only if this direction is non-passable if ( dist.l > min ) min = dist.l; if ( dist.r > min ) min = dist.r; if ( dist.d > min ) min = dist.d; if ( dist.u > min ) min = dist.u; if ( dist.l == min ) { rws2.x += dist.l; min = 0; } if ( dist.r == min ) { rws2.x -= dist.r; min = 0; } if ( dist.u == min ) { rws2.y += dist.u; min = 0; } if ( dist.d == min ) { rws2.y -= dist.d; min = 0; } } *4 // vector of each quad vm = s->rmc - s->rms; //vw = s->rwc - s->rws; vw = s_xy_Copy( s->rwc - rws2 ); // movement vector of mighty quad relative to weak, M - V vq = vm - vw; // if they're moving together then they won't intersect if (( vq.x == 0 ) && ( vq.y == 0 )) return -2.0; // so now in the cycle, move the quads by small steps. Here are the rules: // - If they intersect then move weak quad by movement of strong one. // - If they're moving in opposite directions, and they are past the // intersection point they won't intersect anymore. So quit the loop. // calc the steps // do they intersect ? bool intersectx, intersecty; bool intersectprevx, intersectprevy; struct { bool l, r, u, d; } intersect_direction; // find out in which quad direction the number of steps is smallest *5 steps = abs( vm.x ); if ( abs( vm.y ) > steps ) steps = abs( vm.y ); if ( abs( vw.x ) > steps ) steps = abs( vw.x ); if ( abs( vw.y ) > steps ) steps = abs( vw.y ); *6 // calculate the quad movement deltas dw.Set( vw.x, vw.y ); dw /= (float)steps; dm.Set( vm.x, vm.y ); dm /= (float)steps; // initialize quad positions in float pm.Set( s->rms.x, s->rms.y ); pw.Set( rws2.x, rws2.y ); *7 // Initialize [intersect] variables with state of intersection in X & Y directions // it will be used in detection of direction intersection. // they will be copied to [intersectprev] in start of the loop if (( (int)pm.x >= (int)( pw.x + s->rwsize.x )) || ( (int)(pm.x + s->rmsize.x) <= (int)pw.x )) intersectx = false; else intersectx = true; if (( (int)pm.y >= (int)( pw.y + s->rwsize.y )) || ( (int)(pm.y + s->rmsize.y) <= (int)pw.y )) intersecty = false; else intersecty = true; *7 // as I tried to move weak out of mighty before, it shouldn't be possible // to intersect in both directions now. If it does, then something went wrong. assert(( intersectx == false ) || ( intersecty == false )); *8 // move the quads and detect intersections, or end of intersections for( stepi=0; stepi<steps; stepi++ ) { ppw = pw; *9 pm += dm; pw += dw; intersectprevx = intersectx; intersectprevy = intersecty; intersectx = intersecty = false; intersect_direction.l = intersect_direction.r = intersect_direction.u = intersect_direction.d = false; // Mighty is moving from right to the left from Weak if ( vq.x < 0 ) { // is Mighty's left edge to the left from Weak's right edge ? that // means - did they intersect or passed away ? *11 if ( pm.x < pw.x + s->rwsize.x ) { // if M's right edge is to the left from W's left edge it // wont intersect anymore as we're moving to the left. // so we can quit. *12 if ( pm.x + s->rmsize.x < pw.x ) { break; } // it seems like we're intersecting quads in X axis right now intersectx = true; // if there was no intersection in previous frame then mark it as intersection from this side if ( intersectprevy ) { intersect_direction.l = true; } } } // Mighty is moving from left to the right from Weak if ( vq.x > 0 ) { *11 if ( pm.x + s->rmsize.x > pw.x ) { if ( pm.x > pw.x + s->rwsize.x ) { *12 break; } intersectx = true; if ( intersectprevy ) { intersect_direction.r = true; } } } // if X is not moved then only evaluate if quads intersect if ( vq.x == 0 ) { *11 if (( pm.x + s->rmsize.x >= pw.x ) && ( pm.x <= pw.x + s->rwsize.x )) { intersectx = true; } } // Mighty is moving from top to the bottom from Weak if ( vq.y > 0 ) { *11 if ( pm.y + s->rmsize.y > pw.y ) { if ( pm.y > pw.y + s->rwsize.y ) { *12 break; } intersecty = true; if ( intersectprevx ) { intersect_direction.d = true; } } } // Mighty is moving from bottom to the top from Weak if ( vq.y < 0 ) { *11 if ( pm.y < pw.y + s->rwsize.y ) { if ( pm.y + s->rmsize.y < pw.y ) { *12 break; } intersecty = true; if ( intersectprevx ) { intersect_direction.u = true; } } } if ( vq.y == 0 ) { if (( pm.y + s->rmsize.y >= pw.y ) && ( pm.y <= pw.y + s->rwsize.y )) { *11 intersecty = true; } } // if quads do intersect *13 if ( intersectx & intersecty ) { *14 // move weak quad by mighty's position pw -= dw; pw += dm; // move weak quad back if its stuck from the direction *15 // calculate delta for weak quad, which could be added to weak's position // it will be modified weak quad by collision limitations. dwadd = dw; if (( intersect_direction.l ) && ( dwadd.x > 0 )) dwadd.x = 0; if (( intersect_direction.r ) && ( dwadd.x < 0 )) dwadd.x = 0; if (( intersect_direction.u ) && ( dwadd.y > 0 )) dwadd.y = 0; if (( intersect_direction.d ) && ( dwadd.y < 0 )) dwadd.y = 0; pw += dwadd; if (( intersectx ) && ( dwadd.x == 0 )) { intersectx = intersectprevx; } if (( intersecty ) && ( dwadd.y == 0 )) { intersecty = intersectprevy; } } *16 }// for steps *17 // Breaking out of the 'steps' cycle can mean only one thing - quads do not // intersect anymore. So in case of that I should finish Weak's movement. for( ; stepi<steps; stepi++ ) { pw += dw; } *18 // set new position to the referenced variable s->rwc.Set( pw.x, pw.y ); // set flags if ( intersect_direction.l ) s->collision |= cf_collision_right; if ( intersect_direction.r ) s->collision |= cf_collision_left; if ( intersect_direction.u ) s->collision |= cf_collision_down; if ( intersect_direction.d ) s->collision |= cf_collision_up; return (float)stepi / (float)steps; }// CollisionOfTwoQuads

enum quad_direction_flag { qdf_none = 0x00, qdf_collision_left = 0x01, qdf_collision_right = 0x02, qdf_collision_up = 0x04, qdf_collision_down = 0x08, } ; struct s_collision_of_two_quads_spec { // size of quads s_xy_long rmsize, rwsize; // starting and ending (current) position of mighty quad s_xy_long rms, rmc; // starting and ending (current) position of weak quad s_xy_float rws, rwc; // is mighty quad sticky on some side ? [quad_direction_flag] int sticky; // is mighty quad passable on some side ? [quad_direction_flag] // if its filled with [qdf_none] then it collides from all directions int passable; // returned values // did weak one collide on some side ? [quad_direction_flag] int collision; // did weak one got stuck on some side ? [quad_direction_flag] int stuck; } ;

From picture we can see that quads positions are:
*start*
Weak quad position [2,-6] and size [8,8]
Mighty quad position [-7,4] and size [8,8]
*end*
ending position of Weak [1,-5]
Mighty position [-4,1]

Quads should collide, and W should be pushed away by M. Let's see how algorithm works, going through the points mentioned earlier:

first check if:

- 1. Both quad sizes are positive. Passed.
- 2. Quads do intersect while moving, so we can continue
- 3. Quads are not intersecting in their starting position, so nothing is done here.

it looks like that quads will collide, so make some preparations:

- 4. Calculated delta: Weak delta: [-1,+1] Mighty delta: [+3,-3]. Quad delta: [+4,-4]. Quad delta is not [0,0] so we continue on.
- 5. Calculated number of steps will be 3.
- 6. Because number of steps is 3, deltas will be dw[-1/3,1/3], dm[1,-1]. Starting positions are initialized to pw[2,-6], pm[-7,4]
- 7. intersectx and also intersecty are set to false, because quads are quite far.

Now, lets start up the movement loop. What we want to do here is:

- 8. Now, lets start up the movement loop. There are 3 steps. In first step this will happen:
- 9. pm moved to pm[-6,3] and pw to pw[1.66,-5.66]
- 10. Now quads do intersect, as rounded value of pw is [1,-5]
- 11. W intersects with M
- 12. quads are not out of each other, so we continue

Did they intersect ?

- 13. In each loop step check if quads did intersect.
- 14. if they did then move the W back to the position where it was before, and move it by M's movement delta so it seems as M pushed W away
- 15. calculate W's movement in a way which would not collide with M. Make it move in direction where it does not intersect with M.

After the loop is finished:

- 16. end of the loop
- 17. After the loop is finished, then check if all steps were passed. If they were not, it means that loop was broken because quads won't intersect anymore, so just move the quads and do not calculate intersections.
- 18. Set the result and return result flags

We have two rectangles. One is Weak (w) and one is Strong (s). These are possibilities how two rectangles can intersect: Fig.1. no intersection +----+ | | | | +----+ +-----+ | | | | +-----+ Fig.2. intersection by corner +----+ | | | +-+---+ +--+-+ | | | +-----+ Fig.3. intersection by 2 points. Either W can have 2 points in S, or S can have 2 points in W +----------+ | | | +-----+ | +--+-----+-+ | | +-----+ Fig.4. cross intersection +-----+ +--+-----+-+ | | | | | | | | +--+-----+-+ | | +-----+ Fig.5. one lying inside another Either W is inside S, or S is inside W +---------+ | | | +-----+ | | | | | | | | | | +-----+ | | | +---------+ Question is how to move out Weak rectangle out of Strong one, if we have information about current position of both rectangles and about their position in last frame. Their size does not change from previous to current frame. Fig 2. can be calculated out easily. We also want to calculate how much space is there around the Weak quad relative to Strong quad. Lets divide 2d space into 9 segments | | 0 | 1 | 2 minx,y | | maxx miny -------+=========+------- | | | | 3 | 4 | 5 | | -------+=========+------- minx | | maxx,y maxy | | 6 | 7 | 8 | | Our rectangle is defined by segment 4. If point lies into segment 4 it lies inside the rectangle. We check all 4 of the points of W rectangle against S rectangle and mark the segments in which they lie. If one point lies inside segment 4 (fig.2) then math is easy. Figure out which sides sides intersect and calculate how deep is W inside S. If two points lie inside segment 4 (fig.3) we figure out which side is inside S and calculate how deep it is. Another problem is that even if W is not intersecting with S, it might have passed through the S during last frame. This can be indicated if it passed through segments ... Important point: Even if rect1 points don't lie into rect2 or vice versa they can be intersect each other ( see fig 4. )

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 3.0 Unported