#include <iostream>
#include <ctime>
#include <math.h>
#include "world.h"
#include "vector.h"
#include "triangle.h"
#include "constants.h"
#define GLUT_DISABLE_ATEXIT_HACK 
#include <GL/glut.h>
#include <stdlib.h>
#include "terrain.h"
#include <string>

double linePointMinimumDistance(const Vector& start, const Vector& end, const Vector& v);
void lineLineMinimumDistance(const Vector& start1, const Vector& end1, 
							 const Vector& start2, const Vector& end2, 
							 double& alpha, double& beta);

using namespace std;
	

World::World(int numPlayers_)
{
	ground = new Terrain();
	nTri = ground->getGridSize();
	triangles = ground->getGrid();

	bullet = NULL;

	numPlayers = numPlayers_;
	tanksAlive = numPlayers;
	currentTank = 0;
	scores = new int[numPlayers];
	tanks = new Tank[numPlayers];
	tankColors = new Vector[MAX_PLAYERS];
	colors = new string[MAX_PLAYERS];
	defLoc = new Vector[MAX_PLAYERS];
	bulletExists = false;
	hasFired = false;
	initTanks();

	// Array of strings of colors
	colors[0] = "Red";
	colors[1] = "Green";
	colors[2] = "Blue";
	colors[3] = "Pink";
	colors[4] = "Purple";
	colors[5] = "Cyan";
	colors[6] = "Yellow";
	colors[7] = "Orange";

}

World::~World()
{
	if (tanks != NULL)
	{
		delete[] tanks;
	}
	if (tankColors != NULL)
	{
		delete[] tankColors;
	}
	if (defLoc != NULL)
	{
		delete[] defLoc;
	}
	if (scores != NULL)
	{
		delete[] scores;
	}
	if (ground != NULL)
	{
		delete ground;
	}
	if (colors != NULL)
	{
		delete[] colors;
	}
	if (bulletExists)
	{
		delete bullet;
	}
}

void World::step()
{
	if (tanksAlive > 1)	// if there is more than one tank alive, keep the game going, otherwise end the game
	{
		if (tanks[currentTank].isAlive()) // 
		{
			if (bulletExists)
			{
				bullet->decrementLife();
				detect();
			}
			else // !bulletExists
			{
				if (hasFired)
				{
					++currentTank;
					currentTank  = currentTank % numPlayers;
					cout << colors[currentTank] << "\'s turn." << endl;
					hasFired = false;
					display();
				}
			}
		}
		else
		{
			cout << colors[currentTank] << "\'s turn is over." << endl;
			if (bulletExists)
			{
				delete bullet;
				bulletExists = false;
			}
			++currentTank;
			currentTank  = currentTank % numPlayers;
			cout << "It's " << colors[currentTank] << "\'s turn!" << endl;
			hasFired = false;
			display();
		}
	}
	else
	{
		int winner = -1;	// an invalid winner number, indicative of an error
		for (int i = 0; i < numPlayers; ++i)
		{
			if (tanks[i].isAlive())
			{
				winner = i;
			}
		}
		cout << "Game Over.  " << colors[winner] << " is the winner!" << endl;
		cout << endl;
		cout << "The scores for each of the players are as follows: " << endl;
		cout << endl;

		for (int i = 0; i < numPlayers; ++i)
		{
			cout << colors[i] << " killed " << scores[i] << " enemy tanks." << endl;
		}
		// Choose a peace sound randomly.
		double selection = ((double)rand())/RAND_MAX;
		if (selection < 0.5)
		{
			PlaySound("PEACE1", 0, SND_RESOURCE | SND_SYNC);
		}
		else
		{
			PlaySound("PEACE2", 0, SND_RESOURCE | SND_SYNC);
		}
		cout << endl;
		exit(1);
	}

}


