collision

AABB.as

package simulation.collision 
{
	import math.vec2;
	
	public class AABB
	{
		public var min:vec2;
		public var max:vec2;
		
		public function AABB(xmin:Number, ymin:Number, xmax:Number, ymax:Number) 
		{
			min = new vec2(xmin, ymin);
			max = new vec2(xmax, ymax);
		}
		
	}

}

colutils.as

package simulation.collision 
{
	import math.vec2;
	
	//this is a package of collision-related functions
	//	-very little functionality really belongs inside collision classes; most of it is generally applicable and should be accessible to anyone
	public class colutils
	{
		
		private static var cp:vec2 = new vec2();//we re-use this to avoid generating garbage
		private static var segList:Vector.<Segment> = new Vector.<Segment>();
		
		/* not used
		//this is used by our static circle-collision functions; each iteration we find the single closest point and push out of it
		public static function GetSingleClosestPoint(segGrid:Grid_Segment, querypos:vec2, queryrad:Number, out_closestpoint:vec2):
		{
			var closest_pos:vec2 = null;
			var closest_dist2:Number = 99999999;//++TODO: better way to handle this..
			
			//gather nearby segs, checking for closest-ness
			var segs:Vector.<Segment> = segGrid.GatherCellContentsFromWorldspaceRegion(querypos.x - queryrad, querypos.y - queryrad, querypos.x + queryrad, querypos.y + queryrad);
			for (var i:int = 0; i < segs.length; i++)
			{
				var cp:vec2 = segs[i].GetClosestPoint(querypos);
				var dist2:Number = querypos.To(cp).LenSq();
				if (dist2 < closest_dist2)
				{
					closest_pos = cp;
					closest_dist2 = dist2;
				}
			}
			
			return closest_pos;
		}
		*/
		
		//returns 1 to indicate "no collision" and a number in [0,1) to indicate "collision at time t" (or maybe it's (0,1], i forget: point is, 1 means no collision)
		//
		//NOTE: this sweeps a fat ray vs tile geometry
		//	-it's meant as a helper to keep simulated particles (player, ragdoll) inside the world at all times (assuming they start inside the world)
		//		-use it like this: client calls this, then sets particle state to t=whatever we say, then they run static collision
		//		NOTE: the radius we're passed should be a shrunken inner core, not the total radius of the particle, or else resting contact will result in particles forever stuck at t=0
		public static function SweepCircleVsTiles(segGrid:Grid_Segment, pos:vec2, vel:vec2, radius:Number):Number
		{
			var t:Number = 1;
		
			var min_x:Number = Math.min(pos.x, pos.x + vel.x);
			var max_x:Number = Math.max(pos.x, pos.x + vel.x);
			var min_y:Number = Math.min(pos.y, pos.y + vel.y);
			var max_y:Number = Math.max(pos.y, pos.y + vel.y);
			
			segGrid.GatherCellContentsFromWorldspaceRegion(min_x - (radius + 1), min_y - (radius + 1), max_x + (radius +1), max_y + (radius + 1), segList);//NOTE: we don't really need to inflate things by +1, we're just being superstitious
			
			for (var i:int = 0; i < segList.length; i++)
			{
				/*
				//NOTE: IntersetWithRay is supposed to report -1 if we start overlapping, but I suspect it's not.. so, do static test ourselves
				segList[i].GetClosestPoint(pos, cp)
				if (cp.To(pos).Len() <= radius)
				{
					t = -1;
					
					trace("STARTING IN PENETRATION");
				}
				*/
				
				var result:Number = segList[i].IntersectWithRay(pos, vel, radius, new vec2(), new vec2());//NOTE: those temp vec2s generate garbage!!
				
				//DEBUG
				//trace("  result " + i + " = " + result);
				
				t = Math.min(t, result);
			}
			
			
			return Math.max(0, t);//if we started inside/penetrating something, we want to report t=0; it's up to the client to recover/push out of this situation
			
		}
		
		//returns 0 for "no closest point", -1 for "closest point is backfacing/penetration", 1 for "closest point is frontfacing"
		public static function GetSingleClosestPoint_Signed(segGrid:Grid_Segment, querypos:vec2, queryrad:Number, out_closestpoint:vec2):int
		{
			var closest_sign:int = 0;
			var closest_dist2:Number = 99999999;//++TODO: better way to handle this..
			
			//gather nearby segs, checking for closest-ness
			segGrid.GatherCellContentsFromWorldspaceRegion(querypos.x - queryrad, querypos.y - queryrad, querypos.x + queryrad, querypos.y + queryrad, segList);
			for (var i:int = 0; i < segList.length; i++)
			{
				//DEBUG: draw seg
				//rend.SetStyle(3, 0x228822, 20);
				//segs[i].DebugDraw_NoStyle(rend);
				
				var isPen:Boolean = segList[i].GetClosestPoint_IsBackfacing(querypos, cp);
				//var dist2:Number = querypos.To(cp).LenSq();
				var dx:Number = (cp.x - querypos.x);
				var dy:Number = (cp.y - querypos.y);
				var dist2:Number = (dx * dx) + (dy * dy);
				
				//HACKY: for two-sided segs, we want to "prefer" the front-facing edge; a simple way is to add a bias
				if (!isPen)
				{
					dist2 -= 0.1;//make front-facing points appear slightly closer
				}
				
				if (dist2 < closest_dist2)
				{
					out_closestpoint.Copy(cp);
					closest_dist2 = dist2;
					
					if (isPen)
					{
						closest_sign = -1;
					}
					else
					{
						closest_sign = 1;
					}
				}
			}
			
			return closest_sign;
		}
		
		
		//UGH: when the query point is ON a seg and we need the normal, we need to be able to ask the seg for it
		//	BUT: for some stupid reason the segment was ending up null.. so instead of fixing that bug, we'll just return a normal
		//		BUUUUUT: this normal is going to be wrong UNLESS the query point is on the surface of the closest seg
		public static function GetSingleClosestPoint_Signed_HACKY_NORMAL_IF_DIST_IS_ZERO(segGrid:Grid_Segment, querypos:vec2, queryrad:Number, out_closestpoint:vec2, out_normal:vec2):int
		{
			var temp_n:vec2 = new vec2();
			var closest_sign:int = 0;
			var closest_dist2:Number = 99999999;//++TODO: better way to handle this..
			
			//gather nearby segs, checking for closest-ness
			segGrid.GatherCellContentsFromWorldspaceRegion(querypos.x - queryrad, querypos.y - queryrad, querypos.x + queryrad, querypos.y + queryrad, segList);
			for (var i:int = 0; i < segList.length; i++)
			{
				//DEBUG: draw seg
				//rend.SetStyle(3, 0x228822, 20);
				//segs[i].DebugDraw_NoStyle(rend);
				
				var isPen:Boolean = segList[i].GetClosestPoint_IsBackfacing(querypos, cp);
				//var dist2:Number = querypos.To(cp).LenSq();
				var dx:Number = (cp.x - querypos.x);
				var dy:Number = (cp.y - querypos.y);
				var dist2:Number = (dx * dx) + (dy * dy);
				
				//HACKY: for two-sided segs, we want to "prefer" the front-facing edge; a simple way is to add a bias
				if (!isPen)
				{
					dist2 -= 0.1;//make front-facing points appear slightly closer
				}
				
				if (dist2 < closest_dist2)
				{
					out_closestpoint.Copy(cp);
					
					segList[i].HACKY_GetNormalAtPoint(cp, temp_n);
					out_normal.Copy(temp_n);
					
					closest_dist2 = dist2;
					if (isPen)
					{
						closest_sign = -1;
					}
					else
					{
						closest_sign = 1;
					}
				}
			}
			
			
			return closest_sign;
		}
		
		
		//NEW: an experiment with alt bounceblock collision: treat ninja as a circle
		public static function Penetration_Square_vs_Circle(spos:vec2, sr:Number, cpos:vec2, cr:Number, out_n:vec2):Number
		{
			//find closest point on square
			var v:vec2 = spos.To(cpos);
			
			var penx:Number = Math.abs(v.x) - sr;
			var peny:Number = Math.abs(v.y) - sr;
			if (penx <= 0 && peny <= 0)
			{
				//++TODO: deal with the case where cpos is inside the square (correct smallest penetration)
				//	++TODO: add a tiny bit of slop to make sure we catch the "pen is 0" case?
				
			}
			
			//clamp vector-to-circle to box surface
			v.x = Math.max( -sr, Math.min(sr, v.x));
			v.y = Math.max( -sr, Math.min(sr, v.y));
			
			var cp:vec2 = spos.Plus(v);//cp is the point on the square closest to the circle
			
			var n:vec2 = cp.To(cpos);
			var d:Number = n.Len();
			if (d == 0)
			{
				//cpos is exactly ON the surface; we should have handled this in the penetration case above!
				trace("WARNING! Penetration_Square_vs_Circle() gave up on a point on the surface");
				return 0;
			}
			var penr:Number = d - cr;
			if (penr < 0)
			{
				//circle is penetrating closest point; push it out
				out_n.x = n.x / d;
				out_n.y = n.y / d;
				
				return Math.abs(penr);			
				
			}
			
			
			
			
			//if we've reached here, no collision
			return 0;
		}
		
		//returns the minimum-translation vector (normal out_n, length = return value) that pushes the point out of the square, or 0 if the point isn't touching the square
		public static function Penetration_Square_vs_Point(pos:vec2, r:Number, point:vec2, out_n:vec2):Number
		{
			//var delta:vec2 = pos.To(point);
			var delta_X:Number = point.x - pos.x;
			var delta_Y:Number = point.y - pos.y;
			
			var pen_y:Number = r - Math.abs(delta_Y);
			if(0 < pen_y)
			{
				//overlapping in y; test x axis
				var pen_x:Number = r - Math.abs(delta_X);
				
				if(0 < pen_x)
				{
					//colliding!
					
					//handle collision physics
					if(pen_y <= pen_x)
					{
						//project along y
						out_n.x = 0;
						out_n.y = 1;
						if(delta_Y <= 0)
						{
							out_n.y = -1;
						}
						return pen_y;
					}
					else
					{
						//project along x
						out_n.y = 0;
						out_n.x = 1;
						if(delta_X <= 0)
						{
							out_n.x = -1;
						}
						
						return pen_x;
					}
				}
			}
			
			//if we've reached here, no collision
			return 0;
		}
		
		//returns true if the seg and circle intersect
		//
		//++TODO: why the fuck does this take p0,p1, AND length?! seems like stupid premature optimization.. .just calc length on-the-fly!
		public static function Overlap_Circle_Vs_Segment(circle_pos:vec2, circle_r:Number, seg_p0:vec2, seg_p1:vec2, seg_len:Number):Boolean
		{
			//var delta:vec2 = seg_p0.To(circle_pos);
			var delta_X:Number = circle_pos.x - seg_p0.x;
			var delta_Y:Number = circle_pos.y - seg_p0.y;
			
			//var temp_dir:vec2 = seg_p0.To(seg_p1);
			//temp_dir.Scale(1 / seg_len);
			var temp_dir_X:Number = (seg_p1.x - seg_p0.x) / seg_len;
			var temp_dir_Y:Number = (seg_p1.y - seg_p0.y) / seg_len;
			
			var dp:Number = (delta_X * temp_dir_X) + (delta_Y * temp_dir_Y);// temp_dir.Dot(delta);
			
			if (dp <= 0)
			{
				cp.Copy(seg_p0);//player is closest to laser's startpoing
			}
			else if (dp >= seg_len)
			{
				cp.Copy(seg_p1);//player is closest to laser's endpoint
			}
			else
			{
				//player is closest to a point on the interior of the laser lineseg
				cp.x = seg_p0.x + (dp * temp_dir_X);
				cp.y = seg_p0.y + (dp * temp_dir_Y);
			}
			
			var delta2_X:Number = circle_pos.x - cp.x;
			var delta2_Y:Number = circle_pos.y - cp.y;
			var len2:Number = (delta2_X * delta2_X) + (delta2_Y * delta2_Y);
			//if (test_pos.To(circle_pos).LenSq() < (circle_r * circle_r))
			if(len2 < (circle_r * circle_r))
			{
				return true;
			}
			return false;
		}
		
		//returns true if the distance between the two circle centers is less than total_r
		public static function Overlap_Circle_Vs_Circle(posA:vec2, rA:Number, posB:vec2, rB:Number):Boolean
		{
			//var delta:vec2 = posA.To(posB);
			var delta_X:Number = posB.x - posA.x;
			var delta_Y:Number = posB.y - posA.y;
			var len2:Number = (delta_X * delta_X) + (delta_Y * delta_Y);
			
			var rtot:Number = rA + rB;
			if (len2 < rtot * rtot)
			{
				return true;
			}
			return false;
		}
		
		
		//NOTE: these "time of intersection" functions return:
		//	a number in [0,1] to indicate an intersection
		//	-1 to indicate "starts in collision"
		//	2 to indicate "no intersection"
		public static function TimeOfIntersection_Circle_vs_Circle(posA:vec2, velA:vec2, posB:vec2, velB:vec2, total_radius:Number):Number
		{
			//shift everything so that B is stationary at the origin
			//var v:vec2 = velA.Minus(velB);
			//var p:vec2 = posA.Minus(posB);
			
			var v_X:Number = velA.x - velB.x;
			var v_Y:Number = velA.y - velB.y;
			
			var p_X:Number = posA.x - posB.x;
			var p_Y:Number = posA.y - posB.y;
			
			//var a:Number = v.Dot(v);
			//var b:Number = 2 * p.Dot(v);
			//var c:Number = p.Dot(p) - (total_radius * total_radius);
			
			var a:Number = (v_X * v_X) + (v_Y * v_Y);
			var b:Number = 2 * ((p_X * v_X) + (p_Y * v_Y));
			var c:Number = ((p_X * p_X) + (p_Y * p_Y)) - (total_radius * total_radius);
			
			var EPSILON:Number = 0.0001;//++TODO: use a real epsilon
			
			//NOTE: rather than solving the quadratic "blind", we'll apply the knowledge we have about the meaning of a,b,c in order to simplify things
			if ( c <= 0)
			{
				//the circles start in collision: don't bother sweeping
				//
				//++TODO: we might want to consider the relative velocities of the circles; if they're moving away from each other, maybe they shouldn't collide?
				return -1;
			}
			else 
			{
				//circles don't start in collision
				if (Math.abs(a) < EPSILON)
				{
					//circles aren't moving relative to each other; we're done
					return 2;
				}
				else
				{
					//circles are moving relative to each other
					if (b >= 0)
					{
						//circles are moving away from each other; we're done
						return 2;
					}
					else
					{
						//circles are moving towards each other: we have to perform the actual sweep test
						//
						//	-note that at this point we know the following, which should be enough to solve the quadratic "simply"
						//		a > 0 (we tested for a != 0, and since a is a vector dotted with itself it must be >= 0)
						//		b < 0
						//		c > 0
						var temp:Number = b*b - 4*a*c;
						if (temp < 0)
						{
							//imaginary roots: no solution
							return 2;
						}
						else
						{
							var d:Number = -0.5 * (b - Math.sqrt(temp));//note that d > 0 since b < 0 and Math.sqrt(temp) > 0
							var root_1:Number = d / a;	
							var root_2:Number = c / d;
							
							//++TODO: the above may not be robust; specifically, it may be better to calculate the roots using:
							// temp1 = (-b + sqrt(temp)) / 2a
							// temp2 = (-b - sqrt(temp)) / 2a
							//
							//and then use the root with the larger magnitude to re-calc the other root using the identity r1r2 = c/a:
							//	r1 = max(temp1, temp2) 
							//	r2 = c / (a*r1)
							//
							//our current code is assuming temp2 has the larger magnitude, then doing:
							//	r2 = (c/a)*(1/r1)	= (c/a)*(1/(d/a)) = c / d
							//
							//BUT: _temp1_ will always have the larger magnitude, since we know b<0 (and thus abs(-b+z) > abs(-b-z) for any z>0 (and since z = sqrt() we know it's >0)
							//	so: we should do:
							//		root_1 = (-b + sqrt(temp)) / 2a;
							//		root_2 = c / (a * root_1);
							//
							//wait: does our code use temp1, or temp2? -0.5*(b - sqrt) = (-b + sqrt)/2, so.. it's temp1, not temp2!!
							//SOOOOO: leave the code as-is
							
							//NOTE: we know both roots are positive (because a,c, and d are all > 0, see above), and we only care about the "earliest" root
							//	-so, we can use "min" to select the earliest root without worrying about finding a negative root
							return Math.min(root_1, root_2);
						}
					}
				}
			}
			
		}
		public static function TimeOfIntersection_Point_vs_Lineseg(startPos:vec2, vel:vec2, linepos0:vec2, linepos1:vec2, total_radius:Number):Number
		{
			//calculate lineseg's normal
			//var d:vec2 = linepos0.To(linepos1);
			//var dlen:Number = d.Len();
			//d.Scale(1 / dlen);
			//var n:vec2 = d.Perp();
			
			var d_X:Number = linepos1.x - linepos0.x;
			var d_Y:Number = linepos1.y - linepos0.y;
			var dlen:Number = Math.sqrt((d_X * d_X) + (d_Y * d_Y));
			d_X /= dlen;
			d_Y /= dlen;
			var n_X:Number = -d_Y;
			var n_Y:Number = d_X;
			
			//var p:vec2 = linepos0.To(startPos);//point's position relative to lineseg
			var p_X:Number = startPos.x - linepos0.x;
			var p_Y:Number = startPos.y - linepos0.y;
			
			
			//point's state along normal: position and velocity
			//var pn:Number = n.Dot(p);
			//var vn:Number = n.Dot(vel);
			var pn:Number = (n_X * p_X) + (n_Y * p_Y);
			var vn:Number = (n_X * vel.x) + (n_Y * vel.y);
			
			
			//point's position along line dir; this tells us if point is in lineseg's VR
			//var pd:Number = d.Dot(p);
			var pd:Number = (d_X * p_X) + (d_Y * p_Y);
			
			var apn:Number = Math.abs(pn);
			var relpos:Number = apn - total_radius;
			if (relpos < 0)
			{
				//point starts in slab region
				if (pd < 0 || pd > dlen)
				{
					return 2;//point is outside of lineseg VR; it will collide with lineseg endcap/circle before lineseg surface
				}
				else
				{
					return -1;//point is penetrating inflated lineseg
				}
			}
			else
			{
				//objects are initially separated
				if (pn * vn >= 0)
				{
					//circle is moving away from lineseg, OR circle isn't moving (vn == 0)
					return 2;
				}
				else
				{
					//circle is moving towards lineseg
					//
					//consider the case of r=0 (i.e intersection with line containing lineseg): solve pn + t*vn = 0 for t
					//	-the offset is tricky because we want: pn + t*vn = sign(pn)*r, or pn + t*vn = -sign(vn)*r
					//		-but we don't know how to handle the "sign" part
					//BUT: we know that pn and vn have opposite signs
					//	-so, we really just need to "reduce" pn by r (i.e shift everything so that the offset surface is at 0)
					//	-so, an equivalent equation should be:
					//		abs(pn) - r - t*abs(vn) = 0
					//		abs(pn) - r = t*abs(vn)
					//		t = (abs(pn) - r) / abs(vn)	//note that we know that abs(vn) != 0 because we know abs(pn) > 0 and pn*vn < 0
					//
					//this version considers the velocity to always be -ve, and the position to always be +ve
					//also, note that t will always be >= 0
					var t:Number = relpos / Math.abs(vn);
					
					//now, test to see if the point is within the lineseg VR at the time of intersection
					//var vd:Number = d.Dot(vel);
					var vd:Number = (d_X * vel.x) + (d_Y * vel.y);
					
					var intersection_pos:Number = pd + t * vd;
					if (intersection_pos < 0 || intersection_pos > dlen)
					{
						//the point intersects the slab, BUT not within the lineseg's VR
						return 2;
					}
					else
					{
						//we found an intersection
						return t;
					}
				}
			}					
		}
		//NOTE: this is sort of hacky; we're using circle-vs-circle and then filtering
		//	-note that this doesn't properly handle the endpoints of the arc, you need to sweep those seperately (just like Point_vs_Lineseg)
		public static function TimeOfIntersection_Circle_vs_Arc(posA:vec2, vel:vec2, arc_center:vec2, arc_p0:vec2, arc_p1:vec2, total_radius:Number):Number
		{
			//NOTE: this is sort of tricky/weird.. arc is two-sided, so we don't know whether we should offset it inward or outward, so for now we just do both and use the first intersection :)
			//
			//++TODO: a less brute-force method please!
			//var arcrad:Number = arc_center.To(arc_p0).Len();
			var dx:Number = arc_p0.x - arc_center.x;
			var dy:Number = arc_p0.y - arc_center.y;
			var arcrad:Number = Math.sqrt((dx * dx) + (dy * dy));
			
			var t0:Number = TimeOfIntersection_Circle_vs_Arc_HELPER(posA, vel, arc_center, arc_p0, arc_p1, arcrad + total_radius);
			var t1:Number = TimeOfIntersection_Circle_vs_Arc_HELPER(posA, vel, arc_center, arc_p0, arc_p1, arcrad - total_radius);
			
			return Math.min(t0, t1);			
		}
		private static function TimeOfIntersection_Circle_vs_Arc_HELPER(posA:vec2, vel:vec2, arc_center:vec2, arc_p0:vec2, arc_p1:vec2, radius:Number):Number
		{
			//shift everything so that B is stationary at the origin
			//var p:vec2 = posA.Minus(arc_center);
			var p_X:Number = posA.x - arc_center.x;
			var p_Y:Number = posA.y - arc_center.y;
			
			var a:Number = vel.Dot(vel);
			//var b:Number = 2 * p.Dot(vel);
			//var c:Number = p.Dot(p) - (radius * radius);
			var b:Number = 2 * ((p_X * vel.x) + (p_Y * vel.y));
			var c:Number = ((p_X * p_X) + (p_Y * p_Y)) - (radius * radius);
			
			
			var EPSILON:Number = 0.0001;//++TODO: use a real epsilon
			
			//NOTE: we're assuming that the ray doesn't start in collision with the arc, but it MAY start in collision with the circle
			//	(i.e c may be negative, unline in the circle-vs-circle case)
			
			if (Math.abs(a) < EPSILON)
			{
				//circles aren't moving relative to each other; we're done
				return 2;
			}
			else
			{

				//circles are moving towards each other: we have to perform the actual sweep test
				//
				//	-note that at this point we know the following, which should be enough to solve the quadratic "simply"
				//		a > 0 (we tested for a != 0, and since a is a vector dotted with itself it must be >= 0)
				//
				//unlike in the circle-vs-circle case, c may be negative and b may be positive
				var temp:Number = b*b - 4*a*c;
				if (temp < 0)
				{
					//imaginary roots: no solution
					return 2;
				}
				else
				{
					var d:Number = -0.5 * (b - Math.sqrt(temp));//note that d > 0 since b < 0 and Math.sqrt(temp) > 0
					var root_1:Number = d / a;	
					var root_2:Number = c / d;
					
					//++TODO: the above may not be robust; specifically, it may be better to calculate the roots using:
					// temp1 = (-b + sqrt(temp)) / 2a
					// temp2 = (-b - sqrt(temp)) / 2a
					//
					//and then use the root with the larger magnitude to re-calc the other root using the identity r1r2 = c/a:
					//	r1 = max(temp1, temp2) 
					//	r2 = c / (a*r1)
					//
					//our current code is assuming temp2 has the larger magnitude, then doing:
					//	r2 = (c/a)*(1/r1)	= (c/a)*(1/(d/a)) = c / d
					//
					//BUT: _temp1_ will always have the larger magnitude, since we know b<0 (and thus abs(-b+z) > abs(-b-z) for any z>0 (and since z = sqrt() we know it's >0)
					//	so: we should do:
					//		root_1 = (-b + sqrt(temp)) / 2a;
					//		root_2 = c / (a * root_1);
					//
					//wait: does our code use temp1, or temp2? -0.5*(b - sqrt) = (-b + sqrt)/2, so.. it's temp1, not temp2!!
					//SOOOOO: leave the code as-is
					
					//we now need to filter out the roots depending on which is actually on the arc
					//
					//NOTE: code is copy+pasted from closest-point-on-arc
					//var v0:vec2 = arc_center.To(arc_p0);	
					//var v1:vec2 = arc_center.To(arc_p1);	
					var v0_X:Number = arc_p0.x - arc_center.x;
					var v0_Y:Number = arc_p0.y - arc_center.y;
					var v1_X:Number = arc_p1.x - arc_center.x;
					var v1_Y:Number = arc_p1.y - arc_center.y;
					
					//var v:vec2 = arc_p0.To(arc_p1);				//this tell us the "direction" of the arc; we use this to handle concave and convex arcs uniformly
					var v_X:Number = arc_p1.x - arc_p0.x;
					var v_Y:Number = arc_p1.y - arc_p0.y;
					
					//var vp0:Number = v.Dot(v0.Perp());	//NOTE: this is a bit hacky; really we only care about the signs of vp0,vp1;
					//var vp1:Number = v.Dot(v1.Perp());	//if d is on the "same side" of v0.Perp as v is, it's "inside" the arc region, otherwise it's outside; the opposite applies to v1 
					var vp0:Number = (v_X * -v0_Y) + (v_Y * v0_X);
					var vp1:Number = (v_X * -v1_Y) + (v_Y * v1_X);
					
					if (root_1 < 0)
					{
						root_1 = 2;
					}
					if (root_2 < 0)
					{
						root_2 = 2;
					}
					if (root_1 <= 1)
					{
						//root is valid; check if it's on the arc
						//var pos1:vec2 = new vec2(posA.x + root_1 * vel.x, posA.y + root_1 * vel.y);
						//var d1:vec2 = arc_center.To(pos1);
						var d1_X:Number = (posA.x + (root_1 * vel.x)) - arc_center.x;
						var d1_Y:Number = (posA.y + (root_1 * vel.y)) - arc_center.y;
						
						//var d1p0:Number = d1.Dot(v0.Perp());
						//var d1p1:Number = d1.Dot(v1.Perp());
						var d1p0:Number = (d1_X * -v0_Y) + (d1_Y * v0_X);
						var d1p1:Number = (d1_X * -v1_Y) + (d1_Y * v1_X);
						
						if ((d1p0 * vp0 <= 0) || (d1p1 * vp1 >= 0))
						{
							//root is not in arc
							root_1 = 2;
						}
					}
					if (root_2 <= 1)
					{
						//root is valid; check if it's on the arc
						//var pos2:vec2 = new vec2(posA.x + root_2 * vel.x, posA.y + root_2 * vel.y);
						//var d2:vec2 = arc_center.To(pos2);
						var d2_X:Number = (posA.x + (root_2 * vel.x)) - arc_center.x;
						var d2_Y:Number = (posA.y + (root_2 * vel.y)) - arc_center.y;
						
						//var d2p0:Number = d2.Dot(v0.Perp());
						//var d2p1:Number = d2.Dot(v1.Perp());
						var d2p0:Number = (d2_X * -v0_Y) + (d2_Y * v0_X);
						var d2p1:Number = (d2_X * -v1_Y) + (d2_Y * v1_X);
						
						if ((d2p0 * vp0 <= 0) || (d2p1 * vp1 >= 0))
						{
							//root is not in arc
							root_2 = 2;
						}
					}
					
					return Math.min(root_1, root_2);
				}
				
			}
			
		}
		
		
	}

}

