//========= Copyright © 1996-2002, Valve LLC, All rights reserved. ============
//
// Purpose: 
//
// $NoKeywords: $
//=============================================================================

#include "cbase.h"
#include "engine/IEngineSound.h"
#include "mempool.h"
#include "movevars_shared.h"
#include "utlrbtree.h"
#include "tier0/vprof.h"

// memory pool for storing links between entities
static CMemoryPool g_EdictTouchLinks( sizeof(touchlink_t), 512, CMemoryPool::GROW_NONE );

int linksallocated = 0;

// Prints warnings if any entity think functions take longer than this many milliseconds
#ifdef _DEBUG
#define DEF_THINK_LIMIT "20"
#else
#define DEF_THINK_LIMIT "10"
#endif
ConVar think_limit( "think_limit", DEF_THINK_LIMIT, FCVAR_REPLICATED, "Maximum think time in milliseconds, warning is printed if this is exceeded." );

//-----------------------------------------------------------------------------
// Purpose: 
// Output : inline touchlink_t
//-----------------------------------------------------------------------------
inline touchlink_t *AllocTouchLink( void )
{
	touchlink_t *link = (touchlink_t*)g_EdictTouchLinks.Alloc( sizeof(touchlink_t) );
	if ( link )
	{
		++linksallocated;
	}
	else
	{
		Error( "AllocTouchLink:  Progamming error, failed to allocate touchlink_t.  Touchlinks not being freed correctly!!!\n" );
	}

	return link;
}

//-----------------------------------------------------------------------------
// Purpose: 
// Input  : *link - 
// Output : inline void
//-----------------------------------------------------------------------------
inline void FreeTouchLink( touchlink_t *link )
{
	if ( link )
	{
		--linksallocated;
	}

	g_EdictTouchLinks.Free( link );
}

//-----------------------------------------------------------------------------
// Purpose: Checks to see if any entities that have been touching this one
//			have stopped touching it, and notify the entity if so.
//			Called at the end of a frame, after all the entities have run
//-----------------------------------------------------------------------------
void CBaseEntity::PhysicsCheckForEntityUntouch( void )
{
	touchlink_t *link, *nextLink;

	link = m_EntitiesTouched.nextLink;
	while ( link != &m_EntitiesTouched )
	{
		nextLink = link->nextLink;

		// these touchlinks are not polled.  The ents are touching due to an outside
		// system that will add/delete them as necessary (vphysics in this case)
		if ( link->touchStamp == TOUCHSTAMP_EVENT_DRIVEN )
		{
			// refresh the touch call
			PhysicsTouch( link->entityTouched );
		}
		else
		{
			// check to see if the touch stamp is up to date
			if ( link->touchStamp != touchStamp )
			{
				// stamp is out of data, so entities are no longer touching
				// remove self from other entities touch list
				PhysicsNotifyOtherOfUntouch( this, link->entityTouched );

				// remove other entity from this list
				PhysicsRemoveToucher( this, link );
			}
		}

		link = nextLink;
	}

	SetCheckUntouch( false );
}

//-----------------------------------------------------------------------------
// Purpose: notifies an entity than another touching entity has moved out of contact.
// Input  : *other - the entity to be acted upon
//-----------------------------------------------------------------------------
void CBaseEntity::PhysicsNotifyOtherOfUntouch( CBaseEntity *ent, CBaseEntity *other )
{
	if ( !other )
		return;

	// loop through ed's touch list, looking for the notifier
	// remove and call untouch if found
	touchlink_t *link = other->m_EntitiesTouched.nextLink;
	while ( link != &other->m_EntitiesTouched )
	{
		if ( link->entityTouched == ent )
		{
			PhysicsRemoveToucher( other, link );
			return;
		}

		link = link->nextLink;
	}
}

//-----------------------------------------------------------------------------
// Purpose: removes a toucher from the list
// Input  : *link - the link to remove
//-----------------------------------------------------------------------------
void CBaseEntity::PhysicsRemoveToucher( CBaseEntity *other, touchlink_t *link )
{
	// Every start Touch gets a corresponding end touch
	if ( (link->flags & FTOUCHLINK_START_TOUCH) && link->entityTouched != NULL )
	{
		CBaseEntity *linkEntity = link->entityTouched;
		CBaseEntity *otherEntity = other;
		if ( linkEntity && otherEntity )
		{
			otherEntity->EndTouch( linkEntity );
		}
	}

	link->nextLink->prevLink = link->prevLink;
	link->prevLink->nextLink = link->nextLink;
	FreeTouchLink( link );
}

//-----------------------------------------------------------------------------
// Purpose: Clears all touches from the list
//-----------------------------------------------------------------------------
void CBaseEntity::PhysicsRemoveTouchedList( CBaseEntity *ent )
{
	touchlink_t *link, *nextLink;

	link = ent->m_EntitiesTouched.nextLink;
	while ( link && link != &ent->m_EntitiesTouched )
	{
		nextLink = link->nextLink;

		// notify the other entity that this ent has gone away
		PhysicsNotifyOtherOfUntouch( ent, link->entityTouched );

		// kill it
		FreeTouchLink( link );

		link = nextLink;
	}

	ent->m_EntitiesTouched.nextLink = ent->m_EntitiesTouched.prevLink = &ent->m_EntitiesTouched;
	ent->touchStamp = 0;
}

