be_aas_cluster.c

quakeIII源码这个不用我多说吧

			{
				if (numareas >= MAX_PORTALAREAS)
				{
					AAS_Error("MAX_PORTALAREAS");
					return numareas;
				} //end if
				numareas = AAS_GetAdjacentAreasWithLessPresenceTypes_r(areanums, numareas, otherareanum);
			} //end if
		} //end if
	} //end for
	return numareas;
} //end of the function AAS_GetAdjacentAreasWithLessPresenceTypes_r
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_CheckAreaForPossiblePortals(int areanum)
{
	int i, j, k, fen, ben, frontedgenum, backedgenum, facenum;
	int areanums[MAX_PORTALAREAS], numareas, otherareanum;
	int numareafrontfaces[MAX_PORTALAREAS], numareabackfaces[MAX_PORTALAREAS];
	int frontfacenums[MAX_PORTALAREAS], backfacenums[MAX_PORTALAREAS];
	int numfrontfaces, numbackfaces;
	int frontareanums[MAX_PORTALAREAS], backareanums[MAX_PORTALAREAS];
	int numfrontareas, numbackareas;
	int frontplanenum, backplanenum, faceplanenum;
	aas_area_t *area;
	aas_face_t *frontface, *backface, *face;

	//if it isn't already a portal
	if (aasworld.areasettings[areanum].contents & AREACONTENTS_CLUSTERPORTAL) return 0;
	//it must be a grounded area
	if (!(aasworld.areasettings[areanum].areaflags & AREA_GROUNDED)) return 0;
	//
	Com_Memset(numareafrontfaces, 0, sizeof(numareafrontfaces));
	Com_Memset(numareabackfaces, 0, sizeof(numareabackfaces));
	numareas = numfrontfaces = numbackfaces = 0;
	numfrontareas = numbackareas = 0;
	frontplanenum = backplanenum = -1;
	//add any adjacent areas with less presence types
	numareas = AAS_GetAdjacentAreasWithLessPresenceTypes_r(areanums, 0, areanum);
	//
	for (i = 0; i < numareas; i++)
	{
		area = &aasworld.areas[areanums[i]];
		for (j = 0; j < area->numfaces; j++)
		{
			facenum = abs(aasworld.faceindex[area->firstface + j]);
			face = &aasworld.faces[facenum];
			//if the face is solid
			if (face->faceflags & FACE_SOLID) continue;
			//check if the face is shared with one of the other areas
			for (k = 0; k < numareas; k++)
			{
				if (k == i) continue;
				if (face->frontarea == areanums[k] || face->backarea == areanums[k]) break;
			} //end for
			//if the face is shared
			if (k != numareas) continue;
			//the number of the area at the other side of the face
			if (face->frontarea == areanums[i]) otherareanum = face->backarea;
			else otherareanum = face->frontarea;
			//if the other area already is a cluter portal
			if (aasworld.areasettings[otherareanum].contents & AREACONTENTS_CLUSTERPORTAL) return 0;
			//number of the plane of the area
			faceplanenum = face->planenum & ~1;
			//
			if (frontplanenum < 0 || faceplanenum == frontplanenum)
			{
				frontplanenum = faceplanenum;
				frontfacenums[numfrontfaces++] = facenum;
				for (k = 0; k < numfrontareas; k++)
				{
					if (frontareanums[k] == otherareanum) break;
				} //end for
				if (k == numfrontareas) frontareanums[numfrontareas++] = otherareanum;
				numareafrontfaces[i]++;
			} //end if
			else if (backplanenum < 0 || faceplanenum == backplanenum)
			{
				backplanenum = faceplanenum;
				backfacenums[numbackfaces++] = facenum;
				for (k = 0; k < numbackareas; k++)
				{
					if (backareanums[k] == otherareanum) break;
				} //end for
				if (k == numbackareas) backareanums[numbackareas++] = otherareanum;
				numareabackfaces[i]++;
			} //end else
			else
			{
				return 0;
			} //end else
		} //end for
	} //end for
	//every area should have at least one front face and one back face
	for (i = 0; i < numareas; i++)
	{
		if (!numareafrontfaces[i] || !numareabackfaces[i]) return 0;
	} //end for
	//the front areas should all be connected
	if (!AAS_ConnectedAreas(frontareanums, numfrontareas)) return 0;
	//the back areas should all be connected
	if (!AAS_ConnectedAreas(backareanums, numbackareas)) return 0;
	//none of the front faces should have a shared edge with a back face
	for (i = 0; i < numfrontfaces; i++)
	{
		frontface = &aasworld.faces[frontfacenums[i]];
		for (fen = 0; fen < frontface->numedges; fen++)
		{
			frontedgenum = abs(aasworld.edgeindex[frontface->firstedge + fen]);
			for (j = 0; j < numbackfaces; j++)
			{
				backface = &aasworld.faces[backfacenums[j]];
				for (ben = 0; ben < backface->numedges; ben++)
				{
					backedgenum = abs(aasworld.edgeindex[backface->firstedge + ben]);
					if (frontedgenum == backedgenum) break;
				} //end for
				if (ben != backface->numedges) break;
			} //end for
			if (j != numbackfaces) break;
		} //end for
		if (fen != frontface->numedges) break;
	} //end for
	if (i != numfrontfaces) return 0;
	//set the cluster portal contents
	for (i = 0; i < numareas; i++)
	{
		aasworld.areasettings[areanums[i]].contents |= AREACONTENTS_CLUSTERPORTAL;
		//this area can be used as a route portal
		aasworld.areasettings[areanums[i]].contents |= AREACONTENTS_ROUTEPORTAL;
		Log_Write("possible portal: %d\r\n", areanums[i]);
	} //end for
	//
	return numareas;
} //end of the function AAS_CheckAreaForPossiblePortals
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_FindPossiblePortals(void)
{
	int i, numpossibleportals;

	numpossibleportals = 0;
	for (i = 1; i < aasworld.numareas; i++)
	{
		numpossibleportals += AAS_CheckAreaForPossiblePortals(i);
	} //end for
	botimport.Print(PRT_MESSAGE, "\r%6d possible portal areas\n", numpossibleportals);
} //end of the function AAS_FindPossiblePortals
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_RemoveAllPortals(void)
{
	int i;

	for (i = 1; i < aasworld.numareas; i++)
	{
		aasworld.areasettings[i].contents &= ~AREACONTENTS_CLUSTERPORTAL;
	} //end for
} //end of the function AAS_RemoveAllPortals