Grid_Base.as

package simulation.collision 
{
	import math.vec2;
	
	//a basic grid; because we don't have generics in AS3, the actual "payload" of the grid 
	//
	//NOTE: this class _should_ be abstract, but isn't because of stupid AS3
	public class Grid_Base
	{
		protected var numcols:int;
		protected var numrows:int;
		protected var numcells:int;
		protected var cellsize:Number;
		
		public function Grid_Base(num_cols:int, num_rows:int, cell_size:Number) 
		{
			numcols = num_cols;
			numrows = num_rows;
			cellsize = cell_size;
			numcells = numcols * numrows;
		}
		
		
		// ACCESS/MAPPING ---------------------------------------------------------------------------
		
		//converts a worldspace coord into a gridspace coord (i.e column or row index)
		protected final function WorldspaceToGridspace(pos:Number):int
		{
			return Math.floor(pos / cellsize);
		}

		//given a position (relative to grid origin), returns a UID to the cell corresponding to that position
		protected final function GetCellIndexFromWorldspacePosition(pos_x:Number, pos_y:Number):int
		{
			return GetCellIndexFromGridspacePosition(WorldspaceToGridspace(pos_x), WorldspaceToGridspace(pos_y));
		}
		
		//given a grid position (index of a cell in the virtual 2D grid), returns a UID to the cell corresponding to that position
		//	NOTE: this sanitizes input, i.e it will clamp invalid coords to the closest valid coord
		protected final function GetCellIndexFromGridspacePosition(pos_u:int, pos_v:int):int
		{
			if (pos_u < 0 || pos_u >= numcols || pos_v < 0 || pos_v >= numrows)
			{
				//NEW: we clamp silently to "correct" this problem, rather than failing and complaining about it
				pos_u = Math.max(0, Math.min(numcols - 1, pos_u));
				pos_v = Math.max(0, Math.min(numrows - 1, pos_v));
				
				//++TODO: enable this to propagate the error to calling functions
				//trace("WARNING! GetCellIndexFromGridspacePosition() was called with an invalid position: " + pos_u + "," + pos_v);
				//return -1;
			}
			
			return ((pos_v * numcols) + pos_u);
		}
		
		//used for debugging
		public final function DEBUG_GetWorldspaceCellCenterPositionFromIndex(id:int):vec2
		{
			if (id != -1)
			{
				var u:int = id % numcols;
				var v:int = Math.floor(id / numcols);
				
				return new vec2((u + 0.5) * cellsize, (v + 0.5) * cellsize);
			}
			else
			{
				return null;
			}
		}
		
	}

}