void World::display()
{
#if AXES
	// positive axes
	glColor3f(1.0f, 0.0f, 0.0f);
	glBegin(GL_LINES);
		glVertex3f(0.0f, 0.0f, 0.0f);
		glVertex3f(100.0f, 0.0f, 0.0f);
	glEnd();
	glColor3f(0.0f, 1.0f, 0.0f);
	glBegin(GL_LINES);
		glVertex3f(0.0f, 0.0f, 0.0f);
		glVertex3f(0.0f, 100.0f, 0.0f);
	glEnd();
	glColor3f(0.0f, 0.0f, 1.0f);
	glBegin(GL_LINES);
		glVertex3f(0.0f, 0.0f, 0.0f);
		glVertex3f(0.0f, 0.0f, 100.0f);
	glEnd();
	// negative axes
		glColor3f(0.7f, 0.5f, 0.5f);
	glBegin(GL_LINES);
		glVertex3f(1.0f, 0.0f, 0.0f);
		glVertex3f(-100.0f, 0.0f, 0.0f);
	glEnd();
	glColor3f(0.5f, 0.7f, 0.5f);
	glBegin(GL_LINES);
		glVertex3f(0.0f, 0.0f, 0.0f);
		glVertex3f(0.0f, -100.0f, 0.0f);
	glEnd();
	glColor3f(0.5f, 0.5f, 0.7f);
	glBegin(GL_LINES);
		glVertex3f(0.0f, 0.0f, 0.0f);
		glVertex3f(0.0f, 0.0f, -100.0f);
	glEnd();
#endif

// Draw the sky
#if SPHERE_SKY
	Vector mapCenter(MAP_SIZE/2, 0, MAP_SIZE/2);

	glCullFace(GL_FRONT);
	glColor3f(SKY_R, SKY_G, SKY_B);
	glPushMatrix();
	glTranslatef(mapCenter[0], mapCenter[1], mapCenter[2]); // move center
	glutSolidSphere(SKY_RADIUS, RESOLUTION, RESOLUTION);   // draw a unit sphere at the origin
	glPopMatrix(); //end sphere draw
	glEnd();
	glCullFace(GL_BACK);
#endif

// Draw the terrain
	ground->draw();
	if (bulletExists)
	{
		bullet->draw();
	}

// Draw the tanks
	for (int i = 0; i < numPlayers; ++i)
	{
		if (tanks[i].isAlive())
		{
			tanks[i].draw();
		}
	}

	tanks[currentTank].drawBar();
	glutPostRedisplay();  // redraw screen when all other requests 
						  // are satisfied
}

void World::fire()
{
	if (!bulletExists)
	{
		bullet = tanks[currentTank].launch();
		bulletExists = true;
		hasFired = true;
	}
}

/*
 * detect handles the collision detect between the bullet and all physical objects
 * in the World.
 */
