The Algebra of Animation

I was inspired by this lovely animation example made by ahmwma using Decker. I like that it shows how a complex animation can be built out of simpler parts that are easy to understand conceptually¹.

I wanted to build something like that in PICO-8. It’s also a perfect opportunity for me to talk about a subject near and dear to me: algebraic programming.

I love functional programming. Even more than that, I love algebraic programming². In fact, I’d say that functional programming on its own is fairly uninteresting. It’s powerful because it lays the foundation for algebraic programming³.

What is algebraic programming?

Algebraic programming is an approach that’s focused on data types that adhere to simple rules. This allows us to write very generalized programs, and rearrange code in particular ways with confidence that it will still work as intended!

For example, here are some rules you’ve probably seen when doing algebra with numbers:

The first rule is an associativity law. The other two are additive identity laws. When you add zero to something, it doesn’t change the thing. There are a lot of things that aren’t numbers that still work this way. Strings and lists are a couple examples (the empty string or empty list acts much the same way as the number 0). Generalizing to non-numbers, this combination of an associative addition function and an identity element is an algebraic structure called a monoid.

When programming with monoids, we can introduce or eliminate an extra 0 object at will. This doesn’t seem like much, but it can let us avoid branching or conditional logic that can make our code harder to read. Later, we’ll look at some more algebraic rules that enable more refactors.

Representing animation in code

I wanted to build a system that will let me “do algebra” to animations. To do that, I needed to decide what an animation is. Here’s what I came up with⁴:

type Anim<A> = { at: (time: number) => A; dur: number };

An anim is a value that can change over time. It also has a defined duration (in seconds). That’s it — it’s little more than a number and a function stapled together!

Both functions and numbers already obey several algebraic rules. For example, the number 0 is an additive identity with respect to the + operator. Same goes for 0 and the max function (for non-negative numbers). The identity function is also an additive identity with respect to function composition — a very abstract kind of “addition”. This will be useful in making anims also obey algebraic rules.

I also want to highlight that the value can be any type, which will turn out to be important for certain kinds of composability. Often, I’ll want the animated value to be a suspended draw function. I’ll be calling that specific case an animation, and the more general case an anim⁵.

type Draw = () => void;
type Animation = Anim<Draw>;

The Algebra of Animation

If anims are the “numbers” in this metaphor, then “doing algebra to them” means deciding what operators to use and how they behave. What notions of “addition” might apply to this context?

I found three kinds of operators:

• Combining Animations
• Transforming Animations
• Time Warping

Combining

One way to combine two animations is to run one animation after another. Another useful way to combine animations is to run both at the same time, with the second one being drawn on top of the first one. Both of these are a kind of addition, and in both cases there’s a 0 element: an animation that lasts 0 seconds, and draws nothing to the screen.

I like how easy it is to generalize to combining a whole list of animations either in a stack or in a sequence. We don’t even have to write a special case for empty lists. That’s handled automatically by the empty animation⁶.

-- Run one animation after the other
function anim_concat(a1,a2)
    return {
        at = function(t)
            return t <= a1.dur
                and a1.at(t)
                or  a2.at(t - a1.dur)
        end,
        dur = a1.dur + a2.dur,
    }
end

anim_empty = {
    at = const(noop),
    dur = 0,
}

-- Run a list of animations in sequence
anim_seq = reduce(anim_concat, anim_empty)

-- Run two animations in parallel
function anim_stack(a1,a2)
    return {
        at = function(t)
            -- return a new suspended draw call
            return function()
                a1.at(t)()
                a2.at(t)()
            end
        end,
        dur = max(a1.dur, a2.dur),
    }
end

-- Draw a list of animations from back to front
anim_par = reduce(anim_stack, anim_empty)

Transforming

There are a few more useful ways to transform anims that are once again algebraic in nature. The first is to map a function over an anim. The second is similar. It’s a way of applying a function to an animated value, but where the function itself is also an animated value. These go hand-in-hand with a function that constructs an animated value out of a plain non-animated one. Together, these three form another algebraic structure called an applicative functor.

-- Map a function over an animated value
function anim_map(a,f)
    return {
        at = compose(a.at, f),
        dur = a.dur,
    }
end

-- Apply an animated function to an animated value
function anim_ap(ax,af)
    return {
        f = function(t)
            local x = ax.at(t)
            local f = af.at(t)
            return f(x)
        end,
        dur = max(ax.dur, af.dur),
    }
end

-- Convert a non-animated value to an animated one
function anim_const(v)
    return {
        f = function(t) return v end,
        dur = 0,
    }
end

Converting a non-animated value to an animated one in this way is quite boring. I’m not doing anything with the time component. I’m returning an anim that always yields the same value. Still it’s useful to be able to “cast” values this way.

Time Warping

I’ve been intentional about not including any notion of frames in my definiton of animations. Defining animations as continuous functions gives us more freedom to manipulate the timing. We can apply easing to an animation, slow it down or speed it up, or loop it indefinitely.

-- Use an easing function to adjust the animation timing
function anim_ease(a,ease)
    return {
        at = compose(ease,a.at),
        dur = a.dur,
    }
end

-- Stretch an animation by a factor of `s`
function anim_scale(a,s)
    return {
        at = function(t)
            return a.at(t/s)
        end,
        dur = s * a.dur,
    }