Grid_Edges.as

package simulation.collision 
{
	import math.vec2;
	import simpleFramework.SimpleRenderer;
	
	import tiles.edgetypes;
	import tiles.edgedefs;
	
	//annoyingly, entity navigation/movement was very difficult to get working without edge states
	//	-this is only because we wanted to replicate the old behaviours, which are predicated on edge states
	//
	//anyway, this grid is used to store the state of edges on a grid that's 2x the resolution of the tile grid
	//	-using double resolution lets us support entity placement in half-tile increments (the old movement can be emulated by simply testing in tile-sized movement increments)
	//
	//each "cell" in this grid tracks the state of its right and bottom edges
	//	-this means the top-left corner can't have edge states, but this is fine since in N that location is invalid (i.e is beyond the barrier/boundary edges)
	//	-to simplify door handling, we track door-based edge states independantly from tile-based edge states
	//
	//NEW: doors function slightly differently
	//	-we can't set the edge states directly, since there may be multiple doors affecting a particular edge
	//	-instead, doors increment/decrement the edge states; non-0 state is considered "interesting", 0 is considered "empty"
	public class Grid_Edges extends Grid_Base
	{
		private var edges_tileX:Vector.<int>;//NOTE: "X" means "edge that's +X from the cell center"
		private var edges_tileY:Vector.<int>;//	-this is a bit confusing, because X edges are vertical and Y edges are horizontal
		private var edges_doorX:Vector.<int>;	
		private var edges_doorY:Vector.<int>;	
		
		public function Grid_Edges(num_cols:int, num_rows:int, cell_size:Number) 
		{
			super(num_cols, num_rows, cell_size);
			
			edges_tileX = new Vector.<int>(numcells, true);
			edges_tileY = new Vector.<int>(numcells, true);
			edges_doorX = new Vector.<int>(numcells, true);
			edges_doorY = new Vector.<int>(numcells, true);
		}
		
		public function Clear():void
		{
			for (var i:int = 0; i < numcells; i++)
			{
				edges_tileX[i] = edgetypes.EMPTY;
				edges_tileY[i] = edgetypes.EMPTY;
				edges_doorX[i] = 0;
				edges_doorY[i] = 0;
			}
		}
		
		public function Debug_Draw(rend:SimpleRenderer):void
		{
			for (var u:int = 0; u < numcols; u++)
			{
				for (var v:int = 0; v < numrows; v++)
				{
					var halfwidth:Number = cellsize * 0.5;
					var index:int = GetCellIndexFromGridspacePosition(u, v);
					var cellpos:vec2 = DEBUG_GetWorldspaceCellCenterPositionFromIndex(index);
					
					
					if (edges_tileX[index] != edgetypes.EMPTY)
					{
						if (edges_tileX[index] == edgetypes.PARTIAL)
						{
							rend.SetStyle(0, 0xAAAAAA, 100);
						}
						else
						{
							rend.SetStyle(0, 0x222222, 100);
						}
						rend.DrawLine(cellpos.x + halfwidth - 2, cellpos.y - halfwidth + 2, cellpos.x + halfwidth - 2, cellpos.y + halfwidth - 2);
					}
					if (edges_tileY[index] != edgetypes.EMPTY)
					{
						if (edges_tileY[index] == edgetypes.PARTIAL)
						{
							rend.SetStyle(0, 0xAAAAAA, 100);
						}
						else
						{
							rend.SetStyle(0, 0x222222, 100);
						}
						rend.DrawLine(cellpos.x - halfwidth + 2, cellpos.y + halfwidth - 2, cellpos.x + halfwidth - 2, cellpos.y + halfwidth - 2);
					}
					
					
					rend.SetStyle(0, 0x228822, 100);
					if (edges_doorX[index] != 0)
					{
						rend.DrawAABB(cellpos.x + halfwidth - 2, cellpos.x + halfwidth + 2, cellpos.y - halfwidth + 2, cellpos.y + halfwidth - 2);
					}
					if (edges_doorY[index] != 0)
					{
						rend.DrawAABB(cellpos.x - halfwidth + 2, cellpos.x + halfwidth - 2, cellpos.y + halfwidth - 2, cellpos.y + halfwidth + 2);
					}
					
				}
			}
		}
		
		//this is used to allow doors to directly add/remove themselves from specific cells
		public function DOOR_GetCellIndexFromGridspacePosition(u:int, v:int):int
		{
			return GetCellIndexFromGridspacePosition(u, v);
		}
		
		public function GetGridCoordinateFromWorldspace_1D(world_coord:Number):int
		{
			return WorldspaceToGridspace(world_coord);
		}
		//this is used to get the worldspace position of an edge of the cell specified by grid_coord
		//	dir should be -1 or 1
		public function GetWorldspaceCoordinateFromGridEdge_1D(grid_coord:int, dir:int):int
		{
			return ((grid_coord + Math.max(0,dir)) * cellsize);
		}
		
		//++TODO: is there some sort of single generic query we could use here?
		//
		//++TODO: this code is a bit hacky and not "robust" (i.e dir_v == 0 doesn't imply dir_u != 0)
		//	-also, it seems stupid to set things up like this.. there must be a more elegant API for querying 
		public function IsSolid(u:int, v:int, dir_u:int, dir_v:int):Boolean
		{
			var index:int = GetIndexFromGridspaceAndOffset(u, v, dir_u, dir_v);
			if (dir_v == 0)
			{
				return (edges_tileX[index] == edgetypes.SOLID || edges_doorX[index] != 0);
			}
			else
			{
				return (edges_tileY[index] == edgetypes.SOLID || edges_doorY[index] != 0);
			}
		}
		public function IsSolid_IgnoreDoors(u:int, v:int, dir_u:int, dir_v:int):Boolean
		{
			var index:int = GetIndexFromGridspaceAndOffset(u, v, dir_u, dir_v);	
			if (dir_v == 0)
			{
				return (edges_tileX[index] == edgetypes.SOLID);
			}
			else
			{
				return (edges_tileY[index] == edgetypes.SOLID);
			}
		}
		public function IsEmpty(u:int, v:int, dir_u:int, dir_v:int):Boolean
		{
			var index:int = GetIndexFromGridspaceAndOffset(u, v, dir_u, dir_v);
			if (dir_v == 0)
			{
				return (edges_tileX[index] == edgetypes.EMPTY && edges_doorX[index] == 0);
			}
			else
			{
				return (edges_tileY[index] == edgetypes.EMPTY && edges_doorY[index] == 0);
			}
		}
		
		//these functions return true if the path from start_ to end_ is empty (i.e the rect swept by the lineseg min_ max_ from start_ to end_)
		//
		//++TODO: clients shouldn't have to pass in dir, this can be inferred from start_ and end_
		public function ScanHorizontal(min_v:int, max_v:int, start_u:int, end_u:int):Boolean
		{
			var du:int = end_u - start_u;
			if (du != 0)
			{
				var dir_u:int = du / Math.abs(du);
				return ScanHorizontal_Directed(min_v, max_v, start_u, end_u, dir_u);
			}
			return true;//if we've reached here, we were able to move from start_ to end_ without hitting anything
		}
		public function ScanHorizontal_Directed(min_v:int, max_v:int, start_u:int, end_u:int, dir_u:int):Boolean
		{
			var u:int = start_u;
			while (u != end_u)
			{
				//try to step forward to the next cell
				if (!IsEmpty_Column(u, min_v, max_v, dir_u))
				{
					return false;//we've hit something; we can't step forward
				}
				
				//if we reached here, the current column is empty; advance the search front
				u += dir_u;
				
				//DEBUG
				if (Math.abs(u) > 100)
				{
					trace("-infinite loop in ScanHorizontal: " + min_v + "-" + max_v + " .. " + start_u + "," + dir_u);
					return false;
				}
			}
			return true;
		}
		public function ScanVertical(min_u:int, max_u:int, start_v:int, end_v:int):Boolean
		{
			var dv:int = end_v - start_v;
			if (dv != 0)
			{
				var dir_v:int = dv / Math.abs(dv);
				return ScanVertical_Directed(min_u, max_u, start_v, end_v, dir_v);
			}
			return true;//if we've reached here, we were able to move from start_ to end_ without hitting anything
		}
		public function ScanVertical_Directed(min_u:int, max_u:int, start_v:int, end_v:int, dir_v:int):Boolean
		{
			var v:int = start_v;
			while (v != end_v)
			{
				//scan current row
				if (!IsEmpty_Row(v, min_u, max_u, dir_v))
				{
					return false;//we've hit something; we can't step forward
				}
				
				//if we reached here, the current row is empty; advance the search front
				v += dir_v;
				
				//DEBUG
				if (Math.abs(v) > 100)
				{
					trace("-infinite loop in ScanVertical: " + min_u + "-" + max_u + " .. " + start_v + "," + dir_v);
					return false;
				}
			}
			return true;
		}
		
		//these functions search a "slab" of cells along an axis, stopping once they find a non-empty cell (and reporting the grid coord where this cell was located)
		//	NOTE: these functions report the LAST REACHABLE CELL
		//
		//++TODO: it's really stupid/annoying that we have to handle each axis separately
		public function SweepHorizontal(min_v:int, max_v:int, start_u:int, dir:int):int
		{
			var u:int = start_u;
			while (true)
			{
				//scan current column
				if (!IsEmpty_Column(u, min_v, max_v, dir))
				{
					break;
				}
				
				//if we reached here, the current column is empty; advance the search front
				u += dir;
				
				//DEBUG
				if (Math.abs(u) > 100)
				{
					trace("-infinite loop in SweepHorizontal: " + min_v + "-" + max_v + " .. " + start_u + "," + dir);
					return start_u;
				}
			}
			
			return u;
		}
		public function SweepVertical(min_u:int, max_u:int, start_v:int, dir:int):int
		{
			var v:int = start_v;
			while (true)
			{
				//scan current row
				if (!IsEmpty_Row(v, min_u, max_u, dir))
				{
					break;
				}
				
				//if we reached here, the current row is empty; advance the search front
				v += dir;
				
				//DEBUG
				if (Math.abs(v) > 100)
				{
					trace("-infinite loop in SweepVertical: " + min_u + "-" + max_u + " .. " + start_v + "," + dir);
					return start_v;
				}
			}
			
			return v;
		}
		//returns true if the row/column is empty
		public function IsEmpty_Column(u:int, min_v:int, max_v:int, dir:int):Boolean
		{
			for (var v:int = min_v; v <= max_v; v++)
			{
				if (!IsEmpty(u, v, dir, 0))
				{
					return false;//we hit something
				}
			}
			return true;
		}
		public function IsEmpty_Row(v:int, min_u:int, max_u:int, dir:int):Boolean
		{
			for (var u:int = min_u; u <= max_u; u++)
			{
				if (!IsEmpty(u, v, 0, dir))
				{
					return false;//we hit something
				}
			}
			return true;
		}
		
		
		
		//uses the edgedefs to set edge states
		public function GAME_LoadTileEdges(tile_u:int, tile_v:int, tileID:int):void
		{
			var origin_u:int = tile_u * 2;
			var origin_v:int = tile_v * 2;
			
			for (var i:int = 0; i < 3; i++)
			{
				for (var j:int = 0; j < 2; j++)
				{
					var Xu:int = origin_u - 1 + i;
					var Xv:int = origin_v + j;
					
					var Yu:int = origin_u + j;
					var Yv:int = origin_v - 1 + i;
					
					var Xid:int = GetCellIndexFromGridspacePosition(Xu, Xv);
					var Yid:int = GetCellIndexFromGridspacePosition(Yu, Yv);
					
					var offset:int = i + (j * 3);
					
					LoadEdgeState_X(Xid, edgedefs.GetEdgeState_X(tileID, offset));
					LoadEdgeState_Y(Yid, edgedefs.GetEdgeState_Y(tileID, offset));
				}
			}
		}
		
		//doors index their cells directly (they're setup at load time with the correct index)
		public function DOOR_IncrementEdge(cell_index:int, isHorizontal:Boolean):void
		{
			if (cell_index < 0 || cell_index >= numcells)
			{
				trace("WARNING! DOOR_IncrementEdge() was called with an invalid index: " + cell_index);
				return;
			}
			
			if (isHorizontal)
			{
				edges_doorX[cell_index] += 1;
			}
			else
			{
				edges_doorY[cell_index] += 1;
			}
		}
		public function DOOR_DecrementEdge(cell_index:int, isHorizontal:Boolean):void
		{
			if (cell_index < 0 || cell_index >= numcells)
			{
				trace("WARNING! DOOR_DecrementEdge() was called with an invalid index: " + cell_index);
				return;
			}
			
			if (isHorizontal)
			{
				if (edges_doorX[cell_index] <= 0)
				{
					trace("WARNING! DOOR_DecrementEdge() was called on an empty edge! " + cell_index);
					return;
				}
				edges_doorX[cell_index] -= 1;
			}
			else
			{
				if (edges_doorY[cell_index] <= 0)
				{
					trace("WARNING! DOOR_DecrementEdge() was called on an empty edge! " + cell_index);
					return;
				}
				
				edges_doorY[cell_index] -= 1;
			}
		}
		
		private function GetIndexFromGridspaceAndOffset(u:int, v:int, dir_u:int, dir_v:int):int
		{
			var index:int = -1;
			
			if (dir_v == 0)
			{
				if (dir_u == -1)
				{
					index = GetCellIndexFromGridspacePosition(u - 1, v);
				}
				else if (dir_u == 1)
				{
					index = GetCellIndexFromGridspacePosition(u, v);
				}
			}
			else if (dir_u == 0)
			{
				if (dir_v == -1)
				{
					index = GetCellIndexFromGridspacePosition(u, v - 1);
				}
				else if (dir_v == 1)
				{
					index = GetCellIndexFromGridspacePosition(u, v);
				}
				
			}
			
			return index;
		}
		
		//NOTE: we use max() to choose the most-solid edgestate (this is how we resolve adjacent tiles with different edge states -- we choose the most-solid state)
		private function LoadEdgeState_X(index:int, edgestate:int):void
		{
			if (edges_tileX[index] == edgetypes.SOLID && edgestate == edgetypes.SOLID)
			{
				edges_tileX[index] = edgetypes.EMPTY;//suppress this edge; it's an internal edge
			}
			else
			{
				edges_tileX[index] = Math.max(edges_tileX[index], edgestate);
			}
		}
		private function LoadEdgeState_Y(index:int, edgestate:int):void
		{
			if (edges_tileY[index] == edgetypes.SOLID && edgestate == edgetypes.SOLID)
			{
				edges_tileY[index] = edgetypes.EMPTY;//suppress this edge; it's an internal edge
			}
			else
			{
				edges_tileY[index] = Math.max(edges_tileY[index], edgestate);
			}
		}
		private function SetDoorState_X(index:int, edgestate:int):void
		{
			edges_doorX[index] = edgestate;
		}
		private function SetDoorState_Y(index:int, edgestate:int):void
		{
			edges_doorY[index] = edgestate;
		}
		
		
	}

}

