Variable Timesteps and Holy Crap Math is Hard
Note: This article originally appeared on my Tumblr and was reposted here in 2019.
Bullet hell shooters with intricate bullet patterns seem to rely on
fixed timesteps to simplify the math. If you can ensure that every
bullet is always handled consistently with the same timestep every
frame regardless of actual framerate, you can pretty much guarantee
that your pretty bullet pattern will deterministically look the same
every time you run it on whatever hardware you run it on.
These games tend to handle a drop in framerate with a simple slowdown
of gameplay. Sometimes this can be advantageous to the player, and
even something desired by the designer themselves. And to make sure
you aren’t cheating by artificially slowing down your game to a crawl,
some measure of your average frame rate gets recorded next to your
high score.
It’s a pretty simple approach, and it means that the bullet movement
doesn’t have to be more accurate than one frame’s worth of linear
movement, because it’s all consistent and everything is treated
exactly the same frame-after frame. Basically, you don’t have to worry
about your bullet pattern having uneven spacing or ugly breakages
because some bullets launched in an earlier frame got a bigger change
to their velocity because of the acceleration value than some bullets
from some other frame.
An example of how some of these might run their iteration is:
- Check to see if we have any behavior change scheduled. This can be
a change in any of: acceleration, speed, angle, angular velocity,
or position. Angles can be offset from the direction to the target,
and some values can be randomized (though it is discouraged).
- Add Acceleration to the current speed. There’s no need to multiply
the acceleration by some time value, because the time value is
fixed!
- Add the angular velocity to the current angle. Again, no timestep
multiplication required.
- Add the vector [speed * cos(angle), speed * sin(angle)] to the
current position.
- Check for collision with the enemy.
- Spawn any child bullets we’re scheduled to this frame.
- Destroy this bullet if we’re scheduled to this frame.
All time values for events (spawn, die, change behavior) can be done
in frame counts instead of actual time values.
And None of That’s Gonna Fly in UE4
So UE4 does variable time steps. How on earth can we make variable
time steps give the same level of consistency that we get from a
simple movement in a fixed timestep simulation?
Let’s assume for the moment that I don’t care about floating point
precision error, for the sake of sanity.
The angle, speed, angular velocity, and acceleration are all constant
across some keyframe’s time. They aren’t interpolated as they would be
if I had gone with the keyframe approach I was talking about before.
In Danmakufu, they just change instantly at a scheduled frame number.
So I think we can come up with an equation that gives the velocity, in
game plane space, at some time t, given those four starting values. I
think I can do even better and replace speed with just a local space
velocity vector, and acceleration with a local space acceleration.
(StartingVelocity, CurrentVelocity, Acceleration, and FinalVelocity
are all vectors.)
CurrentVelocity = StartingVelocity + Acceleration * t
Angle = StartingAngle + AngularVelocity * t
FinalVelocity = [
cos(Angle) * CurrentVelocity[1] - sin(Angle) * CurrentVelocity[2],
sin(Angle) * CurrentVelocity[1] + cos(Angle) * CurrentVelocity[2]
];
This is the simple version that doesn’t clamp stuff to a maximum
speed. The last line is really just a 2D rotation matrix multiplied
directly by the velocity vector.
The complicated version takes the velocity vector, normalizes it (just
divides it by its magnitude) and then multiplies it by the maximum
speed. This is the version we want for after the velocity has hit
maximum speed. Because you can only accelerate in one direction over
the course of a keyframe, you can never go from over max speed to
under max speed. Only from under max speed to over max speed. The
exception being if you started off over max speed in one direction and
accelerated back in the other direction. I’m eliminating that
possibility by just clamping the velocity to the maximum speed for the
actual value stored on the bullet state structure when it switches to
a new keyframe.
All we have to do now is integrate FinalVelocity with respect to t.
Turns out that I have no idea how to do that! Yeah, I never actually
made it through the integration part of calculus class. Derivatives
were fine, but not integrals. Thankfully the class was split into two
courses and I got to pass the first one.
My calculator kinda sucks
I figured I could just punch this whole thing into my TI-89 and mash
the “integrate” (with respect to t) button. After thinking about it
for a while, it spat back a really loooooong answer with many still
un-integrated parts.
I was pretty disappointed! Mainly because the terrible UI on the
calculator made it take forever to punch the stupid thing in.
Modes are
BAD!
(And the TI-89 makes you switch modes to go between text entry and
anything-else entry!)
Time to learn something better? Finally?
I’ve been using that TI-89 for over a decade. I know the UI (well, the
important parts) inside and out! How the heck am I going to learn
something new? But even if the cell phone I carry around in my pocket
has about a bajillion times the computing power of the
oh-my-god-I-didn’t-know-they-sell-processors-this-weak-anymore TI-89.
So I’ve heard of Maple and Matlab. Looks like to even get a trial
version of them you need to go through some silly process. To heck
with that. I just want to solve one integral!
There’s got to be some open source Linuxy thing out there, right? What
about GNU Octave? Well, that’s
just a numerical solver. I want a symbolic solver. There is some
symbols package for it, but I couldn't get it to do anything.
(Wouldn’t even load?)
Hey, it’s just one problem, maybe Wolfram
Alpha? Not a terribly conventient way
to enter an equation so big. I mean, I guess I could try? Maybe I’ll
dig around a little more first. I need a system where I can iterate on
an idea. Something that takes a scripted input file and just outputs
the integrated version of whatever equation I set up in there.
Dug around a little more. Found
Maxima. Maxima is pretty sweet. At
least my not-a-mathematician brain thinks so, anyway. After a brief
learning curve, it looks like it can let me set up this crazy symbolic
monstrosity, script the whole thing, plot it, integrate it, plot the
integrated thing, and everything I ever used my TI-89 for. Awesome! So
what does the script look like that I finally pieced together?
/* I couldn’t find a vector magnitude thingy in Maxima, so I just made my own. */
vecMag(x) := sqrt(x[1]*x[1]+x[2]*x[2]);
/* We just have to explicitly declare vectors to use them like vectors. */
StartingVelocity:[‘StartingVelocityX, 'StartingVelocityY];
Acceleration:['AccelerationX, 'AccelerationY];
Velocity:’('StartingVelocity + ’t * 'Acceleration);
/* This is what we’re trying to achieve. We need to split it into two
separate equations, though. I can’t integrate “clamp”. */
/*Speed:clamp(vecMag('Velocity), 0, 'MaxSpeed);*/
/* Non-maxspeed version. */
Speed:’(vecMag('Velocity));
/* Maxspeed version. */
/*Speed:'MaxSpeed;*/
NormalizedVelocity:’(Velocity / vecMag(Velocity));
VelocityAfterSpeed:’('NormalizedVelocity * 'Speed);
/* Angular velocity != 0 version. */
Angle:’('StartingAngle + 'AngularVelocity * ’t);
/* No angular velocity version. */
/*Angle:'StartingAngle;*/
/* Rotate the velocity vector by a rotation matrix. */
VelocityAtAngle:’(
[ cos('Angle) * VelocityAfterSpeed[1] - sin('Angle) * VelocityAfterSpeed[2],
sin('Angle) * VelocityAfterSpeed[1] + cos('Angle) * VelocityAfterSpeed[2] ]);
Result:integrate(ev(VelocityAtAngle, infeval), t);
ev(Result);
And what does it spit out?
(%o188) [(AccelerationX*((AngularVelocity*t+StartingAngle)
*sin(AngularVelocity*t+StartingAngle)
+cos(AngularVelocity*t+StartingAngle))
/AngularVelocity
+StartingVelocityX*sin(AngularVelocity*t+StartingAngle)
-AccelerationX*StartingAngle*sin(AngularVelocity*t+StartingAngle)
/AngularVelocity)
/AngularVelocity
-(AccelerationY*sin(AngularVelocity*t+StartingAngle)
+(-AccelerationY*(AngularVelocity*t+StartingAngle)
-AngularVelocity*StartingVelocityY+AccelerationY*StartingAngle)
*cos(AngularVelocity*t+StartingAngle))
/AngularVelocity^2,
(AccelerationY*((AngularVelocity*t+StartingAngle)
*sin(AngularVelocity*t+StartingAngle)
+cos(AngularVelocity*t+StartingAngle))
/AngularVelocity
+StartingVelocityY*sin(AngularVelocity*t+StartingAngle)
-AccelerationY*StartingAngle*sin(AngularVelocity*t+StartingAngle)
/AngularVelocity)
/AngularVelocity
+(AccelerationX*sin(AngularVelocity*t+StartingAngle)
+(-AccelerationX*(AngularVelocity*t+StartingAngle)
-AngularVelocity*StartingVelocityX+AccelerationX*StartingAngle)
*cos(AngularVelocity*t+StartingAngle))
/AngularVelocity^2]
Err... Okay. Well, I can deal with that. This is good, though. I don't
know integration very well, and I sure as heck don’t know what in this
corresponds to the thing I fed into it, but it works! And if I need to
add some functionality to the bullet integration in the future, I can
just go back to my script and modify the velocity equation.
Also, there are so many redundant terms in there that the optimizer on
the compiler does a pretty good job of sorting it out.
I was pretty surprised by the fact that this version of the equation
seems to be undefined for AngularVelocity=0. The integrated version
has it in the denominator pretty much everywhere. So that’s why
there’s a commented-out version that drops the angular velocity, and
we just use that instead if we have to. It spits out a very different
result:
(%o223) [cos(StartingAngle)*(AccelerationX*t^2/2+StartingVelocityX*t)
-sin(StartingAngle)*(AccelerationY*t^2/2+StartingVelocityY*t),
cos(StartingAngle)*(AccelerationY*t^2/2+StartingVelocityY*t)
+sin(StartingAngle)*(AccelerationX*t^2/2+StartingVelocityX*t)]
As expected, it’s just the velocity integration pointed in the angle’s
direction.
Here’s what it looks like when we plot that position for some time t
with some acceleration and angular velocity:
{% include article_image.md img="danmaku_ue4_maxima1.png" %}
(After plugging in actual values instead of variables, the equation
got simplified.)
So now we can pretty much determine whatever the bullet’s position is
for any time with just this one equation.
The MaxSpeed Monkey Wrench
So here’s what happens when you use the “MaxSpeed” version of the
equation and tell Maxima to integrate it:
(%o874) [MaxSpeed*'integrate(t*cos(AngularVelocity*t+StartingAngle)/abs(t),t),
MaxSpeed*'integrate(t*sin(AngularVelocity*t+StartingAngle)/abs(t),t)]
It doesn’t even know what the heck to do with it.
In the end I opted for a much simpler but less accurate approach. I’ll
just have acceleration zero out when it reaches max speed. This has a
flaw, but I don’t think it’ll be a serious hindrance to authoring
content.
This is the flaw...
In this diagram, the blue line is the velocity vector from the last
keyframe frame. Magenta is the acceleration vector. The radius of the
circle is the maximum speed, so the velocity vector will hit the edge
of the circle and stop accelerating.
If we zero out the acceleration when we hit another edge of the circle
(magnitude of velocity is >= max speed), then we’ll start at point A,
travel to point B, and then stop. If we didn’t clamp the velocity at
all, the velocity vector might at some point look like the cyan arrow.
Clamping the cyan line to max speed would get you point C. The problem
is that, even though the speed isn’t changing, the direction is still
changing as a result of acceleration. If you accelerate long enough,
the velocity direction would even appear to approach the direction of
the acceleration vector itself (clamped).
But I couldn’t integrate the equation for max speed correctly, so I’ll
just do the dumb way that stops at B. I only have this problem at all
because I allowed 2D vectors for the local space velocity and
acceleration instead of a 1D speed and acceleration that just went
down one axis. If it’s used like a 1D speed (just velocity and
acceleration on a single axis) this issue evaporates entirely. That’s
why I’m not worried about it.
Stuff
So I think I’ve proven here that I’m not really that great at
calculus. So if anyone out there wants to tell me that I’m doing this
all wrong and there’s a way easier way, I’d like to hear it!
(Unless it involves a fixed timestep or anything to do with bezier
curves.)
In the meantime, I’m going forward with this.
Posted: 2014-09-16
The Camera and the Game Plane
Note: This article originally appeared on my Tumblr and was reposted here in 2019.
So my first task for the shooter was to get that Ikaruga-style camera
motion. The one where the camera flies around in the level, but the
gameplay stays fixed to your view.
UE4 Matinee
Unreal has the perfect set of controls for driving the camera around
the level, in their Matinee editor. It’s kind of a cutscene editor,
but can be used to script game events like doors opening and whatever
too. There’s a neat example project that hows off some of its
capabilities, but long store short: I can use it to drive the camera
around the level with a bunch of keyframes. So I’m using it.
The Game Plane
So I have the camera, and it’s flying around the level. The easy thing
to do now is just to parent all the gameplay actors to the camera,
give them a fixed depth from the camera, and do all the action in
camera-space. But what about games like Einhander? In its first level
it turns the camera independent of the 2D plane that all the action is
happening on, and even has actors visibly transitioning onto the
plane. Video here.
Here’s a screenshot showing a rough outline of the playable area in
red.
Even Ikaruga often hides its enemy-transition-to-gameplay by having
background baddies run off the edge of the screen, only to reappear on
the same edge, now suddenly on an alignment where you can shoot them.
So I made the decision to split the gameplay plane and camera,
allowing them to be moved independently of each other.
{% include article_image.md img="danmaku_ue4_camera1.png" %}
Of course, that introduces more weird issues. Now how do we constrain
the player movement? We could just limit their movement to some area
on the plane. But every time the camera looks at a weird angle your
bounds area is going to turn into, effectively, a trapezoid. What if
we wanted to do stuff like zooming out the camera and giving the
player a wider area, or expressing a tight passageway by zooming in
and constraining the player to the view?
Einhander didn’t do this and just had the player limited to the plane
in 3D space, regardless of camera and view behavior.
Now the math gets interesting
First, some terms...
View space is the coordinate space where everything is relative to the
camera, in world-space units. The camera is at 0,0,0 and looking down
some axis (often Z) with the camera’s “up” direction also being along
some axis (often Y).
To go from world space to view space, we can just transform things by
the inverse of the camera matrix. Even better than that, because we
aren’t worried about scale - only position and rotation - UE4 can
“unrotate” a vector, and we can just subtract the camera’s position
vector. This is almost certainly way faster than calculating the
inverse of a matrix.
Clip space is the coordinate space that corresponds to your screen.
-1,1 is the upper left corner, and 1,-1 is the lower-right corner. The
X axis is horizontal, and the Y axis is vertical. This is after the
perspective transformation, so at this point things that are further
away from the camera have been shifted towards the center of the
screen. The Z value is depth in clip-space, and it’s either in the
range of 0 to 1 or -1 to 1.
Here’s information on setting up an OpenGL Projection
Matrix, and
what all the numbers mean. This transformation will take us from view
space to clip space.
And now the math...
So if the camera is always looking straight at the plane, it’s pretty
straightforward. We can just clamp the coordinates of the player in
view-space. We just need to figure out how big the gameplay area is at
that distance from the camera. There’s a little bit of math behind
that, but I’m not going into it because it’s no the approach I went
with. I don’t want to be constrained to cases where the camera is
facing the plane perfectly like this (gameplay plane in medium-gray,
viewable area in lighter-grey)...
I want to be able to handle situations where the camera is facing the
plane at an angle, causing the actual playable area to become a
trapezoid in world space like this...
So the first approach I tried was to convert the coordinates of our
player (or whatever other actor we want constrained here) to clip
space, clamp it to that -1,-1 to 1,1 area that represents your screen,
and then convert it back. The problem with this is that by NOT
changing the depth (Z) component of the vector, we have actually moved
something off of the plane by doing this. Think about it, the camera
is looking at it from some weird angle. If we scoot something directly
sideways in the view, it’s going to move off the plane.
I ended up doing the math later on to snap something onto the gameplay
plane without moving it relative the view, but it was after I had
abandoned this approach.
The main reason for giving up on that was the fact that things got
REALLY weird for anything that ended up behind the camera or on the
same plane as Z=0 in clip space.
Something Simpler
It’s pretty easy to figure out the screen bounds for some plane in
view space. (Copy+Pasted from the code. X is depth in this case!)
float YMax =
tan((PI / 180.0f) * Camera->FieldOfView / 2.0f) * ViewSpace.X;
float ZMax =
tan((PI / 180.0f) * (Camera->FieldOfView / Camera->AspectRatio) / 2.0f) * ViewSpace.X;
The maximum bound for each axis is specified there and, because
everything’s centered around 0,0, that means the negative bound is
just negative YMax, ZMax.
So we clamp the object’s view-space coordinates like that, and then
snap it back onto the gameplay plane (while keeping its position in
screen-space!)
In gameplay-plane space, with the camera position being “Start” and
the actor’s current position being “End”, the function for doing that
is this:
FVector UExpopShooterMath::ProjectToZPlane(FVector Start, FVector End)
{
float t = (Start.Z * -1) / (End.Z - Start.Z);
FVector FromStartToPoint = (End - Start) * t;
return FromStartToPoint + Start;
}
And bam. We have our gameplay area defined by the visible area of the
gameplay plane object.
Posted: 2014-09-15