//-----------------------------------------------------------------------------
// Purpose: Called every frame that two entities are touching
// Input  : *pentOther - the entity who it has touched
//-----------------------------------------------------------------------------
void CBaseEntity::PhysicsTouch( CBaseEntity *pentOther )
{
	if ( pentOther )
	{
		if ( !(IsMarkedForDeletion() || pentOther->IsMarkedForDeletion()) )
		{
			Touch( pentOther );
		}
	}
}

//-----------------------------------------------------------------------------
// Purpose: Called whenever two entities come in contact
// Input  : *pentOther - the entity who it has touched
//-----------------------------------------------------------------------------
void CBaseEntity::PhysicsStartTouch( CBaseEntity *pentOther )
{
	if ( pentOther )
	{
		if ( !(IsMarkedForDeletion() || pentOther->IsMarkedForDeletion()) )
		{
			StartTouch( pentOther );
			Touch( pentOther );
		}
	}
}

//-----------------------------------------------------------------------------
// Purpose: Marks in an entity that it is touching another entity, and calls
//			it's Touch() function if it is a new touch.
//			Stamps the touch link with the new time so that when we check for
//			untouch we know things haven't changed.
// Input  : *other - entity that it is in contact with
//-----------------------------------------------------------------------------
touchlink_t *CBaseEntity::PhysicsMarkEntityAsTouched( CBaseEntity *other )
{
	touchlink_t *link;

	if ( this == other )
		return NULL;

	// check if either entity doesn't generate touch functions
	if ( (GetFlags() | other->GetFlags()) & FL_DONTTOUCH )
	{
		return NULL;
	}

	// check if the edict is already in the list
	for ( link = m_EntitiesTouched.nextLink; link != &m_EntitiesTouched; link = link->nextLink )
	{
		if ( link->entityTouched == other )
		{
			// update stamp
			link->touchStamp = touchStamp;
			
			PhysicsTouch( other );

			// no more to do
			return link;
		}
	}

	// entity is not in list, so it's a new touch
	// add it to the touched list and then call the touch function

	// build new link
	link = AllocTouchLink();
	if ( !link )
		return NULL;

	link->touchStamp = touchStamp;
	link->entityTouched = other;
	link->flags = 0;
	// add it to the list
	link->nextLink = m_EntitiesTouched.nextLink;
	link->prevLink = &m_EntitiesTouched;
	link->prevLink->nextLink = link;
	link->nextLink->prevLink = link;

	// non-solid entities don't get touched
	bool bShouldTouch = (IsSolid() && !IsSolidFlagSet(FSOLID_VOLUME_CONTENTS)) || IsSolidFlagSet(FSOLID_TRIGGER);
	if ( bShouldTouch && !other->IsSolidFlagSet(FSOLID_TRIGGER) )
	{
		link->flags |= FTOUCHLINK_START_TOUCH;
		PhysicsStartTouch( other );
	}

	return link;
}

static trace_t g_TouchTrace;
trace_t CBaseEntity::GetTouchTrace( void )
{
	return g_TouchTrace;
}

//-----------------------------------------------------------------------------
// Purpose: Marks the fact that two edicts are in contact
// Input  : *other - other entity
//-----------------------------------------------------------------------------
void CBaseEntity::PhysicsMarkEntitiesAsTouching( CBaseEntity *other, trace_t &trace )
{
	g_TouchTrace = trace;
	PhysicsMarkEntityAsTouched( other );
	other->PhysicsMarkEntityAsTouched( this );
}

void CBaseEntity::PhysicsMarkEntitiesAsTouchingEventDriven( CBaseEntity *other, trace_t &trace )
{
	g_TouchTrace = trace;

	touchlink_t *link;
	link = this->PhysicsMarkEntityAsTouched( other );
	if ( link )
	{
		// mark these links as event driven so they aren't untouched the next frame
		// when the physics doesn't refresh them
		link->touchStamp = TOUCHSTAMP_EVENT_DRIVEN;
	}
	link = other->PhysicsMarkEntityAsTouched( this );
	if ( link )
	{
		link->touchStamp = TOUCHSTAMP_EVENT_DRIVEN;
	}
}

//-----------------------------------------------------------------------------
// Purpose: Two entities have touched, so run their touch functions
// Input  : *other - 
//			*ptrace - 
//-----------------------------------------------------------------------------
void CBaseEntity::PhysicsImpact( CBaseEntity *other, trace_t &trace )
{
	if ( !other )
	{
		return;
	}

	// If either of the entities is flagged to be deleted, 
	//  don't call the touch functions
	if ( ( GetFlags() | other->GetFlags() ) & FL_KILLME )
	{
		return;
	}

	PhysicsMarkEntitiesAsTouching( other, trace );
}

//-----------------------------------------------------------------------------
// Purpose: Returns the mask of what is solid for the given entity
// Output : unsigned int
//-----------------------------------------------------------------------------
unsigned int CBaseEntity::PhysicsSolidMaskForEntity( void ) const
{
	return MASK_SOLID;
}