Grid_Entity.as

package simulation.collision 
{
	
	import math.vec2;
	import simpleFramework.SimpleRenderer;
	
	import simulation.entities.Entity_Base;
	
	//a simple grid that stores each entity in the cell containing its center-point
	public class Grid_Entity extends Grid_Base
	{
		private var cells:Vector.< Vector.<Entity_Base> >;
		
		public function Grid_Entity(num_cols:int, num_rows:int, cell_size:Number)
		{
			super(num_cols, num_rows, cell_size);
			
			cells = new Vector.< Vector.< Entity_Base > >(numcells, true);
			for (var i:int = 0; i < numcells; i++)
			{
				cells[i] = new Vector.<Entity_Base>();
			}
		}
			
		public function Debug_Draw(rend:SimpleRenderer):void
		{
			rend.SetStyle(0, 0x222288, 100);
			for (var u:int = 0; u < numcols; u++)
			{
				for (var v:int = 0; v < numrows; v++)
				{
					var cellpos:vec2 = new vec2((0.5 + u) * cellsize, (0.5 + v) * cellsize);
					rend.DrawStringAtPosition("" + cells[GetCellIndexFromGridspacePosition(u, v)].length, cellpos.x, cellpos.y);
				}
			}
		}
		
		//empties all cells; note that whatever was in the cells should have been deleted before this is called, we don't take responsibility for cleaning up the contents
		public function Clear():void
		{
			for (var i:int = 0; i < numcells; i++)
			{
				var cell:Vector.<Entity_Base> = cells[i];//GHA.. stupid FD doesn't recognize the type of cells[i] unless we do this
				cell.length = 0;//this is apparently how you delete/clear a vector
			}
		}
		
		public function ENTITY_Move(new_pos:vec2, entity:Entity_Base):void
		{
			var cur_index:int = entity.GRID_GetGridIndex();
			var new_index:int = GetCellIndexFromWorldspacePosition(new_pos.x, new_pos.y);
			
			if (cur_index != new_index)
			{
				if (cur_index == -1)
				{
					trace("WARNING! ENTITY_Move() was called with an entity that's not in the grid: " + entity.GetUID());
				}
				else
				{
					RemoveEntityFromCell(cur_index, entity);
					InsertEntityIntoCell(new_index, entity);
					entity.GRID_SetGridIndex(new_index);
				}
			}
			
		}
		public function ENTITY_Remove(entity:Entity_Base):void
		{
			var index:int = entity.GRID_GetGridIndex();
			if (index == -1)
			{
				trace("WARNING! ENTITY_Remove() was called with an entity that's not in the grid: " + entity.GetUID());
			}
			else
			{
				RemoveEntityFromCell(index, entity);
				entity.GRID_SetGridIndex(-1);
			}
		}
		public function ENTITY_Add(pos:vec2, entity:Entity_Base):void
		{
			var index:int = entity.GRID_GetGridIndex();
			if (index != -1)
			{
				trace("WARNING! ENTITY_Add() was called with an entity that's already in the grid: " + entity.GetUID() + "," + index);
			}
			else
			{
				var new_index:int = GetCellIndexFromWorldspacePosition(pos.x, pos.y);
				InsertEntityIntoCell(new_index, entity);
				entity.GRID_SetGridIndex(new_index);
			}
		}
		
		//NOTE: Insert/Remove don't update the entity's cached index, that needs to be done by the caller
		private function RemoveEntityFromCell(cell_index:int, entity:Entity_Base):void
		{
			var cell:Vector.<Entity_Base> = cells[cell_index];
			var entity_index:int = cell.indexOf(entity);
			if (entity_index == -1)
			{
				//couldn't find the entity!
				trace("WARNING! RemoveEntityFromCell() found an out-of-sync cell index: " + cell_index);
			}
			else
			{
				cell.splice(entity_index, 1);
			}
		}
		private function InsertEntityIntoCell(cell_index:int, entity:Entity_Base):void
		{
			var cell:Vector.<Entity_Base> = cells[cell_index];
			cell.push(entity);
		}
		
		//returns a list of all entities the 3x3 region of cells centered on the query pos
		//	NOTE: the name is meant to reflect that this isn't a simple "look at a cell's list" operation, we have to build a list of Entities
		//	NOTE: this should never be called with a position located in the outer/boundary region of cells; this is an invalid position for any object to be
		//
		//NEW: to avoid creating garbage, caller is expected to pass in a list to fill
		public function GatherCellContentsInNeighbourhood(query_pos:vec2, out_entList:Vector.<Entity_Base>):void
		{
			//var outList:Vector.<Entity_Base> = new Vector.<Entity_Base>();
			out_entList.length = 0;//clear the list
			
			var query_u:int = WorldspaceToGridspace(query_pos.x);
			var query_v:int = WorldspaceToGridspace(query_pos.y);
			
			//NEW: we might be using an over-inflated query radius, so we want to handle (via clamping) the case where the query region is out-of-bounds
			//	-the base class will clamp indices passed to GetCellIndexFromGridspacePosition
			/*
			if (query_u <= 0 || query_u >= (numcols - 1) || query_v <= 0 || query_v >= (numrows-1))
			{
				//query position is in an outer/boundary row or column; this is unsupported
				//trace("WARNING! GatherCellContentsInNeighbourhood() was passed a query position in a boundary cell: " + query_u + "," + query_v);
				return outList;	
			}
			*/
			
			for (var offset_u:int = -1; offset_u < 2; offset_u++)
			{
				for (var offset_v:int = -1; offset_v < 2; offset_v++)
				{
					//NOTE: we know the index will be valid, because we know that u and v aren't in the first/last row or column
					var index:int = GetCellIndexFromGridspacePosition(query_u + offset_u, query_v + offset_v);
					var cell:Vector.<Entity_Base> = cells[index];
					
					//++TODO: would it make more sense to use concat()? this just seemed stupid -- it would keep creating new vectors!
					for (var k:int = 0; k < cell.length; k++)
					{
						out_entList.push(cell[k]);
					}
				}
			}
		}
		
	}

}

