be_aas_reach.c

quakeIII源码这个不用我多说吧

/*
===========================================================================
Copyright (C) 1999-2005 Id Software, Inc.

This file is part of Quake III Arena source code.

Quake III Arena source code 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.

Quake III Arena source code 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 Foobar; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
===========================================================================
*/

/*****************************************************************************
 * name:		be_aas_reach.c
 *
 * desc:		reachability calculations
 *
 * $Archive: /MissionPack/code/botlib/be_aas_reach.c $
 *
 *****************************************************************************/

#include "../game/q_shared.h"
#include "l_log.h"
#include "l_memory.h"
#include "l_script.h"
#include "l_libvar.h"
#include "l_precomp.h"
#include "l_struct.h"
#include "aasfile.h"
#include "../game/botlib.h"
#include "../game/be_aas.h"
#include "be_aas_funcs.h"
#include "be_aas_def.h"

extern int Sys_MilliSeconds(void);


extern botlib_import_t botimport;

//#define REACH_DEBUG

//NOTE: all travel times are in hundreth of a second
//maximum number of reachability links
#define AAS_MAX_REACHABILITYSIZE			65536
//number of areas reachability is calculated for each frame
#define REACHABILITYAREASPERCYCLE			15
//number of units reachability points are placed inside the areas
#define INSIDEUNITS							2
#define INSIDEUNITS_WALKEND					5
#define INSIDEUNITS_WALKSTART				0.1
#define INSIDEUNITS_WATERJUMP				15
//area flag used for weapon jumping
#define AREA_WEAPONJUMP						8192	//valid area to weapon jump to
//number of reachabilities of each type
int reach_swim;			//swim
int reach_equalfloor;	//walk on floors with equal height
int reach_step;			//step up
int reach_walk;			//walk of step
int reach_barrier;		//jump up to a barrier
int reach_waterjump;	//jump out of water
int reach_walkoffledge;	//walk of a ledge
int reach_jump;			//jump
int reach_ladder;		//climb or descent a ladder
int reach_teleport;		//teleport
int reach_elevator;		//use an elevator
int reach_funcbob;		//use a func bob
int reach_grapple;		//grapple hook
int reach_doublejump;	//double jump
int reach_rampjump;		//ramp jump
int reach_strafejump;	//strafe jump (just normal jump but further)
int reach_rocketjump;	//rocket jump
int reach_bfgjump;		//bfg jump
int reach_jumppad;		//jump pads
//if true grapple reachabilities are skipped
int calcgrapplereach;
//linked reachability
typedef struct aas_lreachability_s
{
	int areanum;					//number of the reachable area
	int facenum;					//number of the face towards the other area
	int edgenum;					//number of the edge towards the other area
	vec3_t start;					//start point of inter area movement
	vec3_t end;						//end point of inter area movement
	int traveltype;					//type of travel required to get to the area
	unsigned short int traveltime;	//travel time of the inter area movement
	//
	struct aas_lreachability_s *next;
} aas_lreachability_t;
//temporary reachabilities
aas_lreachability_t *reachabilityheap;	//heap with reachabilities
aas_lreachability_t *nextreachability;	//next free reachability from the heap
aas_lreachability_t **areareachability;	//reachability links for every area
int numlreachabilities;

