Strict Standards: Declaration of action_plugin_importoldchangelog::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /nfsmnt/hosting1_2/8/2/82f54cb0-e474-4da4-9cdc-40dcd737e16b/mypage.sk/sub/tery/dokuwiki/lib/plugins/importoldchangelog/action.php on line 8

Strict Standards: Declaration of action_plugin_safefnrecode::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /nfsmnt/hosting1_2/8/2/82f54cb0-e474-4da4-9cdc-40dcd737e16b/mypage.sk/sub/tery/dokuwiki/lib/plugins/safefnrecode/action.php on line 0

Strict Standards: Declaration of action_plugin_popularity::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /nfsmnt/hosting1_2/8/2/82f54cb0-e474-4da4-9cdc-40dcd737e16b/mypage.sk/sub/tery/dokuwiki/lib/plugins/popularity/action.php on line 0

Strict Standards: Declaration of Doku_Renderer_metadata::table_open() should be compatible with Doku_Renderer::table_open($maxcols = NULL, $numrows = NULL, $pos = NULL) in /nfsmnt/hosting1_2/8/2/82f54cb0-e474-4da4-9cdc-40dcd737e16b/mypage.sk/sub/tery/dokuwiki/inc/parser/metadata.php on line 24

Strict Standards: Declaration of Doku_Renderer_metadata::table_close() should be compatible with Doku_Renderer::table_close($pos = NULL) in /nfsmnt/hosting1_2/8/2/82f54cb0-e474-4da4-9cdc-40dcd737e16b/mypage.sk/sub/tery/dokuwiki/inc/parser/metadata.php on line 24
tery:intersection_of_quads [TeryWiki]
 

Collision of two quads in 2D space

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.

How to

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

Variables used

  • 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

Code

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 values

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

Example

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

Obsolete text, going to be deleted

	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. )
tery/intersection_of_quads.txt · Last modified: 2008/08/27 16:47 by mirex
 
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki