Finding intersections with angled vectors

9 posts

Flag Post

I’ve finally finished my collision code for my ball and block game, but I’ve decided My process for now is projecting the ball’s motion vector from its top, bottom, left, and right points and checking for the closest collision with four vectors drawn representing the four sides of rectangles. I’m checking for corner collisions separately, and everything is working so far.

I want to have some of the blocks rotating and moving in patterns to prevent monotony taking over, though, and I was wondering if you had suggestions for finding the best way to do this. I was thinking of creating a separate invisible layer to orient the ball to the block’s rotation angle, running a normal collision, and then reversing it to the proper orientation after the collision. I’m sure I can figure this out for myself, but rather than screwing around, I figured it might be wise to post here to see if anyone else had some concrete ideas on how to better implement this. The problem with just running my current collision code, even if I adjust and angle vectors is that it’s configured to test only those four points against the vectors of the blocks, which are all grid aligned, so I only need to deal with 90 degree angles aligned to the stage.

My code for corner collisions finds points other than those four as the closest, collision, but it’s only set up to find the point of contact based on a vector between the ball and a single point projected the inversion of the ball’s velocity toward the ball.

Does anyone know of any simpler ways to do this, or should I just set it up to temporarily orient the ball to the rotation of the block so I’m essentially using the same code? I started this whole project to teach myself more about working with vectors, especially vector collisions, so any advice from more experienced programmers would be greatly appreciated.

Here’s the relevant code. I still have to go through and reduce redundant code, but it should be understandable.

 
Flag Post

Oops, accidentally hit submit before posting code. Give me a second.

 
Flag Post

The only thing that would probably be relevant is the circleVsRectangle function, which finds blocks close enough to bother checking, finds the closest collision point, and then checks that for a collision. VectorModels are just a class that allow me to access data from vectors such as magnitude, normalized vectors, vector normals, etc. I’m going to consolodate some of the redundant functions later on, but if you have any suggestions about the easiest way to do what I want, I’d be happy to hear them.

V0 the ball’s motion vector, between it’s position and it’s next position with its velocity.
V1 is the vector I’m checking for a collision.
V2 is a helper vector between the the ball’s position and the beginning of the target vector
v3 is the final vector between the ball’s collision point and the intersection point
v4 and v5 check to make sure the intersection is actually on the vector


