/*
   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.
   --------------------------------------------------------------
   The ACE Bot is a product of Steve Yeager, and is available from
   the ACE Bot homepage, at http://www.axionfx.com/ace.

   This program is a modification of the ACE Bot, and is therefore
   in NO WAY supported by Steve Yeager.
 */

#include "../g_local.h"
#include "ai_local.h"


//ACE



//===========================================================
//
//				NODES
//
//===========================================================



//==========================================
// AI_DropNodeOriginToFloor
//==========================================
qboolean AI_DropNodeOriginToFloor( vec3_t origin, edict_t *passent )
{
	trace_t	trace;

	G_Trace( &trace, origin, tv( playerbox_stand_mins[0], playerbox_stand_mins[1], 0 ), tv( playerbox_stand_maxs[0], playerbox_stand_maxs[1], 0 ), tv( origin[0], origin[1], world->r.mins[2] ), passent, MASK_NODESOLID ); //jalfixme. 0?
	//trace = gi.trace( origin, tv(-15, -15, 0), tv(15, 15, 0), tv(origin[0], origin[1], origin[2]-2048), passent, MASK_NODESOLID );
	if( trace.startsolid )
		return qfalse;

	origin[0] = trace.endpos[0];
	origin[1] = trace.endpos[1];
	origin[2] = trace.endpos[2] + 2 + abs( playerbox_stand_mins[2] );

	return qtrue;
}


//==========================================
// AI_FlagsForNode
// check the world and set up node flags
//==========================================
int AI_FlagsForNode( vec3_t origin, edict_t *passent )
{
	trace_t	trace;
	int flagsmask = 0;

	//water
	if( G_PointContents( origin ) & MASK_WATER )
		flagsmask |= NODEFLAGS_WATER;

	//floor
	G_Trace( &trace, origin, tv( -15, -15, 0 ), tv( 15, 15, 0 ), tv( origin[0], origin[1], origin[2] - AI_JUMPABLE_HEIGHT ), passent, MASK_NODESOLID );
	if( trace.fraction < 1.0 )
		flagsmask &= ~NODEFLAGS_FLOAT; //ok, it wasn't set, I know...
	else
		flagsmask |= NODEFLAGS_FLOAT;

	//ladder
	//	G_Trace( &trace, origin, tv(-18, -18, -16), tv(18, 18, 16), origin, passent, MASK_ALL );
	//	if( trace.startsolid && trace.contents & CONTENTS_LADDER )
	//		flagsmask |= NODEFLAGS_LADDER;

	return flagsmask;
}


//#define SHOW_JUMPAD_GUESS
#ifdef SHOW_JUMPAD_GUESS
//==========================================
// just a debug tool
//==========================================
static void AI_JumpadGuess_ShowPoint( vec3_t origin, char *modelname )
{
	edict_t	*ent;

	ent = G_Spawn();
	VectorCopy( origin, ent->s.origin );
	ent->movetype = MOVETYPE_NONE;
	ent->r.clipmask = MASK_WATER;
	ent->r.solid = SOLID_NOT;
	ent->s.type = ET_GENERIC;
	ent->s.renderfx |= RF_NOSHADOW;
	VectorClear( ent->r.mins );
	VectorClear( ent->r.maxs );
	ent->s.modelindex = trap_ModelIndex( modelname );
	ent->nextthink = level.time + 20000000;
	ent->think = G_FreeEdict;
	ent->classname = "checkent";
	ent->r.svflags &= ~SVF_NOCLIENT;

	GClip_LinkEntity( ent );
}
#endif