end

-- Loop an animation forever
function anim_loop(a)
    return {
        at = function(t)
            return a.at(t % a.dur)
        end,
        dur = infinity,
    }
end

Example

With that, we now have enough pieces to put together the butterfly animation example.

Let’s first break it down into components.

• A keyframe animation
• An animated position that moves back and forth along a path
• An animated position that bobs up and down

Frame-by-frame animation

Just because anims don’t have a concept of frames doesn’t mean we can’t make frame-by-frame animations.

function anim_from_frames(frames, framerate)
  return {
        at = function(t)
            local index = (t*framerate) % #frames
            return frames[index+1] -- lua arrays start at 1
        end,
        dur = #frames/framerate,
  }
end

butterfly_flap = anim_loop(
    anim_from_frames({
        -- set the sprite indices, width, and height for the keyframes
        draw_spr(9,2,2),
        draw_spr(11,2,2),
        draw_spr(13,2,2),
        draw_spr(11,2,2),
    }, 15)
)
flower_wave = anim_loop(
    anim_from_frames({
        -- set the sprite indices, width, and height for the keyframes
        draw_spr(1,4,4),
        draw_spr(5,4,4),
        draw_spr(65,4,4),
        draw_spr(69,4,4),
    }, 15)
)

In this case, I have 2x2 butterfly sprites at position 9, 11, and 13 in the spritesheet. I can build a short looping animation from those frames.

Movement

Next I want to build an animation that moves.

I already have a function draw_with_position that I can use. It takes a draw call and returns a modified draw call that changes the position of the drawing. It’s now time to use the anim_map and anim_ap functions to connect the pieces.

anim_linear = {
    at = function(t) return t end,
    dur = 1,
}

function anim_from_to(p1,p2)
	return anim_map(anim_linear, lerp(p1,p2))
end

p1,p2 = v2(24,60), v2(100,82)
move_path = anim_map(
    anim_from_to(p1,p2),
    draw_with_position
)

move_hover = anim_map(
    anim_map(anim_linear, function(t)
        return v2(0, sin(t))
    end),
    draw_with_position
)

-- draw the butterfly flapping its wings while moving along a path
anim_ap(butterfly_flap, move_path)

-- draw the butterfly flapping its wings while hovering up and down
anim_ap(butterfly_flap, move_hover)

All that’s left is to combine the back-and-forth movement with the up-and-down movement. One way to achieve this would be to nest calls to anim_ap, one with each motion.

-- draw the butterfly flapping its wings while hovering up and down AND moving along a path
anim_ap(
    anim_ap(
        butterfly_flap,
        move_hover,
    ),
    move_path
)

That works fine, and gives the right result (as long as you make sure draw_with_position composes correctly), but it isn’t my preferred approach. I find it more elegant to combine the movements into a single animation, then use anim_ap to move the flapping butterfly animation around.

We already have all the pieces needed to do that, it’s just a matter of putting them together in the right way. I’ll admit, my first time seeing applicative functors it wasn’t obvious how to do that. There’s only one function that combines multiple anims: anim_ap, but it only works if one of the anims returns a function. How on earth do you combine multiple anims when both of them return vectors? The trick is to use a curried function in combination with anim_map and anim_ap.

move_path = anim_from_to(p1,p2)

move_hover = anim_map(anim_linear, function(t)
    return v2(0, sin(t))
end)

function plus(x)
    return function(y)
        return x+y
    end
end

-- build a complex path that moves back-and-forth AND up-and-down
move_butterfly = anim_ap(
   anim_map(move_path, plus),
   move_hover
)

-- draw the butterfly flapping its wings while moving along a complex path
anim_ap(
    butterfly_flap,
    anim_map(move_butterfly, draw_with_position),
)

Putting it all together

Here’s the final animation using all the tools built-up so far: keyframes, combining, transforming, and timewarping.

function anim_reverse(a)
    return anim_ease(a, function(t) return a.dur - t end)
end

function ping_pong(a)
    return anim_loop(anim_concat(a, anim_reverse(a)))
end

-- animation of a butterfly flapping its wings, bobbing up and down, and flying between two flowers, which are also animated
anim_par({
    -- flower 1
    anim_loop(anim_map(flower_wave, draw_with_position(p1))),
    -- flower 2
    anim_loop(anim_map(flower_wave, draw_with_position(p2))),
    -- butterfly
    ping_pong(
        anim_ap(
            butterfly_flap,
            anim_map(move_butterfly, draw_with_position),
        )
    )
})

The sharp-eyed reader will notice a few details in the finished animation that I haven’t discussed here yet. Specificailly, I wanted the butterfly to flip directions when it reaches the flower on the right. I’m leaving that as an exercise for the reader (or you can always download the cart and read the source code to see how it’s done). I feel like the implementation is uninteresting in the sense that it doesn’t touch on any of the algebraic facets of animations.

Closing remarks

Thanks for reading this far! This article got to be a pretty long and code-dense one. I hope you were able to glean something useful from it.

This method of breaking down animations has really helped me to build up more complicated animations like the “magical garakei” I made for Tomodachi 8-in-1. If it’s useful to you, feel free to check out the source cart.

License: CC BY-NC-SA 4.0.

Footnotes