be_aas_cluster.c

quakeIII源码这个不用我多说吧

			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

//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================

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]);
					face = &aasworld.faces[facenum];
					//
					if (face->frontarea != link->areanum) otherareanum = face->frontarea;
					else otherareanum = face->backarea;
					//
					if (!otherareanum) continue;
					//
					if (aasworld.areasettings[otherareanum].contents & AREACONTENTS_CLUSTERPORTAL)
					{
						continue;
					} //end if
					//
					AAS_FloodCluster_r(otherareanum, 1);
				} //end for
			} //end for
			//if the teleport destination IS in the same cluster
			if (aasworld.areasettings[area2num].cluster)
			{
				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
			} //end if
		} //end if
	} //end for
	AAS_FreeBSPEntities(entities);
} //end of the function AAS_AddTeleporterPortals

//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_AddTeleporterPortals(void)
{
	int i, j, areanum;

	for (i = 1; i < aasworld.numareas; i++)
	{
		for (j = 0; j < aasworld.areasettings[i].numreachableareas; j++)
		{
			if (aasworld.reachability[aasworld.areasettings[i].firstreachablearea + j].traveltype != TRAVEL_TELEPORT) continue;
			areanum = aasworld.reachability[aasworld.areasettings[i].firstreachablearea + j].areanum;
			aasworld.areasettings[areanum].contents |= AREACONTENTS_CLUSTERPORTAL;
		} //end for
	} //end for
} //end of the function AAS_AddTeleporterPortals

#endif

//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_TestPortals(void)
{
	int i;
	aas_portal_t *portal;

	for (i = 1; i < aasworld.numportals; i++)
	{
		portal = &aasworld.portals[i];
		if (!portal->frontcluster)
		{
			aasworld.areasettings[portal->areanum].contents &= ~AREACONTENTS_CLUSTERPORTAL;
			Log_Write("portal area %d has no front cluster\r\n", portal->areanum);
			return qfalse;
		} //end if
		if (!portal->backcluster)
		{
			aasworld.areasettings[portal->areanum].contents &= ~AREACONTENTS_CLUSTERPORTAL;
			Log_Write("portal area %d has no back cluster\r\n", portal->areanum);
			return qfalse;
		} //end if
	} //end for
	return qtrue;
} //end of the function
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_CountForcedClusterPortals(void)
{
	int num, i;

	num = 0;
	for (i = 1; i < aasworld.numareas; i++)
	{
		if (aasworld.areasettings[i].contents & AREACONTENTS_CLUSTERPORTAL)
		{
			Log_Write("area %d is a forced portal area\r\n", i);
			num++;
		} //end if
	} //end for
	botimport.Print(PRT_MESSAGE, "%6d forced portal areas\n", num);
} //end of the function AAS_CountForcedClusterPortals
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void AAS_CreateViewPortals(void)
{
	int i;

	for (i = 1; i < aasworld.numareas; i++)
	{
		if (aasworld.areasettings[i].contents & AREACONTENTS_CLUSTERPORTAL)
		{
			aasworld.areasettings[i].contents |= AREACONTENTS_VIEWPORTAL;
		} //end if
	} //end for
} //end of the function AAS_CreateViewPortals
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_SetViewPortalsAsClusterPortals(void)
{
	int i;

	for (i = 1; i < aasworld.numareas; i++)
	{
		if (aasworld.areasettings[i].contents & AREACONTENTS_VIEWPORTAL)
		{
			aasworld.areasettings[i].contents |= AREACONTENTS_CLUSTERPORTAL;
		} //end if
	} //end for
} //end of the function AAS_SetViewPortalsAsClusterPortals
//===========================================================================
//
// 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