
#import <gamekit/gamekit.h>
#import <math.h>

// Note:  There are plenty of nice ways to do all this.  What I'm going
// for here is blinding speed.  Therefore, I have a lot of special cases
// and other things that take advantage of 2-d geometry.  The tradeoff is
// that I don't care how much code it takes if it is _fast_.  I have defined
// a few geometric functions here to make the code easier to read...and I
// realize that sacrifices speed, my my sanity is more important that
// ultimate speed...

double GKDistanceBetweenPoints(NXPoint *point1, NXPoint *point2)
{	// using standard 2-d distance formula:  d=sqrt(x^2+y^2)
	float x = point1->x - point2->x;
	float y = point1->y - point2->y;
	// it might make sense to do a fast approx. of sqrt() here instead...
	return sqrt(GK_SQUARE(x) + GK_SQUARE(y));
}

BOOL GKOuterLineSegmentIntersectsRect(NXPoint *point1, NXPoint *point2, NXRect *rect)
{	// assumes neither point lies inside rect; if that's true, you have
	// intersection already, so don't call here!
	double slope, intercept1, intercept2;
	NXPoint max = {	NX_MAXX(rect), NX_MAXY(rect) };
	// is line completely to one side of the rect?
	if (((point1->x < NX_X(rect)) && (point2->x < NX_X(rect))) ||
		((point1->y < NX_Y(rect)) && (point2->y < NX_Y(rect))) ||
		((point1->x > max.x) && (point2->x > max.x)) ||
		((point1->y > max.y) && (point2->y > max.y))) return NO;
	// find y-coord of line when it crosses max.x and min.x...if
	// one of these points is min.y<point<max.y have intersect on sides
	// of rect.  Have intersect on top or bottom if one is above max.y
	// while the other is below min.y...
	slope = (point1->y - point2->y) / (point1->x - point2->x);
	intercept1 = slope * (NX_X(rect) - point1->x) + point1->y;
	intercept2 = slope * (max.x - point1->x) + point1->y;
	if (((intercept1 > max.y) && (intercept2 < NX_Y(rect))) ||
		((intercept2 > max.y) && (intercept1 < NX_Y(rect))) ||
		((intercept1 < max.y) && (intercept1 > NX_Y(rect))) ||
		((intercept2 < max.y) && (intercept2 > NX_Y(rect)))) return YES;
	return NO;
}

// I should probably make this an inline procedure...
double GKSegmentAngle(NXPoint *point1, NXPoint *point2)
{	// for speed I assume point1 is left of point2
	double deltaY = GK_VECTOR_Y(point2) - GK_VECTOR_Y(point1);
	double deltaX = GK_VECTOR_X(point2) - GK_VECTOR_X(point1);
	return (asin(deltaY/sqrt(GK_SQUARE(deltaX)+GK_SQUARE(deltaY))));
}

// this should probably be inline...
BOOL GKPointAboveLine(NXPoint *point, NXPoint *start, NXPoint *end)
{	// YES if point is above the line defined by start and end
	// if the end points of the line form a vertical line (unlikely but
	// possible) then points to the left of the line are considered to
	// be "above" the line. 
	double x1 = GK_VECTOR_X(start);
	double diff = GK_VECTOR_X(end) - x1; // only calc it once...
	if (ABS(diff) < 0.00001) { // if x1 and x2 are too close together,
		// we may still encounter problems with overflow/underflow...
		// so I'm using a small delta; if the slope is more than 100000,
		// we figure that the line is vertical for all intents and purposes.
		// We check the point's y coord against y-coord of line
		// interpolated/extrapolated to same x-coord (I did a little
		// algebra to y=mx+b to make it faster)
		if (GK_VECTOR_Y(point) > (((GK_VECTOR_X(point) - x1) *
				((GK_VECTOR_Y(end) - GK_VECTOR_Y(start)) / diff)) +
				GK_VECTOR_Y(start)))
			return YES;
	} else { // vertical line case -- need to avoid divide by zero!
		if (GK_VECTOR_X(point) < x1) return YES;
	}
	return NO;
}