//-----------------------------------------------------------------------------
// Computes the water level + type
//-----------------------------------------------------------------------------
void CBaseEntity::UpdateWaterState()
{
	// FIXME: This computation is nonsensical for rigid child attachments
	// Should we just grab the type + level of the parent?
	// Probably for rigid children anyways...

	// Compute the point to check for water state
	Vector	point;
	point[0] = (GetAbsMins()[0] + GetAbsMaxs()[0]) * 0.5;
	point[1] = (GetAbsMins()[1] + GetAbsMaxs()[1]) * 0.5;
	point[2] = GetAbsMins()[2] + 1;

	SetWaterLevel( 0 );
	SetWaterType( CONTENTS_EMPTY );
	int cont = UTIL_PointContents (point);

	if (( cont & MASK_WATER ) == 0)
		return;

	SetWaterType( cont );
	SetWaterLevel( 1 );

	// point sized entities are always fully submerged
	if (GetAbsMins()[2] == GetAbsMaxs()[2])
	{
		SetWaterLevel( 3 );
	}
	else
	{
		// Check the exact center of the box
		point[2] = (GetAbsMins()[2] + GetAbsMaxs()[2])*0.5;
		int midcont = UTIL_PointContents (point);
		if ( midcont & MASK_WATER )
		{
			// Now check where the eyes are...
			SetWaterLevel( 2 );
			point[2] = point[2] + GetViewOffset()[2];

			int eyecont = UTIL_PointContents (point);
			if ( eyecont & MASK_WATER )
			{
				SetWaterLevel( 3 );
			}
		}
	}
}


//-----------------------------------------------------------------------------
// Purpose: Check if entity is in the water and applies any current to velocity
// and sets appropriate water flags
// Output : Returns true on success, false on failure.
//-----------------------------------------------------------------------------
bool CBaseEntity::PhysicsCheckWater( void )
{
	if (GetMoveParent())
		return GetWaterLevel() > 1;

	int cont = GetWaterType();

	// If we're not in water + don't have a current, we're done
	if ( cont & (MASK_WATER | MASK_CURRENT) != (MASK_WATER | MASK_CURRENT) )
		return GetWaterLevel() > 1;

	// Compute current direction
	Vector v( 0, 0, 0 );
	if ( cont & CONTENTS_CURRENT_0 )
	{
		v[0] += 1;
	}
	if ( cont & CONTENTS_CURRENT_90 )
	{
		v[1] += 1;
	}
	if ( cont & CONTENTS_CURRENT_180 )
	{
		v[0] -= 1;
	}
	if ( cont & CONTENTS_CURRENT_270 )
	{
		v[1] -= 1;
	}
	if ( cont & CONTENTS_CURRENT_UP )
	{
		v[2] += 1;
	}
	if ( cont & CONTENTS_CURRENT_DOWN )
	{
		v[2] -= 1;
	}

	// The deeper we are, the stronger the current.
	Vector newBaseVelocity;
	VectorMA (GetBaseVelocity(), 50.0*GetWaterLevel(), v, newBaseVelocity);
	SetBaseVelocity( newBaseVelocity );
	
	return GetWaterLevel() > 1;
}


//-----------------------------------------------------------------------------
// Purpose: Bounds velocity
//-----------------------------------------------------------------------------
void CBaseEntity::PhysicsCheckVelocity( void )
{
	Vector origin = GetAbsOrigin();
	Vector vecAbsVelocity = GetAbsVelocity();

	bool bReset = false;
	for ( int i=0 ; i<3 ; i++ )
	{
		if ( IS_NAN(vecAbsVelocity[i]) )
		{
			Msg( "Got a NaN velocity on %s\n", GetClassname() );
			vecAbsVelocity[i] = 0;
			bReset = true;
		}
		if ( IS_NAN(origin[i]) )
		{
			Msg( "Got a NaN origin on %s\n", GetClassname() );
			origin[i] = 0;
			bReset = true;
		}

		if ( vecAbsVelocity[i] > sv_maxvelocity.GetFloat() ) 
		{
#ifdef _DEBUG
			DevWarning( 2, "Got a velocity too high on %s\n", GetClassname() );
#endif
			vecAbsVelocity[i] = sv_maxvelocity.GetFloat();
			bReset = true;
		}
		else if ( vecAbsVelocity[i] < -sv_maxvelocity.GetFloat() )
		{
#ifdef _DEBUG
			DevWarning( 2, "Got a velocity too low on %s\n", GetClassname() );
#endif
			vecAbsVelocity[i] = -sv_maxvelocity.GetFloat();
			bReset = true;
		}
	}

	if (bReset)
	{
		SetAbsOrigin( origin );
		SetAbsVelocity( vecAbsVelocity );
	}
}


