/*
Copyright (C) 1997-2001 Id Software, Inc.

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  

See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

*/

#include "g_local.h"


void SP_misc_teleporter_dest( edict_t *ent );


/*QUAKED info_player_start (1 0 0) (-16 -16 -24) (16 16 32)
The normal starting point for a level.
*/
void SP_info_player_start( edict_t *self )
{
	G_DropSpawnpointToFloor( self );
}

/*QUAKED info_player_deathmatch (1 0 1) (-16 -16 -24) (16 16 32)
potential spawning position for deathmatch games
*/
void SP_info_player_deathmatch( edict_t *self )
{
	G_DropSpawnpointToFloor( self );
}

/*QUAKED info_player_intermission (1 0 1) (-16 -16 -24) (16 16 32)
The deathmatch intermission point will be at one of these
Use 'angles' instead of 'angle', so you can set pitch or roll as well as yaw.  'pitch yaw roll'
*/
void SP_info_player_intermission( edict_t *ent )
{
}


/*
=======================================================================

  SelectSpawnPoints

=======================================================================
*/

//================
//PlayersRangeFromSpot
//
//Returns the distance to the nearest player from the given spot
//================
float PlayersRangeFromSpot( edict_t *spot, int ignore_team )
{
	edict_t	*player;
	float	bestplayerdistance;
	int		n;
	float	playerdistance;

	bestplayerdistance = 9999999;

	for( n = 1; n <= game.maxclients; n++ )
	{
		player = &game.edicts[n];

		if( !player->r.inuse )
			continue;
		if( G_IsDead(player) )
			continue;
		if( ignore_team && ignore_team == player->s.team )
			continue;

		playerdistance = DistanceFast( spot->s.origin, player->s.origin );

		if( playerdistance < bestplayerdistance )
			bestplayerdistance = playerdistance;
	}

	return bestplayerdistance;
}


//===========
// G_SelectIntermissionSpawnPoint
// Returns a intermission spawnpoint, or a deathmatch spawnpoint if
// no info_player_intermission was found.
//============
edict_t *G_SelectIntermissionSpawnPoint( void )
{
	edict_t *ent;
	int		i;

	// find an intermission spot
	ent = G_Find (NULL, FOFS(classname), "info_player_intermission");
	if (!ent)
	{	// the map creator forgot to put in an intermission point...
		ent = G_Find (NULL, FOFS(classname), "info_player_start");
		if (!ent)
			ent = G_Find (NULL, FOFS(classname), "info_player_deathmatch");
	}
	else
	{	
		// chose one of four spots
		i = rand() & 3;
		while (i--)
		{
			ent = G_Find (ent, FOFS(classname), "info_player_intermission");
			if (!ent)	// wrap around the list
				ent = G_Find (ent, FOFS(classname), "info_player_intermission");
		}
	}

	return ent;
}

//================
//SelectRandomDeathmatchSpawnPoint
//
//go to a random point, but NOT the two points closest
//to other players
//================
edict_t *SelectRandomDeathmatchSpawnPoint( edict_t *ent )
{
	edict_t	*spot, *spot1, *spot2;
	int		count = 0;
	int		selection, ignore_team = 0;
	float	range, range1, range2;

	spot = NULL;
	range1 = range2 = 99999;
	spot1 = spot2 = NULL;

	if( ent && GS_Gametype_IsTeamBased(game.gametype) )
		ignore_team = ent->s.team;

	while( (spot = G_Find (spot, FOFS(classname), "info_player_deathmatch")) != NULL )
	{
		count++;
		range = PlayersRangeFromSpot( spot, ignore_team );
		if( range < range1 )
		{
			range1 = range;
			spot1 = spot;
		}
		else if( range < range2 )
		{
			range2 = range;
			spot2 = spot;
		}
	}

	if( !count )
		return NULL;

	if( count <= 2 )
	{
		spot1 = spot2 = NULL;
	}
	else
	{
		if( spot1 )
			count--;
		if( spot2 && spot2 != spot1 )
			count--;
	}

	selection = rand() % count;
	spot = NULL;
	do
	{
		spot = G_Find( spot, FOFS(classname), "info_player_deathmatch" );
		if( spot == spot1 || spot == spot2 )
			selection++;
	} while( selection-- );

	return spot;
}

/* disable DF_SPAWN_FARTHEST
//================
//SelectFarthestDeathmatchSpawnPoint
//================
edict_t *SelectFarthestDeathmatchSpawnPoint (void)
{
	edict_t	*bestspot;
	float	bestdistance, bestplayerdistance;
	edict_t	*spot;

	spot = NULL;
	bestspot = NULL;
	bestdistance = 0;
	while ((spot = G_Find (spot, FOFS(classname), "info_player_deathmatch")) != NULL)
	{
		bestplayerdistance = PlayersRangeFromSpot (spot);

		if (bestplayerdistance > bestdistance)
		{
			bestspot = spot;
			bestdistance = bestplayerdistance;
		}
	}

	if (bestspot)
	{
		return bestspot;
	}

	// if there is a player just spawned on each and every start spot
	// we have no choice to turn one into a telefrag meltdown
	spot = G_Find (NULL, FOFS(classname), "info_player_deathmatch");

	return spot;
}*/

edict_t *SelectDeathmatchSpawnPoint( edict_t *ent )
{
	/* disable DF_SPAWN_FARTHEST
	if (dmflags->integer & DF_SPAWN_FARTHEST)
		return SelectFarthestDeathmatchSpawnPoint (e);
	else*/
		return SelectRandomDeathmatchSpawnPoint(ent);
}