//==========================================
// AI_PredictJumpadDestity
// Make a guess on where a jumpad will send
// the player.
//==========================================
static qboolean AI_PredictJumpadDestity( edict_t *ent, vec3_t out )
{
	int i;
	edict_t *target;
	trace_t	trace;
	vec3_t pad_origin, v1, v2;
	float htime, vtime, tmpfloat, player_factor; //player movement guess
	vec3_t floor_target_origin, target_origin;
	vec3_t floor_dist_vec, floor_movedir;

	VectorClear( out );

	if( !ent->target )
		return qfalse;

	// get target entity
	target = G_Find( NULL, FOFS( targetname ), ent->target );
	if( !target )
		return qfalse;

	// find pad origin
	VectorCopy( ent->r.maxs, v1 );
	VectorCopy( ent->r.mins, v2 );
	pad_origin[0] = ( v1[0] - v2[0] ) / 2 + v2[0];
	pad_origin[1] = ( v1[1] - v2[1] ) / 2 + v2[1];
	pad_origin[2] = ent->r.maxs[2];

	//make a projection 'on floor' of target origin
	VectorCopy( target->s.origin, target_origin );
	VectorCopy( target->s.origin, floor_target_origin );
	floor_target_origin[2] = pad_origin[2]; //put at pad's height

	//make a guess on how player movement will affect the trajectory
	tmpfloat = DistanceFast( pad_origin, floor_target_origin );
	htime = sqrt( ( tmpfloat ) );
	vtime = sqrt( ( target->s.origin[2] - pad_origin[2] ) );
	if( !vtime ) return qfalse;
	htime *= 4; vtime *= 4;
	if( htime > vtime )
		htime = vtime;
	player_factor = vtime - htime;

	// find distance vector, on floor, from pad_origin to target origin.
	for( i = 0; i < 3; i++ )
		floor_dist_vec[i] = floor_target_origin[i] - pad_origin[i];

	// movement direction on floor
	VectorCopy( floor_dist_vec, floor_movedir );
	VectorNormalize( floor_movedir );

	// move both target origin and target origin on floor by player movement factor.
	VectorMA( target_origin, player_factor, floor_movedir, target_origin );
	VectorMA( floor_target_origin, player_factor, floor_movedir, floor_target_origin );

	// move target origin on floor by floor distance, and add another player factor step to it
	VectorMA( floor_target_origin, 1, floor_dist_vec, floor_target_origin );
	VectorMA( floor_target_origin, player_factor, floor_movedir, floor_target_origin );

#ifdef SHOW_JUMPAD_GUESS
	// this is our top of the curve point, and the original target
	AI_JumpadGuess_ShowPoint( target_origin, PATH_AMMO_BOX_MODEL );
	AI_JumpadGuess_ShowPoint( target->s.origin, PATH_AMMO_BOX_MODEL );
#endif

	//trace from target origin to endPoint.
	G_Trace( &trace, target_origin, tv( -15, -15, -8 ), tv( 15, 15, 8 ), floor_target_origin, NULL, MASK_NODESOLID );
	//trace = gi.trace(  target_origin, tv(-15, -15, -8), tv(15, 15, 8), floor_target_origin, NULL, MASK_NODESOLID);
	if( ( trace.fraction == 1.0 && trace.startsolid ) || ( trace.allsolid && trace.startsolid ) )
	{
		G_Printf( "JUMPAD LAND: ERROR: trace was in solid.\n" ); //started inside solid (target should never be inside solid, this is a mapper error)
		return qfalse;
	}
	else if( trace.fraction == 1.0 )
	{

		//didn't find solid. Extend Down (I have to improve this part)
		vec3_t target_origin2, extended_endpoint, extend_dist_vec;

		VectorCopy( floor_target_origin, target_origin2 );
		for( i = 0; i < 3; i++ )
			extend_dist_vec[i] = floor_target_origin[i] - target_origin[i];

		VectorMA( target_origin2, 1, extend_dist_vec, extended_endpoint );
		//repeat tracing
		G_Trace( &trace, target_origin2, tv( -15, -15, -8 ), tv( 15, 15, 8 ), extended_endpoint, NULL, MASK_NODESOLID );
		//trace = gi.trace(  target_origin2, tv(-15, -15, -8), tv(15, 15, 8), extended_endpoint, NULL, MASK_NODESOLID);
		if( trace.fraction == 1.0 )
			return qfalse; //still didn't find solid
	}

#ifdef SHOW_JUMPAD_GUESS
	// destiny found
	AI_JumpadGuess_ShowPoint( trace.endpos, PATH_AMMO_BOX_MODEL );
#endif

	VectorCopy( trace.endpos, out );
	return qtrue;
}


//==========================================
// AI_AddNode_JumpPad
// Drop two nodes, one at jump pad and other
// at predicted destity
//==========================================
static int AI_AddNode_JumpPad( edict_t *ent )
{
	vec3_t v1, v2;
	vec3_t out;

	if( nav.num_nodes + 1 > MAX_NODES )
		return INVALID;

	if( !AI_PredictJumpadDestity( ent, out ) )
		return INVALID;

	// jumpad node
	nodes[nav.num_nodes].flags = ( NODEFLAGS_JUMPPAD|NODEFLAGS_SERVERLINK|NODEFLAGS_REACHATTOUCH );

	// find the origin
	VectorCopy( ent->r.maxs, v1 );
	VectorCopy( ent->r.mins, v2 );
	nodes[nav.num_nodes].origin[0] = ( v1[0] - v2[0] ) / 2 + v2[0];
	nodes[nav.num_nodes].origin[1] = ( v1[1] - v2[1] ) / 2 + v2[1];
	nodes[nav.num_nodes].origin[2] = ent->r.maxs[2] + 16; //raise it up a bit

	nodes[nav.num_nodes].flags |= AI_FlagsForNode( nodes[nav.num_nodes].origin, NULL );

	nav.num_nodes++;

	// Destiny node
	nodes[nav.num_nodes].flags = ( NODEFLAGS_JUMPPAD_LAND|NODEFLAGS_SERVERLINK );
	nodes[nav.num_nodes].origin[0] = out[0];
	nodes[nav.num_nodes].origin[1] = out[1];
	nodes[nav.num_nodes].origin[2] = out[2]; //raise it up a bit
	AI_DropNodeOriginToFloor( nodes[nav.num_nodes].origin, NULL );

	nodes[nav.num_nodes].flags |= AI_FlagsForNode( nodes[nav.num_nodes].origin, NULL );

	// link jumpad to dest
	AI_AddLink( nav.num_nodes-1, nav.num_nodes, LINK_JUMPPAD );

	nav.num_nodes++;
	return nav.num_nodes -1;
}