//-----------------------------------------------------------------------------
// Purpose: Applies gravity to falling objects
//-----------------------------------------------------------------------------
void CBaseEntity::PhysicsAddGravityMove( Vector &move )
{
	float	ent_gravity;

	if ( GetGravity() )
	{
		ent_gravity = GetGravity();
	}
	else
	{
		ent_gravity = 1.0;
	}

	Vector vecAbsVelocity = GetAbsVelocity();

	move.x = (vecAbsVelocity.x + GetBaseVelocity().x ) * gpGlobals->frametime;
	move.y = (vecAbsVelocity.y + GetBaseVelocity().y ) * gpGlobals->frametime;

	if ( GetFlags() & FL_ONGROUND )
	{
		move.z = GetBaseVelocity().z * gpGlobals->frametime;
		return;
	}

	// linear acceleration due to gravity
	float newZVelocity = vecAbsVelocity.z - ent_gravity * sv_gravity.GetFloat() * gpGlobals->frametime;

	move.z = ((vecAbsVelocity.z + newZVelocity) / 2.0 + GetBaseVelocity().z ) * gpGlobals->frametime;

	Vector vecBaseVelocity = GetBaseVelocity();
	vecBaseVelocity.z = 0.0f;
	SetBaseVelocity( vecBaseVelocity );
	
	vecAbsVelocity.z = newZVelocity;
	SetAbsVelocity( vecAbsVelocity );

	// Bound velocity
	PhysicsCheckVelocity();
}


#define	STOP_EPSILON	0.1
//-----------------------------------------------------------------------------
// Purpose: Slide off of the impacting object.  Returns the blocked flags (1 = floor, 2 = step / wall)
// Input  : in - 
//			normal - 
//			out - 
//			overbounce - 
// Output : int
//-----------------------------------------------------------------------------
int CBaseEntity::PhysicsClipVelocity( const Vector& in, const Vector& normal, Vector& out, float overbounce )
{
	float	backoff;
	float	change;
	float angle;
	int		i, blocked;
	
	blocked = 0;

	angle = normal[ 2 ];

	if ( angle > 0 )
	{
		blocked |= 1;		// floor
	}
	if ( !angle )
	{
		blocked |= 2;		// step
	}
	
	backoff = DotProduct (in, normal) * overbounce;

	for ( i=0 ; i<3 ; i++ )
	{
		change = normal[i]*backoff;
		out[i] = in[i] - change;
		if (out[i] > -STOP_EPSILON && out[i] < STOP_EPSILON)
		{
			out[i] = 0;
		}
	}
	
	return blocked;
}

//-----------------------------------------------------------------------------
// Purpose:
//-----------------------------------------------------------------------------
void CBaseEntity::ResolveFlyCollisionBounce( trace_t &trace, Vector &vecVelocity )
{
	// Get the impact surface's elasticity.
	float flSurfaceElasticity;
	physprops->GetPhysicsProperties( trace.surface.surfaceProps, NULL, NULL, NULL, &flSurfaceElasticity );
	
	float flTotalElasticity = GetElasticity() * flSurfaceElasticity;
	flTotalElasticity = clamp( flTotalElasticity, 0.0f, 0.9f );

	// NOTE: A backoff of 2.0f is a reflection
	Vector vecAbsVelocity;
	PhysicsClipVelocity( GetAbsVelocity(), trace.plane.normal, vecAbsVelocity, 2.0f );
	vecAbsVelocity *= flTotalElasticity;

	// Stop if on ground.
	if ( trace.plane.normal.z > 0.7 )			// Floor
	{
		// Get the total velocity (player + conveyors, etc.)
		VectorAdd( vecAbsVelocity, GetBaseVelocity(), vecVelocity );
		float flSpeedSqr = DotProduct( vecVelocity, vecVelocity );

		// Verify that we have an entity.
		CBaseEntity *pEntity = trace.m_pEnt;
		Assert( pEntity );

		// Are we on the ground?
		if ( vecVelocity.z < ( sv_gravity.GetFloat() * gpGlobals->frametime ) )
		{
			if ( pEntity->IsStandable() )
			{
				AddFlag( FL_ONGROUND );
				SetGroundEntity( pEntity );
			}

			vecAbsVelocity.z = 0.0f;
		}
		SetAbsVelocity( vecAbsVelocity );

		if ( flSpeedSqr < ( 30 * 30 ) )
		{
			if ( pEntity->IsStandable() )
			{
				AddFlag( FL_ONGROUND );
				SetGroundEntity( pEntity );
			}

			// Reset velocities.
			SetAbsVelocity( vec3_origin );
			SetLocalAngularVelocity( vec3_angle );
		}
		else
		{
			Vector vecDelta = GetBaseVelocity() - vecAbsVelocity;	
			Vector vecBaseDir = GetBaseVelocity();
			VectorNormalize( vecBaseDir );
			float flScale = vecDelta.Dot( vecBaseDir );

			VectorScale( vecAbsVelocity, ( 1.0f - trace.fraction ) * gpGlobals->frametime, vecVelocity ); 
			VectorMA( vecVelocity, ( 1.0f - trace.fraction ) * gpGlobals->frametime, GetBaseVelocity() * flScale, vecVelocity );
			trace = PhysicsPushEntity( vecVelocity );
		}
	}
	else
	{
		SetAbsVelocity( vecAbsVelocity );
	}
}

