//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void AAS_ParseBSPEntities(void)
{
	script_t *script;
	token_t token;
	bsp_entity_t *ent;
	bsp_epair_t *epair;

	script = LoadScriptMemory(bspworld.dentdata, bspworld.entdatasize, "entdata");
	SetScriptFlags(script, SCFL_NOSTRINGWHITESPACES|SCFL_NOSTRINGESCAPECHARS);//SCFL_PRIMITIVE);

	bspworld.numentities = 1;

	while(PS_ReadToken(script, &token))
	{
		if (strcmp(token.string, "{"))
		{
			ScriptError(script, "invalid %s\n", token.string);
			AAS_FreeBSPEntities();
			FreeScript(script);
			return;
		} //end if
		if (bspworld.numentities >= MAX_BSPENTITIES)
		{
			botimport.Print(PRT_MESSAGE, "too many entities in BSP file\n");
			break;
		} //end if
		ent = &bspworld.entities[bspworld.numentities];
		bspworld.numentities++;
		ent->epairs = NULL;
		while(PS_ReadToken(script, &token))
		{
			if (!strcmp(token.string, "}")) break;
			epair = (bsp_epair_t *) GetClearedHunkMemory(sizeof(bsp_epair_t));
			epair->next = ent->epairs;
			ent->epairs = epair;
			if (token.type != TT_STRING)
			{
				ScriptError(script, "invalid %s\n", token.string);
				AAS_FreeBSPEntities();
				FreeScript(script);
				return;
			} //end if
			StripDoubleQuotes(token.string);
			epair->key = (char *) GetHunkMemory(strlen(token.string) + 1);
			strcpy(epair->key, token.string);
			if (!PS_ExpectTokenType(script, TT_STRING, 0, &token))
			{
				AAS_FreeBSPEntities();
				FreeScript(script);
				return;
			} //end if
			StripDoubleQuotes(token.string);
			epair->value = (char *) GetHunkMemory(strlen(token.string) + 1);
			strcpy(epair->value, token.string);
		} //end while
		if (strcmp(token.string, "}"))
		{
			ScriptError(script, "missing }\n");
			AAS_FreeBSPEntities();
			FreeScript(script);
			return;
		} //end if
	} //end while
	FreeScript(script);
} //end of the function AAS_ParseBSPEntities

//===========================================================================
// returns true if in Potentially Hearable Set
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
qbool AAS_inPVS(vec3_t p1, vec3_t p2)
{
	return botimport.inPVS(p1, p2);
} //end of the function AAS_InPVS

//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_BSPModelMinsMaxsOrigin(int modelnum, vec3_t angles, vec3_t mins, vec3_t maxs, vec3_t origin)
{
	botimport.BSPModelMinsMaxsOrigin(modelnum, angles, mins, maxs, origin);
} //end of the function AAS_BSPModelMinsMaxs

//===========================================================================
// traces axial boxes of any size through the world
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
bsp_trace_t AAS_Trace(vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, int passent, int contentmask)
{
	bsp_trace_t bsptrace;
	botimport.Trace(&bsptrace, start, mins, maxs, end, passent, contentmask);
	return bsptrace;
} //end of the function AAS_Trace

//===========================================================================
// returns the contents at the given point
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_PointContents(vec3_t point)
{
	return botimport.PointContents(point);
} //end of the function AAS_PointContents