void World::detect()
{
	/*
	 * Get information about the bullet to use for detection.
	 */

	// Get the bullet's location information.
	Vector bulletLoc = bullet->getLoc();
	double bulletx = bulletLoc[0];
	double bullety = bulletLoc[1];
	double bulletz = bulletLoc[2];

	// Get the bullet's velocity information.
	Vector bulletVel = bullet->getVel();
	double vbulletx = bulletVel[0];
	double vbullety = bulletVel[1];
	double vbulletz = bulletVel[2];
	double bulletspeed = bulletVel.length();

	// Get the bullet's radius.
	double radius = BULLET_RADIUS + EPSILON;

	// Get the bullet's projected next location and path.
	Vector bulletNextLoc = bullet->getNextLoc(TIME_PER_STEP);
	Vector path = (bulletNextLoc - bulletLoc);


	/*
	 * Pre-detection checks. Terminate if the ball is not moving or dead.
	 */

	// If we determine that the ball is "not moving," no collision detection is necessary.
	if (GRAVITY == 0)
	{
		if (path.length() < EPSILON)
		{
			return;
		}
	}

	// If the bullet ran out of life, kill it. No further collision detection is necessary.
	if (bullet->getLife() < 0)
	{
		PlaySound("FUSE_OUT", 0, SND_RESOURCE | SND_SYNC);
		cout << "Bullet's fuse ran out of time." << endl;
		delete bullet;
		bulletExists = false;
		return;
	}

#if SPHERE_SKY
	if (bulletNextLoc.length() > SKY_RADIUS)
	{
		// Going down -> hits water; going up -> escape velocity
		if ((bullet->getVel())[1] < 0)
		{
			cout << "Bullet splashed into the ocean." << endl;
		}
		else
		{
			cout << "Bullet achieved escape velocity!" << endl;
		}
		delete bullet;
		bulletExists = false;
		return;
	}
#endif

	/*
	 * Start the collision detection.
	 *
	 * Collision detection is split into multiple stages:
	 * (1) Triangle-Bullet Collision Detection.
	 * (2) Tank-Bullet Collision Detection.
	 * 
	 * In each stage, the time of the earliest collision in the stage is determined.
	 * These values are then compared to each other, to determine the earliest
	 * collision overall. This then determines the result of the collision.
	 */

	/*
	 * Variables to keep track of collisions.
	 */

	// Variables to keep track of what type of collisions are found.
	bool triangleCollision = false;
	bool tankCollision = false;

	// Variables to keep track of collision times.
	double triangleBestTime = TIME_PER_STEP;
	double tankBestTime = TIME_PER_STEP;
	int triangleHit = -1;
	int tankShot = -1;

	/*
	 * Stage 1: Triangle-Bullet Collision Detection.
	 *
	 * Triangle collision detection is split into three parts.
	 * (1) Face collision.
	 * (2) Edge collision.
	 * (3) Vertex collision.
	 */

	// Go through all the triangles and check for collisions.
	for (int i = 0; i < nTri; i++)
	{
		// Keep track of whether the bullet collides with this triangle and when.
		double collisionTime = TIME_PER_STEP;
		bool collidedThisTriangle = false;

		// Get the triangle information.
		Vector v1 = triangles[i]->verts[0];
		Vector v2 = triangles[i]->verts[1];
		Vector v3 = triangles[i]->verts[2];

		// Standardize the bullet's position and velocity.
		Vector sbulletvel = bullet->transformVelocity(triangles[i]->tmatrix);
		double sbulletvelx = sbulletvel[0];
		double sbulletvely = sbulletvel[1];
		double sbulletvelz = sbulletvel[2];
		Vector sbulletpos = bullet->transformPosition(triangles[i]->tmatrix);
		double sbulletposx = sbulletpos[0];
		double sbulletposy = sbulletpos[1];
		double sbulletposz = sbulletpos[2];

		/*
		 * Part 1: Face collision.
		 */

		// If the bullet is moving down toward the triangle, then a face collision is possible.
		if (sbulletvely <= 0)
		{
			// Determine the time when the bullet could hit the triangle.
			double testtime = -(sbulletposy - radius) / (sbulletvely); 

			// If there is enough time to hit the triangle, continue checking.
			if (testtime >= EPSILON && testtime < TIME_PER_STEP)
			{
				// Calculate the expected standardized position.
				double testx = sbulletposx + sbulletvelx*testtime;
				double testy = sbulletposy + sbulletvely*testtime;
				double testz = sbulletposz + sbulletvelz*testtime;

				// This is for checking whether the bullet is in the triangle.
				double v2x = (triangles[i]->sverts[1])[0];
				double v2z = (triangles[i]->sverts[1])[2];
				double v3x = (triangles[i]->sverts[2])[0];

				// Find the slopes for the lines composing the triangle.
				// More to the point, find the x values on those lines where
				// z = our intercept z. If we have a line x = mz + b, then
				// we can plug in testz and get out an x value.
				// Our two lines are (v2 - v1) and (v3 - v2);
				// the former has no x-intercept as it passes through the 
				// origin (i.e. v1 = <0, 0, 0>), thanks to standardization. 
				// Thus the first slope is (v2x / v2z), the second slope is
				// (v2x - v3x) / (v2z), since v3z = 0, and the second
				// line's x-intercept is simply v3x.
				double line1 = (v2x / v2z) * testz;
				double line2 = ((v2x - v3x) / v2z) * testz + v3x;

				/*
				 * Check whether the bullet is inside the triangle.
				 * This happens if:
				 * testz > 0, that is, the bullet's z-intercept has at least
				 *   a plausible chance of being within the triangle
				 * testx > line1. line1 is the x-value obtained by plugging
				 *   in the bullet's z-intercept into the equation for the line
				 *   that passes through the origin. 
				 * testx < line2. line2 is the x-value from the line that doesn't
				 * pass through the origin.
				 * In practice, we need to check to see if either line1 or line2
				 * is really close to zero (i.e. our triangle is more like a line),
				 * because we can still collide with those so they need to be checked.
				 */

				if ((testz > 0) && (testx > line1) && (testx < line2))
				{
					collidedThisTriangle = true;
					collisionTime = testtime;
				}
			}
		}

		// If a collision has not already occurred, check for collisions with edges and vertices.
		if (!collidedThisTriangle)
		{
			// Initialize alpha and beta.
			double alpha = -1, beta = -1;

			/*
			 * Part 2: Edge collision.
			 */

			// Check each vertex
			for (int j = 0; j < 3; ++j)
			{
				double tmpAlpha;

				// Get tmpAlpha, beta
				lineLineMinimumDistance(bulletLoc, bulletNextLoc, triangles[i]->verts[j], 
										triangles[i]->verts[(j+1)%3], tmpAlpha, beta);

				// Use the alphas and betas to find the closest points on each line and find the
				// distance between these points. We know that
				//		p1 = start1 + alpha * (end1-start1)
				//		p2 = start2 + beta * (end2-start2)
				// where p1 is the closest point on line 1, which is the line of motion for the
				// bullet and p2 is the closest point on line 2, which is the edge.

				Vector pathPoint = bulletLoc + path * tmpAlpha;
				Vector edgePoint = triangles[i]->verts[j] + 
								   (triangles[i]->verts[(j+1)%3] - triangles[i]->verts[j]) * beta;
				double distToEdge = (edgePoint - pathPoint).length();

				// Have a newer collision; if alpha < 0 then we don't have any collisions yet.
				if (distToEdge < BULLET_RADIUS && ((tmpAlpha < alpha) || (alpha < 0)))
				{
					alpha = tmpAlpha - BULLET_RADIUS / path.length();

					// Don't collide earlier than the bullet's path!
					if (alpha < 0)
					{
						alpha = EPSILON;
					}
					collidedThisTriangle = true;
					collisionTime = alpha*path.length() / bulletspeed;
				}
			}


			/*
			 * Part 3: Vertex detection.
			 */

			// Find alpha.
			alpha = -1;
			for (int j=0; j<3; j++) 
			{
				double tmpAlpha = linePointMinimumDistance(bulletLoc, bulletNextLoc, triangles[i]->verts[j]);
				double tmpDistToVertex = (bulletLoc + path * tmpAlpha).length();
				// Newer collision; if alpha < 0 then no collisions yet
				if (tmpDistToVertex <= BULLET_RADIUS && (tmpAlpha < alpha || alpha < 0)) 
				{
					alpha = tmpAlpha;
				}
			}
			
			// check if collision occurs
			if (alpha >=0) 
			{
				collidedThisTriangle = true;

				// Fudge factor - make certain the collision doesn't happen with the vertex
				// inside of the bullet-> Subtract radius.
				alpha -= (radius / path.length());

				// Don't collide before we start!
				if (alpha < 0)
				{
					alpha = EPSILON;
				}
				collisionTime = alpha*(bulletNextLoc - bulletLoc).length() / bulletspeed;
			}
		}

		/*
		 * Check whether this collision is better the best collision time so far.
		 */
		if (collidedThisTriangle && !triangleCollision)
		{
			triangleHit = i;
			triangleCollision = true;
			triangleBestTime = collisionTime;
		}
		else if (collidedThisTriangle && (collisionTime < triangleBestTime))
		{
			triangleHit = i;
			triangleBestTime = collisionTime;
		}
	} // End of checking triangles for collisions.


	/*
	 * Stage 2: Tank-Bullet Collision Detection.
	 */

	double dist = -10000;
	double bulletAlpha = -1;

	// Check each tank for whether the bullet collides with it.
	for (int i = 0; i < numPlayers; ++i)
	{
		// Only check tanks that are alive.
		if (tanks[i].isAlive())
		{
			bulletAlpha = linePointMinimumDistance(bulletLoc, bulletNextLoc, tanks[i].getLoc());
			Vector closestPoint = (bulletNextLoc - bulletLoc)*bulletAlpha + bulletLoc;
			dist = (closestPoint).distance(tanks[i].getLoc());

			// If the bullet touches the tank at the closest point.
			if (dist < (BULLET_RADIUS + TANK_RADIUS + EPSILON))
			{
				double collisionTime = dist / bulletspeed;
				// If this is the first collision.
				if (!tankCollision)
				{
					tankShot = i;
					tankCollision = true;
					tankBestTime = collisionTime;
				}
				// If there was already another tank shot, check whether this was earlier.
				else if (tankCollision && (collisionTime < tankBestTime))
				{
					tankShot = i;
					tankBestTime = collisionTime;	
				}
			}
		}
	}


	/*
	 * Determine whether the bullet collided or not and how to respond.
	 */

	// If the ball collides.
	if ( (triangleCollision && tankCollision && (triangleBestTime < tankBestTime)) || 
		 (triangleCollision && !tankCollision))
	{

		Vector sbulletpos = bullet->transformPosition(triangles[triangleHit]->tmatrix);
		Vector sbulletvel = bullet->transformVelocity(triangles[triangleHit]->tmatrix);
		// The bullet hits the terrain.
		cout << "Whiff!" << endl;
		delete bullet;
		bulletExists = false;
		PlaySound("TERRAIN_HIT", 0, SND_RESOURCE | SND_SYNC);
	}
	else if (tankCollision)
	{
		PlaySound("TANK_HIT", 0, SND_RESOURCE | SND_SYNC);
		// The bullet hits a tanks.
		if (tankShot == currentTank)
		{
			cout << colors[currentTank] << " has committed suicide!" << endl;
		}
		else
		{
			cout << colors[currentTank] << " has killed " << colors[tankShot] << "!" << endl;
		}
		tanks[tankShot].die();
		++scores[currentTank];
		--tanksAlive;
		delete bullet;
		bulletExists = false;

		// Choose a destruction message randomly.
		double selection = ((double)rand())/RAND_MAX;
		if (selection < 0.25)
		{
			PlaySound("CONGRATS1", 0, SND_RESOURCE | SND_SYNC);
		}
		else if (selection < 0.5)
		{
			PlaySound("CONGRATS2", 0, SND_RESOURCE | SND_SYNC);
		}
		else if (selection < 0.75)
		{
			PlaySound("CONGRATS3", 0, SND_RESOURCE | SND_SYNC);
		}
		else
		{
			PlaySound("CONGRATS4", 0, SND_RESOURCE | SND_SYNC);
		}
	}
	// If the ball did not collide.
	else
	{
		bullet->move(TIME_PER_STEP);
	}
}

