Critical Importance: Finding Jump Apex

Why find the apex?

There are a few reasons all of which are critical to ensuring the best player experience and/or fidelity of the game

Player Expectations

It's critical the player can trust their expectations, especially in games with platforming or parkour movement mechanics such that they can learn how far the jump gets them, or the distance of a jump vs slide jump...etc.

If the movements aren't deterministic to reasonable accuracy players will miss judge movement actions and ultimately will lead to frustration at inconsistencies.

Level Designers

LDs need to know how far the player can move in certain situations so they can adequately build levels otherwise geometry might be too close, far, or downright impossible for the player to reach

• imagine a ledge up at the player's expected max height that's the only way out of a section of the game, but players with lower framerate can't reliably hit the expected max so they literally cannot complete the game

Lesser degree but still valid: Animation fidelity

Animators may want to play some special animation, or react in some way to the player reaching the apex

• Imagine the player punching the sky when they reach the apex

The list could go on to other areas as well like Audio, or VFX...etc depending on what the jump is for.

Why won't the apex be consistent?

Framerate and other factors affecting delta time.

All of the curves are read by reading values based off time, and DeltaTime controls the step size

JumpTime += aDeltaTime;
	...
float jumpCurveVal = JumpCurve->GetFloatValue(JumpTime);

This makes perfect sense for achieving framerate independent movement, however it does mean that at different frame rates the step size will be larger when reading from the graph, especially if there is some drop in frames mid jump.

It's small, but you can see the inconsistencies with the highest achieved apex

To illustrate it graphically, here we can see the jump curve with the apex in Green. The Yellow x's represent values of the curve sampled at each step size. Lets say a frame drop (Red) happens in which case the sample value was before, and after the Apex but never actually reaching the Apex

How to find the Jump Apex

Inspiration comes from Back Face Culling

We can actually use a similar method that rendering uses for back face culling in which we take the cross product of two sample vectors and compare the normal to determine directionality of the face.

In back face culling the computed is dotted against the viewing direction to determine if the face is pointing towards or away from the camera

Here instead of using the viewing direction, we're going to take 2 samples and compare the normals and whenever the normals point in different directions, apex has been found.

Finding normal along the curve given two points

You can think of the float curves just like vectors in 3D space.

Given a sample point on the graph P1 we can get the next sample point by just adding a step size to achieve P2.

P2-P1 gives us a vector in the direction of the "next value on the graph".

Time is constant in that it only increases, so you can imagine a constant vector pointing in the direction of time.

Taking the cross product of those two vectors yields a normal following right hand rule (even though Unreal is a left handed coordinate system) such that

Normal = CrossProduct(Time, P2-P1)

The great thing is depending on the sample points, the Normal will change depending on if we're going up or down the curve by the nature of the right hand rule

Normal.Z > 0 == up / out of the screen / towards you the reader
Normal.Z < 0 == down / into the screen / away from you the reader
    or
NDot = Dot(NormalA, NormalB) // as long as both vectors are normalized
    - NDot > 0 Vectors differ by < 90 degrees (roughly same direction)
    - NDot < 0 Vectors differ by > 90 degrees (roughly different direction)

Comparing Normals Iteratively to find where they differ

Start by taking 3 points on the curve, a constant step size, and creating vectors P2-P1, P3-P2 and finding the Normals then comparing them.

Continue as long as the Normals are in the same direction

Reduce step size and repeat

However once the Normals differ, then we know the Apex is somewhere between P1 & P3

Now we reduce the step size and rerun the computation.

Don't forget to update the new starting point for the next computation to be P1 and the end to be P3 rather than the min and max of the graph since we know it can only be within that range

The more times you run the computation with smaller and smaller step sizes (I chose to half the stepsize each time) the more accurate you'll be.

Since the curves are constant this algorithm can (and should) be run entirely outside of runtime and value for the apex stored in some asset data rather than having to do it at runtime since the curves cannot change at runtime.

Apex is midpoint between final start and end

Finally the apex will be at the midpoint between points P1 & P3

Notable mention

There are a few gatchas to watch out for which is why this function returns a bool as well as an out param, if the function returns false that means we have some degenerate case where no apex exists