#if 0
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_FloodCluster_r(int areanum, int clusternum)
{
	int i, otherareanum;
	aas_face_t *face;
	aas_area_t *area;

	//set cluster mark
	aasworld.areasettings[areanum].cluster = clusternum;
	//if the area is a portal
	//if (aasworld.areasettings[areanum].contents & AREACONTENTS_CLUSTERPORTAL) return;
	//
	area = &aasworld.areas[areanum];
	//use area faces to flood into adjacent areas
	for (i = 0; i < area->numfaces; i++)
	{
		face = &aasworld.faces[abs(aasworld.faceindex[area->firstface + i])];
		//
		if (face->frontarea != areanum) otherareanum = face->frontarea;
		else otherareanum = face->backarea;
		//if there's no area at the other side
		if (!otherareanum) continue;
		//if the area is a portal
		if (aasworld.areasettings[otherareanum].contents & AREACONTENTS_CLUSTERPORTAL) continue;
		//if the area is already marked
		if (aasworld.areasettings[otherareanum].cluster) continue;
		//
		AAS_FloodCluster_r(otherareanum, clusternum);
	} //end for
	//use the reachabilities to flood into other areas
	for (i = 0; i < aasworld.areasettings[areanum].numreachableareas; i++)
	{
		otherareanum = aasworld.reachability[
					aasworld.areasettings[areanum].firstreachablearea + i].areanum;
		if (!otherareanum)
		{
			continue;
			AAS_Error("reachability %d has zero area\n", aasworld.areasettings[areanum].firstreachablearea + i);
		} //end if
		//if the area is a portal
		if (aasworld.areasettings[otherareanum].contents & AREACONTENTS_CLUSTERPORTAL) continue;
		//if the area is already marked
		if (aasworld.areasettings[otherareanum].cluster) continue;
		//
		AAS_FloodCluster_r(otherareanum, clusternum);
	} //end for
} //end of the function AAS_FloodCluster_r
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_RemoveTeleporterPortals(void)
{
	int i, j, areanum;

	for (i = 1; i < aasworld.numareas; i++)
	{
		for (j = 0; j < aasworld.areasettings[i].numreachableareas; j++)
		{
			areanum = aasworld.reachability[aasworld.areasettings[i].firstreachablearea + j].areanum;
			if (aasworld.reachability[aasworld.areasettings[i].firstreachablearea + j].traveltype == TRAVEL_TELEPORT)
			{
				aasworld.areasettings[i].contents &= ~AREACONTENTS_CLUSTERPORTAL;
				aasworld.areasettings[areanum].contents &= ~AREACONTENTS_CLUSTERPORTAL;
				break;
			} //end if
		} //end for
	} //end for
} //end of the function AAS_RemoveTeleporterPortals
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_FloodClusterReachabilities(int clusternum)
{
	int i, j, areanum;

	for (i = 1; i < aasworld.numareas; i++)
	{
		//if this area already has a cluster set
		if (aasworld.areasettings[i].cluster) continue;
		//if this area is a cluster portal
		if (aasworld.areasettings[i].contents & AREACONTENTS_CLUSTERPORTAL) continue;
		//loop over the reachable areas from this area
		for (j = 0; j < aasworld.areasettings[i].numreachableareas; j++)
		{
			//the reachable area
			areanum = aasworld.reachability[aasworld.areasettings[i].firstreachablearea + j].areanum;
			//if this area is a cluster portal
			if (aasworld.areasettings[areanum].contents & AREACONTENTS_CLUSTERPORTAL) continue;
			//if this area has a cluster set
			if (aasworld.areasettings[areanum].cluster == clusternum)
			{
				AAS_FloodCluster_r(i, clusternum);
				i = 0;
				break;
			} //end if
		} //end for
	} //end for
} //end of the function AAS_FloodClusterReachabilities

