be_aas_sample.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_sample.c
 *
 * desc:		AAS environment sampling
 *
 * $Archive: /MissionPack/code/botlib/be_aas_sample.c $
 *
 *****************************************************************************/

#include "../game/q_shared.h"
#include "l_memory.h"
#include "l_script.h"
#include "l_precomp.h"
#include "l_struct.h"
#ifndef BSPC
#include "l_libvar.h"
#endif
#include "aasfile.h"
#include "../game/botlib.h"
#include "../game/be_aas.h"
#include "be_interface.h"
#include "be_aas_funcs.h"
#include "be_aas_def.h"

extern botlib_import_t botimport;

//#define AAS_SAMPLE_DEBUG

#define BBOX_NORMAL_EPSILON		0.001

#define ON_EPSILON					0 //0.0005

#define TRACEPLANE_EPSILON			0.125

typedef struct aas_tracestack_s
{
	vec3_t start;		//start point of the piece of line to trace
	vec3_t end;			//end point of the piece of line to trace
	int planenum;		//last plane used as splitter
	int nodenum;		//node found after splitting with planenum
} aas_tracestack_t;

int numaaslinks;

//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_PresenceTypeBoundingBox(int presencetype, vec3_t mins, vec3_t maxs)
{
	int index;
	//bounding box size for each presence type
	vec3_t boxmins[3] = {{0, 0, 0}, {-15, -15, -24}, {-15, -15, -24}};
	vec3_t boxmaxs[3] = {{0, 0, 0}, { 15,  15,  32}, { 15,  15,   8}};

	if (presencetype == PRESENCE_NORMAL) index = 1;
	else if (presencetype == PRESENCE_CROUCH) index = 2;
	else
	{
		botimport.Print(PRT_FATAL, "AAS_PresenceTypeBoundingBox: unknown presence type\n");
		index = 2;
	} //end if
	VectorCopy(boxmins[index], mins);
	VectorCopy(boxmaxs[index], maxs);
} //end of the function AAS_PresenceTypeBoundingBox
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_InitAASLinkHeap(void)
{
	int i, max_aaslinks;

	max_aaslinks = aasworld.linkheapsize;
	//if there's no link heap present
	if (!aasworld.linkheap)
	{
#ifdef BSPC
		max_aaslinks = 6144;
#else
		max_aaslinks = (int) LibVarValue("max_aaslinks", "6144");
#endif
		if (max_aaslinks < 0) max_aaslinks = 0;
		aasworld.linkheapsize = max_aaslinks;
		aasworld.linkheap = (aas_link_t *) GetHunkMemory(max_aaslinks * sizeof(aas_link_t));
	} //end if
	//link the links on the heap
	aasworld.linkheap[0].prev_ent = NULL;
	aasworld.linkheap[0].next_ent = &aasworld.linkheap[1];
	for (i = 1; i < max_aaslinks-1; i++)
	{
		aasworld.linkheap[i].prev_ent = &aasworld.linkheap[i - 1];
		aasworld.linkheap[i].next_ent = &aasworld.linkheap[i + 1];
	} //end for
	aasworld.linkheap[max_aaslinks-1].prev_ent = &aasworld.linkheap[max_aaslinks-2];
	aasworld.linkheap[max_aaslinks-1].next_ent = NULL;
	//pointer to the first free link
	aasworld.freelinks = &aasworld.linkheap[0];
	//
	numaaslinks = max_aaslinks;
} //end of the function AAS_InitAASLinkHeap
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_FreeAASLinkHeap(void)
{
	if (aasworld.linkheap) FreeMemory(aasworld.linkheap);
	aasworld.linkheap = NULL;
	aasworld.linkheapsize = 0;
} //end of the function AAS_FreeAASLinkHeap
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
aas_link_t *AAS_AllocAASLink(void)
{
	aas_link_t *link;

	link = aasworld.freelinks;
	if (!link)
	{
#ifndef BSPC
		if (bot_developer)
#endif
		{
			botimport.Print(PRT_FATAL, "empty aas link heap\n");
		} //end if
		return NULL;
	} //end if
	if (aasworld.freelinks) aasworld.freelinks = aasworld.freelinks->next_ent;
	if (aasworld.freelinks) aasworld.freelinks->prev_ent = NULL;
	numaaslinks--;
	return link;
} //end of the function AAS_AllocAASLink
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_DeAllocAASLink(aas_link_t *link)
{
	if (aasworld.freelinks) aasworld.freelinks->prev_ent = link;
	link->prev_ent = NULL;
	link->next_ent = aasworld.freelinks;
	link->prev_area = NULL;
	link->next_area = NULL;
	aasworld.freelinks = link;
	numaaslinks++;
} //end of the function AAS_DeAllocAASLink
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_InitAASLinkedEntities(void)
{
	if (!aasworld.loaded) return;
	if (aasworld.arealinkedentities) FreeMemory(aasworld.arealinkedentities);
	aasworld.arealinkedentities = (aas_link_t **) GetClearedHunkMemory(
						aasworld.numareas * sizeof(aas_link_t *));
} //end of the function AAS_InitAASLinkedEntities
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_FreeAASLinkedEntities(void)
{
	if (aasworld.arealinkedentities) FreeMemory(aasworld.arealinkedentities);
	aasworld.arealinkedentities = NULL;
} //end of the function AAS_InitAASLinkedEntities
//===========================================================================
// returns the AAS area the point is in
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_PointAreaNum(vec3_t point)
{
	int nodenum;
	vec_t	dist;
	aas_node_t *node;
	aas_plane_t *plane;

	if (!aasworld.loaded)
	{
		botimport.Print(PRT_ERROR, "AAS_PointAreaNum: aas not loaded\n");
		return 0;
	} //end if

	//start with node 1 because node zero is a dummy used for solid leafs
	nodenum = 1;
	while (nodenum > 0)
	{
//		botimport.Print(PRT_MESSAGE, "[%d]", nodenum);
#ifdef AAS_SAMPLE_DEBUG
		if (nodenum >= aasworld.numnodes)
		{
			botimport.Print(PRT_ERROR, "nodenum = %d >= aasworld.numnodes = %d\n", nodenum, aasworld.numnodes);
			return 0;
		} //end if
#endif //AAS_SAMPLE_DEBUG
		node = &aasworld.nodes[nodenum];
#ifdef AAS_SAMPLE_DEBUG
		if (node->planenum < 0 || node->planenum >= aasworld.numplanes)
		{
			botimport.Print(PRT_ERROR, "node->planenum = %d >= aasworld.numplanes = %d\n", node->planenum, aasworld.numplanes);
			return 0;
		} //end if
#endif //AAS_SAMPLE_DEBUG
		plane = &aasworld.planes[node->planenum];
		dist = DotProduct(point, plane->normal) - plane->dist;
		if (dist > 0) nodenum = node->children[0];
		else nodenum = node->children[1];
	} //end while
	if (!nodenum)
	{
#ifdef AAS_SAMPLE_DEBUG
		botimport.Print(PRT_MESSAGE, "in solid\n");
#endif //AAS_SAMPLE_DEBUG
		return 0;
	} //end if
	return -nodenum;
} //end of the function AAS_PointAreaNum
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
int AAS_PointReachabilityAreaIndex( vec3_t origin )
{
	int areanum, cluster, i, index;

	if (!aasworld.initialized)
		return 0;

	if ( !origin )
	{
		index = 0;
		for (i = 0; i < aasworld.numclusters; i++)
		{
			index += aasworld.clusters[i].numreachabilityareas;
		} //end for
		return index;
	} //end if

	areanum = AAS_PointAreaNum( origin );
	if ( !areanum || !AAS_AreaReachability(areanum) )
		return 0;
	cluster = aasworld.areasettings[areanum].cluster;
	areanum = aasworld.areasettings[areanum].clusterareanum;
	if (cluster < 0)
	{
		cluster = aasworld.portals[-cluster].frontcluster;
		areanum = aasworld.portals[-cluster].clusterareanum[0];
	} //end if

	index = 0;
	for (i = 0; i < cluster; i++)
	{
		index += aasworld.clusters[i].numreachabilityareas;
	} //end for
	index += areanum;
	return index;
} //end of the function AAS_PointReachabilityAreaIndex
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_AreaCluster(int areanum)
{
	if (areanum <= 0 || areanum >= aasworld.numareas)
	{
		botimport.Print(PRT_ERROR, "AAS_AreaCluster: invalid area number\n");
		return 0;
	} //end if
	return aasworld.areasettings[areanum].cluster;
} //end of the function AAS_AreaCluster
//===========================================================================
// returns the presence types of the given area
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_AreaPresenceType(int areanum)
{
	if (!aasworld.loaded) return 0;
	if (areanum <= 0 || areanum >= aasworld.numareas)
	{
		botimport.Print(PRT_ERROR, "AAS_AreaPresenceType: invalid area number\n");
		return 0;
	} //end if
	return aasworld.areasettings[areanum].presencetype;
} //end of the function AAS_AreaPresenceType
//===========================================================================
// returns the presence type at the given point
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_PointPresenceType(vec3_t point)
{
	int areanum;

	if (!aasworld.loaded) return 0;

	areanum = AAS_PointAreaNum(point);
	if (!areanum) return PRESENCE_NONE;
	return aasworld.areasettings[areanum].presencetype;
} //end of the function AAS_PointPresenceType
//===========================================================================
// calculates the minimum distance between the origin of the box and the
// given plane when both will collide on the given side of the plane
//
// normal	=	normal vector of plane to calculate distance from
// mins		=	minimums of box relative to origin
// maxs		=	maximums of box relative to origin
// side		=	side of the plane we want to calculate the distance from
//					0 normal vector side
//					1 not normal vector side
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
vec_t AAS_BoxOriginDistanceFromPlane(vec3_t normal, vec3_t mins, vec3_t maxs, int side)
{
	vec3_t v1, v2;
	int i;

	//swap maxs and mins when on the other side of the plane
	if (side)
	{
		//get a point of the box that would be one of the first
		//to collide with the plane
		for (i = 0; i < 3; i++)
		{
			if (normal[i] > BBOX_NORMAL_EPSILON) v1[i] = maxs[i];
			else if (normal[i] < -BBOX_NORMAL_EPSILON) v1[i] = mins[i];
			else v1[i] = 0;
		} //end for
	} //end if
	else
	{
		//get a point of the box that would be one of the first
		//to collide with the plane
		for (i = 0; i < 3; i++)
		{
			if (normal[i] > BBOX_NORMAL_EPSILON) v1[i] = mins[i];
			else if (normal[i] < -BBOX_NORMAL_EPSILON) v1[i] = maxs[i];
			else v1[i] = 0;
		} //end for
	} //end else
	//
	VectorCopy(normal, v2);
	VectorInverse(v2);
//	VectorNegate(normal, v2);
	return DotProduct(v1, v2);
} //end of the function AAS_BoxOriginDistanceFromPlane
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
qboolean AAS_AreaEntityCollision(int areanum, vec3_t start, vec3_t end,
										int presencetype, int passent, aas_trace_t *trace)
{
	int collision;
	vec3_t boxmins, boxmaxs;
	aas_link_t *link;
	bsp_trace_t bsptrace;

	AAS_PresenceTypeBoundingBox(presencetype, boxmins, boxmaxs);

	Com_Memset(&bsptrace, 0, sizeof(bsp_trace_t)); //make compiler happy
	//assume no collision
	bsptrace.fraction = 1;
	collision = qfalse;
	for (link = aasworld.arealinkedentities[areanum]; link; link = link->next_ent)
	{
		//ignore the pass entity
		if (link->entnum == passent) continue;
		//
		if (AAS_EntityCollision(link->entnum, start, boxmins, boxmaxs, end,
												CONTENTS_SOLID|CONTENTS_PLAYERCLIP, &bsptrace))
		{
			collision = qtrue;
		} //end if
	} //end for
	if (collision)
	{
		trace->startsolid = bsptrace.startsolid;
		trace->ent = bsptrace.ent;
		VectorCopy(bsptrace.endpos, trace->endpos);
		trace->area = 0;
		trace->planenum = 0;
		return qtrue;
	} //end if
	return qfalse;
} //end of the function AAS_AreaEntityCollision
//===========================================================================
// recursive subdivision of the line by the BSP tree.
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
aas_trace_t AAS_TraceClientBBox(vec3_t start, vec3_t end, int presencetype,
																				int passent)
{
	int side, nodenum, tmpplanenum;
	float front, back, frac;
	vec3_t cur_start, cur_end, cur_mid, v1, v2;
	aas_tracestack_t tracestack[127];
	aas_tracestack_t *tstack_p;
	aas_node_t *aasnode;
	aas_plane_t *plane;
	aas_trace_t trace;

	//clear the trace structure
	Com_Memset(&trace, 0, sizeof(aas_trace_t));

	if (!aasworld.loaded) return trace;