Grid_Segment.as

package simulation.collision 
{
	import math.vec2;
	import simpleFramework.SimpleRenderer;
	
	import simulation.collision.Segment;
	
	//the static grid holds lists of Segments that define the tile collision shapes
	//
	//NOTE: this is a very basic grid, it doesn't support virtual/hashing access (i.e all coords must be +ve and within the grid bounds)
	//	-each segment is stored in a single cell: the cell that contains the tile which generated the segment
	public class Grid_Segment extends Grid_Base
	{	
		private var cells:Vector.< Vector.<Segment> >;
		
		//new: keep temp variables around so we don't create garbage
		private var TEMP_ray_pos:vec2;
		private var TEMP_ray_vec:vec2;
		private var TEMP_temp_p:vec2;
		private var TEMP_temp_n:vec2;
		
		public function Grid_Segment(num_cols:int, num_rows:int, cell_size:Number)
		{
			super(num_cols, num_rows, cell_size);
			
			cells = new Vector.< Vector.< Segment > >(numcells, true);
			for (var i:int = 0; i < numcells; i++)
			{
				cells[i] = new Vector.<Segment>();
			}
			
			TEMP_ray_pos = new vec2();
			TEMP_ray_vec = new vec2();
			TEMP_temp_p = new vec2();
			TEMP_temp_n = new vec2();
		}
		
		public function DEBUG_Draw(rend:SimpleRenderer):void
		{
			for (var i:int = 0; i < cells.length; i++)
			{
				for (var j:int = 0; j < cells[i].length; j++)
				{
					cells[i][j].DebugDraw(rend);
				}
			}
		}
		
		//this finds the first intersection of a ray vs all segments in the grid, using Amanitides/Woo's "A Fast Voxel Traversal" method
		//	-it returns the distance from pos to the intersection point of the ray starting at pos and having direction dir (and fills out the intersection position and direction)
		//	-it returns -1 if there were any problems
		//
		//++TODO: this is super-non-robust
		//	-we assume that pos is in the grid/world
		//	-we assume that the ray will hit something before exiting the world
		//++TODO: does dir have to be unit-length? this should work either way, i.e the result returned is parametric distance in units of length-of-dir
		//
		//++TODO: does this belong in the grid, or in a helper? (or the sim?)
		public function GetRaycastDistance(pos_x:Number, pos_y:Number, dir_x:Number, dir_y:Number, out_pos:vec2, out_normal:vec2):Number
		{
			//DEBUG
			//trace("GetRaycastDistance: " + pos_x + "," + pos_y + "," + dir_x + "," + dir_y);
			
			
			// INIT 
			var U:int = WorldspaceToGridspace(pos_x);//get starting grid coords
			var V:int = WorldspaceToGridspace(pos_y);
				
			//++TODO: a less hacky way to init the tMax params
				
			var stepU:int = 0;			//sign of ray direction along each axis
			var stepV:int = 0;
			var tMaxX:Number = 999999;	//value of t (ray parameter) at which ray crosses first x/y boundary
			var tMaxY:Number = 999999;	
			var tDeltaX:Number = 0;		//width/height of a cell in units of 't'
			var tDeltaY:Number = 0;
			
			if(dir_x < 0)
			{
				stepU = -1;
				tMaxX = ((U * cellsize) - pos_x) / dir_x;
				tDeltaX = cellsize / -dir_x;
			}
			else if(dir_x > 0)
			{
				stepU = 1;
				tMaxX = (((U + 1) * cellsize) - pos_x) / dir_x;
				tDeltaX = cellsize / dir_x;
			}
			
			if(dir_y < 0)
			{
				stepV = -1;
				tMaxY = ((V * cellsize) - pos_y) / dir_y;
				tDeltaY = cellsize / -dir_y;
			}
			else if(dir_y > 0)
			{
				stepV = 1;
				tMaxY = (((V + 1) * cellsize) - pos_y) / dir_y;
				tDeltaY = cellsize / dir_y;
			}
			
			if (stepU == 0 && stepV == 0)
			{
				//uh.. someone passed in a null vector!
				trace("WARNING! some jackass called GetRaycastDistance() with a null ray vector: " + dir_x + "," + dir_y);
				return -1;
			}
			
			// TRAVERSAL
			
			//build an explicit "ray" (the narrow-phase tests test vs. a lineseg and not an actual "ray")
			//
			//++TODO: we should calculate the point where the ray exits the world/grid bounds, and use that point instead
			//	-we could also then determine if that point is in the same row/column as the start point, and if so iterate over a row/column instead of using ray-marching
			var HACKY_LEN:Number = 2000;
			
			//var ray_pos:vec2 = new vec2(pos_x, pos_y);
			TEMP_ray_pos.x = pos_x;
			TEMP_ray_pos.y = pos_y;
			
			//var ray_vec:vec2 = new vec2(HACKY_LEN * dir_x, HACKY_LEN * dir_y);//++TODO: a less hacky way to find an endpoint.. using a too-long ray can result in numerical errors
			TEMP_ray_vec.x = HACKY_LEN * dir_x;
			TEMP_ray_vec.y = HACKY_LEN * dir_y;
			
			//++TODO: we could use the edge grid to accelerate this (i.e only perform actual ray tests vs non-axis-aligned edges; the rest can be performed implicitly using our traversal values)
			//	-we would just need to traverse the edgegrid instead of this grid (i.e multiply all values by 1/2, and only change U,V in seggrid when U,V of edgegrid has changed twice
			var hit_t:Number = 2;
			while (true)
			{
				//DEBUG
				//rend.SetStyle(0, 0x000000, 10);
				//rend.DrawAABB(U * cellsize, (U + 1) * cellsize, V * cellsize, (V + 1) * cellsize);
				
				//intersect ray vs current cell contents
				var result:Number = IntersectRayVsCellContents(U, V, TEMP_ray_pos, TEMP_ray_vec, out_pos, out_normal);
				if (result == -1)
				{
					//problems
					trace("WARNING! GetRaycastDistance() was passed an invalid ray (start position overlaps seg geometry)");
					return -1;
				}
				else if (result != 2)
				{
					//we found a hit; stop iterating
					hit_t = result;
					break;
				}
				
				
				//if we've reached here, we need to iterate to the next cell (making sure to detect if we've moved out of the grid, to avoid infloops or invalid indexing)
				//
				//++TODO: are the checks for valid U,V really necessary?
				if (tMaxX < tMaxY)
				{
					tMaxX += tDeltaX;
					U += stepU;
					
					if (U < 0 || U >= numcols)
					{
						trace("WARNING! GetRaycastDistance() has a ray that missed everything in U");
						return -1;
					}
				}
				else
				{
					tMaxY += tDeltaY;
					V += stepV;
					
					if (V < 0 || V >= numrows)
					{
						trace("WARNING! GetRaycastDistance() has a ray that missed everything in V");
						return -1;
					}
				}
				
			}
				
			//if we've reached here, we found an intersection and out_ values have been filled in
			return (hit_t * HACKY_LEN);
		}
		
		//this is "raycast vs object" in the original code: return true if the ray hits the player before hitting tile geometry, false otherwise
		//	-if this returns false, hit_ values are filled with info on the intersection with the tile geometry
		//
		//++TODO: this belongs in the segGrid or somewhere else, where everyone can use it
		public function RaycastVsPlayer(query_pos:vec2, player_pos:vec2, player_r:Number, hit_pos:vec2, hit_n:vec2):Boolean
		{
			//var dir_to_player:vec2 = query_pos.To(player_pos);
			var dir_to_player_X:Number = player_pos.x - query_pos.x;
			var dir_to_player_Y:Number = player_pos.y - query_pos.y;
			
			//var dist_to_player:Number = dir_to_player.Len();
			var dist_to_player:Number = Math.sqrt((dir_to_player_X * dir_to_player_X) + (dir_to_player_Y * dir_to_player_Y));
			
			if (dist_to_player < player_r)
			{
				return true;//player's right on top of us.. trivially true :)
			}
			else
			{
				//dir_to_player.Normalize();	//dir is guaranteed to not be 0-length if we've reached here
				dir_to_player_X /= dist_to_player;
				dir_to_player_Y /= dist_to_player;
				
				dist_to_player -= player_r;	//this now is the distance from the turret to the closest point on the player
				
				//++TODO: this is potentially wasteful/slow, because we always raycast until we hit a tile
				//	-really, we only need to raycast until we reach the player, and we can stop/quit at that point instead of continuing on
				//raycast towards player
				//var hit_dist:Number = GetRaycastDistance(query_pos.x, query_pos.y, dir_to_player.x, dir_to_player.y, hit_pos, hit_n);
				var hit_dist:Number = GetRaycastDistance(query_pos.x, query_pos.y, dir_to_player_X, dir_to_player_Y, hit_pos, hit_n);
				
				//DEBUG
				//trace("dist to player: " + dist_to_player);
				//trace("      hit dist: " + hit_dist);
				
				if (dist_to_player < hit_dist)
				{
					return true;//the ray reached the player; we can see them
				}
				
				if (hit_dist == -1)
				{
					//there were problems; to avoid div-by-0 or null references, stuff intersection info with junk values
					hit_pos.x = 0;
					hit_pos.y = 0;
					hit_n.x = 1;
					hit_n.y = 0;
					
					trace("WARNING! RaycastVsPlayer() has a problem ray");
				}
				
				return false;
			}
		}
		
		//this returns the parametric time of intersection (and fills out the intersection position/normal) of the earliest intersection between a ray and the segs in the specified cell
		//	-returns 2 if no intersections found, -1 if the ray started in intersection
		//
		//NOTE: for now, we treat "ray starts intersecting with something" as "no intersection"
		//	++TODO: handle this case properly
		//
		//++TODO: add a tiny radius to the ray?
		private function IntersectRayVsCellContents(u:int, v:int, ray_pos:vec2, ray_vec:vec2, out_pos:vec2, out_normal:vec2):Number
		{
			var best_t:Number = 2;//++TODO: a better way to init this
			//var temp_p:vec2 = new vec2();
			//var temp_n:vec2 = new vec2();
			TEMP_temp_p.x = 0;
			TEMP_temp_p.y = 0;
			TEMP_temp_n.x = 0;
			TEMP_temp_n.y = 0;
			
			var index:int = GetCellIndexFromGridspacePosition(u, v);
			var segList:Vector.<Segment> = cells[index];
			for (var i:int = 0; i < segList.length; i++)
			{
				var seg:Segment = segList[i];
				var temp_t:Number = seg.IntersectWithRay(ray_pos, ray_vec, 0, TEMP_temp_p, TEMP_temp_n);
				if (temp_t == -1)
				{
					return -1;
				}
				else if(temp_t < best_t)
				{
					//we found a new closest intersection; remember it
					best_t = temp_t;
					out_pos.Copy(TEMP_temp_p);
					out_normal.Copy(TEMP_temp_n);
				}
			}
			
			return best_t;
		}
		
		//DEBUG: used for testing
		public function DEBUG_GetCellContentsFromGridspacePosition(u:int, v:int):Vector.<Segment>
		{
			var index:int = GetCellIndexFromGridspacePosition(u, v);
			return cells[index];
		}
		
		
		// MANAGEMENT/BOOKKEEPPING ---------------------------------------------------------------------------
		
		//empties all cells; note that whatever was in the cells should have been deleted before this is called, we don't take responsibility for cleaning up the contents
		public function Clear():void
		{
			for (var i:int = 0; i < numcells; i++)
			{
				var cell:Vector.<Segment> = cells[i];//GHA.. stupid FD doesn't recognize the type of cells[i] unless we do this
				cell.length = 0;//this is apparently how you delete/clear a vector
			}
		}
		
		public function AddSegToCell(cell_u:int, cell_v:int, seg:Segment):void
		{
			var index:int = GetCellIndexFromGridspacePosition(cell_u, cell_v);
			if (index < 0)
			{
				trace("WARNING! AddSegToCell() was passed invalid cell coords: " + cell_u + "," + cell_v);
				return;
			}
			cells[index].push(seg);
		}
		
		
		public function DOOR_AddSegment(cell_index:int, seg:Segment):void
		{
			if (cell_index < 0 || cell_index >= numcells)
			{
				trace("WARNING! DOOR_AddSegment() was called with an invalid index: " + cell_index);
				return;
			}
			
			//++TODO: we're making sure the seg isn't in the grid; this is possibly needlessly slow (once doors are written and tested, this error-checking can be removed)
			var cell:Vector.<Segment> = cells[cell_index];
			var seg_index:int = cell.indexOf(seg);
			if (seg_index != -1)
			{
				//seg's already in the grid!
				trace("WARNING! DOOR_AddSegment() was passed an already-in-grid seg: " + cell_index);
				return;
			}
			
			cells[cell_index].push(seg);
		}
		public function DOOR_RemoveSegment(cell_index:int, seg:Segment):void
		{
			if (cell_index < 0 || cell_index >= numcells)
			{
				trace("WARNING! DOOR_RemoveSegment() was called with an invalid index: " + cell_index);
				return;
			}
			
			var cell:Vector.<Segment> = cells[cell_index];
			var seg_index:int = cell.indexOf(seg);
			if (seg_index == -1)
			{
				//couldn't find the seg!
				trace("WARNING! DOOR_RemoveSegment() couldn't find a seg: " + cell_index);
				return;
			}
			
			cell.splice(seg_index, 1);
		}
		//this is used to allow doors to directly add/remove themselves from specific cells
		public function DOOR_GetCellIndexFromGridspacePosition(u:int, v:int):int
		{
			return GetCellIndexFromGridspacePosition(u, v);
		}
		
		//returns a list of all segments in all cells overlapping a worldspace AABB
		//	NOTE: the name is meant to reflect that this isn't a simple "look at a cell's list" operation, we have to build a list of Segments
		//	NOTE: we could iterate row-by-row (i.e we know we want to visit all indices between min and max on each row, so we only need to map the first/last index in each row and iterate between them), but this is tricky/fancy -- for now we'll just map each grid position to an index
		//	NOTE: we don't support "lookup contents of individual cell from worldspace position", because that's only useful for points (i.e shapes with no area).. and those will need to be swept or something anyway, so basically: useless
		//
		//NEW: to avoid creating garbage, caller is expected to pass in a list to fill
		public function GatherCellContentsFromWorldspaceRegion(min_x:Number, min_y:Number, max_x:Number, max_y:Number, out_segList:Vector.<Segment>):void
		{
			var min_u:int = WorldspaceToGridspace(min_x);
			var max_u:int = WorldspaceToGridspace(max_x);
			var min_v:int = WorldspaceToGridspace(min_y);
			var max_v:int = WorldspaceToGridspace(max_y);
			
			//var outList:Vector.<Segment> = new Vector.<Segment>();
			out_segList.length = 0;
			
			for (var j:int = min_v; j <= max_v; j++)
			{
				for (var i:int = min_u; i <= max_u; i++)
				{
					var index:int = GetCellIndexFromGridspacePosition(i, j);
					if (index < 0)
					{
						trace("WARNING! GatherCellContentsFromWorldspaceRegion() was passed an invalid region: " + min_u + "," + min_v + " .. " + max_u + "," + max_v);
					}
					var cell:Vector.<Segment> = cells[index];
					
					//++TODO: would it make more sense to use concat()? this just seemed stupid -- it would keep creating new vectors!
					for (var k:int = 0; k < cell.length; k++)
					{
						out_segList.push(cell[k]);
					}
				}
			}
		}
		
	}

}