//==========================================
// AI_AddNode_Door
// Drop a node at each side of the door
// and force them to link. Only typical
// doors are covered.
//==========================================
static int AI_AddNode_Door( edict_t *ent )
{
	edict_t	*other;
	vec3_t mins, maxs;
	vec3_t door_origin, movedir, moveangles;
	vec3_t moveaxis[3];
	vec3_t MOVEDIR_UP = { 0, 0, 1 };
	float nodeOffset = NODE_DENSITY * 0.75f;
	int i, j;
	int dropped[4];

	if( ent->flags & FL_TEAMSLAVE )
		return INVALID; // only team master will drop the nodes

	for( i = 0; i < 4; i++ )
		dropped[i] = INVALID;

	//make box formed by all team members boxes
	VectorCopy( ent->r.absmin, mins );
	VectorCopy( ent->r.absmax, maxs );

	for( other = ent->teamchain; other; other = other->teamchain )
	{
		AddPointToBounds( other->r.absmin, mins, maxs );
		AddPointToBounds( other->r.absmax, mins, maxs );
	}

	for( i = 0; i < 3; i++ )
		door_origin[i] = ( maxs[i] + mins[i] ) * 0.5;

	VectorSubtract( ent->moveinfo.end_origin, ent->moveinfo.start_origin, movedir );
	VectorNormalizeFast( movedir );
	VecToAngles( movedir, moveangles );

	AnglesToAxis( moveangles, moveaxis );

	//add nodes in "side" direction

	nodes[nav.num_nodes].flags = 0;
	VectorMA( door_origin, nodeOffset, moveaxis[1], nodes[nav.num_nodes].origin );
#ifdef SHOW_JUMPAD_GUESS
	AI_JumpadGuess_ShowPoint( nodes[nav.num_nodes].origin, PATH_AMMO_BOX_MODEL );
#endif
	if( AI_DropNodeOriginToFloor( nodes[nav.num_nodes].origin, NULL ) )
	{
		nodes[nav.num_nodes].flags |= AI_FlagsForNode( nodes[nav.num_nodes].origin, NULL );
		dropped[0] = nav.num_nodes;
		nav.num_nodes++;
	}

	nodes[nav.num_nodes].flags = 0;
	VectorMA( door_origin, -nodeOffset, moveaxis[1], nodes[nav.num_nodes].origin );
#ifdef SHOW_JUMPAD_GUESS
	AI_JumpadGuess_ShowPoint( nodes[nav.num_nodes].origin, PATH_AMMO_BOX_MODEL );
#endif
	if( AI_DropNodeOriginToFloor( nodes[nav.num_nodes].origin, NULL ) )
	{
		nodes[nav.num_nodes].flags |= AI_FlagsForNode( nodes[nav.num_nodes].origin, NULL );
		dropped[1] = nav.num_nodes;
		nav.num_nodes++;
	}

	// if moving in the Y axis drop also in the other crossing direction and hope the
	// bad ones are inhibited by a solid
	if( DotProduct( MOVEDIR_UP, moveaxis[0] ) > 0.8 || DotProduct( MOVEDIR_UP, moveaxis[0] ) < -0.8 )
	{
		nodes[nav.num_nodes].flags = 0;
		VectorMA( door_origin, nodeOffset, moveaxis[2], nodes[nav.num_nodes].origin );
#ifdef SHOW_JUMPAD_GUESS
		AI_JumpadGuess_ShowPoint( nodes[nav.num_nodes].origin, PATH_AMMO_BOX_MODEL );
#endif
		if( AI_DropNodeOriginToFloor( nodes[nav.num_nodes].origin, NULL ) )
		{
			nodes[nav.num_nodes].flags |= AI_FlagsForNode( nodes[nav.num_nodes].origin, NULL );
			dropped[2] = nav.num_nodes;
			nav.num_nodes++;
		}

		nodes[nav.num_nodes].flags = 0;
		VectorMA( door_origin, -nodeOffset, moveaxis[2], nodes[nav.num_nodes].origin );
#ifdef SHOW_JUMPAD_GUESS
		AI_JumpadGuess_ShowPoint( nodes[nav.num_nodes].origin, PATH_AMMO_BOX_MODEL );
#endif
		if( AI_DropNodeOriginToFloor( nodes[nav.num_nodes].origin, NULL ) )
		{
			nodes[nav.num_nodes].flags |= AI_FlagsForNode( nodes[nav.num_nodes].origin, NULL );
			dropped[3] = nav.num_nodes;
			nav.num_nodes++;
		}
	}

	// link those we dropped
	for( i = 0; i < 4; i++ )
	{
		if( dropped[i] == INVALID )
			continue;

		for( j = 0; j < 4; j++ )
		{
			if( dropped[j] == INVALID )
				continue;

			AI_AddLink( dropped[i], dropped[j], LINK_MOVE|LINK_DOOR );
		}
	}

	return nav.num_nodes-1;
}