//-----------------------------------------------------------------------------
// Purpose:
//-----------------------------------------------------------------------------
void CBaseEntity::ResolveFlyCollisionSlide( trace_t &trace, Vector &vecVelocity )
{
	// Get the impact surface's friction.
	float flSurfaceFriction;
	physprops->GetPhysicsProperties( trace.surface.surfaceProps, NULL, NULL, &flSurfaceFriction, NULL );

	// A backoff of 1.0 is a slide.
	float flBackOff = 1.0f;	
	Vector vecAbsVelocity;
	PhysicsClipVelocity( GetAbsVelocity(), trace.plane.normal, vecAbsVelocity, flBackOff );

	// Stop if on ground.
	if ( trace.plane.normal.z > 0.7 )			// Floor
	{
		// Get the total velocity (player + conveyors, etc.)
		VectorAdd( vecAbsVelocity, GetBaseVelocity(), vecVelocity );
		float flSpeedSqr = DotProduct( vecVelocity, vecVelocity );

		// Verify that we have an entity.
		CBaseEntity *pEntity = trace.m_pEnt;
		Assert( pEntity );

		// Are we on the ground?
		if ( vecVelocity.z < ( sv_gravity.GetFloat() * gpGlobals->frametime ) )
		{
			if ( pEntity->IsStandable() )
			{
				AddFlag( FL_ONGROUND );
				SetGroundEntity( pEntity );
			}

			vecAbsVelocity.z = 0.0f;
		}
		SetAbsVelocity( vecAbsVelocity );

		if ( flSpeedSqr < ( 30 * 30 ) )
		{
			if ( pEntity->IsStandable() )
			{
				AddFlag( FL_ONGROUND );
				SetGroundEntity( pEntity );
			}

			// Reset velocities.
			SetAbsVelocity( vec3_origin );
			SetLocalAngularVelocity( vec3_angle );
		}
		else
		{
			VectorScale ( vecAbsVelocity, ( 1.0f - trace.fraction ) * gpGlobals->frametime * flSurfaceFriction, vecAbsVelocity );
			VectorMA( vecAbsVelocity, ( 1.0f - trace.fraction ) * gpGlobals->frametime * flSurfaceFriction, GetBaseVelocity(), vecVelocity );

			SetAbsVelocity( vecAbsVelocity );
			trace = PhysicsPushEntity( vecVelocity );
		}
	}
	else
	{
		SetAbsVelocity( vecAbsVelocity );
	}
}

//-----------------------------------------------------------------------------
// Purpose:
//-----------------------------------------------------------------------------
void CBaseEntity::ResolveFlyCollisionCustom( trace_t &trace, Vector &vecVelocity )
{
	// Stop if on ground.
	if ( trace.plane.normal.z > 0.7 )			// Floor
	{
		// Get the total velocity (player + conveyors, etc.)
		VectorAdd( GetAbsVelocity(), GetBaseVelocity(), vecVelocity );

		// Verify that we have an entity.
		CBaseEntity *pEntity = trace.m_pEnt;
		Assert( pEntity );

		// Are we on the ground?
		if ( vecVelocity.z < ( sv_gravity.GetFloat() * gpGlobals->frametime ) )
		{
			Vector vecAbsVelocity = GetAbsVelocity();
			vecAbsVelocity.z = 0.0f;
			SetAbsVelocity( vecAbsVelocity );
		}

		if ( pEntity->IsStandable() )
		{
			AddFlag( FL_ONGROUND );
			SetGroundEntity( pEntity );
		}
	}
}

//-----------------------------------------------------------------------------
// Performs the collision resolution for fliers.
//-----------------------------------------------------------------------------
void CBaseEntity::PerformFlyCollisionResolution( trace_t &trace, Vector &move )
{
	switch( GetMoveCollide() )
	{
	case MOVECOLLIDE_FLY_CUSTOM:
		{
			ResolveFlyCollisionCustom( trace, move );
			break;
		}

	case MOVECOLLIDE_FLY_BOUNCE:
		{
			ResolveFlyCollisionBounce( trace, move );
			break;
		}

	case MOVECOLLIDE_FLY_SLIDE:
	case MOVECOLLIDE_DEFAULT:
	// NOTE: The default fly collision state is the same as a slide (for backward capatability).
		{
			ResolveFlyCollisionSlide( trace, move );
			break;
		}

	default:
		{
			// Invalid MOVECOLLIDE_<type>
			Assert( 0 );
			break;
		}
	}
}

//-----------------------------------------------------------------------------
// Purpose: Checks if an object has passed into or out of water and sets water info, alters velocity, plays splash sounds, etc.
//-----------------------------------------------------------------------------
void CBaseEntity::PhysicsCheckWaterTransition( void )
{
	int oldcont = GetWaterType();
	UpdateWaterState();
	int cont = GetWaterType();

	// We can exit right out if we're a child... don't bother with this...
	if (GetMoveParent())
		return;

	if ( cont & MASK_WATER )
	{
		if (oldcont == CONTENTS_EMPTY)
		{	
			// just crossed into water
			EmitSound( "BaseEntity.EnterWater" );

			Vector vecAbsVelocity = GetAbsVelocity();
			vecAbsVelocity[2] *= 0.5;
			SetAbsVelocity( vecAbsVelocity );
		}
	}
	else
	{
		if ( oldcont != CONTENTS_EMPTY )
		{	
			// just crossed out of water
			EmitSound( "BaseEntity.ExitWater" );
		}		
	}
}