public static function circleVsRectangle(gameModel:Object, c1:CircleModel, b:Number = 1, f:Number = 1):Object
{
	var model:Object = gameModel;
	var data:Object = new Object();
	var rad:Number = c1.radius * MOD;
	var cx:Number = c1.pxpos;
        var cy:Number = c1.pypos;
			
	var v0:VectorModel = new VectorModel();
        var v1:VectorModel = new VectorModel();
	var v2:VectorModel = new VectorModel();
	var v3:VectorModel = new VectorModel(0, 0, 500, 500);
	var v4:VectorModel = new VectorModel();
	var v5:VectorModel = new VectorModel();
	var cornerVector:VectorModel = new VectorModel();
	var corner:Point;
			
	var v0t:VectorModel = new VectorModel();
        var v1t:VectorModel = new VectorModel();
	var v2t:VectorModel = new VectorModel();
	var v3t:VectorModel = new VectorModel();
	var hitIndex:uint = 0;
	var sideIndex:uint = 0;
			
	var cornerData:Object = new Object();
			
	for(var i:uint = 0; i < model.blockModels.length; i++)
	{
		var r1:RectangleModel = model.blockModels[i];
		var inRange:Boolean = false;
		var cv0:VectorModel = new VectorModel(cx, cy, cx + c1.vx, cy + c1.vy);
		var cv1:VectorModel = new VectorModel(cx, cy, r1.xpos, r1.ypos);
				
		if(cv1.m < cv0.m + r1.width)
		{
			inRange = true;
		}
		if(model.blockModels[i].active && !model.blockModels[i].hit && inRange)
		{	
			var hw:Number = r1.width * 0.5;
			var hh:Number = r1.height * 0.5;
			var perp1:Number;
			var perp2:Number;
			var t:Number;
			var ix:Number = 0;
			var iy:Number = 0;
			var dp1:Number;
			var dp2:Number;
			var p1:Point = new Point(r1.xpos - hw, r1.ypos + hh);
			var p2:Point = new Point(r1.xpos - hw, r1.ypos - hh);
			var p3:Point = new Point(r1.xpos + hw, r1.ypos - hh);
			var p4:Point = new Point(r1.xpos + hw, r1.ypos + hh);
			var s1:VectorModel = new VectorModel(p1.x, p1.y, p2.x, p2.y);//left side
			var s2:VectorModel = new VectorModel(p2.x, p2.y, p3.x, p3.y);//top side
			var s3:VectorModel = new VectorModel(p3.x, p3.y, p4.x, p4.y);//right side
			var s4:VectorModel = new VectorModel(p4.x, p4.y, p1.x, p1.y);//bottom side
			var sides:Array = new Array(s1, s2, s3, s4);
					
			for(var j:uint = 0; j < sides.length; j++)
			{
				switch(j)
			        {
			                case 0:
					v0t.update(cx + rad, cy, cx + rad + c1.vx, cy + c1.vy);
					break;
							
					case 1:
					v0t.update(cx, cy + rad, cx + c1.vx, cy + rad + c1.vy);
					break;
							
					case 2:
					v0t.update(cx - rad, cy, cx - rad + c1.vx, cy + c1.vy);
					break;
							
					case 3:
					v0t.update(cx, cy - rad, cx + c1.vx, cy - rad + c1.vy);
					break;	
				}
				v1t.update(sides[j].a.x, sides[j].a.y, sides[j].b.x, sides[j].b.y);
				v2t.update(v0t.a.x, v0t.a.y, v1t.a.x, v1t.a.y);
				perp1 = VectorMath.perpProduct(v2t, v1t);
				perp2 = VectorMath.perpProduct(v0t, v1t);
				t = perp1 / perp2;
				ix = v0t.a.x + v0t.vx * t;
				iy = v0t.a.y + v0t.vy * t;
				v3t.update(v0t.a.x, v0t.a.y, ix, iy);
				v4.update(v1t.a.x, v1t.a.y, ix, iy);
				v5.update(v1t.b.x, v1t.b.y, ix, iy);
				dp1 = VectorMath.dotProduct(v2t, v1t.ln);
				dp2 = VectorMath.dotProduct(v0t, v3t);
						
				if(dp1 == 0)
				{
					dp2 *= -1;
				}
						
				if(v3t.m != 0.001 && v3t.m < v3.m && v4.m <= v1t.m && v5.m <= v1t.m && dp1 <= 0                               && dp2 > 0)
				{
					v0.update(v0t.a.x, v0t.a.y, v0t.b.x, v0t.b.y);
					v1.update(v1t.a.x, v1t.a.y, v1t.b.x, v1t.b.y);
					v2.update(v2t.a.x, v2t.a.y, v2t.b.x, v2t.b.y);
					v3.update(v3t.a.x, v3t.a.y, v3t.b.x, v3t.b.y);
					hitIndex = i;
					sideIndex = j;
				}
			}
		}
	}
	cornerData = checkCornerCollision(model, c1);
	cornerVector = cornerData.vector;
	corner = cornerData.corner;
			
	if(cornerVector.m != 0.001 && cornerVector.m < v3.m)
	{
		v3.update(cornerVector.a.x, cornerVector.a.y, corner.x, corner.y);
		ix = cornerData.ix;
		iy = cornerData.iy;
		data.collision = circleVsCorner(c1, cornerVector.a.x, cornerVector.a.y, corner.x, corner.y, ix, iy);
		data.index = cornerData.index;
		return data;
	}
	ix = v3.b.x;
	iy = v3.b.y;
				
	if(v3.m < v0.m)
	{
		switch(sideIndex)
	        {
			case 0:
		        c1.xpos = ix - rad;
			c1.ypos = iy;
			c1.vx *= -1;
			break;
						
			case 1:
			c1.ypos = iy - rad;
			c1.xpos = ix;
			c1.vy *= -1;
			break;
						
			case 2:
			c1.xpos = ix + rad;
			c1.ypos = iy;
			c1.vx *= -1;
			break;
					
			case 3:
			c1.ypos = iy + rad;
			c1.xpos = ix;
			c1.vy *= -1;
			break;		
		}
		data.collision = true;
		data.index = hitIndex;
		return data;
	}
	data.collision = false;
	return data;	
}
public static function checkCornerCollision(gameModel:Object, c1:CircleModel, b:Number = 1):Object
{
	var model:Object = gameModel;
	var data:Object = new Object();
	var rad:Number = c1.radius * MOD;
	var cx:Number = c1.pxpos;
	var cy:Number = c1.pypos;
	
	var v1:VectorModel = new VectorModel();
	var v2:VectorModel = new VectorModel();
	var v3:VectorModel = new VectorModel(0, 0, 500, 500);
	var rad0:VectorModel = new VectorModel();
	var cornerVector:VectorModel = new VectorModel(0, 0, 500, 500);
	var corner:Point = new Point(1000, 1000);
			
	var hitIndex:uint = 0;
			
	for(var i:uint = 0; i < model.blockModels.length; i++)
	{
		var r1:RectangleModel = model.blockModels[i];
		var inRange:Boolean = false;
		var cv0:VectorModel = new VectorModel(cx, cy, cx + c1.vx, cy + c1.vy);
		var cv1:VectorModel = new VectorModel(cx, cy, r1.xpos, r1.ypos);
		
		if(cv1.m < cv0.m + r1.width)
		{
			inRange = true;
		}
		if(model.blockModels[i].active && !model.blockModels[i].hit && inRange)
		{
			var intersectionData:Object = new Object();
			var hw:Number = r1.width * 0.5;
			var hh:Number = r1.height * 0.5;
			var cix:Number;
			var ciy:Number;
			var ixt:Number;
			var iyt:Number;
			var ix:Number;
			var iy:Number;
			var px:Number;
			var py:Number;
			var p1:Point = new Point(r1.xpos - hw, r1.ypos + hh);
			var p2:Point = new Point(r1.xpos - hw, r1.ypos - hh);
			var p3:Point = new Point(r1.xpos + hw, r1.ypos - hh);
			var p4:Point = new Point(r1.xpos + hw, r1.ypos + hh);
			var points:Array = new Array(p1, p2, p3, p4);
			
			var v4:VectorModel = new VectorModel();
			
			for(var j:uint = 0; j < points.length; j++)
			{
				intersectionData = lineIntersectingCircle(c1, points[j].x, points[j].y);
				if(intersectionData.intersects)
			        {
				        px = points[j].x;
				        py = points[j].y;
				        cix = intersectionData.intersection.x;
				        ciy = intersectionData.intersection.y;
				        rad0.update(cix, ciy, c1.pxpos, c1.pypos);
				        ixt = px + rad0.vx;
				        iyt = py + rad0.vy;
				        v1.update(ixt, iyt, ixt + c1.vx, iyt + c1.vy);
				        v2.update(ixt, iyt, px, py);
				        v3.update(cix, ciy, px, py);
			        }
			        if(v3.m < cornerVector.m)
				{
					hitIndex = i;
					ix = ixt;
					iy = iyt;
					cornerVector.update(v3.a.x, v3.a.y, v3.b.x, v3.b.y);
					corner = points[j];
				}
			}
		}
	}
	data.index = hitIndex;
	data.vector = cornerVector;
	data.corner = corner;
	data.ix = ix;
	data.iy = iy;
	return data;
}
private static function lineIntersectingCircle(c1:CircleModel, px:Number, py:Number):Object
{	
	var data:Object = new Object ();
	data.intersects = false;
	
	var cx:Number = c1.xpos;
	var cy:Number = c1.ypos;
	var vx:Number = c1.vx * 100;
	var vy:Number = c1.vy * 100;
	var p0:Point = new Point(px, py);
	var p1:Point = new Point(px - vx, py - vy);
	var p2:Point = new Point(c1.pxpos, c1.pypos);
	var rad:Number = c1.radius * MOD;
		
	var a:Number = (p1.x - p0.x) * (p1.x - p0.x) + (p1.y - p0.y) * (p1.y - p0.y);
	var b:Number = 2 * ((p1.x - p0.x) * (p0.x - p2.x) +(p1.y - p0.y) * (p0.y - p2.y));
	var cc:Number = p2.x * p2.x + p2.y * p2.y + p0.x * p0.x + p0.y * p0.y - 2 * (p2.x * p0.x + p2.y * p0.y) - rad * rad;
	var determinant:Number = b * b - 4 * a * cc;
			
	if(determinant > 0)
	{
		var e:Number = Math.sqrt (determinant);
		var u1:Number = (-b + e) / (2 * a);
		var u2:Number = (-b - e) / (2 * a);
		
		if ((u1 < 0 || u1 > 1) && (u2 < 0 || u2 > 1)) 
		{
			if ((u1 < 0 && u2 < 0) || (u1 > 1 && u2 > 1)) 
			{
				data.intersects = false;
				return data;
			} 
			else 
			{
				data.intersects = false;
				return data;
			}
		} 
		else 
		{
			if (0 <= u2 && u2 <= 1) 
			{
				data.intersects = true;
				data.intersection = Point.interpolate (p0, p1, 1 - u2);
				return data;
			}
		}
	}
	return data;
}
private static function circleVsCorner(c1:CircleModel, cx:Number, cy:Number, px:Number, py:Number, ix:Number, iy:Number, ba:Number = 1):Boolean
{
	var v0:VectorModel = new VectorModel(cx, cy, px, py);
	var v1:VectorModel = new VectorModel(cx, cy, cx + c1.vx, cy + c1.vy);
        var rad:Number = c1.radius * MOD;
			
	if(v0.m <= v1.m)
	{
		c1.xpos = ix;
		c1.ypos = iy;
		
		v0.update(c1.xpos, c1.ypos, px, py);
		v1.update(c1.xpos, c1.ypos, c1.xpos + c1.vx, c1.ypos + c1.vy);
				
		var bounce:VectorModel = VectorMath.bounce(v1, v0.ln);
				
		c1.vx = bounce.vx * ba;
		c1.vy = bounce.vy * ba;
				
		return true;
	}
	else
	{
		return false;
	}
}

 
Flag Post