//===========
//SelectSpawnPoint
//
//Chooses a player start, deathmatch start, etc
//============
void SelectSpawnPoint( edict_t *ent, vec3_t origin, vec3_t angles )
{
	trace_t	trace;
	edict_t	*spot = NULL;

	if( game.gametype == GAMETYPE_CTF )
		spot = G_Gametype_CTF_SelectSpawnPoint(ent);
	else
		spot = SelectDeathmatchSpawnPoint(ent);

	// find a single player start spot
	if( !spot )
	{
		while( (spot = G_Find (spot, FOFS(classname), "info_player_start")) != NULL )
		{
			if( !game.spawnpoint[0] && !spot->targetname )
				break;

			if( !game.spawnpoint[0] || !spot->targetname )
				continue;

			if( Q_stricmp(game.spawnpoint, spot->targetname) == 0 )
				break;
		}

		if( !spot ) {
			if( !game.spawnpoint[0] )
			{	// there wasn't a spawnpoint without a target, so use any
				spot = G_Find( spot, FOFS(classname), "info_player_start" );
			}
			if( !spot )
				G_Error( "Couldn't find spawn point %s\n", game.spawnpoint );
		}
	}

	VectorCopy( spot->s.origin, origin );
	VectorCopy( spot->s.angles, angles );

	// SPAWN TELEFRAGGING PROTECTION.
	//-----------------------------------------------------------------
	// we got a spawnpoint, but this is not enough for us, we want also
	// the player to be moved in fractions of the player box width inside
	// a radius defined in the entity

	// first check the normal spawn location
	//trap_Trace( &trace, origin, playerbox_stand_mins, playerbox_stand_maxs, origin, NULL, MASK_PLAYERSOLID );
	//if( trace.startsolid || trace.allsolid || trace.fraction < 1.0f )
	{
		float	radius = 150; // fixme: radius should be a field of the spawnpoint entity
		vec3_t	virtualorigin;
		// we will use a grid of player boxes instead of just moving it
		float	playerbox_rowwidth = playerbox_stand_maxs[0] - playerbox_stand_mins[0];
		float	playerbox_columnwidth = playerbox_stand_maxs[1] - playerbox_stand_mins[1];
		int		rows, columns;
		int		i, row = 0, column = 0;
		int		rowseed = rand() & 255;
		int		columnseed = rand() & 255;
		int		contents = (CONTENTS_SOLID|CONTENTS_PLAYERCLIP);
		int		othercontents = (CONTENTS_LAVA|CONTENTS_SLIME|CONTENTS_TELEPORTER|CONTENTS_JUMPPAD|CONTENTS_BODY|CONTENTS_NODROP);

		rows = radius / playerbox_rowwidth;
		columns = radius / playerbox_columnwidth;

		// no, we won't just do a while, let's go safe and just check as many times as 
		// positions in the grid. If we didn't found a spawnpoint by then, we let it telefrag.
		for( i = 0; i < (rows * columns); i++ ) {
			row = Q_brandom( &rowseed, -rows, rows );
			column = Q_brandom( &columnseed, -columns, columns );

			VectorSet( virtualorigin, origin[0] + (row * playerbox_rowwidth),
				origin[1] + (column * playerbox_columnwidth),
				origin[2] );

			// we must do 2 checks. First one must check only against the world
			// to verify we can move the box to that point (checking contents
			// of the final position seems to not be enough since it can go outside of the collision hulls)
			contents = (CONTENTS_SOLID|CONTENTS_PLAYERCLIP);
			othercontents = (CONTENTS_LAVA|CONTENTS_SLIME|CONTENTS_TELEPORTER|CONTENTS_JUMPPAD|CONTENTS_BODY|CONTENTS_NODROP);

			trap_Trace( &trace, origin, playerbox_stand_mins, playerbox_stand_maxs, virtualorigin, NULL, contents );
			if( trace.startsolid || trace.allsolid || trace.fraction < 1.0f ) {
				//G_Printf( "INVALID (WORLDCHECK): startsolid %i, allsoid %i, contents %i\n", trace.startsolid, trace.allsolid, trace.contents );
				continue;
			}

			contents |= othercontents;
			// now we check this position for other type of problems (players, lava, teleporters)
			trap_Trace( &trace, virtualorigin, playerbox_stand_mins, playerbox_stand_maxs, virtualorigin, NULL, contents );
			if( trace.startsolid || trace.allsolid || trace.fraction < 1.0f ) {
				//G_Printf( "INVALID (PLAYERCHECK): startsolid %i, allsoid %i, contents %i\n", trace.startsolid, trace.allsolid, trace.contents );
				continue;
			}

			// one more check before accepting this spawn: there's ground at our feets?
			if( !(spot->spawnflags & 1) ) // if floating item flag is not set
			{
				vec3_t origin_from, origin_to;
				VectorCopy( virtualorigin, origin_from );
				origin_from[2] += playerbox_stand_mins[2];
				VectorCopy( origin_from, origin_to );
				origin_to[2] -= 16;
				// use point trace instead of box trace to avoid small gliches that can't support the player
				// but will stop the trace
				trap_Trace( &trace, origin_from, vec3_origin, vec3_origin, origin_to, NULL, contents );
				if( trace.startsolid || trace.allsolid || trace.fraction == 1.0f ) { // full run means no ground
					//G_Printf( "INVALID (GROUNDCHECK): startsolid %i, allsoid %i, contents %i\n", trace.startsolid, trace.allsolid, trace.contents );
					continue;
				}
				VectorCopy( trace.endpos, virtualorigin );
				virtualorigin[2] -= playerbox_stand_mins[2];
			}

			//G_Printf( "VALID(%i,%i): startsolid %i, allsoid %i, contents %i\n", row, column, trace.startsolid, trace.allsolid, trace.contents );
			VectorCopy( virtualorigin, origin );
			break;
		}
	}
}