//===========================================================================
// returns the surface area of the given face
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
float AAS_FaceArea(aas_face_t *face)
{
	int i, edgenum, side;
	float total;
	vec_t *v;
	vec3_t d1, d2, cross;
	aas_edge_t *edge;

	edgenum = aasworld.edgeindex[face->firstedge];
	side = edgenum < 0;
	edge = &aasworld.edges[abs(edgenum)];
	v = aasworld.vertexes[edge->v[side]];

	total = 0;
	for (i = 1; i < face->numedges - 1; i++)
	{
		edgenum = aasworld.edgeindex[face->firstedge + i];
		side = edgenum < 0;
		edge = &aasworld.edges[abs(edgenum)];
		VectorSubtract(aasworld.vertexes[edge->v[side]], v, d1);
		VectorSubtract(aasworld.vertexes[edge->v[!side]], v, d2);
		CrossProduct(d1, d2, cross);
		total += 0.5 * VectorLength(cross);
	} //end for
	return total;
} //end of the function AAS_FaceArea
//===========================================================================
// returns the volume of an area
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
float AAS_AreaVolume(int areanum)
{
	int i, edgenum, facenum, side;
	vec_t d, a, volume;
	vec3_t corner;
	aas_plane_t *plane;
	aas_edge_t *edge;
	aas_face_t *face;
	aas_area_t *area;

	area = &aasworld.areas[areanum];
	facenum = aasworld.faceindex[area->firstface];
	face = &aasworld.faces[abs(facenum)];
	edgenum = aasworld.edgeindex[face->firstedge];
	edge = &aasworld.edges[abs(edgenum)];
	//
	VectorCopy(aasworld.vertexes[edge->v[0]], corner);

	//make tetrahedrons to all other faces
	volume = 0;
	for (i = 0; i < area->numfaces; i++)
	{
		facenum = abs(aasworld.faceindex[area->firstface + i]);
		face = &aasworld.faces[facenum];
		side = face->backarea != areanum;
		plane = &aasworld.planes[face->planenum ^ side];
		d = -(DotProduct (corner, plane->normal) - plane->dist);
		a = AAS_FaceArea(face);
		volume += d * a;
	} //end for

	volume /= 3;
	return volume;
} //end of the function AAS_AreaVolume
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_BestReachableLinkArea(aas_link_t *areas)
{
	aas_link_t *link;

	for (link = areas; link; link = link->next_area)
	{
		if (AAS_AreaGrounded(link->areanum) || AAS_AreaSwim(link->areanum))
		{
			return link->areanum;
		} //end if
	} //end for
	//
	for (link = areas; link; link = link->next_area)
	{
		if (link->areanum) return link->areanum;
		//FIXME: this is a bad idea when the reachability is not yet
		// calculated when the level items are loaded
		if (AAS_AreaReachability(link->areanum))
			return link->areanum;
	} //end for
	return 0;
} //end of the function AAS_BestReachableLinkArea
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
int AAS_GetJumpPadInfo(int ent, vec3_t areastart, vec3_t absmins, vec3_t absmaxs, vec3_t velocity)
{
	int modelnum, ent2;
	float speed, height, gravity, time, dist, forward;
	vec3_t origin, angles, teststart, ent2origin;
	aas_trace_t trace;
	char model[MAX_EPAIRKEY];
	char target[MAX_EPAIRKEY], targetname[MAX_EPAIRKEY];

	//
	AAS_FloatForBSPEpairKey(ent, "speed", &speed);
	if (!speed) speed = 1000;
	VectorClear(angles);
	//get the mins, maxs and origin of the model
	AAS_ValueForBSPEpairKey(ent, "model", model, MAX_EPAIRKEY);
	if (model[0]) modelnum = atoi(model+1);
	else modelnum = 0;
	AAS_BSPModelMinsMaxsOrigin(modelnum, angles, absmins, absmaxs, origin);
	VectorAdd(origin, absmins, absmins);
	VectorAdd(origin, absmaxs, absmaxs);
	VectorAdd(absmins, absmaxs, origin);
	VectorScale (origin, 0.5, origin);

	//get the start areas
	VectorCopy(origin, teststart);
	teststart[2] += 64;
	trace = AAS_TraceClientBBox(teststart, origin, PRESENCE_CROUCH, -1);
	if (trace.startsolid)
	{
		botimport.Print(PRT_MESSAGE, "trigger_push start solid\n");
		VectorCopy(origin, areastart);
	} //end if
	else
	{
		VectorCopy(trace.endpos, areastart);
	} //end else
	areastart[2] += 0.125;
	//
	//AAS_DrawPermanentCross(origin, 4, 4);
	//get the target entity
	AAS_ValueForBSPEpairKey(ent, "target", target, MAX_EPAIRKEY);
	for (ent2 = AAS_NextBSPEntity(0); ent2; ent2 = AAS_NextBSPEntity(ent2))
	{
		if (!AAS_ValueForBSPEpairKey(ent2, "targetname", targetname, MAX_EPAIRKEY)) continue;
		if (!strcmp(targetname, target)) break;
	} //end for
	if (!ent2)
	{
		botimport.Print(PRT_MESSAGE, "trigger_push without target entity %s\n", target);
		return qfalse;
	} //end if
	AAS_VectorForBSPEpairKey(ent2, "origin", ent2origin);
	//
	height = ent2origin[2] - origin[2];
	gravity = aassettings.phys_gravity;
	time = sqrt( height / ( 0.5 * gravity ) );
	if (!time)
	{
		botimport.Print(PRT_MESSAGE, "trigger_push without time\n");
		return qfalse;
	} //end if
	// set s.origin2 to the push velocity
	VectorSubtract ( ent2origin, origin, velocity);
	dist = VectorNormalize( velocity);
	forward = dist / time;
	//FIXME: why multiply by 1.1
	forward *= 1.1f;
	VectorScale(velocity, forward, velocity);
	velocity[2] = time * gravity;
	return qtrue;
} //end of the function AAS_GetJumpPadInfo
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
int AAS_BestReachableFromJumpPadArea(vec3_t origin, vec3_t mins, vec3_t maxs)
{
	int area2num, ent, bot_visualizejumppads, bestareanum;
	float volume, bestareavolume;
	vec3_t areastart, cmdmove, bboxmins, bboxmaxs;
	vec3_t absmins, absmaxs, velocity;
	aas_clientmove_t move;
	aas_link_t *areas, *link;
	char classname[MAX_EPAIRKEY];

#ifdef BSPC
	bot_visualizejumppads = 0;
#else
	bot_visualizejumppads = LibVarValue("bot_visualizejumppads", "0");
#endif
	VectorAdd(origin, mins, bboxmins);
	VectorAdd(origin, maxs, bboxmaxs);
	for (ent = AAS_NextBSPEntity(0); ent; ent = AAS_NextBSPEntity(ent))
	{
		if (!AAS_ValueForBSPEpairKey(ent, "classname", classname, MAX_EPAIRKEY)) continue;
		if (strcmp(classname, "trigger_push")) continue;
		//
		if (!AAS_GetJumpPadInfo(ent, areastart, absmins, absmaxs, velocity)) continue;
		//get the areas the jump pad brush is in
		areas = AAS_LinkEntityClientBBox(absmins, absmaxs, -1, PRESENCE_CROUCH);
		for (link = areas; link; link = link->next_area)
		{
			if (AAS_AreaJumpPad(link->areanum)) break;
		} //end for
		if (!link)
		{
			botimport.Print(PRT_MESSAGE, "trigger_push not in any jump pad area\n");
			AAS_UnlinkFromAreas(areas);
			continue;
		} //end if
		//
		//botimport.Print(PRT_MESSAGE, "found a trigger_push with velocity %f %f %f\n", velocity[0], velocity[1], velocity[2]);
		//
		VectorSet(cmdmove, 0, 0, 0);
		Com_Memset(&move, 0, sizeof(aas_clientmove_t));
		area2num = 0;
		AAS_ClientMovementHitBBox(&move, -1, areastart, PRESENCE_NORMAL, qfalse,
								velocity, cmdmove, 0, 30, 0.1f, bboxmins, bboxmaxs, bot_visualizejumppads);
		if (move.frames < 30)
		{
			bestareanum = 0;
			bestareavolume = 0;
			for (link = areas; link; link = link->next_area)
			{
				if (!AAS_AreaJumpPad(link->areanum)) continue;
				volume = AAS_AreaVolume(link->areanum);
				if (volume >= bestareavolume)
				{
					bestareanum = link->areanum;
					bestareavolume = volume;
				} //end if
			} //end if
			AAS_UnlinkFromAreas(areas);
			return bestareanum;
		} //end if
		AAS_UnlinkFromAreas(areas);
	} //end for
	return 0;
} //end of the function AAS_BestReachableFromJumpPadArea
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_BestReachableArea(vec3_t origin, vec3_t mins, vec3_t maxs, vec3_t goalorigin)
{
	int areanum, i, j, k, l;
	aas_link_t *areas;
	vec3_t absmins, absmaxs;
	//vec3_t bbmins, bbmaxs;
	vec3_t start, end;
	aas_trace_t trace;

	if (!aasworld.loaded)
	{
		botimport.Print(PRT_ERROR, "AAS_BestReachableArea: aas not loaded\n");
		return 0;
	} //end if
	//find a point in an area
	VectorCopy(origin, start);
	areanum = AAS_PointAreaNum(start);
	//while no area found fudge around a little
	for (i = 0; i < 5 && !areanum; i++)
	{
		for (j = 0; j < 5 && !areanum; j++)
		{
			for (k = -1; k <= 1 && !areanum; k++)
			{
				for (l = -1; l <= 1 && !areanum; l++)
				{