/*
 * initTanks initializes the properties of the tanks. It uses an array of colors to
 * assign colors, and randomly generates tank positions if possible.
 */
void World::initTanks()
{
	// Array of tank colors
	tankColors[0] = Vector(1,0,0);
	tankColors[1] = Vector(.25,1,.25);
	tankColors[2] = Vector(0,0,1);
	tankColors[3] = Vector(1,0,1);
	tankColors[4] = Vector(0.5,0,1);
	tankColors[5] = Vector(0,1,1);
	tankColors[6] = Vector(1,1,0);
	tankColors[7] = Vector(1,0.5,0);

	// Array of default locations for tanks
	defLoc[0] = Vector(0,0,0);
	defLoc[1] = Vector(2,0,0);
	defLoc[2] = Vector(4,0,0);
	defLoc[3] = Vector(4,0,2);
	defLoc[4] = Vector(4,0,4);
	defLoc[5] = Vector(2,0,4);
	defLoc[6] = Vector(0,0,4);
	defLoc[7] = Vector(0,0,2);


	time_t curr=time(0);
	long seed = (long)curr;
	srand(seed);

	int solution = 0;
    
	double* heightMap = ground->getMap();

	for (int i = 0; i < numPlayers; ++i)
	{
		bool startLocGood = false;

		tanks[i].setColor(tankColors[i]);
		Vector initLoc(0,0,0);

		while (!startLocGood)
		{
			++solution;
			int farCounter = 0;
			double ratio = ((double)MAP_SIZE)/TERRAIN_COLS;
			initLoc[0] = snap((((double)rand())/RAND_MAX)*(MAP_SIZE-1));			
			initLoc[2] = snap((((double)rand())/RAND_MAX)*(MAP_SIZE-1));

			int colLoc = initLoc[0]/ratio;
			int rowLoc = initLoc[2]/ratio;
			double lowerBound = 0;
			double upperBound = MAP_SIZE - 2*ratio;

			initLoc[1] = heightMap[colLoc + rowLoc*TERRAIN_COLS];

			if (i == 0 &&
				initLoc[0] > lowerBound &&
				initLoc[2] > lowerBound &&
				initLoc[0] < upperBound &&
				initLoc[2] < upperBound)	// first tank is always in a "good" position relative to the other tanks
			{
				startLocGood = true;
			}

			for (int j = 0; j < i; ++j)
			{
				if (i != j)
				{
					double tankDist = initLoc.distance(tanks[j].getLoc());
					if (tankDist > TANK_CLOSENESS)
					{
						++farCounter;	// if the distance is insufficient, increment the counter
					}
				}
			}
			if (farCounter > i-1 &&
				initLoc[0] > lowerBound &&
				initLoc[2] > lowerBound &&
				initLoc[0] < upperBound &&
				initLoc[2] < upperBound) // if far enough from every other other tank, accept location
			{
				startLocGood = true; // will cause a break from the while loop
			}

			if (solution > 1000)
			{
                cout << "Reverting to default solution.  Random solution deemed impossible.\n"
					 << "If a random solution is still desired, restart game and try again." << endl;
				startLocGood = true;

				for (int k = 0; k < numPlayers; ++k)
				{
					tanks[k].setLoc(defLoc[k]);
				}
				return;
			}

		}  // end while loop

		tanks[i].setLoc(initLoc);
		scores[i] = 0;

	}	// end for loop
}