Theres an edit button directly under your post count. Beside your avatar.
Also, its helpful to remove a lot of the “tabs” from the code you posted.

The difference between

					public function main(e:Event):void{
						//random code here
					}

and…

public function functionName(e:Event):void{
	//random code here
}

is Immense and the only reason its pushed out that far to begin with is because your function is most likely in package and class, and ect. Which is fine… Just remove some of those tabs! haha

 
Flag Post

I wonder why don’t you store all the vectors that are rectangles’ sides with the rectangles as object fields, but instead you dynamically calculate and allocate them each time you call that big function, and you get the same value over and over? I understand about the ball, it moves and all that, but blocks either don’t move (yet), or only turn (and when you turn a block, you’d better recalculate its borders at once), so you don’t need to run that many calculations each frame (most likely this is called once per frame).

In order to generate the required vectors to check collision witha turned block, you need to know the angle (in radians) that the block is turned – it should be stored with the block. Then you change the code under switch(j) to include adjustment for current angle, I see that right now there are only 90 degrees angles in form of -1 and +1 as multipliers to “rad”. This should do.

 
Flag Post

Sorry about that. Let me edit them out. The reason I didn’t the first time is because there seems to be a problem realigning things when I post them, but let me make it more legible real quick. Also, would it be more useful if I made a basic psuedocode translation? Also, for some reason, the edit button has been kind of quirky. It has occasionally not been letting me edit, for some reason.

 
Flag Post

