Dev Blog #02 – Smoothing a path for Terrator
The last week we’ve been implementing a new enemy in “Something Ate My Alien” called “Terrator”.
He’s much larger than the other enemies, and he’s a worm like creature that we wanted to randomly appear, work its way across the screen and ‘Eat’ our alien if he gets in the way.
Kat created the art, and split it up into sprites for each of the ‘worm’ sections, head, body and tail.
We didn’t want to create a random path as it was moving, because we wanted more control over him. So we decide to plan out a batch of paths that he should follow and then just pick one at random during spawn. To mix things up a bit, the path should be offset by a random number of pixels, and his start position relative to the path should also change. We also allowed it to be ‘flipped’ randomly to create more variation.
We planned out a path with about 15 or so points, and then used a smoothing algorithm called “Chaikin’s Algorithm” to create a smooth path.
Chaikin is nice and quick, not 100% accurate though, because of the way it works, the result doesn’t pass through the original points, but its good enough for what we needed it for.
It works by ‘cutting corners’ off each point to create a more smoothed curve, and then repeating 3 or 4 times makes it get smoother and smoother. We found 4 times was good enough to make Terrator animate smoothly in the game.
I found a C# example which helped, here: C# Smoothing Path
Although it was a quick algorithm, the implementation I found actually created quite a bit of C# Garbage, so I looked into re-writing it to remove any Garbage.
Now, rather than creating a new array on every smooth pass, you can pre-create an big array, and then it fills in that one array.
So now it was generating zero Garbage during game play. Yay!!
And as a bonus, with a bit of extra tweaking, I got it to process faster also. For 15 original points and smoothing 4 times, the original routine took about 1.22ms and allocated 3.3kb of Garbage. My new one took 1.05ms and allocated none.
Here is a video clip of it in game:
Here is the barebones C# code I wrote for Unity, to generate the smooth curve if anyone else might find it useful:
// Setup smooth info
int smoothness = 4;
int NumMainPoints = 15;
Vector2[] smoothPoints = new Vector2[(NumMainPoints - 2) * (int)Mathf.Pow(2,smoothness) + 2];
Vector2 startpoint = new Vector2(25,50);
Vector2 centerPoint = new Vector2(50,50);
smoothPoints[0] = startpoint;
smoothPoints[1] = startpoint + new Vector2(8,0);
smoothPoints[2] = startpoint + new Vector2((8 + 2),0);
smoothPoints[3] = centerPoint + new Vector2(-6.0f, 0.5f);
smoothPoints[4] = centerPoint + new Vector2(-2.0f, -1.5f);
smoothPoints[5] = centerPoint + new Vector2(1.5f, 0.5f);
smoothPoints[6] = centerPoint + new Vector2(5.0f, -2.5f);
smoothPoints[7] = centerPoint + new Vector2(2.5f, -5.5f);
smoothPoints[8] = centerPoint + new Vector2(-3.0f, -3.0f);
smoothPoints[9] = centerPoint + new Vector2(-4.5f, -0.5f);
smoothPoints[10] = centerPoint + new Vector2(-2.5f, 2.0f);
smoothPoints[11] = centerPoint + new Vector2(1.5f, 2.5f);
smoothPoints[12] = centerPoint + new Vector2(5.0f, 2.0f);
smoothPoints[13] = centerPoint + new Vector2(9.0f, 2.5f);
smoothPoints[14] = centerPoint + new Vector2(150, -0.5f);
ChaikinFast(ref smoothPoints, smoothness, NumMainPoints);
private void ChaikinFast(ref Vector2[] smoothPoints, int smoothness, int NumMainPoints) {
Vector2 lastVector = smoothPoints[NumMainPoints - 1]; // Save last point
int p = NumMainPoints - 2;
int factor = 2;
int lastPoint;
Vector2 offsetRight, offsetLeft;
// Loop through mulitple times to smooth
for (int s=1; s<=smoothness; s++) {
lastPoint = (NumMainPoints - 2) * factor;
offsetRight = (smoothPoints[p+1] - smoothPoints[p]) * 0.25f;
// For each point, replace with 2,
// with each one being 25% more towards the left and right points
for (int n=lastPoint; n>1; n-=2) {
offsetLeft = (smoothPoints[p] - smoothPoints[p-1]) * 0.25f;
smoothPoints[n] = smoothPoints[p] + offsetRight;
smoothPoints[n-1] = smoothPoints[p] - offsetLeft;
offsetRight = offsetLeft;
p--;
}
// Prepare for next loop
p = lastPoint;
smoothPoints[p+1] = lastVector; // Copy the end point to the end
factor *= 2;
}
}