//==========================================
// AI_AddNode_Platform_FindLowerLinkableCandidate
// helper to AI_AddNode_Platform -  //jabot092(2)
//==========================================
static int AI_AddNode_Platform_FindLowerLinkableCandidate( edict_t *ent )
{
	trace_t	trace;
	float plat_dist;
	float platlip;
	int numtries = 0, maxtries = 10;
	int candidate;
	vec3_t candidate_origin, virtualorigin;
	float mindist = 0;

	if( ent->flags & FL_TEAMSLAVE )
		return INVALID;

	plat_dist = ent->moveinfo.start_origin[2] - ent->moveinfo.end_origin[2];
	platlip = ( ent->r.maxs[2] - ent->r.mins[2] ) - plat_dist;

	//find a good candidate for lower
	candidate_origin[0] = ( ent->r.maxs[0] - ent->r.mins[0] ) / 2 + ent->r.mins[0];
	candidate_origin[1] = ( ent->r.maxs[1] - ent->r.mins[1] ) / 2 + ent->r.mins[1];
	candidate_origin[2] = ent->r.mins[2] + platlip;

	//try to find the closer reachable node to the bottom of the plat
	do
	{
		candidate = AI_FindClosestNode( candidate_origin, mindist, NODE_DENSITY*2, NODE_ALL );
		if( candidate != INVALID )
		{
			mindist = DistanceFast( candidate_origin, nodes[candidate].origin );

			//check to see if it would be valid
			if( fabs( candidate_origin[2] - nodes[candidate].origin[2] )
			   < ( fabs( platlip ) + AI_JUMPABLE_HEIGHT ) )
			{
				//put at linkable candidate height
				virtualorigin[0] = candidate_origin[0];
				virtualorigin[1] = candidate_origin[1];
				virtualorigin[2] = nodes[candidate].origin[2];

				G_Trace( &trace, virtualorigin, vec3_origin, vec3_origin, nodes[candidate].origin, ent, MASK_NODESOLID );
				//trace = gi.trace( virtualorigin, vec3_origin, vec3_origin, nodes[candidate].origin, ent, MASK_NODESOLID );
				if( trace.fraction == 1.0 && !trace.startsolid )
				{
#ifdef SHOW_JUMPAD_GUESS
					AI_JumpadGuess_ShowPoint( virtualorigin, "models/objects/grenade/tris.md2" );
#endif
					return candidate;
				}
			}
		}
	}
	while( candidate != INVALID && numtries++ < maxtries );

	return INVALID;
}

//==========================================
// AI_AddNode_Platform
// drop two nodes one at top, one at bottom
//==========================================
static int AI_AddNode_Platform( edict_t *ent )
{
	float plat_dist;
	float platlip;
	int candidate;
	vec3_t lorg;

	if( nav.num_nodes + 2 > MAX_NODES )
		return INVALID;

	if( ent->flags & FL_TEAMSLAVE )
		return INVALID; //only team master will drop the nodes

	plat_dist = ent->moveinfo.start_origin[2] - ent->moveinfo.end_origin[2];
	platlip = ( ent->r.maxs[2] - ent->r.mins[2] ) - plat_dist;

	//make a guess on lower plat position
	candidate = AI_AddNode_Platform_FindLowerLinkableCandidate( ent );
	if( candidate != INVALID )
	{                    //base lower on cadidate's height
		lorg[0] = ( ent->r.maxs[0] - ent->r.mins[0] ) / 2 + ent->r.mins[0];
		lorg[1] = ( ent->r.maxs[1] - ent->r.mins[1] ) / 2 + ent->r.mins[1];
		lorg[2] = nodes[candidate].origin[2];

	}
	else
	{
		lorg[0] = ( ent->r.maxs[0] - ent->r.mins[0] ) / 2 + ent->r.mins[0];
		lorg[1] = ( ent->r.maxs[1] - ent->r.mins[1] ) / 2 + ent->r.mins[1];
		lorg[2] = ent->r.mins[2] + platlip + 16;
	}

	// Upper node
	nodes[nav.num_nodes].flags = ( NODEFLAGS_PLATFORM|NODEFLAGS_SERVERLINK|NODEFLAGS_FLOAT );
	nodes[nav.num_nodes].origin[0] = lorg[0];
	nodes[nav.num_nodes].origin[1] = lorg[1];
	nodes[nav.num_nodes].origin[2] = lorg[2] + plat_dist;
#ifdef SHOW_JUMPAD_GUESS
	AI_JumpadGuess_ShowPoint( nodes[nav.num_nodes].origin, PATH_AMMO_BOX_MODEL );
#endif
	nodes[nav.num_nodes].flags |= AI_FlagsForNode( nodes[nav.num_nodes].origin, NULL );

	//put into ents table
	nav.ents[nav.num_ents].ent = ent;
	nav.ents[nav.num_ents].node = nav.num_nodes;
	nav.num_ents++;

	nav.num_nodes++;

	// Lower node
	nodes[nav.num_nodes].flags = ( NODEFLAGS_PLATFORM|NODEFLAGS_SERVERLINK|NODEFLAGS_FLOAT );
	nodes[nav.num_nodes].origin[0] = lorg[0];
	nodes[nav.num_nodes].origin[1] = lorg[1];
	nodes[nav.num_nodes].origin[2] = lorg[2] + 16;
#ifdef SHOW_JUMPAD_GUESS
	AI_JumpadGuess_ShowPoint( nodes[nav.num_nodes].origin, PATH_AMMO_BOX_MODEL );
#endif
	nodes[nav.num_nodes].flags |= AI_FlagsForNode( nodes[nav.num_nodes].origin, NULL );

	//put into ents table
	nav.ents[nav.num_ents].ent = ent;
	nav.ents[nav.num_ents].node = nav.num_nodes;
	nav.num_ents++;

	// link lower to upper
	AI_AddLink( nav.num_nodes, nav.num_nodes-1, LINK_PLATFORM );

	//next
	nav.num_nodes++;
	return nav.num_nodes-1;
}