//-----------------------------------------------------------------------------
// Computes new angles based on the angular velocity
//-----------------------------------------------------------------------------
void CBaseEntity::SimulateAngles( float flFrameTime )
{
	// move angles
	QAngle angles;
	VectorMA ( GetLocalAngles(), flFrameTime, GetLocalAngularVelocity(), angles );
	SetLocalAngles( angles );
}


//-----------------------------------------------------------------------------
// Purpose: Toss, bounce, and fly movement.  When onground, do nothing.
//-----------------------------------------------------------------------------
void CBaseEntity::PhysicsToss( void )
{
	trace_t	trace;
	Vector	move;

	PhysicsCheckWater();

	// regular thinking
	if ( !PhysicsRunThink() )
		return;

	// Moving upward, off the ground, or  resting on a client/monster, remove FL_ONGROUND
	if ( GetAbsVelocity()[2] > 0 || !GetGroundEntity() || !GetGroundEntity()->IsStandable() )
	{
		RemoveFlag( FL_ONGROUND );
	}

	// Check to see if entity is on the ground at rest
	if ( GetFlags() & FL_ONGROUND )
	{
		if ( VectorCompare( GetAbsVelocity(), vec3_origin ) )
		{
			// Clear rotation if not moving (even if on a conveyor)
			SetLocalAngularVelocity( vec3_angle );
			if ( VectorCompare( GetBaseVelocity(), vec3_origin ) )
			{
				return;
			}
		}
	}

	PhysicsCheckVelocity();

	// add gravity
	if ( GetMoveType() == MOVETYPE_FLYGRAVITY && !(GetFlags() & FL_FLY) )
	{
		PhysicsAddGravityMove( move );
	}
	else
	{
		// Base velocity is not properly accounted for since this entity will move again after the bounce without
		// taking it into account
		Vector vecAbsVelocity = GetAbsVelocity();
		vecAbsVelocity += GetBaseVelocity();
		VectorScale(vecAbsVelocity, gpGlobals->frametime, move);
		PhysicsCheckVelocity( );
	}

	// move angles
	SimulateAngles( gpGlobals->frametime );

	// move origin
	trace = PhysicsPushEntity( move );

#if !defined( CLIENT_DLL )
	if ( VPhysicsGetObject() )
	{
		VPhysicsGetObject()->UpdateShadow( GetAbsOrigin(), vec3_angle, true, gpGlobals->frametime );
	}
#endif

	PhysicsCheckVelocity();

	if (trace.allsolid)
	{	
		// entity is trapped in another solid
		// UNDONE: does this entity needs to be removed?
		SetAbsVelocity(vec3_origin);
		SetLocalAngularVelocity(vec3_angle);
		return;
	}
	
#if !defined( CLIENT_DLL )
	if (IsEdictFree())
		return;
#endif

	if (trace.fraction != 1.0f)
	{
		PerformFlyCollisionResolution( trace, move );
	}
	
	// check for in water
	PhysicsCheckWaterTransition();
}


//-----------------------------------------------------------------------------
// Simulation in local space of rigid children
//-----------------------------------------------------------------------------
void CBaseEntity::PhysicsRigidChild( void )
{
	// NOTE: rigidly attached children do simulation in local space
	// Collision impulses will be handled either not at all, or by
	// forwarding the information to the highest move parent
	PhysicsCheckWater();

	// regular thinking
	if ( !PhysicsRunThink() )
		return;

	PhysicsCheckVelocity();

	if (GetLocalVelocity() != vec3_origin || GetLocalAngularVelocity() != vec3_angle )
	{
		// Angles move regardless; we don't have a good way of sweeping them.
		Vector vecOldAbsOrigin = GetAbsOrigin();
		QAngle angOldRotation =	GetLocalAngles();
		SimulateAngles( gpGlobals->frametime );

		// Figure out how far to sweep through local space
		Vector	vecMove;
		VectorMultiply( GetLocalVelocity(), gpGlobals->frametime, vecMove );
		
		// Try to push the entity though *world space* at see what it hits
		// based on the result, move only as far as possible
		trace_t	trace;
		Vector vecAbsMove;
		ComputeAbsDirection( vecMove, &vecAbsMove );
		PhysicsCheckSweep( vecOldAbsOrigin, vecAbsMove, &trace );

		// Move only as far as the sweep told us we could...
		if ((trace.startsolid) || (trace.allsolid))
		{
			// This could potentially happen in OBB case where we were free initially
			// but rotated into something due to local angular velocity
			SetLocalAngles( angOldRotation );
		}
		else
		{
			vecMove *= trace.fraction;
			Vector vecNewOrigin;
			VectorAdd( GetLocalOrigin(), vecMove, vecNewOrigin );
			SetLocalOrigin( vecNewOrigin );

#if !defined( CLIENT_DLL )
			// Passing in the previous abs origin here will cause the relinker
			// to test the swept ray from previous to current location for trigger intersections
			engine->RelinkEntity( pev, true, &vecOldAbsOrigin );
#else
			Relink();
#endif
		}

		if ( trace.m_pEnt )
		{
			PhysicsImpact( trace.m_pEnt, trace );
		}
	}

#if !defined( CLIENT_DLL )
	// We have to do this regardless owing to hierarchy
	if ( VPhysicsGetObject() )
	{
		VPhysicsGetObject()->UpdateShadow( GetAbsOrigin(), vec3_angle, true, gpGlobals->frametime );
	}
#endif

	PhysicsCheckVelocity();
	
#if !defined( CLIENT_DLL )
	if (IsEdictFree())
		return;
#endif

	// check for in water
	PhysicsCheckWaterTransition();
}