void World::upTheta()
{
	tanks[currentTank].rotateTheta(THETA_INCREMENT);
}

void World::downTheta()
{
	tanks[currentTank].rotateTheta(-THETA_INCREMENT);
}

void World::upPhi()
{
	tanks[currentTank].rotatePhi(PHI_INCREMENT);
}

void World::downPhi()
{
	tanks[currentTank].rotatePhi(-PHI_INCREMENT);
}

void World::upPower()
{
	tanks[currentTank].powerUp();
}

void World::downPower()
{
	tanks[currentTank].powerDown();
}





/*
 * Helpful functions.
 */

/************************************************************/
/*															*/
/*	this routine finds the closest point q on the line		*/
/*	segment defined by the points "start" and "end"			*/
/*	to the point "v"										*/
/*															*/
/*	it returns alpha where q=start + alpha * (end-start)	*/
/*															*/
/************************************************************/
				
double linePointMinimumDistance(const Vector& start, const Vector& end, const Vector& v)
{

	// construct a vector along the line
	Vector v1=end-start;
	double len = v1.length();
	// check if the line is actually a point
	if (len == 0)
		// if so the point start=end is desired point and alpha=0
		return 0; 

	// construct a vector from the line to the point
	Vector v2=v-start;
	// q=start + alpha * v1 is the closest point on the line to the point v
	// where alph is defined below
	double alpha = v1.dot(v2)/(len*len);

	// if q is not on the line segment then an endpoint of the line
	// segment is the desired point
	if (alpha<0)
		alpha=0;
	if (alpha>1)
		alpha=1;
	
	return alpha;
}