//==========================================
// AI_AddNode_Teleporter
// Drop two nodes, one at trigger and other
// at target entity
//==========================================
static int AI_AddNode_Teleporter( edict_t *ent )
{
	vec3_t v1, v2;
	edict_t	*dest;

	if( nav.num_nodes + 1 > MAX_NODES )
		return INVALID;

	dest = G_Find( NULL, FOFS( targetname ), ent->target );
	if( !dest )
		return INVALID;

	//NODE_TELEPORTER_IN
	nodes[nav.num_nodes].flags = ( NODEFLAGS_TELEPORTER_IN|NODEFLAGS_SERVERLINK );

	if( !strcmp( ent->classname, "misc_teleporter" ) ) //jabot092(2)
	{
		nodes[nav.num_nodes].origin[0] = ent->s.origin[0];
		nodes[nav.num_nodes].origin[1] = ent->s.origin[1];
		nodes[nav.num_nodes].origin[2] = ent->s.origin[2]+16;

	}
	else
	{

		VectorCopy( ent->r.maxs, v1 );
		VectorCopy( ent->r.mins, v2 );
		nodes[nav.num_nodes].origin[0] = ( v1[0] - v2[0] ) / 2 + v2[0];
		nodes[nav.num_nodes].origin[1] = ( v1[1] - v2[1] ) / 2 + v2[1];
		nodes[nav.num_nodes].origin[2] = ent->r.mins[2]+32;
	}

	nodes[nav.num_nodes].flags |= AI_FlagsForNode( nodes[nav.num_nodes].origin, ent );
#ifdef SHOW_JUMPAD_GUESS
	AI_JumpadGuess_ShowPoint( nodes[nav.num_nodes].origin, PATH_AMMO_BOX_MODEL );
#endif
	nav.num_nodes++;

	//NODE_TELEPORTER_OUT
	nodes[nav.num_nodes].flags = ( NODEFLAGS_TELEPORTER_OUT|NODEFLAGS_SERVERLINK );
	VectorCopy( dest->s.origin, nodes[nav.num_nodes].origin );
	if( ent->spawnflags & 1 )  // droptofloor
		nodes[nav.num_nodes].flags |= NODEFLAGS_FLOAT;
	else
		AI_DropNodeOriginToFloor( nodes[nav.num_nodes].origin, NULL );

	nodes[nav.num_nodes].flags |= AI_FlagsForNode( nodes[nav.num_nodes].origin, ent );
#ifdef SHOW_JUMPAD_GUESS
	AI_JumpadGuess_ShowPoint( nodes[nav.num_nodes].origin, PATH_AMMO_BOX_MODEL );
#endif
	// link from teleport_in
	AI_AddLink( nav.num_nodes-1, nav.num_nodes, LINK_TELEPORT );

	nav.num_nodes++;
	return nav.num_nodes -1;
}


//==========================================
// AI_AddNode_BotRoam
// add nodes from bot roam entities
//==========================================
static int AI_AddNode_BotRoam( edict_t *ent )
{
	if( nav.num_nodes + 1 > MAX_NODES )
		return INVALID;

	nodes[nav.num_nodes].flags = NODEFLAGS_BOTROAM; //bot roams are not NODEFLAGS_NOWORLD

	// Set location
	VectorCopy( ent->s.origin, nodes[nav.num_nodes].origin );
	if( ent->spawnflags & 1 )  // floating items
		nodes[nav.num_nodes].flags |= NODEFLAGS_FLOAT;
	else
	if( !AI_DropNodeOriginToFloor( nodes[nav.num_nodes].origin, NULL ) )
		return INVALID; //spawned inside solid

	nodes[nav.num_nodes].flags |= AI_FlagsForNode( nodes[nav.num_nodes].origin, NULL );

	//count into bot_roams table
	nav.broams[nav.num_broams].node = nav.num_nodes;

	if( ent->count )
		nav.broams[nav.num_broams].weight = ent->count * 0.01f; //count is a int with a value in between 0 and 100
	else
		nav.broams[nav.num_broams].weight = 0.3f;

	nav.num_broams++;
	nav.num_nodes++;
	return nav.num_nodes-1; // return the node added
}


//==========================================
// AI_AddNode_ItemNode
// Used to add nodes from items
//==========================================
static int AI_AddNode_ItemNode( edict_t *ent )
{
	if( nav.num_nodes + 1 > MAX_NODES )
		return INVALID;

	VectorCopy( ent->s.origin, nodes[nav.num_nodes].origin );
	if( ent->spawnflags & 1 )  // floating items
		nodes[nav.num_nodes].flags |= NODEFLAGS_FLOAT;
	else
	if( !AI_DropNodeOriginToFloor( nodes[nav.num_nodes].origin, NULL ) )
		return INVALID; //spawned inside solid

	nodes[nav.num_nodes].flags |= AI_FlagsForNode( nodes[nav.num_nodes].origin, NULL );
	nodes[nav.num_nodes].flags |= NODEFLAGS_REACHATTOUCH;

	nav.num_nodes++;
	return nav.num_nodes-1; // return the node added
}