// this should probably be inline...
BOOL GKPointsOnSameSideOfLine(NXPoint *point1, NXPoint *point2, NXPoint *start, NXPoint *end)
{	// YES if point1 and point2 are on same side of line
	// defined by start and end
	if (GKPointAboveLine(point1, start, end) ==
		GKPointAboveLine(point2, start, end)) return YES;
	return NO;
}

BOOL GKPointInTriangle(NXPoint *point, GKTriangle *tri)
{
	int left, first, second, x[3];
	x[0] = GK_VECTOR_X(GK_VERTEX(tri, 0));
	x[1] = GK_VECTOR_X(GK_VERTEX(tri, 1));
	x[2] = GK_VECTOR_X(GK_VERTEX(tri, 2));
	// sort vertices.  need to know leftmost point and then which point
	// is next going counter clockwise ("first")
	if (x[0] < x[1]) {
		if (x[0] < x[2]) {
			left = 0; first = 1; second = 2;
		} else {
			left = 2; first = 1; second = 0;
		}
	} else {
		if (x[1] < x[2]) {
			left = 1; first = 0; second = 2;
		} else { // this code is repeated from above...I did this for speed
			left = 2; first = 1; second = 0;
		}
	}
	
	if ( ((!GKPointAboveLine(point, GK_VERTEX(tri, left),
				GK_VERTEX(tri, second)) &&
			GKPointAboveLine(point, GK_VERTEX(tri, left),
				GK_VERTEX(tri, first))) ||
		  (!GKPointAboveLine(point, GK_VERTEX(tri, left),
				GK_VERTEX(tri, first)) &&
			GKPointAboveLine(point, GK_VERTEX(tri, left),
				GK_VERTEX(tri, second)))) &&
			GKPointsOnSameSideOfLine(point, GK_VERTEX(tri, left),
				GK_VERTEX(tri, first), GK_VERTEX(tri, second)))
				
				return YES;
	return NO;
}

static id theGKColliderInstance = nil;

@implementation GKCollider

+ new
{
	if (!theGKColliderInstance)
		theGKColliderInstance = [[[self alloc] init] buildHashTable];
	return theGKColliderInstance;
}

- buildHashTable
{	// set up the method hash table
	collisionHash = [[HashTable alloc]
			initKeyDesc:"i" valueDesc:"!" capacity:10];
	// ***** I assume that casting to void * is OK for all these -*key:
	// methods; ie. I don't need a pointer to an int...the docs are unclear
	[collisionHash insertKey:(void *)(GK_RECTANGLE_SHAPE * GK_RECTANGLE_SHAPE)
			value:@selector(rect:intersectsRect:)];
	[collisionHash insertKey:(void *)(GK_RECTANGLE_SHAPE * GK_CIRCLE_SHAPE)
			value:@selector(rect:intersectsCircle:)];
	[collisionHash insertKey:(void *)(GK_RECTANGLE_SHAPE * GK_TRIANGLE_SHAPE)
			value:@selector(rect:intersectsTriangle:)];
	[collisionHash insertKey:(void *)(GK_RECTANGLE_SHAPE * GK_COMPOSITE_SHAPE)
			value:@selector(rect:intersectsComposite:)];
	[collisionHash insertKey:(void *)(GK_CIRCLE_SHAPE * GK_CIRCLE_SHAPE)
			value:@selector(circle:intersectsCircle:)];
	[collisionHash insertKey:(void *)(GK_CIRCLE_SHAPE * GK_TRIANGLE_SHAPE)
			value:@selector(circle:intersectsTriangle:)];
	[collisionHash insertKey:(void *)(GK_CIRCLE_SHAPE * GK_COMPOSITE_SHAPE)
			value:@selector(circle:intersectsComposite:)];
	[collisionHash insertKey:(void *)(GK_TRIANGLE_SHAPE * GK_TRIANGLE_SHAPE)
			value:@selector(triangle:intersectsTriangle:)];
	[collisionHash insertKey:(void *)(GK_TRIANGLE_SHAPE * GK_COMPOSITE_SHAPE)
			value:@selector(triangle:intersectsComposite:)];
	[collisionHash insertKey:(void *)(GK_COMPOSITE_SHAPE * GK_COMPOSITE_SHAPE)
			value:@selector(composite:intersectsComposite:)];
	return self;
}

