be_aas_reach.c

quakeIII源码这个不用我多说吧

				for (l = 0; l < groundface2->numedges; l++)
				{
					edge2num = abs(aasworld.edgeindex[groundface2->firstedge + l]);
					edge2 = &aasworld.edges[edge2num];
					//vertexes of the edge
					VectorCopy(aasworld.vertexes[edge2->v[0]], v3);
					VectorCopy(aasworld.vertexes[edge2->v[1]], v4);
					//check the distance between the two points and the vertical plane
					//through the edge of area1
					diff = DotProduct(normal, v3) - dist;
					if (diff < -0.1 || diff > 0.1) continue;
					diff = DotProduct(normal, v4) - dist;
					if (diff < -0.1 || diff > 0.1) continue;
					//
					//project the two ground edges into the step side plane
					//and calculate the shortest distance between the two
					//edges if they overlap in the direction orthogonal to
					//the gravity direction
					CrossProduct(invgravity, normal, ort);
					invgravitydot = DotProduct(invgravity, invgravity);
					ortdot = DotProduct(ort, ort);
					//projection into the step plane
					//NOTE: since gravity is vertical this is just the z coordinate
					y1 = v1[2];//DotProduct(v1, invgravity) / invgravitydot;
					y2 = v2[2];//DotProduct(v2, invgravity) / invgravitydot;
					y3 = v3[2];//DotProduct(v3, invgravity) / invgravitydot;
					y4 = v4[2];//DotProduct(v4, invgravity) / invgravitydot;
					//
					x1 = DotProduct(v1, ort) / ortdot;
					x2 = DotProduct(v2, ort) / ortdot;
					x3 = DotProduct(v3, ort) / ortdot;
					x4 = DotProduct(v4, ort) / ortdot;
					//
					if (x1 > x2)
					{
						tmp = x1; x1 = x2; x2 = tmp;
						tmp = y1; y1 = y2; y2 = tmp;
						VectorCopy(v1, tmpv); VectorCopy(v2, v1); VectorCopy(tmpv, v2);
					} //end if
					if (x3 > x4)
					{
						tmp = x3; x3 = x4; x4 = tmp;
						tmp = y3; y3 = y4; y4 = tmp;
						VectorCopy(v3, tmpv); VectorCopy(v4, v3); VectorCopy(tmpv, v4);
					} //end if
					//if the two projected edge lines have no overlap
					if (x2 <= x3 || x4 <= x1)
					{
//						Log_Write("lines no overlap: from area %d to %d\r\n", area1num, area2num);
						continue;
					} //end if
					//if the two lines fully overlap
					if ((x1 - 0.5 < x3 && x4 < x2 + 0.5) &&
							(x3 - 0.5 < x1 && x2 < x4 + 0.5))
					{
						dist1 = y3 - y1;
						dist2 = y4 - y2;
						VectorCopy(v1, p1area1);
						VectorCopy(v2, p2area1);
						VectorCopy(v3, p1area2);
						VectorCopy(v4, p2area2);
					} //end if
					else
					{
						//if the points are equal
						if (x1 > x3 - 0.1 && x1 < x3 + 0.1)
						{
							dist1 = y3 - y1;
							VectorCopy(v1, p1area1);
							VectorCopy(v3, p1area2);
						} //end if
						else if (x1 < x3)
						{
							y = y1 + (x3 - x1) * (y2 - y1) / (x2 - x1);
							dist1 = y3 - y;
							VectorCopy(v3, p1area1);
							p1area1[2] = y;
							VectorCopy(v3, p1area2);
						} //end if
						else
						{
							y = y3 + (x1 - x3) * (y4 - y3) / (x4 - x3);
							dist1 = y - y1;
							VectorCopy(v1, p1area1);
							VectorCopy(v1, p1area2);
							p1area2[2] = y;
						} //end if
						//if the points are equal
						if (x2 > x4 - 0.1 && x2 < x4 + 0.1)
						{
							dist2 = y4 - y2;
							VectorCopy(v2, p2area1);
							VectorCopy(v4, p2area2);
						} //end if
						else if (x2 < x4)
						{
							y = y3 + (x2 - x3) * (y4 - y3) / (x4 - x3);
							dist2 = y - y2;
							VectorCopy(v2, p2area1);
							VectorCopy(v2, p2area2);
							p2area2[2] = y;
						} //end if
						else
						{
							y = y1 + (x4 - x1) * (y2 - y1) / (x2 - x1);
							dist2 = y4 - y;
							VectorCopy(v4, p2area1);
							p2area1[2] = y;
							VectorCopy(v4, p2area2);
						} //end else
					} //end else
					//if both distances are pretty much equal
					//then we take the middle of the points
					if (dist1 > dist2 - 1 && dist1 < dist2 + 1)
					{
						dist = dist1;
						VectorAdd(p1area1, p2area1, start);
						VectorScale(start, 0.5, start);
						VectorAdd(p1area2, p2area2, end);
						VectorScale(end, 0.5, end);
					} //end if
					else if (dist1 < dist2)
					{
						dist = dist1;
						VectorCopy(p1area1, start);
						VectorCopy(p1area2, end);
					} //end else if
					else
					{
						dist = dist2;
						VectorCopy(p2area1, start);
						VectorCopy(p2area2, end);
					} //end else
					//get the length of the overlapping part of the edges of the two areas
					VectorSubtract(p2area2, p1area2, dir);
					length = VectorLength(dir);
					//
					if (groundface1->faceflags & FACE_GROUND)
					{
						//if the vertical distance is smaller
						if (dist < ground_bestdist ||
								//or the vertical distance is pretty much the same
								//but the overlapping part of the edges is longer
								(dist < ground_bestdist + 1 && length > ground_bestlength))
						{
							ground_bestdist = dist;
							ground_bestlength = length;
							ground_foundreach = qtrue;
							ground_bestarea2groundedgenum = edge1num;
							ground_bestface1 = groundface1;
							//best point towards area1
							VectorCopy(start, ground_beststart);
							//normal is pointing into area2
							VectorCopy(normal, ground_bestnormal);
							//best point towards area2
							VectorCopy(end, ground_bestend);
						} //end if
					} //end if
					else
					{
						//if the vertical distance is smaller
						if (dist < water_bestdist ||
								//or the vertical distance is pretty much the same
								//but the overlapping part of the edges is longer
								(dist < water_bestdist + 1 && length > water_bestlength))
						{
							water_bestdist = dist;
							water_bestlength = length;
							water_foundreach = qtrue;
							water_bestarea2groundedgenum = edge1num;
							water_bestface1 = groundface1;
							//best point towards area1
							VectorCopy(start, water_beststart);
							//normal is pointing into area2
							VectorCopy(normal, water_bestnormal);
							//best point towards area2
							VectorCopy(end, water_bestend);
						} //end if
					} //end else
				} //end for
			} //end for
		} //end for
	} //end for
	//
	// NOTE: swim reachabilities are already filtered out
	//
	// Steps
	//
	//        ---------
	//        |          step height -> TRAVEL_WALK
	//--------|
	//
	//        ---------
	//~~~~~~~~|          step height and low water -> TRAVEL_WALK
	//--------|
	//
	//~~~~~~~~~~~~~~~~~~
	//        ---------
	//        |          step height and low water up to the step -> TRAVEL_WALK
	//--------|
	//
	//check for a step reachability
	if (ground_foundreach)
	{
		//if area2 is higher but lower than the maximum step height
		//NOTE: ground_bestdist >= 0 also catches equal floor reachabilities
		if (ground_bestdist >= 0 && ground_bestdist < aassettings.phys_maxstep)
		{
			//create walk reachability from area1 to area2
			lreach = AAS_AllocReachability();
			if (!lreach) return qfalse;
			lreach->areanum = area2num;
			lreach->facenum = 0;
			lreach->edgenum = ground_bestarea2groundedgenum;
			VectorMA(ground_beststart, INSIDEUNITS_WALKSTART, ground_bestnormal, lreach->start);
			VectorMA(ground_bestend, INSIDEUNITS_WALKEND, ground_bestnormal, lreach->end);
			lreach->traveltype = TRAVEL_WALK;
			lreach->traveltime = 0;//1;
			//if going into a crouch area
			if (!AAS_AreaCrouch(area1num) && AAS_AreaCrouch(area2num))
			{
				lreach->traveltime += aassettings.rs_startcrouch;
			} //end if
			lreach->next = areareachability[area1num];
			areareachability[area1num] = lreach;
			//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_step++;
			return qtrue;
		} //end if
	} //end if
	//
	// Water Jumps
	//
	//        ---------
	//        |
	//~~~~~~~~|
	//        |
	//        |          higher than step height and water up to waterjump height -> TRAVEL_WATERJUMP
	//--------|
	//
	//~~~~~~~~~~~~~~~~~~
	//        ---------
	//        |
	//        |
	//        |
	//        |          higher than step height and low water up to the step -> TRAVEL_WATERJUMP
	//--------|
	//
	//check for a waterjump reachability
	if (water_foundreach)
	{
		//get a test point a little bit towards area1
		VectorMA(water_bestend, -INSIDEUNITS, water_bestnormal, testpoint);
		//go down the maximum waterjump height
		testpoint[2] -= aassettings.phys_maxwaterjump;
		//if there IS water the sv_maxwaterjump height below the bestend point
		if (aasworld.areasettings[AAS_PointAreaNum(testpoint)].areaflags & AREA_LIQUID)
		{
			//don't create rediculous water jump reachabilities from areas very far below
			//the water surface
			if (water_bestdist < aassettings.phys_maxwaterjump + 24)
			{
				//waterjumping from or towards a crouch only area is not possible in Quake2
				if ((aasworld.areasettings[area1num].presencetype & PRESENCE_NORMAL) &&
						(aasworld.areasettings[area2num].presencetype & PRESENCE_NORMAL))
				{
					//create water jump reachability from area1 to area2
					lreach = AAS_AllocReachability();
					if (!lreach) return qfalse;
					lreach->areanum = area2num;
					lreach->facenum = 0;
					lreach->edgenum = water_bestarea2groundedgenum;
					VectorCopy(water_beststart, lreach->start);
					VectorMA(water_bestend, INSIDEUNITS_WATERJUMP, water_bestnormal, lreach->end);
					lreach->traveltype = TRAVEL_WATERJUMP;
					lreach->traveltime = aassettings.rs_waterjump;
					lreach->next = areareachability[area1num];
					areareachability[area1num] = lreach;
					//we've got another waterjump reachability
					reach_waterjump++;
					return qtrue;
				} //end if
			} //end if
		} //end if
	} //end if
	//
	// Barrier Jumps
	//
	//        ---------
	//        |
	//        |
	//        |
	//        |         higher than step height lower than barrier height -> TRAVEL_BARRIERJUMP
	//--------|
	//
	//        ---------
	//        |
	//        |
	//        |
	//~~~~~~~~|         higher than step height lower than barrier height
	//--------|         and a thin layer of water in the area to jump from -> TRAVEL_BARRIERJUMP
	//
	//check for a barrier jump reachability
	if (ground_foundreach)
	{
		//if area2 is higher but lower than the maximum barrier jump height
		if (ground_bestdist > 0 && ground_bestdist < aassettings.phys_maxbarrier)
		{
			//if no water in area1 or a very thin layer of water on the ground
			if (!water_foundreach || (ground_bestdist - water_bestdist < 16))
			{
				//cannot perform a barrier jump towards or from a crouch area in Quake2
				if (!AAS_AreaCrouch(area1num) && !AAS_AreaCrouch(area2num))
				{
					//create barrier jump reachability from area1 to area2
					lreach = AAS_AllocReachability();
					if (!lreach) return qfalse;
					lreach->areanum = area2num;
					lreach->facenum = 0;
					lreach->edgenum = ground_bestarea2groundedgenum;
					VectorMA(ground_beststart, INSIDEUNITS_WALKSTART, ground_bestnormal, lreach->start);
					VectorMA(ground_bestend, INSIDEUNITS_WALKEND, ground_bestnormal, lreach->end);
					lreach->traveltype = TRAVEL_BARRIERJUMP;
					lreach->traveltime = aassettings.rs_barrierjump;//AAS_BarrierJumpTravelTime();
					lreach->next = areareachability[area1num];
					areareachability[area1num] = lreach;
					//we've got another barrierjump reachability
					reach_barrier++;
					return qtrue;
				} //end if
			} //end if
		} //end if
	} //end if
	//
	// Walk and Walk Off Ledge
	//
	//--------|
	//        |          can walk or step back -> TRAVEL_WALK
	//        ---------
	//
	//--------|
	//        |
	//        |
	//        |
	//        |          cannot walk/step back -> TRAVEL_WALKOFFLEDGE
	//        ---------
	//
	//--------|
	//        |
	//        |~~~~~~~~
	//        |
	//        |          cannot step back but can waterjump back -> TRAVEL_WALKOFFLEDGE
	//        ---------  FIXME: create TRAVEL_WALK reach??
	//
	//check for a walk or walk off ledge reachability
	if (ground_foundreach)
	{
		if (ground_bestdist < 0)
		{
			if (ground_bestdist > -aassettings.phys_maxstep)
			{
				//create walk reachability from area1 to area2
				lreach = AAS_AllocReachability();
				if (!lreach) return qfalse;
				lreach->areanum = area2num;
				lreach->facenum = 0;
				lreach->edgenum = ground_bestarea2groundedgenum;
				VectorMA(ground_beststart, INSIDEUNITS_WALKSTART, ground_bestnormal, lreach->start);
				VectorMA(ground_bestend, INSIDEUNITS_WALKEND, ground_bestnormal, lreach->end);
				lreach->traveltype = TRAVEL_WALK;
				lreach->traveltime = 1;
				lreach->next = areareachability[area1num];
				areareachability[area1num] = lreach;
				//we've got another walk reachability
				reach_walk++;
				return qtrue;