//==========================================
// AI_CreateNodesForEntities
//
// Entities aren't saved into nodes files anymore.
// They generate and link it's nodes at map load.
//==========================================
static void AI_CreateNodesForEntities( void )
{
	edict_t *ent;
	edict_t *botroams[MAX_EDICTS], *botitems[MAX_EDICTS];
	int i, node, numroams, numitems;

	nav.num_ents = 0;
	memset( nav.ents, 0, sizeof( nav_ents_t ) * MAX_EDICTS );

	numroams = 0;
	numitems = 0;

	// Add special entities
	for( ent = game.edicts; ent < &game.edicts[game.numentities]; ent++ )
	//for( ent = g_edicts; ent < &g_edicts[game.maxentities]; ent++ )
	{
		if( !ent->classname )
			continue;

		if( ent->item )
		{
			botitems[numitems++] = ent;
		}

		// platforms
		if( !Q_stricmp( ent->classname, "func_plat" ) )
		{
			AI_AddNode_Platform( ent );
		}
		// teleporters
		else if( !Q_stricmp( ent->classname, "trigger_teleport" ) || !Q_stricmp( ent->classname, "misc_teleporter" ) )
		{
			AI_AddNode_Teleporter( ent );
		}
		// jump pads
		else if( !Q_stricmp( ent->classname, "trigger_push" ) )
		{
			AI_AddNode_JumpPad( ent );
		}
		// doors
		else if( !Q_stricmp( ent->classname, "func_door" ) )
		{
			AI_AddNode_Door( ent );
		}
		else if( !Q_stricmp( ent->classname, "item_botroam" ) )
		{
			botroams[numroams++] = ent;
		}
	}

	// bot roams
	nav.num_broams = 0;
	memset( nav.broams, 0, sizeof( nav_broam_t ) * MAX_BOT_ROAMS );

	//visit world nodes first, and put in list what we find in there
	for( node = 0; node < nav.num_nodes; node++ )
	{
		if( nodes[node].flags & NODEFLAGS_BOTROAM && nav.num_broams < MAX_BOT_ROAMS )
		{
			nav.broams[nav.num_broams].node = node;
			nav.broams[nav.num_broams].weight = 0.3f;
			nav.num_broams++;
		}
	}

	//now add bot roams from entities
	for( i = 0; i < numroams; i++ )
	{
		ent = botroams[i];

		//if we have a available node close enough to the item, use it instead of dropping a new node
		node = AI_FindClosestReachableNode( ent->s.origin, NULL, 48, NODE_ALL );
		if( node != -1 &&
		   !( nodes[node].flags & NODEFLAGS_SERVERLINK ) &&
		   !( nodes[node].flags & NODEFLAGS_LADDER ) )
		{
			float heightdiff = 0;
			heightdiff = ent->s.origin[2] - nodes[node].origin[2];
			if( heightdiff < 0 ) heightdiff = -heightdiff;

			if( heightdiff < AI_STEPSIZE && nav.num_broams < MAX_BOT_ROAMS ) //near enough
			{
				nodes[node].flags |= NODEFLAGS_BOTROAM;
				//add node to botroam list
				if( ent->count )
					nav.broams[nav.num_broams].weight = ent->count * 0.01f; //count is a int with a value in between 0 and 100
				else
					nav.broams[nav.num_broams].weight = 0.3f; //jalfixme: add cmd to weight (dropped by console cmd, self is player)

				nav.broams[nav.num_broams].node = node;
				nav.num_broams++;
				continue;
			}
		}

		//drop a new node
		if( nav.num_broams < MAX_BOT_ROAMS )
		{
			AI_AddNode_BotRoam( ent );
		}
	}

	// game items (I want all them on top of the nodes array)
	nav.num_items = 0;
	memset( nav.items, 0, sizeof( nav_item_t ) * MAX_EDICTS );

	for( i = 0; i < numitems; i++ )
	{
		ent = botitems[i];

		//if we have a available node close enough to the item, use it
		node = AI_FindClosestReachableNode( ent->s.origin, NULL, 48, NODE_ALL );
		if( node != INVALID )
		{
			if( nodes[node].flags & NODEFLAGS_SERVERLINK ||
			    nodes[node].flags & NODEFLAGS_LADDER )
				node = INVALID;
			else
			{
				float heightdiff = 0;
				heightdiff = ent->s.origin[2] - nodes[node].origin[2];
				if( heightdiff < 0 ) heightdiff = -heightdiff;

				if( heightdiff > AI_STEPSIZE )  //not near enough
					node = INVALID;
			}
		}

		//drop a new node
		if( node == INVALID )
			node = AI_AddNode_ItemNode( ent );

		if( node != INVALID )
		{
			nav.items[nav.num_items].node = node;
			nav.items[nav.num_items].ent = ent;
			nav.items[nav.num_items].item = ent->item->tag;
			nav.num_items++;
		}
	}
}