• infinite curves (i.e. straight lines that don't have an apex)

Code

/*
*using iterative cross products to find where the normal changes from positive to negative (similar to graphics back face checking) which indicates slope changing from positive to negative (i.e. apex)
*Summary:
*	take 3 points (p1, p2, p3) on the curve which are all separated by a step size
*		if the normal for (p2-p1) > 0 and (p3-p2) < 0 then the apex is somewhere between p1 & p3
*			set new start to p1 and end to p3 and run again with reduced step sizes (halving step size each time)
*		
*	At any point if our step size leaves the range before finding an apex then we have an invalid graph (i.e. infinitely increasing or decreasing which has no apex)
*/
bool UDeftCharacterMovementComponent::FindJumpApexTime(float& outApexTime)
{
	// Time is a constant but needed in Vector form for cross products
	const FVector constTimeXAxis = FVector(1.f, 0.f, 0.f);

	float jumpMin, jumpApexHeight;
	JumpCurve->GetValueRange(jumpMin, jumpApexHeight);

	// Range of where we perform the graph  walking
	float startTime, endTime;
	JumpCurve->GetTimeRange(startTime, endTime);

	// how many times to find the estimated apex 
	// each iteration halves the step size so the more iterations the more accurate but more computationally costly
	int apexIterations = 5;
	float timeStepSize = 0.1f;
	bool isApexFound = false;
	
	// time values at various step sizes (increases as we walk the graph)
	float t1 = 0.f, t2 = 0.f, t3 = 0.f;

	// Each apexIteration narrows the range we step through which gives greater accuracy to the apex detection
	while (apexIterations != 0)
	{
		isApexFound = false;

		t1 = startTime;
		t2 = t1 + timeStepSize;
		t3 = FMath::Min(t2 + timeStepSize, endTime); // making sure the last step is always within our step range 

		if (t2 > endTime || t2 > t3)
		{
			// reached end of curve before finding an apex which means this is an invalid graph
			return false;
		}

		// step through the range defined by startTime and endTime looking for where slope changes from pos to neg
		while (!isApexFound)
		{
			// early out apex checks in case any of the time steps are exactly our apex
			float h1 = JumpCurve->GetFloatValue(t1);
			if (h1 == jumpApexHeight)
			{
				outApexTime = t1;
				return true;
			}

			float h2 = JumpCurve->GetFloatValue(t2);
			if (h2 == jumpApexHeight)
			{
				outApexTime = t2;
				return true;
			}

			float h3 = JumpCurve->GetFloatValue(t3);
			if (h3 == jumpApexHeight)
			{
				outApexTime = t3;
				return true;
			}

			// Compare cross product normals to check if a change in slope (pos -> neg) occurred indicating the apex is somewhere between [t1,t3]
			FVector p1, p2, p3;
			p1 = FVector(t1, h1, 0.f);
			p2 = FVector(t2, h2, 0.f);
			p3 = FVector(t3, h3, 0.f);

			const FVector timeBasisVector = FVector(1.f, 0.f, 0.f);
			FVector normal1 = FVector::CrossProduct(timeBasisVector, p2 - p1);
			FVector normal2 = FVector::CrossProduct(timeBasisVector, p3 - p2);

			if (normal1.Z == 0.f || normal2.Z == 0.f)
			{
				// handles curves which have 0 slope for an extended time
				// curve is parallel to time basis vector. Considering the flat part as apex
				outApexTime = t1;
				return true;
			}

			isApexFound = normal1.Z > 0.f && normal2.Z < 0.f;

			if (!isApexFound)
			{
				t1 += timeStepSize;
				t2 += timeStepSize;
				t3 += timeStepSize;
			}
		}

		--apexIterations;
		startTime = t1;
		endTime = t3;
		timeStepSize /= 2.f;
	}

	// apex time is the midpoint of our range
	outApexTime = (t3 + t1) / 2.f;

	return isApexFound;
}

Testing

I tested different framerates (120, 60, 30, 10) and they all reach the exact apex height 100% of the time.

ex: 226.78 is the apex height for all framerates