PointOnSurface.as

package simulation.collision 
{
	import math.vec2;
	
	//this is a heavyweight class used to represent the results of a closest-point or raycast query
	public class PointOnSurface
	{
		public var pos:vec2;	//position on segment
		public var n:vec2;		//normal at position
		public var dist:Number;	//distance to query point / distance along ray (possibly signed distance)
		
		public function PointOnSurface() 
		{
			pos = new vec2();
			n = new vec2();
			dist = 0;
		}
		
	}

}

Segment.as

package simulation.collision 
{
	import math.vec2;
	import simpleFramework.SimpleRenderer;
	
	//this hides the differences between linesegs and arcs.. sadly we're using virtuals instead of finding a way to uniformly represent both
	public interface Segment 
	{
		
		//ARGH: hacky crap added to hack ragdoll-stick-vs-tile collision in
		function GetP0():vec2;
		function GetP1():vec2;
		
		function GetAABB():AABB;
		
		//returns the position of the point on the segment closest to the query position
		function GetClosestPoint(query_pos:vec2, out_closestpoint:vec2):void; 
		
		//returns the parametric time of intersection (in [0,1]) (and fill the out_ variables) if inflated ray intersects seg
		//	-if ray starts in collision with seg, we return -1
		//	-if ray doesn't intersect, we return 2
		function IntersectWithRay(ray_pos:vec2, ray_vec:vec2, ray_radius:Number, OUT_intersection_pos:vec2, OUT_intersection_normal:vec2):Number;	
		
		//returns the closest point on the segment, and a bool indicating penetration (true=query point is behind segment, false=query point is in front of segment)
		function GetClosestPoint_IsBackfacing(query_pos:vec2, out_closestpoint:vec2):Boolean;
		
		//++TODO:
		//	-one-sided raycasts: ignore backfacing segs (or flag them as special, i.e to detect penetration we'd want to know if we hit a backfacing seg first)
		//	-pos+normal+dist version of closest point query?


		//new: this is maybe not so hacky, but anyway: we need a way to report normal explicitly (previously we have inferred them via closest-point vector, but this fails when points are exactly on the surface)
		//
		//IMPORTANT: query_pos is assumed to be a point ON the surface of the shape!! (which is currently the only use-case and lets us massively simplify things
		//	(this really only matters for arcs)
		function HACKY_GetNormalAtPoint(query_pos:vec2, out_unit_normal:vec2):void
	
		//new: this is DEFINITELY hacky, some enemies need to respond to doors differently than regular tiles... and we don't want to use "is" since it's harder to port
		function HACKY_IsDoubleSided():Boolean;
		
		
		function DebugDraw(rend:SimpleRenderer):void;
		function DebugDraw_NoStyle(rend:SimpleRenderer):void;	//this version lets the user specify the style
		function DebugDraw_Simple(rend:SimpleRenderer):void;	//draws the minimal amount necessary; user specifies the style
	}
	
}

Segment_Circular.as