- (BOOL)object:actor1 collidesWith:actor2
{
	NXRect bounds[2];
	int ret, swap, type[3];
	SEL method;
	
	// first, check the bounding boxes.  If they don't intersect,
	// then it is pointless to go any further.
	[actor1 getBoundingBox:&bounds[0]];
	[actor2 getBoundingBox:&bounds[1]];
	// Note:  intersection is still NO if edges shared... have to have
	// true intersection to get a YES.  This leniency shouldn't pose
	// a problem, but you should understand the limits of NXIntersectsRect.
	if (!NXIntersectsRect(&bounds[0], &bounds[1])) return NO;

	// get the collision method's selector and whether or not
	// to reverse the arguments:
	type[1] = [actor1 collisionType];
	type[2] = [actor2 collisionType];
	type[0] = type[1] * type[2];
	// a shortcut to speed up rectangle/rectangle intersections
	if (type[0] == GK_RECTANGLE_SHAPE * GK_RECTANGLE_SHAPE) return YES;
	// note we return a YES if couldn't find collision method; we're
	// reverting to the bounding box intersection
	if (!(method = (SEL)[collisionHash valueForKey:(void *)type[0]]))
		return YES;
	
	// call the collision method
	swap = (type[1] > type[2]);
	if (swap) ret = (int)[self perform:method
			with:(id)[actor2 shapeStruct] with:(id)[actor1 shapeStruct]];
	else ret = (int)[self perform:method
			with:(id)[actor1 shapeStruct] with:(id)[actor2 shapeStruct]];
	// using ret as an int avoids trouble with machine dependencies
	// (a BOOL is defined as a char; docs say that this would be dangerous,
	// presumably due to byte-ordering difficulties.)
	if (ret) return YES;
	return NO;
}

- (int)rect:(NXRect *)rect1 intersectsRect:(NXRect *)rect2
{	// we never call it, but it is here for completeness.
	return NXIntersectsRect(rect1, rect2);
}

- (int)rect:(NXRect *)rect intersectsCircle:(GKCircle *)circ
{	// This code is derived from the book Graphics Gems, ed. Andrew Glassner.
	// algorithm reported by Clifford A. Shaffer; it's really rather obvious
	// when you think about it.
	// NXRect origin should be min point, width/height positive.
	double radiusSquared = GK_SQUARE(GK_RADIUS(circ));
	// translate to circle's center is the origin.
	// and the rect looks like this: (max, min are points)
	//  +========MAX
	//  |         |
	// MIN========+
	NXPoint max = {	NX_MAXX(rect) - ((circ)->center.x),
					NX_MAXY(rect) - circ->center.y };
	NXPoint min = {	NX_X(rect) - GK_CENTER_X(circ),
					NX_Y(rect) - GK_CENTER_Y(circ) };
	if (max.x < 0) // Rect is to the left of center
		if (max.y < 0)	// in lower left corner
			return ((GK_SQUARE(max.x) + GK_SQUARE(max.y)) < radiusSquared);
		else if (min.y > 0) // in upper left corner
			return ((GK_SQUARE(max.x) + GK_SQUARE(min.y)) < radiusSquared);
		else return (-(max.x) < GK_RADIUS(circ));	// to west of circle
	else if (min.x > 0)	// Rect is to the right of center
		if (max.y < 0)	// in lower right corner
			return ((GK_SQUARE(min.x) + GK_SQUARE(max.y)) < radiusSquared);
		else if (min.y > 0) // in upper right corner
			return ((GK_SQUARE(min.x) + GK_SQUARE(min.y)) < radiusSquared);
		else return (min.x < GK_RADIUS(circ));	// to east of circle
	else if (max.y < 0)	// to south of circle
		return (-(max.y) < GK_RADIUS(circ));
	else if (min.y > 0) // to north of circle
		return (min.y < GK_RADIUS(circ));
	return YES;	// rect surrounds circle
}

