be_aas_reach.c

quakeIII源码这个不用我多说吧

// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
unsigned short int AAS_BarrierJumpTravelTime(void)
{
	return aassettings.phys_jumpvel / (aassettings.phys_gravity * 0.1);
} //end op the function AAS_BarrierJumpTravelTime
//===========================================================================
// returns true if there already exists a reachability from area1 to area2
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
qboolean AAS_ReachabilityExists(int area1num, int area2num)
{
	aas_lreachability_t *r;

	for (r = areareachability[area1num]; r; r = r->next)
	{
		if (r->areanum == area2num) return qtrue;
	} //end for
	return qfalse;
} //end of the function AAS_ReachabilityExists
//===========================================================================
// returns true if there is a solid just after the end point when going
// from start to end
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_NearbySolidOrGap(vec3_t start, vec3_t end)
{
	vec3_t dir, testpoint;
	int areanum;

	VectorSubtract(end, start, dir);
	dir[2] = 0;
	VectorNormalize(dir);
	VectorMA(end, 48, dir, testpoint);

	areanum = AAS_PointAreaNum(testpoint);
	if (!areanum)
	{
		testpoint[2] += 16;
		areanum = AAS_PointAreaNum(testpoint);
		if (!areanum) return qtrue;
	} //end if
	VectorMA(end, 64, dir, testpoint);
	areanum = AAS_PointAreaNum(testpoint);
	if (areanum)
	{
		if (!AAS_AreaSwim(areanum) && !AAS_AreaGrounded(areanum)) return qtrue;
	} //end if
	return qfalse;
} //end of the function AAS_SolidGapTime
//===========================================================================
// searches for swim reachabilities between adjacent areas
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_Reachability_Swim(int area1num, int area2num)
{
	int i, j, face1num, face2num, side1;
	aas_area_t *area1, *area2;
	aas_areasettings_t *areasettings;
	aas_lreachability_t *lreach;
	aas_face_t *face1;
	aas_plane_t *plane;
	vec3_t start;

	if (!AAS_AreaSwim(area1num) || !AAS_AreaSwim(area2num)) return qfalse;
	//if the second area is crouch only
	if (!(aasworld.areasettings[area2num].presencetype & PRESENCE_NORMAL)) return qfalse;

	area1 = &aasworld.areas[area1num];
	area2 = &aasworld.areas[area2num];

	//if the areas are not near anough
	for (i = 0; i < 3; i++)
	{
		if (area1->mins[i] > area2->maxs[i] + 10) return qfalse;
		if (area1->maxs[i] < area2->mins[i] - 10) return qfalse;
	} //end for
	//find a shared face and create a reachability link
	for (i = 0; i < area1->numfaces; i++)
	{
		face1num = aasworld.faceindex[area1->firstface + i];
		side1 = face1num < 0;
		face1num = abs(face1num);
		//
		for (j = 0; j < area2->numfaces; j++)
		{
			face2num = abs(aasworld.faceindex[area2->firstface + j]);
			//
			if (face1num == face2num)
			{
				AAS_FaceCenter(face1num, start);
				//
				if (AAS_PointContents(start) & (CONTENTS_LAVA|CONTENTS_SLIME|CONTENTS_WATER))
				{
					//
					face1 = &aasworld.faces[face1num];
					areasettings = &aasworld.areasettings[area1num];
					//create a new reachability link
					lreach = AAS_AllocReachability();
					if (!lreach) return qfalse;
					lreach->areanum = area2num;
					lreach->facenum = face1num;
					lreach->edgenum = 0;
					VectorCopy(start, lreach->start);
					plane = &aasworld.planes[face1->planenum ^ side1];
					VectorMA(lreach->start, -INSIDEUNITS, plane->normal, lreach->end);
					lreach->traveltype = TRAVEL_SWIM;
					lreach->traveltime = 1;
					//if the volume of the area is rather small
					if (AAS_AreaVolume(area2num) < 800)
						lreach->traveltime += 200;
					//if (!(AAS_PointContents(start) & MASK_WATER)) lreach->traveltime += 500;
					//link the reachability
					lreach->next = areareachability[area1num];
					areareachability[area1num] = lreach;
					reach_swim++;
					return qtrue;
				} //end if
			} //end if
		} //end for
	} //end for
	return qfalse;
} //end of the function AAS_Reachability_Swim
//===========================================================================
// searches for reachabilities between adjacent areas with equal floor
// heights
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_Reachability_EqualFloorHeight(int area1num, int area2num)
{
	int i, j, edgenum, edgenum1, edgenum2, foundreach, side;
	float height, bestheight, length, bestlength;
	vec3_t dir, start, end, normal, invgravity, gravitydirection = {0, 0, -1};
	vec3_t edgevec;
	aas_area_t *area1, *area2;
	aas_face_t *face1, *face2;
	aas_edge_t *edge;
	aas_plane_t *plane2;
	aas_lreachability_t lr, *lreach;

	if (!AAS_AreaGrounded(area1num) || !AAS_AreaGrounded(area2num)) return qfalse;

	area1 = &aasworld.areas[area1num];
	area2 = &aasworld.areas[area2num];
	//if the areas are not near anough in the x-y direction
	for (i = 0; i < 2; i++)
	{
		if (area1->mins[i] > area2->maxs[i] + 10) return qfalse;
		if (area1->maxs[i] < area2->mins[i] - 10) return qfalse;
	} //end for
	//if area 2 is too high above area 1
	if (area2->mins[2] > area1->maxs[2]) return qfalse;
	//
	VectorCopy(gravitydirection, invgravity);
	VectorInverse(invgravity);
	//
	bestheight = 99999;
	bestlength = 0;
	foundreach = qfalse;
	Com_Memset(&lr, 0, sizeof(aas_lreachability_t)); //make the compiler happy
	//
	//check if the areas have ground faces with a common edge
	//if existing use the lowest common edge for a reachability link
	for (i = 0; i < area1->numfaces; i++)
	{
		face1 = &aasworld.faces[abs(aasworld.faceindex[area1->firstface + i])];
		if (!(face1->faceflags & FACE_GROUND)) continue;
		//
		for (j = 0; j < area2->numfaces; j++)
		{
			face2 = &aasworld.faces[abs(aasworld.faceindex[area2->firstface + j])];
			if (!(face2->faceflags & FACE_GROUND)) continue;
			//if there is a common edge
			for (edgenum1 = 0; edgenum1 < face1->numedges; edgenum1++)
			{
				for (edgenum2 = 0; edgenum2 < face2->numedges; edgenum2++)
				{
					if (abs(aasworld.edgeindex[face1->firstedge + edgenum1]) !=
							abs(aasworld.edgeindex[face2->firstedge + edgenum2]))
									continue;
					edgenum = aasworld.edgeindex[face1->firstedge + edgenum1];
					side = edgenum < 0;
					edge = &aasworld.edges[abs(edgenum)];
					//get the length of the edge
					VectorSubtract(aasworld.vertexes[edge->v[1]],
								aasworld.vertexes[edge->v[0]], dir);
					length = VectorLength(dir);
					//get the start point
					VectorAdd(aasworld.vertexes[edge->v[0]],
								aasworld.vertexes[edge->v[1]], start);
					VectorScale(start, 0.5, start);
					VectorCopy(start, end);
					//get the end point several units inside area2
					//and the start point several units inside area1
					//NOTE: normal is pointing into area2 because the
					//face edges are stored counter clockwise
					VectorSubtract(aasworld.vertexes[edge->v[side]],
								aasworld.vertexes[edge->v[!side]], edgevec);
					plane2 = &aasworld.planes[face2->planenum];
					CrossProduct(edgevec, plane2->normal, normal);
					VectorNormalize(normal);
					//
					//VectorMA(start, -1, normal, start);
					VectorMA(end, INSIDEUNITS_WALKEND, normal, end);
					VectorMA(start, INSIDEUNITS_WALKSTART, normal, start);
					end[2] += 0.125;
					//
					height = DotProduct(invgravity, start);
					//NOTE: if there's nearby solid or a gap area after this area
					//disabled this crap
					//if (AAS_NearbySolidOrGap(start, end)) height += 200;
					//NOTE: disabled because it disables reachabilities to very small areas
					//if (AAS_PointAreaNum(end) != area2num) continue;
					//get the longest lowest edge
					if (height < bestheight ||
							(height < bestheight + 1 && length > bestlength))
					{
						bestheight = height;
						bestlength = length;
						//create a new reachability link
						lr.areanum = area2num;
						lr.facenum = 0;
						lr.edgenum = edgenum;
						VectorCopy(start, lr.start);
						VectorCopy(end, lr.end);
						lr.traveltype = TRAVEL_WALK;
						lr.traveltime = 1;
						foundreach = qtrue;
					} //end if
				} //end for
			} //end for
		} //end for
	} //end for
	if (foundreach)
	{
		//create a new reachability link
		lreach = AAS_AllocReachability();
		if (!lreach) return qfalse;
		lreach->areanum = lr.areanum;
		lreach->facenum = lr.facenum;
		lreach->edgenum = lr.edgenum;
		VectorCopy(lr.start, lreach->start);
		VectorCopy(lr.end, lreach->end);
		lreach->traveltype = lr.traveltype;
		lreach->traveltime = lr.traveltime;
		lreach->next = areareachability[area1num];
		areareachability[area1num] = lreach;
		//if going into a crouch area
		if (!AAS_AreaCrouch(area1num) && AAS_AreaCrouch(area2num))
		{
			lreach->traveltime += aassettings.rs_startcrouch;
		} //end if
		/*
		//NOTE: if there's nearby solid or a gap area after this area
		if (!AAS_NearbySolidOrGap(lreach->start, lreach->end))
		{
			lreach->traveltime += 100;
		} //end if
		*/
		//avoid rather small areas
		//if (AAS_AreaGroundFaceArea(lreach->areanum) < 500) lreach->traveltime += 100;
		//
		reach_equalfloor++;
		return qtrue;
	} //end if
	return qfalse;
} //end of the function AAS_Reachability_EqualFloorHeight
//===========================================================================
// searches step, barrier, waterjump and walk off ledge reachabilities
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_Reachability_Step_Barrier_WaterJump_WalkOffLedge(int area1num, int area2num)
{
	int i, j, k, l, edge1num, edge2num, areas[10], numareas;
	int ground_bestarea2groundedgenum, ground_foundreach;
	int water_bestarea2groundedgenum, water_foundreach;
	int side1, area1swim, faceside1, groundface1num;
	float dist, dist1, dist2, diff, invgravitydot, ortdot;
	float x1, x2, x3, x4, y1, y2, y3, y4, tmp, y;
	float length, ground_bestlength, water_bestlength, ground_bestdist, water_bestdist;
	vec3_t v1, v2, v3, v4, tmpv, p1area1, p1area2, p2area1, p2area2;
	vec3_t normal, ort, edgevec, start, end, dir;
	vec3_t ground_beststart, ground_bestend, ground_bestnormal;
	vec3_t water_beststart, water_bestend, water_bestnormal;
	vec3_t invgravity = {0, 0, 1};
	vec3_t testpoint;
	aas_plane_t *plane;
	aas_area_t *area1, *area2;
	aas_face_t *groundface1, *groundface2, *ground_bestface1, *water_bestface1;
	aas_edge_t *edge1, *edge2;
	aas_lreachability_t *lreach;
	aas_trace_t trace;

	//must be able to walk or swim in the first area
	if (!AAS_AreaGrounded(area1num) && !AAS_AreaSwim(area1num)) return qfalse;
	//
	if (!AAS_AreaGrounded(area2num) && !AAS_AreaSwim(area2num)) return qfalse;
	//
	area1 = &aasworld.areas[area1num];
	area2 = &aasworld.areas[area2num];
	//if the first area contains a liquid
	area1swim = AAS_AreaSwim(area1num);
	//if the areas are not near anough in the x-y direction
	for (i = 0; i < 2; i++)
	{
		if (area1->mins[i] > area2->maxs[i] + 10) return qfalse;
		if (area1->maxs[i] < area2->mins[i] - 10) return qfalse;
	} //end for
	//
	ground_foundreach = qfalse;
	ground_bestdist = 99999;
	ground_bestlength = 0;
	ground_bestarea2groundedgenum = 0;
	//
	water_foundreach = qfalse;
	water_bestdist = 99999;
	water_bestlength = 0;
	water_bestarea2groundedgenum = 0;
	//
	for (i = 0; i < area1->numfaces; i++)
	{
		groundface1num = aasworld.faceindex[area1->firstface + i];
		faceside1 = groundface1num < 0;
		groundface1 = &aasworld.faces[abs(groundface1num)];
		//if this isn't a ground face
		if (!(groundface1->faceflags & FACE_GROUND))
		{
			//if we can swim in the first area
			if (area1swim)
			{
				//face plane must be more or less horizontal
				plane = &aasworld.planes[groundface1->planenum ^ (!faceside1)];
				if (DotProduct(plane->normal, invgravity) < 0.7) continue;
			} //end if
			else
			{
				//if we can't swim in the area it must be a ground face
				continue;
			} //end else
		} //end if
		//
		for (k = 0; k < groundface1->numedges; k++)
		{
			edge1num = aasworld.edgeindex[groundface1->firstedge + k];
			side1 = (edge1num < 0);
			//NOTE: for water faces we must take the side area 1 is
			// on into account because the face is shared and doesn't
			// have to be oriented correctly
			if (!(groundface1->faceflags & FACE_GROUND)) side1 = (side1 == faceside1);
			edge1num = abs(edge1num);
			edge1 = &aasworld.edges[edge1num];
			//vertexes of the edge
			VectorCopy(aasworld.vertexes[edge1->v[!side1]], v1);
			VectorCopy(aasworld.vertexes[edge1->v[side1]], v2);
			//get a vertical plane through the edge
			//NOTE: normal is pointing into area 2 because the
			//face edges are stored counter clockwise
			VectorSubtract(v2, v1, edgevec);
			CrossProduct(edgevec, invgravity, normal);
			VectorNormalize(normal);
			dist = DotProduct(normal, v1);
			//check the faces from the second area
			for (j = 0; j < area2->numfaces; j++)
			{
				groundface2 = &aasworld.faces[abs(aasworld.faceindex[area2->firstface + j])];
				//must be a ground face
				if (!(groundface2->faceflags & FACE_GROUND)) continue;
				//check the edges of this ground face