//===========================================================================
// predicts the movement
// assumes regular bounding box sizes
// NOTE: out of water jumping is not included
// NOTE: grappling hook is not included
//
// Parameter:			origin			: origin to start with
//						presencetype	: presence type to start with
//						velocity		: velocity to start with
//						cmdmove			: client command movement
//						cmdframes		: number of frame cmdmove is valid
//						maxframes		: maximum number of predicted frames
//						frametime		: duration of one predicted frame
//						stopevent		: events that stop the prediction
//						stopareanum		: stop as soon as entered this area
// Returns:				aas_clientmove_t
// Changes Globals:		-
//===========================================================================
int AAS_ClientMovementPrediction(struct aas_clientmove_s *move,
                                 int entnum, vec3_t origin,
                                 int presencetype, int onground,
                                 vec3_t velocity, vec3_t cmdmove,
                                 int cmdframes,
                                 int maxframes, float frametime,
                                 int stopevent, int stopareanum,
                                 vec3_t mins, vec3_t maxs, int visualize)
{
    float phys_friction, phys_stopspeed, phys_gravity, phys_waterfriction;
    float phys_watergravity;
    float phys_walkaccelerate, phys_airaccelerate, phys_swimaccelerate;
    float phys_maxwalkvelocity, phys_maxcrouchvelocity, phys_maxswimvelocity;
    float phys_maxstep, phys_maxsteepness, phys_jumpvel, friction;
    float gravity, delta, maxvel, wishspeed, accelerate;
    //float velchange, newvel;
    //int ax;
    int n, i, j, pc, step, swimming, crouch, event, jump_frame, areanum;
    int areas[20], numareas;
    vec3_t points[20];
    vec3_t org, end, feet, start, stepend, lastorg, wishdir;
    vec3_t frame_test_vel, old_frame_test_vel, left_test_vel;
    vec3_t up = {0, 0, 1};
    aas_plane_t *plane, *plane2;
    aas_trace_t trace, steptrace;

    if (frametime <= 0) frametime = 0.1f;
    //
    phys_friction = aassettings.phys_friction;
    phys_stopspeed = aassettings.phys_stopspeed;
    phys_gravity = aassettings.phys_gravity;
    phys_waterfriction = aassettings.phys_waterfriction;
    phys_watergravity = aassettings.phys_watergravity;
    phys_maxwalkvelocity = aassettings.phys_maxwalkvelocity;// * frametime;
    phys_maxcrouchvelocity = aassettings.phys_maxcrouchvelocity;// * frametime;
    phys_maxswimvelocity = aassettings.phys_maxswimvelocity;// * frametime;
    phys_walkaccelerate = aassettings.phys_walkaccelerate;
    phys_airaccelerate = aassettings.phys_airaccelerate;
    phys_swimaccelerate = aassettings.phys_swimaccelerate;
    phys_maxstep = aassettings.phys_maxstep;
    phys_maxsteepness = aassettings.phys_maxsteepness;
    phys_jumpvel = aassettings.phys_jumpvel * frametime;
    //
    Com_Memset(move, 0, sizeof(aas_clientmove_t));
    Com_Memset(&trace, 0, sizeof(aas_trace_t));
    //start at the current origin
    VectorCopy(origin, org);
    org[2] += 0.25;
    //velocity to test for the first frame
    VectorScale(velocity, frametime, frame_test_vel);
    //
    jump_frame = -1;
    //predict a maximum of 'maxframes' ahead
    for (n = 0; n < maxframes; n++)
    {
        swimming = AAS_Swimming(org);
        //get gravity depending on swimming or not
        gravity = swimming ? phys_watergravity : phys_gravity;
        //apply gravity at the START of the frame
        frame_test_vel[2] = frame_test_vel[2] - (gravity * 0.1 * frametime);
        //if on the ground or swimming
        if (onground || swimming)
        {
            friction = swimming ? phys_friction : phys_waterfriction;
            //apply friction
            VectorScale(frame_test_vel, 1/frametime, frame_test_vel);
            AAS_ApplyFriction(frame_test_vel, friction, phys_stopspeed, frametime);
            VectorScale(frame_test_vel, frametime, frame_test_vel);
        } //end if
        crouch = qfalse;
        //apply command movement
        if (n < cmdframes)
        {
            //ax = 0;
            maxvel = phys_maxwalkvelocity;
            accelerate = phys_airaccelerate;
            VectorCopy(cmdmove, wishdir);
            if (onground)
            {
                if (cmdmove[2] < -300)
                {
                    crouch = qtrue;
//.........这里部分代码省略.........

int BotExportTest(int parm0, char *parm1, vec3_t parm2, vec3_t parm3)
{

//	return AAS_PointLight(parm2, NULL, NULL, NULL);

#ifdef DEBUG
	static int area = -1;
	static int line[2];
	int newarea, i, highlightarea, flood;
//	int reachnum;
	vec3_t eye, forward, right, end, origin;
//	vec3_t bottomcenter;
//	aas_trace_t trace;
//	aas_face_t *face;
//	aas_entity_t *ent;
//	bsp_trace_t bsptrace;
//	aas_reachability_t reach;
//	bot_goal_t goal;

	// clock_t start_time, end_time;
	vec3_t mins = {-16, -16, -24};
	vec3_t maxs = {16, 16, 32};

//	int areas[10], numareas;


	//return 0;

	if (!aasworld.loaded) return 0;

	/*
	if (parm0 & 1)
	{
		AAS_ClearShownPolygons();
		AAS_FloodAreas(parm2);
	} //end if
	return 0;
	*/
	for (i = 0; i < 2; i++) if (!line[i]) line[i] = botimport.DebugLineCreate();

//	AAS_ClearShownDebugLines();

	//if (AAS_AgainstLadder(parm2)) botimport.Print(PRT_MESSAGE, "against ladder\n");
	//BotOnGround(parm2, PRESENCE_NORMAL, 1, &newarea, &newarea);
	//botimport.Print(PRT_MESSAGE, "%f %f %f\n", parm2[0], parm2[1], parm2[2]);
	//*
	highlightarea = LibVarGetValue("bot_highlightarea");
	if (highlightarea > 0)
	{
		newarea = highlightarea;
	} //end if
	else
	{
		VectorCopy(parm2, origin);
		origin[2] += 0.5;
		//newarea = AAS_PointAreaNum(origin);
		newarea = BotFuzzyPointReachabilityArea(origin);
	} //end else

	botimport.Print(PRT_MESSAGE, "\rtravel time to goal (%d) = %d  ", botlibglobals.goalareanum,
		AAS_AreaTravelTimeToGoalArea(newarea, origin, botlibglobals.goalareanum, TFL_DEFAULT));
	//newarea = BotReachabilityArea(origin, qtrue);
	if (newarea != area)
	{
		botimport.Print(PRT_MESSAGE, "origin = %f, %f, %f\n", origin[0], origin[1], origin[2]);
		area = newarea;
		botimport.Print(PRT_MESSAGE, "new area %d, cluster %d, presence type %d\n",
					area, AAS_AreaCluster(area), AAS_PointPresenceType(origin));
		botimport.Print(PRT_MESSAGE, "area contents: ");
		if (aasworld.areasettings[area].contents & AREACONTENTS_WATER)
		{
			botimport.Print(PRT_MESSAGE, "water &");
		} //end if
		if (aasworld.areasettings[area].contents & AREACONTENTS_LAVA)
		{
			botimport.Print(PRT_MESSAGE, "lava &");
		} //end if
		if (aasworld.areasettings[area].contents & AREACONTENTS_SLIME)
		{
			botimport.Print(PRT_MESSAGE, "slime &");
		} //end if
		if (aasworld.areasettings[area].contents & AREACONTENTS_JUMPPAD)
		{
			botimport.Print(PRT_MESSAGE, "jump pad &");
		} //end if
		if (aasworld.areasettings[area].contents & AREACONTENTS_CLUSTERPORTAL)
		{
			botimport.Print(PRT_MESSAGE, "cluster portal &");
		} //end if
		if (aasworld.areasettings[area].contents & AREACONTENTS_VIEWPORTAL)
		{
			botimport.Print(PRT_MESSAGE, "view portal &");
		} //end if
		if (aasworld.areasettings[area].contents & AREACONTENTS_DONOTENTER)
		{
			botimport.Print(PRT_MESSAGE, "do not enter &");
		} //end if
		if (aasworld.areasettings[area].contents & AREACONTENTS_MOVER)
		{
			botimport.Print(PRT_MESSAGE, "mover &");
//.........这里部分代码省略.........

void AAS_AddTeleporterPortals(void)
{
	int j, area2num, facenum, otherareanum;
	char *target, *targetname, *classname;
	bsp_entity_t *entities, *ent, *dest;
	vec3_t origin, destorigin, mins, maxs, end;
	vec3_t bbmins, bbmaxs;
	aas_area_t *area;
	aas_face_t *face;
	aas_trace_t trace;
	aas_link_t *areas, *link;

	entities = AAS_ParseBSPEntities();

	for (ent = entities; ent; ent = ent->next)
	{
		classname = AAS_ValueForBSPEpairKey(ent, "classname");
		if (classname && !strcmp(classname, "misc_teleporter"))
		{
			if (!AAS_VectorForBSPEpairKey(ent, "origin", origin))
			{
				botimport.Print(PRT_ERROR, "teleporter (%s) without origin\n", target);
				continue;
			} //end if
			//
			target = AAS_ValueForBSPEpairKey(ent, "target");
			if (!target)
			{
				botimport.Print(PRT_ERROR, "teleporter (%s) without target\n", target);
				continue;
			} //end if
			for (dest = entities; dest; dest = dest->next)
			{
				classname = AAS_ValueForBSPEpairKey(dest, "classname");
				if (classname && !strcmp(classname, "misc_teleporter_dest"))
				{
					targetname = AAS_ValueForBSPEpairKey(dest, "targetname");
					if (targetname && !strcmp(targetname, target))
					{
						break;
					} //end if
				} //end if
			} //end for
			if (!dest)
			{
				botimport.Print(PRT_ERROR, "teleporter without destination (%s)\n", target);
				continue;
			} //end if
			if (!AAS_VectorForBSPEpairKey(dest, "origin", destorigin))
			{
				botimport.Print(PRT_ERROR, "teleporter destination (%s) without origin\n", target);
				continue;
			} //end if
			destorigin[2] += 24; //just for q2e1m2, the dork has put the telepads in the ground
			VectorCopy(destorigin, end);
			end[2] -= 100;
			trace = AAS_TraceClientBBox(destorigin, end, PRESENCE_CROUCH, -1);
			if (trace.startsolid)
			{
				botimport.Print(PRT_ERROR, "teleporter destination (%s) in solid\n", target);
				continue;
			} //end if
			VectorCopy(trace.endpos, destorigin);
			area2num = AAS_PointAreaNum(destorigin);
			//reset all cluster fields
			for (j = 0; j < aasworld.numareas; j++)
			{
				aasworld.areasettings[j].cluster = 0;
			} //end for
			//
			VectorSet(mins, -8, -8, 8);
			VectorSet(maxs, 8, 8, 24);
			//
			AAS_PresenceTypeBoundingBox(PRESENCE_CROUCH, bbmins, bbmaxs);
			//
			VectorAdd(origin, mins, mins);
			VectorAdd(origin, maxs, maxs);
			//add bounding box size
			VectorSubtract(mins, bbmaxs, mins);
			VectorSubtract(maxs, bbmins, maxs);
			//link an invalid (-1) entity
			areas = AAS_AASLinkEntity(mins, maxs, -1);
			//
			for (link = areas; link; link = link->next_area)
			{
				if (!AAS_AreaGrounded(link->areanum)) continue;
				//add the teleporter portal mark
				aasworld.areasettings[link->areanum].contents |= AREACONTENTS_CLUSTERPORTAL |
																			AREACONTENTS_TELEPORTAL;
			} //end for
			//
			for (link = areas; link; link = link->next_area)
			{
				if (!AAS_AreaGrounded(link->areanum)) continue;
				//find a non-portal area adjacent to the portal area and flood
				//the cluster from there
				area = &aasworld.areas[link->areanum];
				for (j = 0; j < area->numfaces; j++)
				{
					facenum = abs(aasworld.faceindex[area->firstface + j]);
//.........这里部分代码省略.........

//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_InitClustering(void)
{
	int i, removedPortalAreas;
	int n, total, numreachabilityareas;

	if (!aasworld.loaded) return;
	//if there are clusters
	if (aasworld.numclusters >= 1)
	{
#ifndef BSPC
		//if clustering isn't forced
		if (!((int)LibVarGetValue("forceclustering")) &&
			!((int)LibVarGetValue("forcereachability"))) return;
#endif
	} //end if
	//set all view portals as cluster portals in case we re-calculate the reachabilities and clusters (with -reach)
	AAS_SetViewPortalsAsClusterPortals();
	//count the number of forced cluster portals
	AAS_CountForcedClusterPortals();
	//remove all area cluster marks
	AAS_RemoveClusterAreas();
	//find possible cluster portals
	AAS_FindPossiblePortals();
	//craete portals to for the bot view
	AAS_CreateViewPortals();
	//remove all portals that are not closing a cluster
	//AAS_RemoveNotClusterClosingPortals();
	//initialize portal memory
	if (aasworld.portals) FreeMemory(aasworld.portals);
	aasworld.portals = (aas_portal_t *) GetClearedMemory(AAS_MAX_PORTALS * sizeof(aas_portal_t));
	//initialize portal index memory
	if (aasworld.portalindex) FreeMemory(aasworld.portalindex);
	aasworld.portalindex = (aas_portalindex_t *) GetClearedMemory(AAS_MAX_PORTALINDEXSIZE * sizeof(aas_portalindex_t));
	//initialize cluster memory
	if (aasworld.clusters) FreeMemory(aasworld.clusters);
	aasworld.clusters = (aas_cluster_t *) GetClearedMemory(AAS_MAX_CLUSTERS * sizeof(aas_cluster_t));
	//
	removedPortalAreas = 0;
	botimport.Print(PRT_MESSAGE, "\r%6d removed portal areas", removedPortalAreas);
	while(1)
	{
		botimport.Print(PRT_MESSAGE, "\r%6d", removedPortalAreas);
		//initialize the number of portals and clusters
		aasworld.numportals = 1;		//portal 0 is a dummy
		aasworld.portalindexsize = 0;
		aasworld.numclusters = 1;		//cluster 0 is a dummy
		//create the portals from the portal areas
		AAS_CreatePortals();
		//
		removedPortalAreas++;
		//find the clusters
		if (!AAS_FindClusters())
			continue;
		//test the portals
		if (!AAS_TestPortals())
			continue;
		//
		break;
	} //end while
	botimport.Print(PRT_MESSAGE, "\n");
	//the AAS file should be saved
	aasworld.savefile = qtrue;
	//write the portal areas to the log file
	for (i = 1; i < aasworld.numportals; i++)
	{
		Log_Write("portal %d: area %d\r\n", i, aasworld.portals[i].areanum);
	} //end for
	// report cluster info
	botimport.Print(PRT_MESSAGE, "%6d portals created\n", aasworld.numportals);
	botimport.Print(PRT_MESSAGE, "%6d clusters created\n", aasworld.numclusters);
	for (i = 1; i < aasworld.numclusters; i++)
	{
		botimport.Print(PRT_MESSAGE, "cluster %d has %d reachability areas\n", i,
				aasworld.clusters[i].numreachabilityareas);
	} //end for
	// report AAS file efficiency
	numreachabilityareas = 0;
	total = 0;
	for (i = 0; i < aasworld.numclusters; i++) {
		n = aasworld.clusters[i].numreachabilityareas;
		numreachabilityareas += n;
		total += n * n;
	}
	total += numreachabilityareas * aasworld.numportals;
	//
	botimport.Print(PRT_MESSAGE, "%6i total reachability areas\n", numreachabilityareas);
	botimport.Print(PRT_MESSAGE, "%6i AAS memory/CPU usage (the lower the better)\n", total * 3);
} //end of the function AAS_InitClustering

void AAS_RemoveNotClusterClosingPortals(void)
{
	int i, j, facenum, otherareanum, nonclosingportals, numseperatedclusters;
	aas_area_t *area;
	aas_face_t *face;

	AAS_RemoveTeleporterPortals();
	//
	nonclosingportals = 0;
	for (i = 1; i < aasworld.numareas; i++)
	{
		if (!(aasworld.areasettings[i].contents & AREACONTENTS_CLUSTERPORTAL)) continue;
		//
		numseperatedclusters = 0;
		//reset all cluster fields
		AAS_RemoveClusterAreas();
		//find a non-portal area adjacent to the portal area and flood
		//the cluster from there
		area = &aasworld.areas[i];
		for (j = 0; j < area->numfaces; j++)
		{
			facenum = abs(aasworld.faceindex[area->firstface + j]);
			face = &aasworld.faces[facenum];
			//
			if (face->frontarea != i) otherareanum = face->frontarea;
			else otherareanum = face->backarea;
			//if not solid at the other side of the face
			if (!otherareanum) continue;
			//don't flood into other portals
			if (aasworld.areasettings[otherareanum].contents & AREACONTENTS_CLUSTERPORTAL) continue;
			//if the area already has a cluster set
			if (aasworld.areasettings[otherareanum].cluster) continue;
			//another cluster is seperated by this portal
			numseperatedclusters++;
			//flood the cluster
			AAS_FloodCluster_r(otherareanum, numseperatedclusters);
			AAS_FloodClusterReachabilities(numseperatedclusters);
		} //end for
		//use the reachabilities to flood into other areas
		for (j = 0; j < aasworld.areasettings[i].numreachableareas; j++)
		{
			otherareanum = aasworld.reachability[
						aasworld.areasettings[i].firstreachablearea + j].areanum;
			//this should never be qtrue but we check anyway
			if (!otherareanum) continue;
			//don't flood into other portals
			if (aasworld.areasettings[otherareanum].contents & AREACONTENTS_CLUSTERPORTAL) continue;
			//if the area already has a cluster set
			if (aasworld.areasettings[otherareanum].cluster) continue;
			//another cluster is seperated by this portal
			numseperatedclusters++;
			//flood the cluster
			AAS_FloodCluster_r(otherareanum, numseperatedclusters);
			AAS_FloodClusterReachabilities(numseperatedclusters);
		} //end for
		//a portal must seperate no more and no less than 2 clusters
		if (numseperatedclusters != 2)
		{
			aasworld.areasettings[i].contents &= ~AREACONTENTS_CLUSTERPORTAL;
			nonclosingportals++;
			//recheck all the other portals again
			i = 0;
		} //end if
	} //end for
	botimport.Print(PRT_MESSAGE, "\r%6d non closing portals removed\n", nonclosingportals);
} //end of the function AAS_RemoveNotClusterClosingPortals

//===========================================================================
// recursive subdivision of the line by the BSP tree.
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_TraceAreas(vec3_t start, vec3_t end, int *areas, vec3_t *points, int maxareas)
{
	int side, nodenum, tmpplanenum;
	int numareas;
	float front, back, frac;
	vec3_t cur_start, cur_end, cur_mid;
	aas_tracestack_t tracestack[127];
	aas_tracestack_t *tstack_p;
	aas_node_t *aasnode;
	aas_plane_t *plane;

	numareas = 0;
	areas[0] = 0;
	if (!aasworld.loaded) return numareas;

	tstack_p = tracestack;
	//we start with the whole line on the stack
	VectorCopy(start, tstack_p->start);
	VectorCopy(end, tstack_p->end);
	tstack_p->planenum = 0;
	//start with node 1 because node zero is a dummy for a solid leaf
	tstack_p->nodenum = 1;		//starting at the root of the tree
	tstack_p++;

	while (1)
	{
		//pop up the stack
		tstack_p--;
		//if the trace stack is empty (ended up with a piece of the
		//line to be traced in an area)
		if (tstack_p < tracestack)
		{
			return numareas;
		} //end if
		//number of the current node to test the line against
		nodenum = tstack_p->nodenum;
		//if it is an area
		if (nodenum < 0)
		{
#ifdef AAS_SAMPLE_DEBUG
			if (-nodenum > aasworld.numareasettings)
			{
				botimport.Print(PRT_ERROR, "AAS_TraceAreas: -nodenum = %d out of range\n", -nodenum);
				return numareas;
			} //end if
#endif //AAS_SAMPLE_DEBUG
			//botimport.Print(PRT_MESSAGE, "areanum = %d, must be %d\n", -nodenum, AAS_PointAreaNum(start));
			areas[numareas] = -nodenum;
			if (points) VectorCopy(tstack_p->start, points[numareas]);
			numareas++;
			if (numareas >= maxareas) return numareas;
			continue;
		} //end if
		//if it is a solid leaf
		if (!nodenum)
		{
			continue;
		} //end if
#ifdef AAS_SAMPLE_DEBUG
		if (nodenum > aasworld.numnodes)
		{
			botimport.Print(PRT_ERROR, "AAS_TraceAreas: nodenum out of range\n");
			return numareas;
		} //end if
#endif //AAS_SAMPLE_DEBUG
		//the node to test against
		aasnode = &aasworld.nodes[nodenum];
		//start point of current line to test against node
		VectorCopy(tstack_p->start, cur_start);
		//end point of the current line to test against node
		VectorCopy(tstack_p->end, cur_end);
		//the current node plane
		plane = &aasworld.planes[aasnode->planenum];

//		switch(plane->type)
		{/*FIXME: wtf doesn't this work? obviously the node planes aren't always facing positive!!!
			//check for axial planes
			case PLANE_X:
			{
				front = cur_start[0] - plane->dist;
				back = cur_end[0] - plane->dist;
				break;
			} //end case
			case PLANE_Y:
			{
				front = cur_start[1] - plane->dist;
				back = cur_end[1] - plane->dist;
				break;
			} //end case
			case PLANE_Z:
			{
				front = cur_start[2] - plane->dist;
				back = cur_end[2] - plane->dist;
//.........这里部分代码省略.........

//===========================================================================
// 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;
	
	tstack_p = tracestack;
	//we start with the whole line on the stack
	VectorCopy(start, tstack_p->start);
	VectorCopy(end, tstack_p->end);
	tstack_p->planenum = 0;
	//start with node 1 because node zero is a dummy for a solid leaf
	tstack_p->nodenum = 1;		//starting at the root of the tree
	tstack_p++;
	
	while (1)
	{
		//pop up the stack
		tstack_p--;
		//if the trace stack is empty (ended up with a piece of the
		//line to be traced in an area)
		if (tstack_p < tracestack)
		{
			tstack_p++;
			//nothing was hit
			trace.startsolid = qfalse;
			trace.fraction = 1.0;
			//endpos is the end of the line
			VectorCopy(end, trace.endpos);
			//nothing hit
			trace.ent = 0;
			trace.area = 0;
			trace.planenum = 0;
			return trace;
		} //end if
		//number of the current node to test the line against
		nodenum = tstack_p->nodenum;
		//if it is an area
		if (nodenum < 0)
		{
#ifdef AAS_SAMPLE_DEBUG
			if (-nodenum > aasworld.numareasettings)
			{
				botimport.Print(PRT_ERROR, "AAS_TraceBoundingBox: -nodenum out of range\n");
				return trace;
			} //end if
#endif //AAS_SAMPLE_DEBUG
			//botimport.Print(PRT_MESSAGE, "areanum = %d, must be %d\n", -nodenum, AAS_PointAreaNum(start));
			//if can't enter the area because it hasn't got the right presence type
			if (!(aasworld.areasettings[-nodenum].presencetype & presencetype))
			{
				//if the start point is still the initial start point
				//NOTE: no need for epsilons because the points will be
				//exactly the same when they're both the start point
				if (tstack_p->start[0] == start[0] &&
						tstack_p->start[1] == start[1] &&
						tstack_p->start[2] == start[2])
				{
					trace.startsolid = qtrue;
					trace.fraction = 0.0;
					VectorClear(v1);
				} //end if
				else
				{
					trace.startsolid = qfalse;
					VectorSubtract(end, start, v1);
					VectorSubtract(tstack_p->start, start, v2);
					trace.fraction = VectorLength(v2) / VectorNormalize(v1);
					VectorMA(tstack_p->start, -0.125, v1, tstack_p->start);
				} //end else
				VectorCopy(tstack_p->start, trace.endpos);
				trace.ent = 0;
				trace.area = -nodenum;
//				VectorSubtract(end, start, v1);
				trace.planenum = tstack_p->planenum;
				//always take the plane with normal facing towards the trace start
				plane = &aasworld.planes[trace.planenum];
				if (DotProduct(v1, plane->normal) > 0) trace.planenum ^= 1;
				return trace;
			} //end if
			else
			{
//.........这里部分代码省略.........

aas_link_t *AAS_AASLinkEntity(vec3_t absmins, vec3_t absmaxs, int entnum)
{
	int side, nodenum;
	aas_linkstack_t linkstack[128];
	aas_linkstack_t *lstack_p;
	aas_node_t *aasnode;
	aas_plane_t *plane;
	aas_link_t *link, *areas;

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

	areas = NULL;
	//
	lstack_p = linkstack;
	//we start with the whole line on the stack
	//start with node 1 because node zero is a dummy used for solid leafs
	lstack_p->nodenum = 1;		//starting at the root of the tree
	lstack_p++;
	
	while (1)
	{
		//pop up the stack
		lstack_p--;
		//if the trace stack is empty (ended up with a piece of the
		//line to be traced in an area)
		if (lstack_p < linkstack) break;
		//number of the current node to test the line against
		nodenum = lstack_p->nodenum;
		//if it is an area
		if (nodenum < 0)
		{
			//NOTE: the entity might have already been linked into this area
			// because several node children can point to the same area
			for (link = aasworld.arealinkedentities[-nodenum]; link; link = link->next_ent)
			{
				if (link->entnum == entnum) break;
			} //end for
			if (link) continue;
			//
			link = AAS_AllocAASLink();
			if (!link) return areas;
			link->entnum = entnum;
			link->areanum = -nodenum;
			//put the link into the double linked area list of the entity
			link->prev_area = NULL;
			link->next_area = areas;
			if (areas) areas->prev_area = link;
			areas = link;
			//put the link into the double linked entity list of the area
			link->prev_ent = NULL;
			link->next_ent = aasworld.arealinkedentities[-nodenum];
			if (aasworld.arealinkedentities[-nodenum])
					aasworld.arealinkedentities[-nodenum]->prev_ent = link;
			aasworld.arealinkedentities[-nodenum] = link;
			//
			continue;
		} //end if
		//if solid leaf
		if (!nodenum) continue;
		//the node to test against
		aasnode = &aasworld.nodes[nodenum];
		//the current node plane
		plane = &aasworld.planes[aasnode->planenum];
		//get the side(s) the box is situated relative to the plane
		side = AAS_BoxOnPlaneSide2(absmins, absmaxs, plane);
		//if on the front side of the node
		if (side & 1)
		{
			lstack_p->nodenum = aasnode->children[0];
			lstack_p++;
		} //end if
		if (lstack_p >= &linkstack[127])
		{
			botimport.Print(PRT_ERROR, "AAS_LinkEntity: stack overflow\n");
			break;
		} //end if
		//if on the back side of the node
		if (side & 2)
		{
			lstack_p->nodenum = aasnode->children[1];
			lstack_p++;
		} //end if
		if (lstack_p >= &linkstack[127])
		{
			botimport.Print(PRT_ERROR, "AAS_LinkEntity: stack overflow\n");
			break;
		} //end if
	} //end while
	return areas;
} //end of the function AAS_AASLinkEntity