I’m sorry, but what is an object field? Do you mean just making them available as a stable variable I can access from the rectangle model once it’s created, or using an object as an array to store them? Forgive my ignorance, but I’ve never seen that term before, and I’m very curious.

I do realize there are a lot of unnecessary things in my code right now. I was going to work on it to make it more efficient, but I didn’t seem to notice any slowdown even on my 5 year old laptop, so I figured I’d just work on other parts for now. There are obviously a lot of Math.sqrt calls I could eliminate simply by calculating them in advance, or setting them up to only run them when something changes (like velocity). It seems like this might be pretty easy to implement, after all. I’ll go work on it a bit and get back to you if I need anymore help.

Thanks!

 
Flag Post

Perhaps it’s just my poor English. I meant a class field, not an object field.

public class RectangleModel {
    public var topSide:VectorModel;
    public var bottomSide:VectorModel;
...

Etc, whatever else do you need to store in your object that is used as a brick, say “active” field you already use.

 
Flag Post

The simplest way to do circle/rectangle collision is to translate the circle into the local space of the rectangle (so that its sides run along axis-parallel vectors).

Here’s the code I use for 2D circle/rectangle (BB = bounding box = a rectangle) collision:

	var dv:Vector2 = other.parent.velocity.Subtract(parent.velocity);
// Rotate the real position difference into our local space
if (parent.angle != 0) {
	ds.Rotate( -parent.angle, true);
	dv.Rotate( -parent.angle, true);
}

// [ ... ]

// BB - CIRCLE

var ch:CircularHull = CircularHull(other);
var r:Number = ch.Radius;

// If not in these bounds, definitely no collision
if (ds.y <= -(r + size.y ) || ds.x <= -(r  + size.x ) || ds.y >= r + size.y || ds.x >= r + size.x) return null;

res = new CollisionResponse();
if (ds.x >= -size.x && ds.x < size.x) {
	// Within bounds in X, pure top or bottom collision
	if (ds.y <= 0) {
		res.CVec = new Vector2(0, ds.y + r + size.y, 0);						
	} else {
		res.CVec = new Vector2(0, (ds.y - r) - size.y, 0);
	}
} else if (ds.y >= -size.y && ds.y <= size.y) {
	// Within bounds in Y, pure left or right collision
	if (ds.x < 0) {
		res.CVec = new Vector2(ds.x + r + size.x, 0, 0);						
	} else {
		res.CVec = new Vector2((ds.x - r) - size.x, 0, 0);
	}					
} else {
	// Corner. May not actually be touching
	corner = new Vector2(0, 0, 1);
	corner.x = size.x * (ds.x < 0 ? -1 : 1);
	corner.y = size.y * (ds.y < 0 ? -1 : 1);
	ds.Subtract(corner, true);
	if (ds.Mag2 < r * r) {
		// Collision at this corner.
		ds.Mag = ds.Mag - r;
		res.CVec = ds;
	}
}
if (res.CVec) {
	// Transform the cvec back into global space
	res.CVec.Rotate(parent.angle, true);
	res.GlobalPosition = other.parent.location.Add(res.CVec);
	return res;
} else return null;

This is just static (penetrative) collision detection because I deal with slow or large objects and I don’t need swept collisions. Hopefully the logic path is useful to you.

ed: ds is passed into the method, it’s the difference in origins of the two hulls. And my BB extends from -y to +y and -x to +x.