package simulation.collision 
{
	import math.vec2;
	import simpleFramework.SimpleRenderer;
	
	//a circular arc; by convention p0 is the CCW end, p1 is the CW end
	//
	//++TODO: this will probably break if the arc is >=180deg; we should either split large arcs into multiple small arcs, or rewrite this to be more general
	public class Segment_Circular implements Segment
	{
		private static const zero_vec:vec2 = new vec2(0, 0);//this is used to pass into queries to signify we have 0 vel, without creating garbage
		private static var cp:vec2 = new vec2();//NOTE: we re-use these between *ALL* segments to hold temp query results
		private static var ray_point:vec2 = new vec2();
		//-sharing these between all instances is probably really dangerous if we needed to multithread, but who cares... it's flash!
		
		private var p0:vec2;
		private var p1:vec2;
		private var pC:vec2;
		
		private var aabb:AABB;
		
		public function Segment_Circular(x_center:Number, y_center:Number, x0:Number, y0:Number, x1:Number, y1:Number)
		{
			p0 = new vec2(x0, y0);
			p1 = new vec2(x1, y1);
			pC = new vec2(x_center, y_center);
			
			//++TODO: this isn't correct for arcs in general, only for 90deg axis-aligned arcs as found in N
			aabb = new AABB(Math.min(p0.x, p1.x), Math.min(p0.y, p1.y), Math.max(p0.x, p1.x), Math.max(p0.y, p1.y));
		}
		
		public function GetP0():vec2
		{
			return p0;
		}
		public function GetP1():vec2
		{
			return p1;
		}
		public function GetPC():vec2
		{
			return pC;
		}
		public function GetAABB():AABB
		{
			return aabb;
		}
		
		public function HACKY_IsDoubleSided():Boolean
		{
			return false;
		}
		
		
		public function HACKY_GetNormalAtPoint(query_pos:vec2, out_unit_normal:vec2):void
		{
			out_unit_normal = pC.To(query_pos);
			out_unit_normal.Normalize();
			
			//UGH: the way we keep inferring "is this convex or concave?" on-the-fly (by checking which side of the line througn p0,p1 pC is on) seems wrong/stupid/hacky
			var n:vec2 = p0.To(p1).Perp();
			var d:vec2 = p0.To(pC);
			if (n.Dot(d) > 0)
			{
				//arc is concave, flip normal
				out_unit_normal.Scale( -1);
			}
			
		}
		
		public function GetClosestPoint(query_pos:vec2, out_closestpoint:vec2):void
		{
			//var v0:vec2 = pC.To(p0);	
			//var v1:vec2 = pC.To(p1);	
			var v0_X:Number = p0.x - pC.x;
			var v0_Y:Number = p0.y - pC.y;
			
			var v1_X:Number = p1.x - pC.x;
			var v1_Y:Number = p1.y - pC.y;
			
			//var d:vec2 = pC.To(query_pos);
			var d_X:Number = query_pos.x - pC.x;
			var d_Y:Number = query_pos.y - pC.y;
			
			//var dp0:Number = d.Dot(v0.Perp());
			//var dp1:Number = d.Dot(v1.Perp());
			var dp0:Number = (d_X * -v0_Y) + (d_Y * v0_X);
			var dp1:Number = (d_X * -v1_Y) + (d_Y * v1_X);
			
			
			//var v:vec2 = p0.To(p1);				//this tell us the "direction" of the arc; we use this to handle concave and convex arcs uniformly
			var v_X:Number = p1.x - p0.x;
			var v_Y:Number = p1.y - p0.y;
			
			//var vp0:Number = v.Dot(v0.Perp());	//NOTE: this is a bit hacky; really we only care about the signs of vp0,vp1;
			//var vp1:Number = v.Dot(v1.Perp());	//if d is on the "same side" of v0.Perp as v is, it's "inside" the arc region, otherwise it's outside; the opposite applies to v1 
			var vp0:Number = (v_X * -v0_Y) + (v_Y * v0_X);
			var vp1:Number = (v_X * -v1_Y) + (v_Y * v1_X);
			
			var in0:Boolean = (dp0 * vp0 <= 0);
			var in1:Boolean = (dp1 * vp1 >= 0);
			
			if (in0)
			{
				//d and v are on same side of pC->p0; query point is "before" start point
				
				if (in1)
				{
					//d and v are on same side of pC->p1; query point is "after" end point
					//-we're in the "circle center's VR region"; we're either closest to p0 or p1, depending on what side of the "bisector" we're on
					//	-the bisector is the line passing through pC parallel to v.Perp()
					//if (d.Dot(v) <= 0)
					if (((d_X * v_X) + (d_Y * v_Y)) <= 0)
					{
						//we're closer to p0
						//return p0.Clone();
						out_closestpoint.Copy(p0);
					}
					else
					{
						//we're closer to p1
						//return p1.Clone();
						out_closestpoint.Copy(p1);
					}
					
					//++TODO: technically it's possible to be "close" to both p0 and p1, i.e if the query circle's radius is bigger than the arc's radius..
					//	-for now we're ignoring this
				}
				else
				{
					//we're in p0's region
					//return p0.Clone();
					out_closestpoint.Copy(p0);
				}
			}
			else if (in1)
			{
				//we're in p1's region
				//return p1.Clone();
				out_closestpoint.Copy(p1);
			}
			else
			{
				//we're in the arc's region; closest point is d projected onto arc
				//
				//++TODO: there might be a fancy way of doing this without all the sqrts, but fuck it for now
				
				//var radius:Number = v0.Len();
				var radius:Number = Math.sqrt((v0_X * v0_X) + (v0_Y * v0_Y));
				//d.Normalize();	//NOTE: div-by-0 should be impossible; if query point is ON pC, d is null, in0==in1==true and we should have returned p0 above
				//d.Scale(radius);
				var dlen:Number = Math.sqrt((d_X * d_X) + (d_Y * d_Y));
				d_X /= dlen;
				d_Y /= dlen;
				d_X *= radius;
				d_Y *= radius;
				
				//return pC.Plus(d);
				out_closestpoint.x = pC.x + d_X;
				out_closestpoint.y = pC.y + d_Y;
			}
		}
		
		//++TODO: lots of code duplication here..
		public function GetClosestPoint_IsBackfacing(query_pos:vec2, out_closestpoint:vec2):Boolean
		{
			//var v0:vec2 = pC.To(p0);	
			//var v1:vec2 = pC.To(p1);	
			var v0_X:Number = p0.x - pC.x;
			var v0_Y:Number = p0.y - pC.y;
			
			var v1_X:Number = p1.x - pC.x;
			var v1_Y:Number = p1.y - pC.y;
			
			//var d:vec2 = pC.To(query_pos);
			var d_X:Number = query_pos.x - pC.x;
			var d_Y:Number = query_pos.y - pC.y;
			
			//var dp0:Number = d.Dot(v0.Perp());
			//var dp1:Number = d.Dot(v1.Perp());
			var dp0:Number = (d_X * -v0_Y) + (d_Y * v0_X);
			var dp1:Number = (d_X * -v1_Y) + (d_Y * v1_X);
			
			//var v:vec2 = p0.To(p1);				//this tell us the "direction" of the arc; we use this to handle concave and convex arcs uniformly
			var v_X:Number = p1.x - p0.x;
			var v_Y:Number = p1.y - p0.y;
			
			//var vp0:Number = v.Dot(v0.Perp());	//NOTE: this is a bit hacky; really we only care about the signs of vp0,vp1;
			//var vp1:Number = v.Dot(v1.Perp());	//if d is on the "same side" of v0.Perp as v is, it's "inside" the arc region, otherwise it's outside; the opposite applies to v1 
			var vp0:Number = (v_X * -v0_Y) + (v_Y * v0_X);
			var vp1:Number = (v_X * -v1_Y) + (v_Y * v1_X);
			
			var in0:Boolean = (dp0 * vp0 <= 0);
			var in1:Boolean = (dp1 * vp1 >= 0);
			
			var closest_vertex:int = -1;//-1: closest point is on arc; 0, 1: indicates which is the closest vert
			if (in0)
			{
				//d and v are on same side of pC->p0; query point is "before" start point
				
				if (in1)
				{
					//d and v are on same side of pC->p1; query point is "after" end point
					//-we're in the "circle center's VR region"; we're either closest to p0 or p1, depending on what side of the "bisector" we're on
					//	-the bisector is the line passing through pC parallel to v.Perp()
					//if (d.Dot(v) <= 0)
					if (((d_X * v_X) + (d_Y * v_Y)) <= 0)
					{
						//we're closer to p0
						out_closestpoint.Copy(p0);
						closest_vertex = 0;
					}
					else
					{
						//we're closer to p1
						out_closestpoint.Copy(p1);
						closest_vertex = 1;
					}
					
					//++TODO: technically it's possible to be "close" to both p0 and p1, i.e if the query circle's radius is bigger than the arc's radius..
					//	-for now we're ignoring this
				}
				else
				{
					//we're in p0's region
					out_closestpoint.Copy(p0);
					closest_vertex = 0;
				}
			}
			else if (in1)
			{
				//we're in p1's region
				out_closestpoint.Copy(p1);
				closest_vertex = 1;
			}
			else
			{
				//we're in the arc's region; closest point is d projected onto arc
				//
				//++TODO: there might be a fancy way of doing this without all the sqrts, but fuck it for now
				
				//var radius:Number = v0.Len();
				var radius:Number = Math.sqrt((v0_X * v0_X) + (v0_Y * v0_Y));
				//d.Normalize();	//NOTE: div-by-0 should be impossible; if query point is ON pC, d is null, in0==in1==true and we should have returned p0 above
				//d.Scale(radius);
				var dlen:Number = Math.sqrt((d_X * d_X) + (d_Y * d_Y));
				d_X /= dlen;
				d_Y /= dlen;
				d_X *= radius;
				d_Y *= radius;
				
				//out_closestpoint.Copy(pC.Plus(d));
				out_closestpoint.x = pC.x + d_X;
				out_closestpoint.y = pC.y + d_Y;
			}
			
			//++TODO: if we're going to rely on "convex/concave" info (i.e if the arc is one-sided), this info should be passed in during construction and not inferred here!
			//var to_closest_point:vec2 = query_pos.To(out_closestpoint);
			var to_closest_point_X:Number = out_closestpoint.x - query_pos.x;
			var to_closest_point_Y:Number = out_closestpoint.y - query_pos.y;
			
			if (closest_vertex < 0)
			{
				//the p0->p1 vector's RHnorm points "outward" (NOTE: only for arcs <180deg); test the query->closest vector against this
				//return (to_closest_point.Dot(v.Perp()) > 0);
				return (((to_closest_point_X * -v_Y) + (to_closest_point_Y * v_X)) > 0);
			}
			else
			{
				//this is really stupid and hacky; we treat the endpoints as if they belong to a lineseg that's parallel to the arc's tangent at the endpoint
				//var line_n:vec2 = v0;
				var line_n_X:Number = v0_X;
				var line_n_Y:Number = v0_Y;
				
				if (closest_vertex == 1)
				{
					//line_n = v1;
					line_n_X = v1_X;
					line_n_Y = v1_Y;
				}
				
				//if (line_n.Dot(v.Perp()) < 0)
				if (((line_n_X * -v_Y) + (line_n_Y * v_X)) < 0)
				{
					//arc is concave; we want to flip the normal around so that it points outward/"towards the arc center"
					//line_n.Scale( -1);
					line_n_X *= -1;
					line_n_Y *= -1;
				}
				
				//return (to_closest_point.Dot(line_n) > 0); 
				return (((to_closest_point_X * line_n_X) + (to_closest_point_Y * line_n_Y)) > 0);
			}
		}
		
		
		public function IntersectWithRay(ray_pos:vec2, ray_vec:vec2, ray_radius:Number, OUT_intersection_pos:vec2, OUT_intersection_normal:vec2):Number
		{
			//var t0:Number = colutils.TimeOfIntersection_Circle_vs_Circle(ray_pos, ray_vec, p0, new vec2(0, 0), ray_radius);
			//var t1:Number = colutils.TimeOfIntersection_Circle_vs_Circle(ray_pos, ray_vec, p1, new vec2(0, 0), ray_radius);
			var t0:Number = colutils.TimeOfIntersection_Circle_vs_Circle(ray_pos, ray_vec, p0, zero_vec, ray_radius);
			var t1:Number = colutils.TimeOfIntersection_Circle_vs_Circle(ray_pos, ray_vec, p1, zero_vec, ray_radius);
			
			var t2:Number = 2;
			
			//var cp:vec2 = GetClosestPoint(ray_pos);
			GetClosestPoint(ray_pos, cp);
			
			//if (cp.To(ray_pos).Len() <= ray_radius)
			var temp_dx:Number = ray_pos.x - cp.x;
			var temp_dy:Number = ray_pos.y - cp.y;
			var temp_len:Number = Math.sqrt((temp_dx * temp_dx) + (temp_dy * temp_dy));
			if(temp_len <= ray_radius)
			{
				//we're starting in collision/penetration
				t2 = -1;
			}
			else
			{
				//filtered circle-vs-circle sweep
				t2 = colutils.TimeOfIntersection_Circle_vs_Arc(ray_pos, ray_vec, pC, p0, p1, ray_radius);
			}
			
			var tmin:Number = Math.min(t0, t1, t2);
			
			if (tmin <= 1 && tmin >= 0)
			{
				//we found a valid intersection
				//var ray_point:vec2 = new vec2(ray_pos.x + tmin * ray_vec.x, ray_pos.y + tmin * ray_vec.y);
				ray_point.x = ray_pos.x + (tmin * ray_vec.x);
				ray_point.y = ray_pos.y + (tmin * ray_vec.y);
				if (ray_radius > 0)
				{
					//the point of collision/normal can be derived from the position along the ray at the time of intersection
					GetClosestPoint(ray_point, cp);
					//var n:vec2 = cp.To(ray_point);
					//n.Normalize();
					var n_X:Number = ray_point.x - cp.x;
					var n_Y:Number = ray_point.y - cp.y;
					var nlen:Number = Math.sqrt((n_X * n_X) + (n_Y * n_Y));
					n_X /= nlen;
					n_Y /= nlen;
					
					//OUT_intersection_pos.Copy(cp);
					//OUT_intersection_normal.Copy(n);
					OUT_intersection_pos.x = cp.x;
					OUT_intersection_pos.y = cp.y;
					OUT_intersection_normal.x = n_X;
					OUT_intersection_normal.y = n_Y;
				}
				else
				{
					//ray is infinitely thin; we can only have collided with the arc itself (not an endpoint)
					//var d:vec2 = pC.To(ray_point);
					//d.Normalize();
					var d_X:Number = ray_point.x - pC.x;
					var d_Y:Number = ray_point.y - pC.y;
					var dlen:Number = Math.sqrt((d_X * d_X) + (d_Y * d_Y));
					d_X /= dlen;
					d_Y /= dlen;
					
					//if (d.Dot(ray_vec) > 0)
					if(((d_X*ray_vec.x) + (d_Y*ray_vec.y)) > 0)
					{
						//flip the normal around so it points against the ray
						//d.Scale( -1);
						d_X *= -1;
						d_Y *= -1;
					}
					
					OUT_intersection_pos.Copy(ray_point);
					//OUT_intersection_normal.Copy(d);
					OUT_intersection_normal.x = d_X;
					OUT_intersection_normal.y = d_Y;
				}
			}
			
			return tmin;
		}
		
		
		public function DebugDraw(rend:SimpleRenderer):void
		{
			//draw segment
			rend.SetStyle(0, 0x000000, 100);
			DebugDraw_NoStyle(rend);
		}
		public function DebugDraw_Simple(rend:SimpleRenderer):void
		{
			rend.DrawCircularArc_Convex(pC.x, pC.y, p0.x, p0.y, p1.x, p1.y, pC.To(p0).Len());
		}
		public function DebugDraw_NoStyle(rend:SimpleRenderer):void
		{
			//draw segment
			rend.DrawCircularArc_Convex(pC.x, pC.y, p0.x, p0.y, p1.x, p1.y, pC.To(p0).Len());
			
			//draw ends
			rend.DrawSquare(p0.x, p0.y, 2);
			rend.DrawSquare(p1.x, p1.y, 2);
			//rend.DrawSquare(pC.x, pC.y, 2);
			rend.DrawPlus(pC.x, pC.y, 2);
			
			//draw normal
			var radius:Number = pC.To(p0).Len();
			var v:vec2 = p0.To(p1);
			var n:vec2 = v.Perp();	//n is the LH normal at the arc's midpoint
			n.Normalize();
			v.Scale(0.5);
			var d:vec2 = pC.To(p0.Plus(v));//d is the vector that takes us from pC to the arc's surface (it's +/- n)
			d.Normalize();
			d.Scale(radius);
			rend.DrawLine(pC.x + d.x, pC.y + d.y, pC.x + d.x + 4*n.x, pC.y + d.y + 4*n.y);
			
		}
	}
}