//-----------------------------------------------------------------------------
// Computes the base velocity
//-----------------------------------------------------------------------------
void CBaseEntity::UpdateBaseVelocity( void )
{
#if !defined( CLIENT_DLL )
	if ( GetFlags() & FL_ONGROUND )
	{
		CBaseEntity	*groundentity = GetGroundEntity();
		if ( groundentity )
		{
			// On conveyor belt that's moving?
			if ( groundentity->GetFlags() & FL_CONVEYOR )
			{
				Vector vecNewBaseVelocity;
				groundentity->GetGroundVelocityToApply( vecNewBaseVelocity );
				if ( GetFlags() & FL_BASEVELOCITY )
				{
					vecNewBaseVelocity += GetBaseVelocity();
				}
				AddFlag( FL_BASEVELOCITY );
				SetBaseVelocity( vecNewBaseVelocity );
			}
		}
	}
#endif
}


//-----------------------------------------------------------------------------
// Purpose: Runs a frame of physics for a specific edict (and all it's children)
// Input  : *ent - the thinking edict
//-----------------------------------------------------------------------------
void CBaseEntity::PhysicsSimulate( void )
{
	VPROF( "CBaseEntity::PhysicsSimulate" );
	// NOTE:  Players override PhysicsSimulate and drive through their CUserCmds at that point instead of
	//  processng through this function call!!!  They shouldn't chain to here ever.
	Assert( !IsPlayer() );
	if (IsPlayer())
	{
		return;
	}

	// Make sure not to simulate this guy twice per frame
	if (m_nSimulationTick == gpGlobals->tickcount)
		return;

	m_nSimulationTick = gpGlobals->tickcount;

	// If we've got a moveparent, we must simulate that first.
	CBaseEntity *pMoveParent = GetMoveParent();
	bool bHasMoveParent = pMoveParent != NULL;
	if (pMoveParent)
	{
		pMoveParent->PhysicsSimulate();
	}
	else
	{
		UpdateBaseVelocity();

		if ( ((GetFlags() & FL_BASEVELOCITY) == 0) && (GetBaseVelocity() != vec3_origin) )
		{
			// Apply momentum (add in half of the previous frame of velocity first)
			// BUGBUG: This will break with PhysicsStep() because of the timestep difference
			Vector vecAbsVelocity;
			VectorMA( GetAbsVelocity(), 1.0 + (gpGlobals->frametime*0.5), GetBaseVelocity(), vecAbsVelocity );
			SetAbsVelocity( vecAbsVelocity );
			SetBaseVelocity( vec3_origin );
		}
		RemoveFlag( FL_BASEVELOCITY );
	}

	switch( GetMoveType() )
	{
	case MOVETYPE_PUSH:
		PhysicsPusher();
		break;

	case MOVETYPE_VPHYSICS:
		PhysicsNone();
		break;

	case MOVETYPE_NONE:
		if (!bHasMoveParent)
			PhysicsNone();
		else
			PhysicsRigidChild();
		break;

	case MOVETYPE_NOCLIP:
		PhysicsNoclip();
		break;

	case MOVETYPE_STEP:
		PhysicsStep();
		break;

	case MOVETYPE_FLY:
	case MOVETYPE_FLYGRAVITY:
		PhysicsToss();
		break;

	case MOVETYPE_CUSTOM:
		PhysicsCustom();
		break;

	default:
		Warning( "PhysicsSimulate: %s bad movetype %d", GetClassname(), GetMoveType() );
		Assert(0);
		break;
	}
}

//-----------------------------------------------------------------------------
// Purpose: Runs thinking code if time.  There is some play in the exact time the think
//  function will be called, because it is called before any movement is done
//  in a frame.  Not used for pushmove objects, because they must be exact.
//  Returns false if the entity removed itself.
// Output : Returns true on success, false on failure.
//-----------------------------------------------------------------------------
bool CBaseEntity::PhysicsRunThink( thinkmethods_t thinkMethod )
{
	bool bAlive = true;

	// Don't fire the base if we're avoiding it
	if ( thinkMethod != THINK_FIRE_ALL_BUT_BASE )
	{
		bAlive = PhysicsRunSpecificThink( -1, &CBaseEntity::Think );
		if ( !bAlive )
			return false;
	}

	// Are we just firing the base think?
	if ( thinkMethod == THINK_FIRE_BASE_ONLY )
		return bAlive;

	// Fire the rest of 'em
	for ( int i = 0; i < m_aThinkFunctions.Count(); i++ )
	{
#ifdef _DEBUG
		// Set the context
		m_iCurrentThinkContext = i;
#endif

		bAlive = PhysicsRunSpecificThink( i, m_aThinkFunctions[i].m_pfnThink );

#ifdef _DEBUG
		// Clear our context
		m_iCurrentThinkContext = NO_THINK_CONTEXT;
#endif

		if ( !bAlive )
			return false;
	}
	
	return bAlive;
}

