be_aas_cluster.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_cluster.c
 *
 * desc:		area clustering
 *
 * $Archive: /MissionPack/code/botlib/be_aas_cluster.c $
 *
 *****************************************************************************/

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

extern botlib_import_t botimport;

#define AAS_MAX_PORTALS					65536
#define AAS_MAX_PORTALINDEXSIZE			65536
#define AAS_MAX_CLUSTERS				65536
//
#define MAX_PORTALAREAS			1024

// do not flood through area faces, only use reachabilities
int nofaceflood = qtrue;

//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_RemoveClusterAreas(void)
{
	int i;

	for (i = 1; i < aasworld.numareas; i++)
	{
		aasworld.areasettings[i].cluster = 0;
	} //end for
} //end of the function AAS_RemoveClusterAreas
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_ClearCluster(int clusternum)
{
	int i;

	for (i = 1; i < aasworld.numareas; i++)
	{
		if (aasworld.areasettings[i].cluster == clusternum)
		{
			aasworld.areasettings[i].cluster = 0;
		} //end if
	} //end for
} //end of the function AAS_ClearCluster
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_RemovePortalsClusterReference(int clusternum)
{
	int portalnum;

	for (portalnum = 1; portalnum < aasworld.numportals; portalnum++)
	{
		if (aasworld.portals[portalnum].frontcluster == clusternum)
		{
			aasworld.portals[portalnum].frontcluster = 0;
		} //end if
		if (aasworld.portals[portalnum].backcluster == clusternum)
		{
			aasworld.portals[portalnum].backcluster = 0;
		} //end if
	} //end for
} //end of the function AAS_RemovePortalsClusterReference
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_UpdatePortal(int areanum, int clusternum)
{
	int portalnum;
	aas_portal_t *portal;
	aas_cluster_t *cluster;

	//find the portal of the area
	for (portalnum = 1; portalnum < aasworld.numportals; portalnum++)
	{
		if (aasworld.portals[portalnum].areanum == areanum) break;
	} //end for
	//
	if (portalnum == aasworld.numportals)
	{
		AAS_Error("no portal of area %d", areanum);
		return qtrue;
	} //end if
	//
	portal = &aasworld.portals[portalnum];
	//if the portal is already fully updated
	if (portal->frontcluster == clusternum) return qtrue;
	if (portal->backcluster == clusternum) return qtrue;
	//if the portal has no front cluster yet
	if (!portal->frontcluster)
	{
		portal->frontcluster = clusternum;
	} //end if
	//if the portal has no back cluster yet
	else if (!portal->backcluster)
	{
		portal->backcluster = clusternum;
	} //end else if
	else
	{
		//remove the cluster portal flag contents
		aasworld.areasettings[areanum].contents &= ~AREACONTENTS_CLUSTERPORTAL;
		Log_Write("portal area %d is seperating more than two clusters\r\n", areanum);
		return qfalse;
	} //end else
	if (aasworld.portalindexsize >= AAS_MAX_PORTALINDEXSIZE)
	{
		AAS_Error("AAS_MAX_PORTALINDEXSIZE");
		return qtrue;
	} //end if
	//set the area cluster number to the negative portal number
	aasworld.areasettings[areanum].cluster = -portalnum;
	//add the portal to the cluster using the portal index
	cluster = &aasworld.clusters[clusternum];
	aasworld.portalindex[cluster->firstportal + cluster->numportals] = portalnum;
	aasworld.portalindexsize++;
	cluster->numportals++;
	return qtrue;
} //end of the function AAS_UpdatePortal
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_FloodClusterAreas_r(int areanum, int clusternum)
{
	aas_area_t *area;
	aas_face_t *face;
	int facenum, i;

	//
	if (areanum <= 0 || areanum >= aasworld.numareas)
	{
		AAS_Error("AAS_FloodClusterAreas_r: areanum out of range");
		return qfalse;
	} //end if
	//if the area is already part of a cluster
	if (aasworld.areasettings[areanum].cluster > 0)
	{
		if (aasworld.areasettings[areanum].cluster == clusternum) return qtrue;
		//
		//there's a reachability going from one cluster to another only in one direction
		//
		AAS_Error("cluster %d touched cluster %d at area %d\r\n",
				clusternum, aasworld.areasettings[areanum].cluster, areanum);
		return qfalse;
	} //end if
	//don't add the cluster portal areas to the clusters
	if (aasworld.areasettings[areanum].contents & AREACONTENTS_CLUSTERPORTAL)
	{
		return AAS_UpdatePortal(areanum, clusternum);
	} //end if
	//set the area cluster number
	aasworld.areasettings[areanum].cluster = clusternum;
	aasworld.areasettings[areanum].clusterareanum =
				aasworld.clusters[clusternum].numareas;
	//the cluster has an extra area
	aasworld.clusters[clusternum].numareas++;

	area = &aasworld.areas[areanum];
	//use area faces to flood into adjacent areas
	if (!nofaceflood)
	{
		for (i = 0; i < area->numfaces; i++)
		{
			facenum = abs(aasworld.faceindex[area->firstface + i]);
			face = &aasworld.faces[facenum];
			if (face->frontarea == areanum)
			{
				if (face->backarea) if (!AAS_FloodClusterAreas_r(face->backarea, clusternum)) return qfalse;
			} //end if
			else
			{
				if (face->frontarea) if (!AAS_FloodClusterAreas_r(face->frontarea, clusternum)) return qfalse;
			} //end else
		} //end for
	} //end if
	//use the reachabilities to flood into other areas
	for (i = 0; i < aasworld.areasettings[areanum].numreachableareas; i++)
	{
		if (!aasworld.reachability[
					aasworld.areasettings[areanum].firstreachablearea + i].areanum)
		{
			continue;
		} //end if
		if (!AAS_FloodClusterAreas_r(aasworld.reachability[
				aasworld.areasettings[areanum].firstreachablearea + i].areanum, clusternum)) return qfalse;
	} //end for
	return qtrue;
} //end of the function AAS_FloodClusterAreas_r
//===========================================================================
// try to flood from all areas without cluster into areas with a cluster set
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_FloodClusterAreasUsingReachabilities(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)
			{
				if (!AAS_FloodClusterAreas_r(i, clusternum))
					return qfalse;
				i = 0;
				break;
			} //end if
		} //end for
	} //end for
	return qtrue;
} //end of the function AAS_FloodClusterAreasUsingReachabilities
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void AAS_NumberClusterPortals(int clusternum)
{
	int i, portalnum;
	aas_cluster_t *cluster;
	aas_portal_t *portal;

	cluster = &aasworld.clusters[clusternum];
	for (i = 0; i < cluster->numportals; i++)
	{
		portalnum = aasworld.portalindex[cluster->firstportal + i];
		portal = &aasworld.portals[portalnum];
		if (portal->frontcluster == clusternum)
		{
			portal->clusterareanum[0] = cluster->numareas++;
		} //end if
		else
		{
			portal->clusterareanum[1] = cluster->numareas++;
		} //end else
	} //end for
} //end of the function AAS_NumberClusterPortals
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void AAS_NumberClusterAreas(int clusternum)
{
	int i, portalnum;
	aas_cluster_t *cluster;
	aas_portal_t *portal;

	aasworld.clusters[clusternum].numareas = 0;
	aasworld.clusters[clusternum].numreachabilityareas = 0;
	//number all areas in this cluster WITH reachabilities
	for (i = 1; i < aasworld.numareas; i++)
	{
		//
		if (aasworld.areasettings[i].cluster != clusternum) continue;
		//
		if (!AAS_AreaReachability(i)) continue;
		//
		aasworld.areasettings[i].clusterareanum = aasworld.clusters[clusternum].numareas;
		//the cluster has an extra area
		aasworld.clusters[clusternum].numareas++;
		aasworld.clusters[clusternum].numreachabilityareas++;
	} //end for
	//number all portals in this cluster WITH reachabilities
	cluster = &aasworld.clusters[clusternum];
	for (i = 0; i < cluster->numportals; i++)
	{
		portalnum = aasworld.portalindex[cluster->firstportal + i];
		portal = &aasworld.portals[portalnum];
		if (!AAS_AreaReachability(portal->areanum)) continue;
		if (portal->frontcluster == clusternum)
		{
			portal->clusterareanum[0] = cluster->numareas++;
			aasworld.clusters[clusternum].numreachabilityareas++;
		} //end if
		else
		{
			portal->clusterareanum[1] = cluster->numareas++;
			aasworld.clusters[clusternum].numreachabilityareas++;
		} //end else
	} //end for
	//number all areas in this cluster WITHOUT reachabilities
	for (i = 1; i < aasworld.numareas; i++)
	{
		//
		if (aasworld.areasettings[i].cluster != clusternum) continue;
		//
		if (AAS_AreaReachability(i)) continue;
		//
		aasworld.areasettings[i].clusterareanum = aasworld.clusters[clusternum].numareas;
		//the cluster has an extra area
		aasworld.clusters[clusternum].numareas++;
	} //end for
	//number all portals in this cluster WITHOUT reachabilities
	cluster = &aasworld.clusters[clusternum];
	for (i = 0; i < cluster->numportals; i++)
	{
		portalnum = aasworld.portalindex[cluster->firstportal + i];
		portal = &aasworld.portals[portalnum];
		if (AAS_AreaReachability(portal->areanum)) continue;
		if (portal->frontcluster == clusternum)
		{
			portal->clusterareanum[0] = cluster->numareas++;
		} //end if
		else
		{
			portal->clusterareanum[1] = cluster->numareas++;
		} //end else
	} //end for
} //end of the function AAS_NumberClusterAreas
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-