//******************************************************************//
//																	//
//	This routine finds to closest points p1 & p2 on two	line		//
//	segments, l1 (start1 to end1) and l2 (start2 to end2)			//
//  It computes alpha and beta in [0,1] such that					//
//		p1 = start1 + alpha * (end1-start1)							//
//		p2 = start2 + beta * (end2-start2)							//
//	If the lines are parallel -- which should never result in a		//
//	collision, it returns alpha=beta=-1								//
//																	//
//******************************************************************//	

void lineLineMinimumDistance(const Vector& start1, const Vector& end1, 
							 const Vector& start2, const Vector& end2, 
							 double& alpha, double& beta)
{



	// find vector along first line
	Vector v1=end1-start1;
	double v1dotv1=v1.dot(v1);
	// check if the line is actually a point
	if (v1dotv1==0) {	
		// first line is really a point
		alpha = 0;
		beta = linePointMinimumDistance(start2, end2, start1);
		return;
	}

	// find vector along second line
	Vector v2=end2-start2;
	double v2dotv2=v2.dot(v2);
	// check if the line is actually a point
	if (v2dotv2==0) {
		// second line is really a point
		alpha = linePointMinimumDistance(start1, end1, start2);
		beta=0;
		return;
	}

	// check if lines are parallel
	double v1dotv2=v2.dot(v1);  // we define both for convenience
	double v2dotv1=v1dotv2;

	if (v2dotv2*v1dotv1 != v2dotv1*v1dotv2) {  // do not parallel case first
		// Find closest point
		Vector s=start2-start1;
		double sdotv1=s.dot(v1);
		double sdotv2=s.dot(v2);

		beta = (sdotv2- sdotv1*v1dotv2/v1dotv1)/(v1dotv2*v2dotv1/v1dotv1 - v2dotv2);
		alpha = (sdotv1 + beta*v2dotv1)/(v1dotv1);

		// if alpha and beta are both on their line segments
		// we are done
		// if not, then at least one of the points we are
		// looking for is an endpoint.  we could test each
		// endpoint to find its closest point on the other
		// line.  this would take four calls to linePointMinimumDistance.
		// if we examine the possible cases, however, we
		// need only compute one call to linePointMinimumDistance.
		// we take that approach.

		// alpha and beta are each in one of three states:
		// 0<= alpha <=1, alpha<0, or alpha>1  
		// 0<= beta <=1,  beta <0, or beta>1
		// thus there are nine states to consider
		// testval represents the states
		int testval = 3*(alpha<0) + 6*(alpha>1) + 1*(beta<0) + 2*(beta>1);

		switch (testval) {
		case 0: {	// alpha and beta are in [0,1]
			return;
				}

		case 1: {	// alpha in [0,1], beta<0
				alpha = linePointMinimumDistance(start1,end1,start2);
				beta=0;
				return;
				}

		case 2: {	// alpha in [0,1], beta>1
				alpha = linePointMinimumDistance(start1,end1,end2);
				beta=1;
				return;
				}

		case 3: {	// alpha < 0, beta in [0,1]
				alpha=0;
				beta=linePointMinimumDistance(start2,end2,start1);
				return;
				}

		case 6: {	// alpha > 1, beta in [0,1]
				alpha=1;
				beta=linePointMinimumDistance(start2,end2,end1);
				return;
				}

		case 5: {  // alpha <0, beta >1
				alpha=0;
				beta=1;
				return;
				}

		case 7: {  // alpha >1, beta <0
				alpha=1;
				beta=0;
				return;
				}

		case 4: {  //alpha < 0, beta < 0
					if ((v1*alpha).length() > (v2*beta).length()) {
						alpha=0;
						beta=linePointMinimumDistance(start2,end2,start1);
					}
					else {
						beta=0;
						alpha = linePointMinimumDistance(start1,end1,start2);
					}
					return;
				}

		case 8: {  // alpha > 1, beta > 1
					if ((start1+v1*alpha-end1).length() > (start2+v2*beta).length()) {
						alpha=1;
						beta=linePointMinimumDistance(start2,end2,end1);
					}
					else {
						beta = 1;
						alpha =	linePointMinimumDistance(start1,end1,end2);
					}

					return;
				}

		}

	}
	else { 

		// the lines are parallel
		// this should never result in a collision
		alpha = -1;
		beta=-1;
		return;
	}

}

double leastPositive(double d1, double d2, double d3)
{
	if ((d1 > 0) && (d1 < d2) && (d1 < d3)) return d1;
	if ((d2 > 0) && (d2 < d3)) return d2;
	if (d3 > 0) return d3;
	return -1;
}



double World::snap(double loc)
{
	int cols = TERRAIN_COLS;
	int mult = cols/MAP_SIZE;

	double y = (int)loc;
	double x = loc-y;

	double ratio = ((double)MAP_SIZE) / cols;

	while (x > ratio)
	{
		--mult;
		x = x - ratio;
	}

	x = mult*ratio;
	loc = x + y;

	return loc;
}