//-----------------------------------------------------------------------------
// Purpose: For testing if all thinks are occuring at the same time
//-----------------------------------------------------------------------------
struct ThinkSync
{
	float					thinktime;
	int						thinktick;
	CUtlVector< EHANDLE >	entities;

	ThinkSync()
	{
		thinktime = 0;
	}

	ThinkSync( const ThinkSync& src )
	{
		thinktime = src.thinktime;
		thinktick = src.thinktick;
		int c = src.entities.Count();
		for ( int i = 0; i < c; i++ )
		{
			entities.AddToTail( src.entities[ i ] );
		}
	}
};

#if !defined( CLIENT_DLL )
static ConVar sv_thinktimecheck( "sv_thinktimecheck", "0", 0, "Check for thinktimes all on same timestamp." );
#endif

//-----------------------------------------------------------------------------
// Purpose: For testing if all thinks are occuring at the same time
//-----------------------------------------------------------------------------
class CThinkSyncTester
{
public:
	CThinkSyncTester() :
	  m_Thinkers( 0, 0, ThinkLessFunc )
	{
		  m_nLastFrameCount = -1;
		  m_bShouldCheck = false;
	}

	void EntityThinking( int framecount, CBaseEntity *ent, float thinktime, int thinktick )
	{
#if !defined( CLIENT_DLL )
		if ( m_nLastFrameCount != framecount )
		{
			if ( m_bShouldCheck )
			{
				// Report
				Report();
				m_Thinkers.RemoveAll();
				m_nLastFrameCount = framecount;
			}

			m_bShouldCheck = sv_thinktimecheck.GetBool();
		}

		if ( !m_bShouldCheck )
			return;

		ThinkSync *p = FindOrAddItem( ent, thinktime );
		if ( !p )
		{
			Assert( 0 );
		}

		p->thinktime = thinktime;
		p->thinktick = thinktick;
		EHANDLE h;
		h = ent;
		p->entities.AddToTail( h );
#endif
	}

private:

	static bool ThinkLessFunc( const ThinkSync& item1, const ThinkSync& item2 )
	{
		return item1.thinktime < item2.thinktime;
	}

	ThinkSync	*FindOrAddItem( CBaseEntity *ent, float thinktime )
	{
		ThinkSync item;
		item.thinktime = thinktime;

		int idx = m_Thinkers.Find( item );
		if ( idx == m_Thinkers.InvalidIndex() )
		{
			idx = m_Thinkers.Insert( item );
		}
		
		return &m_Thinkers[ idx ];
	}

	void Report()
	{
		if ( m_Thinkers.Count() == 0 )
			return;

		Msg( "-----------------\nThink report frame %i\n", gpGlobals->tickcount );

		for ( int i = m_Thinkers.FirstInorder(); 
			i != m_Thinkers.InvalidIndex(); 
			i = m_Thinkers.NextInorder( i ) )
		{
			ThinkSync *p = &m_Thinkers[ i ];
			Assert( p );
			if ( !p )
				continue;

			int ecount = p->entities.Count();
			if ( !ecount )
			{
				continue;
			}

			Msg( "thinktime %f, %i entities\n", p->thinktime, ecount );
			for ( int j =0; j < ecount; j++ )
			{
				EHANDLE h = p->entities[ j ];
				int lastthinktick = 0;
				int nextthinktick = 0;
				CBaseEntity *e = h.Get();
				if ( e )
				{
					lastthinktick = e->m_nLastThinkTick;
					nextthinktick = e->m_nNextThinkTick;
				}

				Msg( "  %p : %30s (last %5i/next %5i)\n", h.Get(), h.Get() ? h->GetClassname() : "NULL",
					lastthinktick, nextthinktick );
			}
		}
	}

	CUtlRBTree< ThinkSync >	m_Thinkers;
	int			m_nLastFrameCount;
	bool		m_bShouldCheck;
};

static CThinkSyncTester g_ThinkChecker;

//-----------------------------------------------------------------------------
// Purpose: 
//-----------------------------------------------------------------------------
bool CBaseEntity::PhysicsRunSpecificThink( int nContextIndex, BASEPTR thinkFunc )
{
	int thinktick = GetNextThinkTick( nContextIndex );

	if ( thinktick <= 0 || thinktick > gpGlobals->tickcount )
		return true;
	
	float thinktime = thinktick * TICK_RATE;

	// Don't let things stay in the past.
	//  it is possible to start that way
	//  by a trigger with a local time.
	if ( thinktime < gpGlobals->curtime )
	{
		thinktime = gpGlobals->curtime;	
	}
	
	// Only do this on the game server
#if !defined( CLIENT_DLL )
	g_ThinkChecker.EntityThinking( gpGlobals->tickcount, this, thinktime, m_nNextThinkTick );
#endif

	SetNextThink( nContextIndex, TICK_NEVER_THINK );

	PhysicsDispatchThink( thinkFunc );

	SetLastThink( nContextIndex, gpGlobals->curtime );

	// Return whether entity is still valid
	return ( !IsMarkedForDeletion() );
}