//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_RemoveNotClusterClosingPortals(void)
{
	int i, j, k, facenum, otherareanum, nonclosingportals;
	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;
		//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 (!otherareanum) continue;
			//
			if (aasworld.areasettings[otherareanum].contents & AREACONTENTS_CLUSTERPORTAL)
			{
				continue;
			} //end if
			//reset all cluster fields
			AAS_RemoveClusterAreas();
			//
			AAS_FloodCluster_r(otherareanum, 1);
			AAS_FloodClusterReachabilities(1);
			//check if all adjacent non-portal areas have a cluster set
			for (k = 0; k < area->numfaces; k++)
			{
				facenum = abs(aasworld.faceindex[area->firstface + k]);
				face = &aasworld.faces[facenum];
				//
				if (face->frontarea != i) otherareanum = face->frontarea;
				else otherareanum = face->backarea;
				//
				if (!otherareanum) continue;
				//
				if (aasworld.areasettings[otherareanum].contents & AREACONTENTS_CLUSTERPORTAL)
				{
					continue;
				} //end if
				//
				if (!aasworld.areasettings[otherareanum].cluster) break;
			} //end for
			//if all adjacent non-portal areas have a cluster set then the portal
			//didn't seal a cluster
			if (k >= area->numfaces)
			{
				aasworld.areasettings[i].contents &= ~AREACONTENTS_CLUSTERPORTAL;
				nonclosingportals++;
				//recheck all the other portals again
				i = 0;
				break;
			} //end if
		} //end for
	} //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_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];
			//