//==========================================
// AI_LoadPLKFile
// load nodes and plinks from file
//==========================================
qboolean AI_LoadPLKFile( char *mapname )
{
	char filename[MAX_QPATH];
	int version;
	int length;
	int filenum;

	Q_snprintfz( filename, sizeof( filename ), "%s/%s.%s", NAV_FILE_FOLDER, mapname, NAV_FILE_EXTENSION );

	//Q_strlwr( filename );

	length = trap_FS_FOpenFile( filename, &filenum, FS_READ );
	if( length == -1 )
		return qfalse;

	trap_FS_Read( &version, sizeof( int ), filenum );
	if( version != NAV_FILE_VERSION )
	{
		trap_FS_FCloseFile( filenum );
		return qfalse;
	}

	trap_FS_Read( &nav.num_nodes, sizeof( int ), filenum );
	if( nav.num_nodes > MAX_NODES )
	{
		trap_FS_FCloseFile( filenum );
		G_Printf( "AI_LoadPLKFile: Too many nodes\n" );
		return qfalse;
	}

	//read nodes
	trap_FS_Read( nodes, sizeof( nav_node_t ) * nav.num_nodes, filenum );

	//read plinks
	trap_FS_Read( pLinks, sizeof( nav_plink_t ) * nav.num_nodes, filenum );

	trap_FS_FCloseFile( filenum );

	return qtrue;
}


//==========================================
// AI_IsPlatformLink
// interpretation of this link type
//==========================================
static int AI_IsPlatformLink( int n1, int n2 )
{
	int i;
	if( nodes[n1].flags & NODEFLAGS_PLATFORM && nodes[n2].flags & NODEFLAGS_PLATFORM )
	{
		//the link was added by it's dropping function or it's invalid
		return LINK_INVALID;
	}

	//if first is plat but not second
	if( nodes[n1].flags & NODEFLAGS_PLATFORM && !( nodes[n2].flags & NODEFLAGS_PLATFORM ) )
	{
		edict_t *n1ent = NULL;
		int othernode = -1;

		// find ent
		for( i = 0; i < nav.num_ents; i++ )
		{
			if( nav.ents[i].node == n1 )
				n1ent = nav.ents[i].ent;
		}
		// find the other node from that ent
		for( i = 0; i < nav.num_ents; i++ )
		{
			if( nav.ents[i].node != n1 && nav.ents[i].ent == n1ent )
				othernode = nav.ents[i].node;
		}

		if( othernode == -1 || !n1ent )
			return LINK_INVALID;

		//find out if n1 is the upper or the lower plat node
		if( nodes[n1].origin[2] < nodes[othernode].origin[2] )
		{
			//n1 is plat lower: it can't link TO anything but upper plat node
			return LINK_INVALID;

		}
		else
		{

			trace_t	trace;
			float heightdiff;
			//n1 is plat upper: it can link to visibles at same height
			G_Trace( &trace, nodes[n1].origin, vec3_origin, vec3_origin, nodes[n2].origin, n1ent, MASK_NODESOLID );
			if( trace.fraction == 1.0 && !trace.startsolid )
			{
				heightdiff = nodes[n1].origin[2] - nodes[n2].origin[2];
				if( heightdiff < 0 )
					heightdiff = -heightdiff;

				if( heightdiff < AI_JUMPABLE_HEIGHT )
					return LINK_MOVE;

				return LINK_INVALID;
			}
		}
	}

	//only second is plat node
	if( !( nodes[n1].flags & NODEFLAGS_PLATFORM ) && nodes[n2].flags & NODEFLAGS_PLATFORM )
	{
		edict_t *n2ent = NULL;
		int othernode = -1;

		// find ent
		for( i = 0; i < nav.num_ents; i++ )
		{
			if( nav.ents[i].node == n2 )
				n2ent = nav.ents[i].ent;
		}
		// find the other node from that ent
		for( i = 0; i < nav.num_ents; i++ )
		{
			if( nav.ents[i].node != n2 && nav.ents[i].ent == n2ent )
				othernode = nav.ents[i].node;
		}

		if( othernode == -1 || !n2ent )
			return LINK_INVALID;

		//find out if n2 is the upper or the lower plat node
		if( nodes[n2].origin[2] < nodes[othernode].origin[2] )
		{
			trace_t	trace;
			float heightdiff;

			//n2 is plat lower: other's can link to it when visible and good height
			G_Trace( &trace, nodes[n1].origin, vec3_origin, vec3_origin, nodes[n2].origin, n2ent, MASK_NODESOLID );
			if( trace.fraction == 1.0 && !trace.startsolid )
			{
				heightdiff = nodes[n1].origin[2] - nodes[n2].origin[2];
				if( heightdiff < 0 )
					heightdiff = -heightdiff;

				if( heightdiff < AI_JUMPABLE_HEIGHT )
					return LINK_MOVE;

				return LINK_INVALID;
			}

		}
		else
		{

			//n2 is plat upper: others can't link to plat upper nodes
			return LINK_INVALID;
		}
	}

	return LINK_INVALID;
}

//==========================================
// AI_IsJumpPadLink
// interpretation of this link type
//==========================================
static int AI_IsJumpPadLink( int n1, int n2 )
{
	if( nodes[n1].flags & NODEFLAGS_JUMPPAD )
		return LINK_INVALID; //only can link TO jumppad land, and it's linked elsewhere

	if( nodes[n2].flags & NODEFLAGS_JUMPPAD_LAND )
		return LINK_INVALID; //linked as TO only from it's jumppad. Handled elsewhere

	return AI_GravityBoxToLink( n1, n2 );
}