Segment_Linear.as

package simulation.collision 
{
	import math.vec2;
	import simpleFramework.SimpleRenderer;
	
	//a line segment; by convention p0 is the CCW end, p1 is the CW end
	public class Segment_Linear implements Segment
	{
		protected static const zero_vec:vec2 = new vec2(0, 0);//this is used to pass into queries to signify we have 0 vel, without creating garbage
		protected static var cp:vec2 = new vec2();//NOTE: we re-use these between *ALL* segments to hold temp query results
		protected static var ray_point:vec2 = new vec2();
		//-sharing these between all instances is probably really dangerous if we needed to multithread, but who cares... it's flash!
		
		
		protected var p0:vec2;
		protected var p1:vec2;
		
		private var aabb:AABB;
		
		public function Segment_Linear(x0:Number, y0:Number, x1:Number, y1:Number)
		{
			p0 = new vec2(x0, y0);
			p1 = new vec2(x1, y1);
			
			aabb = new AABB(Math.min(p0.x, p1.x), Math.min(p0.y, p1.y), Math.max(p0.x, p1.x), Math.max(p0.y, p1.y));
		}
		
		public function GetP0():vec2
		{
			return p0;
		}
		public function GetP1():vec2
		{
			return p1;
		}
		
		public function GetAABB():AABB
		{
			return aabb;
		}
		
		public function HACKY_IsDoubleSided():Boolean
		{
			return false;
		}
		
		public function HACKY_GetNormalAtPoint(query_pos:vec2, out_unit_normal:vec2):void
		{
			var temp:vec2 = p0.To(p1).Perp();
			temp.Normalize();
			
			out_unit_normal.Copy(temp);
		}
		
		public function GetClosestPoint(query_pos:vec2, out_closestpoint:vec2):void
		{
			//var v:vec2 = p0.To(p1);	
			var v_X:Number = p1.x - p0.x;
			var v_Y:Number = p1.y - p0.y;
			
			//var d:vec2 = p0.To(query_pos);
			var d_X:Number = query_pos.x - p0.x;
			var d_Y:Number = query_pos.y - p0.y;
			
			//var dp:Number = v.Dot(d);
			var dp:Number = (v_X * d_X) + (v_Y * d_Y);
			
			//var len2:Number = v.Dot(v);
			var len2:Number = (v_X * v_X) + (v_Y * v_Y);
			
			if (dp <= 0)
			{
				//return p0.Clone();//query point is "before" start point
				out_closestpoint.Copy(p0);
			}
			else if (dp >= len2)
			{
				//return p1.Clone();//query point is "after" of end point
				out_closestpoint.Copy(p1);
			}
			else
			{
				//query point is in segment's voronoi region
				
				//closest point = p0 + q
				//	let n = 1/|v| * v
				//	  q	= Dot(d,n)*n
				//		= Dot(d, 1/|v| * v) * 1/|v| * v
				//		= 1/|v|^2 * Dot(d,v) * v
				var t:Number = dp / len2;	//++TODO: possible div-by-0 if the seg is null
				
				//return new vec2(p0.x + t * v.x, p0.y + t * v.y);
				out_closestpoint.x = p0.x + (t * v_X);
				out_closestpoint.y = p0.y + (t * v_Y);
			}
		}
		//++TODO: lots of code duplication here..
		public function GetClosestPoint_IsBackfacing(query_pos:vec2, out_closestpoint:vec2):Boolean
		{
			//var v:vec2 = p0.To(p1);	
			var v_X:Number = p1.x - p0.x;
			var v_Y:Number = p1.y - p0.y;
			
			//var d:vec2 = p0.To(query_pos);
			var d_X:Number = query_pos.x - p0.x;
			var d_Y:Number = query_pos.y - p0.y;
			
			//var dp:Number = v.Dot(d);
			var dp:Number = (v_X * d_X) + (v_Y * d_Y);
			
			//var len2:Number = v.Dot(v);
			var len2:Number = (v_X * v_X) + (v_Y * v_Y);
			
			if (dp <= 0)
			{
				out_closestpoint.Copy(p0);//query point is "before" start point
			}
			else if (dp >= len2)
			{
				out_closestpoint.Copy(p1);//query point is "after" of end point
			}
			else
			{
				//query point is in segment's voronoi region
				
				//closest point = p0 + q
				//	let n = 1/|v| * v
				//	  q	= Dot(d,n)*n
				//		= Dot(d, 1/|v| * v) * 1/|v| * v
				//		= 1/|v|^2 * Dot(d,v) * v
				var t:Number = dp / len2;	//++TODO: possible div-by-0 if the seg is null
				
				out_closestpoint.x = p0.x + (t * v_X);
				out_closestpoint.y = p0.y + (t * v_Y);
			}
			
			//return (d.Dot(v.Perp()) < 0);//query point is behind seg's frontface if to-query-point vector points against the seg's outward normal
			return (((d_X * -v_Y) + (d_Y * v_X)) < 0);
		}
		
		
		
		public function IntersectWithRay(ray_pos:vec2, ray_vec:vec2, ray_radius:Number, OUT_intersection_pos:vec2, OUT_intersection_normal:vec2):Number
		{
			//var t0:Number = colutils.TimeOfIntersection_Circle_vs_Circle(ray_pos, ray_vec, p0, new vec2(0, 0), ray_radius);
			//var t1:Number = colutils.TimeOfIntersection_Circle_vs_Circle(ray_pos, ray_vec, p1, new vec2(0, 0), ray_radius);
			
			var t0:Number = colutils.TimeOfIntersection_Circle_vs_Circle(ray_pos, ray_vec, p0, zero_vec, ray_radius);
			var t1:Number = colutils.TimeOfIntersection_Circle_vs_Circle(ray_pos, ray_vec, p1, zero_vec, ray_radius);
			
			var t2:Number = colutils.TimeOfIntersection_Point_vs_Lineseg(ray_pos, ray_vec, p0, p1, ray_radius);
			
			var tmin:Number = Math.min(t0, t1, t2);
			if (tmin <= 1 && tmin >= 0)
			{
				//we found a valid intersection
				//var ray_point:vec2 = new vec2(ray_pos.x + tmin * ray_vec.x, ray_pos.y + tmin * ray_vec.y);
				ray_point.x = ray_pos.x + (tmin * ray_vec.x);
				ray_point.y = ray_pos.y + (tmin * ray_vec.y);
				if (ray_radius > 0)
				{
					//the point of collision/normal can be derived from the position along the ray at the time of intersection
					//var p:vec2 = GetClosestPoint(ray_point);
					cp.x = 0;
					cp.y = 0;
					GetClosestPoint(ray_point, cp);
					
					//var n:vec2 = p.To(ray_point);
					//n.Normalize();
					var n_X:Number = ray_point.x - cp.x;
					var n_Y:Number = ray_point.y - cp.y;
					var nlen:Number = Math.sqrt((n_X * n_X) + (n_Y * n_Y));
					n_X /= nlen;
					n_Y /= nlen;
					
					//OUT_intersection_pos.Copy(p);
					//OUT_intersection_normal.Copy(n);
					OUT_intersection_pos.x = cp.x;
					OUT_intersection_pos.y = cp.y;
					OUT_intersection_normal.x = n_X;
					OUT_intersection_normal.y = n_Y;
				}
				else
				{
					//ray is infinitely thin; we can only have collided with the lineseg itself (not an endpoint)
					//var d:vec2 = p0.To(p1).Perp();
					//d.Normalize();
					var d_X:Number = -(p1.y - p0.y);
					var d_Y:Number = p1.x - p0.x;
					var dlen:Number = Math.sqrt((d_X * d_X) + (d_Y * d_Y));
					d_X /= dlen;
					d_Y /= dlen;
					
					//if (d.Dot(ray_vec) > 0)
					if (((d_X * ray_vec.x) + (d_Y * ray_vec.y)) > 0)
					{
						//flip the normal around so it points against the ray
						//d.Scale( -1);
						d_X *= -1;
						d_Y *= -1;
					}
					
					OUT_intersection_pos.Copy(ray_point);
					//OUT_intersection_normal.Copy(d);
					OUT_intersection_normal.x = d_X;
					OUT_intersection_normal.y = d_Y;
				}
			}
			
			return tmin;
		}
		
		
		public function DebugDraw(rend:SimpleRenderer):void
		{
			//draw segment
			rend.SetStyle(0, 0x000000, 100);
			DebugDraw_NoStyle(rend);
		}
		public function DebugDraw_Simple(rend:SimpleRenderer):void
		{
			rend.DrawLine(p0.x, p0.y, p1.x, p1.y);
		}
		public function DebugDraw_NoStyle(rend:SimpleRenderer):void
		{
			//draw segment
			rend.DrawLine(p0.x, p0.y, p1.x, p1.y);
			
			//draw ends
			rend.DrawSquare(p0.x, p0.y, 2);
			rend.DrawSquare(p1.x, p1.y, 2);
			
			//draw normal
			var v:vec2 = p0.To(p1);
			var n:vec2 = v.Perp();
			n.Normalize();
			rend.DrawLine(p0.x + 0.5 * v.x, p0.y + 0.5 * v.y, p0.x + 0.5 * v.x + 4 * n.x, p0.y + 0.5 * v.y + 4 * n.y);
		}
		
	}
}

Segment_Linear_DoubleSided.as

package simulation.collision 
{
	import math.vec2;
	import simpleFramework.SimpleRenderer;
	
	//this version models two anti-parallel segs, i.e a two-sided lineseg
	//	-the only difference is that it's impossible to be behind/backfacing a double-sided seg
	public class Segment_Linear_DoubleSided extends Segment_Linear
	{
		public function Segment_Linear_DoubleSided(x0:Number, y0:Number, x1:Number, y1:Number)
		{
			super(x0, y0, x1, y1);
		}
		
		public override function GetClosestPoint_IsBackfacing(query_pos:vec2, out_closestpoint:vec2):Boolean
		{
			super.GetClosestPoint_IsBackfacing(query_pos, out_closestpoint);
			return false;//double-sided segs by definition can never be backfacing
		}
		
		public override function HACKY_IsDoubleSided():Boolean
		{
			return true;
		}
		
		//NOTE: this is wrong!! i.e we might want to use p1->p0 depending...
		//	-but: for our current use-cases, this should never be called anyway
		public override function HACKY_GetNormalAtPoint(query_pos:vec2, out_unit_normal:vec2):void
		{
			trace("WARNING! someone called HACKY_GetNormalAtPoint() on a double-sided seg! we shouldn't be doing this.. right?");
			
			out_unit_normal = p0.To(p1).Perp();
			out_unit_normal.Normalize();
		}
		
		public override function DebugDraw_NoStyle(rend:SimpleRenderer):void
		{
			//draw segment
			rend.DrawLine(p0.x, p0.y, p1.x, p1.y);
			
			//draw ends
			rend.DrawSquare(p0.x, p0.y, 2);
			rend.DrawSquare(p1.x, p1.y, 2);
			
			//draw normals
			var v:vec2 = p0.To(p1);
			var n:vec2 = v.Perp();
			n.Normalize();
			rend.DrawLine(p0.x + 0.5 * v.x, p0.y + 0.5 * v.y, p0.x + 0.5 * v.x + 4 * n.x, p0.y + 0.5 * v.y + 4 * n.y);
			rend.DrawLine(p0.x + 0.5 * v.x, p0.y + 0.5 * v.y, p0.x + 0.5 * v.x - 4 * n.x, p0.y + 0.5 * v.y - 4 * n.y);
		}
		
	}
}