- (int)rect:(NXRect *)rect intersectsTriangle:(GKTriangle *)tri
{	// This one is my algorithm...
	int i;
	for (i=0; i<3; i++) // if any point is in the rect, we have intersection.
		if (NXMouseInRect(&(tri->points[i]), rect, NO)) return YES;
	// Now it gets hairy... we need to see if the triangle (1) encloses rect,
	// (2) clips a rect corner, (3) slices rect, or (4) misses the rect.
	// can check for (2) and (3) with line-rect intersections:
	if (GKOuterLineSegmentIntersectsRect(&(tri->points[0]),
			&(tri->points[1]), rect) ||
		GKOuterLineSegmentIntersectsRect(&(tri->points[1]),
			&(tri->points[2]), rect) ||
		GKOuterLineSegmentIntersectsRect(&(tri->points[2]),
			&(tri->points[0]), rect)) return YES;	
	// check for (1)... triangle enclosing rect?  Yes if any point in
	// rect is in the triangle.
	{
		 NXPoint corner1 = { NX_X(rect), NX_Y(rect) + NX_HEIGHT(rect) };
		 NXPoint corner2 = { NX_X(rect) + NX_WIDTH(rect), NX_Y(rect) };
		 NXPoint corner3 = { NX_X(rect) + NX_WIDTH(rect),
								NX_Y(rect) + NX_HEIGHT(rect) };
		 if (GKPointInTriangle(&(rect->origin), tri) ||
		 	GKPointInTriangle(&corner1, tri) ||
			GKPointInTriangle(&corner2, tri) ||
			GKPointInTriangle(&corner3, tri)) return YES;
	}
	// none of the above, so we assume a miss.
	return NO;
}

- (int)rect:(NXRect *)rect intersectsComposite:comp
{
	
	// ***** need to write this part *****
	
	return NO;
}

- (int)circle:(GKCircle *)circ1 intersectsCircle:(GKCircle *)circ2
{	// if the dist. between centers is less than the two radii added
	// together, then we have an intersection.  Proof is obvious.
	float d = GKDistanceBetweenPoints(GK_CENTER(circ1), GK_CENTER(circ2));
	if (d < GK_RADIUS(circ1) + GK_RADIUS(circ2)) return YES;
	return NO;
}

- (int)circle:(GKCircle *)circ intersectsTriangle:(GKTriangle *)tri
{
	// Three checks:  (1) YES if any triangle vertices are in the circle
	// (2) YES if Triangle encloses circle, and (3) YES if a triangle edge
	// (line segment) intersects the circle.
 
	// ***** need to write this part *****

	return NO;
}

- (int)circle:(GKCircle *)circ intersectsComposite:comp
{
	
	// ***** need to write this part *****
	
	return NO;
}

- (int)triangle:(GKTriangle *)tri1 intersectsTriangle:(GKTriangle *)tri2
{
	// YES if any points of one triangle are inside the other triangle
	// also need to check if any of the sides intersect each other to
	// take care of overlapping triangles
	
	// ***** need to write this part *****
	
	return NO;
}

- (int)triangle:(GKTriangle *)tri intersectsComposite:comp
{
	
	// ***** need to write this part *****
	
	return NO;
}

- (int)composite:(GKTriangle *)comp1 intersectsComposite:comp2
{
	
	// ***** need to write this part *****
	
	return NO;
}

@end