//==========================================
// AI_IsTeleporterLink
// interpretation of this link type
//==========================================
static int AI_IsTeleporterLink( int n1, int n2 )
{
	if( nodes[n1].flags & NODEFLAGS_TELEPORTER_IN )
		return LINK_INVALID;

	if( nodes[n2].flags & NODEFLAGS_TELEPORTER_OUT )
		return LINK_INVALID;

	//find out the link move type against the world
	return AI_GravityBoxToLink( n1, n2 );
}

//==========================================
// AI_FindServerLinkType
// determine what type of link it is
//==========================================
static int AI_FindServerLinkType( int n1, int n2 )
{
	if( AI_PlinkExists( n1, n2 ) )
		return LINK_INVALID; //already saved

	if( nodes[n1].flags & NODEFLAGS_PLATFORM || nodes[n2].flags & NODEFLAGS_PLATFORM )
	{
		return AI_IsPlatformLink( n1, n2 );
	}
	else if( nodes[n2].flags & NODEFLAGS_TELEPORTER_IN || nodes[n1].flags & NODEFLAGS_TELEPORTER_OUT )
	{
		return AI_IsTeleporterLink( n1, n2 );
	}
	else if( nodes[n2].flags & NODEFLAGS_JUMPPAD || nodes[n1].flags & NODEFLAGS_JUMPPAD_LAND )
	{
		return AI_IsJumpPadLink( n1, n2 );
	}
	return LINK_INVALID;
}

//==========================================
// AI_LinkServerNodes
// link the new nodes to&from those loaded from disk
//==========================================
static int AI_LinkServerNodes( int start )
{
	int n1, n2;
	int count = 0;
	float pLinkRadius = NODE_DENSITY*1.2f;
	qboolean ignoreHeight = qtrue;

	if( start >= nav.num_nodes )
		return 0;

	for( n1 = start; n1 < nav.num_nodes; n1++ )
	{
		n2 = 0;
		n2 = AI_findNodeInRadius( 0, nodes[n1].origin, pLinkRadius, ignoreHeight );

		while( n2 != -1 )
		{
			if( nodes[n1].flags & NODEFLAGS_SERVERLINK || nodes[n2].flags & NODEFLAGS_SERVERLINK )
			{
				if( AI_AddLink( n1, n2, AI_FindServerLinkType( n1, n2 ) ) )
					count++;

				if( AI_AddLink( n2, n1, AI_FindServerLinkType( n2, n1 ) ) )
					count++;
			}
			else
			{
				if( AI_AddLink( n1, n2, AI_FindLinkType( n1, n2 ) ) )
					count++;

				if( AI_AddLink( n2, n1, AI_FindLinkType( n2, n1 ) ) )
					count++;
			}

			n2 = AI_findNodeInRadius( n2, nodes[n1].origin, pLinkRadius, ignoreHeight );
		}
	}
	return count;
}

//==========================================
// AI_CreateBotRoams
// subdivide the world bounds in boxes, find the nodes in those
// boxes and set the closest one to the center as botroam if
// no botroam was found in the box.
//==========================================
void AI_CreateBotRoams( void )
{
	//todo
}

//==========================================
// AI_InitNavigationData
// Setup nodes & links for this map
//==========================================
void AI_InitNavigationData( void )
{
	int i;
	int newlinks;
	int newjumplinks;
	int linkscount;
	int servernodesstart = 0;

	nav.editmode = qfalse;

	//Init nodes arrays
	nav.num_nodes = 0;
	memset( nodes, 0, sizeof( nav_node_t ) * MAX_NODES );
	memset( pLinks, 0, sizeof( nav_plink_t ) * MAX_NODES );

	G_Printf( "-------------------------------------\n" );
	G_Printf( "       : AI version: %s\n", AI_VERSION_STRING );

	//Load nodes from file
	nav.loaded = AI_LoadPLKFile( level.mapname );
	if( !nav.loaded )
	{
		G_Printf( "       :  FAILED to load nodes file.\n" );
		return;
	}

	servernodesstart = nav.num_nodes;

	for( linkscount = 0, i = 0; i < nav.num_nodes; i++ )
		linkscount += pLinks[i].numLinks;

	//create nodes for map entities
	AI_CreateNodesForEntities();
	newlinks = AI_LinkServerNodes( servernodesstart );
	newjumplinks = AI_LinkCloseNodes_JumpPass( servernodesstart );
	AI_CreateBotRoams();

	G_Printf( "       : \n" );
	G_Printf( "       : loaded nodes:%i.\n", servernodesstart );
	G_Printf( "       : added nodes:%i.\n", nav.num_nodes - servernodesstart );
	G_Printf( "       : total nodes:%i.\n", nav.num_nodes );
	G_Printf( "       : loaded links:%i.\n", linkscount );
	G_Printf( "       : added links:%i.\n", newlinks );
	G_Printf( "       : added jump links:%i.\n", newjumplinks );
	G_Printf( "       : Nodes Initialized.\n" );

	return;
}
