Animations with Recursion

from manim import *
config.media_embed = True; config.media_width = "100%"
_RV = "-v WARNING -qm --progress_bar None --disable_caching Example"
_RI = "-v WARNING -s --progress_bar None --disable_caching Example"

Manim Community v0.15.1

Theory

Recursion is a very powerful tool for solving problems that loops have a hard time solving.

Although there are people who like to always use recursion, the truth is that this technique uses more memory than loops, so I recommend that you do not marry any technique in particular, always use the correct tools for each problem.

In case you don’t have recursion concepts, I’ll leave you an excellent video (made in Manim) that explains the concept quite well:

• Basic theory

• Towers of Hanoi (video also made in Manim)

Before making the animation of the towers of Hanoi we are going to make the fractal tree, which is very easy to do.

Fractal tree

To build this fractal it is not necessary to use recursion, we could do it with a loop (since every recursive algorithm is computable, and therefore can be converted to a loop), but we are going to do it using recursion.

The idea is to make two copies of the same branch, scale them a bit and then rotate them a certain angle, taking the top end as reference (Line.get_end()), the main idea is this:

While we could subclass VGroup or VMobject to create these branches, to simplify the code we can simply use functions, but it is left as an exercise for the reader to define a subclass of VGroup.

The function would be this:

def get_two_branches(branch, angle=30*DEGREES, scale_factor=0.7):
    b1, b2 = branch.copy(), branch.copy()
    for b, sign in zip([b1,b2],[1,-1]):
        b.scale(scale_factor,about_point=branch.get_end())
        b.rotate(
            PI + angle * sign,
            about_point=branch.get_end()
        )
    return VGroup(b1, b2)

Be careful though, as the new branches will be flipped once they rotate, and they won’t be in the same direction as the main branch, so we need to rotate the branches 180° at the end, here the idea:

So the final code is:

def get_two_branches(branch, angle=30*DEGREES, scale_factor=0.7):
    b1, b2 = branch.copy(), branch.copy()
    for b, sign in zip([b1,b2],[1,-1]):
        b.scale(scale_factor,about_point=branch.get_end())
        b.rotate(
            PI + angle * sign,
            about_point=branch.get_end()
        )
        b.rotate(PI) # <-- to mantain branch direction
    return VGroup(b1, b2)

next_level func

Now comes the interesting part, which is defining the recursive function.

A recursive function receives an object that is going to be manipulated until a condition is met, we must analyze the structure that this object is going to have.

We can think of each iteration as a level, the initial branch is level 0, the first two branches are level 1, the next 4 branches are level 2 and so on, so our object would look something like this:

obj = [
    level0,
    level1,
    level2,
    level3
]

but each level is in turn a set of branches, so it would look something like this:

obj = [
    [branch_l0],
    [branch_l1,branch_l1],
    [branch_l2,branch_l2,branch_l1,branch_l2],
    [branch_l3,branch_l3,branch_l3,branch_l3,branch_l3,branch_l3,branch_l3,branch_l3],
]

Knowing that this is our goal, we can now think about what the function will be like.

It is evident that in order to obtain the next level, it is necessary to operate with the last level of obj, that is to say

last_level = obj[-1]
next_level = get_next_level(last_level)

But as we defined before, last_level is an array of branches, so to get the new branches it would be something like this:

def get_next_level(last_level):
    next_level = [get_two_branches(branch) for branch in last_level]
    return next_level

However, there is a problem here, and the structure of next_branches is going to be like this:

next_branches = [[b,b],[b,b],[b,b]]
# instead of
next_branches = [b,b,b,b,b,b]

which is our desired structure, so we simply need to expand next_branches, this is easy:

def get_next_level(last_level):
    next_level = [get_two_branches(branch) for branch in last_level]
    expanded_branches = []
    for touple_branches in next_level:
        for branch in touple_branches:
            expanded_branches.append(branch)
    return expanded_branches

# Or using list comprehensions

def get_next_level(last_level):
    next_level = [get_two_branches(branch) for branch in last_level]
    expanded_branches = [
        branch
        for touple_branches in next_level
            for branch in touple_branches
    ]
    return expanded_branches

# Refactoring:

def get_next_level(last_level):
    return [
        branch_new_level
        for branch_last_level in last_level
            for branch_new_level in get_two_branches(branch_last_level)
    ]

recursive func

So, our recursive function would be something like:

def recur_func(obj):
    last_level = obj[-1]
    next_level = get_next_level(last_level)

Every recursive function must have a way to mark the limit, in our case it is simple since we indicate how many levels we want to obtain, so we can add a new parameter:

def recur_func(obj, levels=5):
    last_level = obj[-1]
    next_level = get_next_level(last_level)

levels=5 is totally arbitrary, it can be whatever we want.

Let’s see what happens with a practical example

# If
obj = [
     [branch_l0],
     [branch_l1,branch_l1],
]
# then
last_level = obj[-1]
# last_level = [branch_l1,branch_l1]
# so
next_level = get_next_level(last_level)
# next_level = [branch_l2,branch_l2,branch_l1,branch_l2]

What we need to do now is add the next_level to obj:

obj.append(next_level)

And that’s it, now we have our obj with:

obj = [
     [branch_l0],
     [branch_l1,branch_l1],
     [branch_l2,branch_l2,branch_l1,branch_l2]
]

The following is simply calling the same recursive function to do the same thing, like so:

def recur_func(obj, levels=5):
    last_level = obj[-1]
    next_level = get_next_level(last_level)
    obj.append(next_level)
    recur_func(obj)

But if we do this then the function will run forever, so we have to use levels as a limit in some conditional, something like this:

def recur_func(obj, levels=5):
    if levels == 0:
        return
    last_level = obj[-1]
    next_level = get_next_level(last_level)
    obj.append(next_level)
    recur_func(obj,levels=levels-1)

In this way, when the next iteration is passed, then the levels will have decreased by one, and when it reaches 0, then the function will end.

In general, this counter is referred to as iterations, rather than levels:

def recur_func(obj, iterations=5):
    if iterations == 0:
        return
    last_level = obj[-1]
    next_level = get_next_level(last_level)
    obj.append(next_level)
    recur_func(obj,iterations-1)

Passing the code to Manim, our obj would be something like this:

obj = VGroup(
    VGroup(branch_l0),
    VGroup(branch_l1,branch_l1),
    VGroup(branch_l2,branch_l2,branch_l1,branch_l2)
)

Adjusting the functions that we just defined, then everything would be like:

def get_next_level(last_level):
    return VGroup(*[
        branch_new_level
        for branch_last_level in last_level
            for branch_new_level in get_two_branches(branch_last_level)
    ])

def recur_func(branch_grp, iterations=5):
    if iterations == 0:
        return
    last_level = branch_grp[-1]
    next_level = get_next_level(last_level)
    branch_grp.add(next_level)
    recur_func(branch_grp, iterations-1)

Let’s see if this works:

class Example(Scene):
    def construct(self):
        branch = Line(DOWN,UP)
        branch.to_edge(DOWN)
        branch_grp = VGroup(
            VGroup(branch)
        )
        recur_func(branch_grp, 6)
        for level in branch_grp:
            self.play(Create(level,lag_ratio=0))
            self.wait(0.3)

%manim $_RV

Perfect, we see that it works without any problem, to make it a little more aesthetic we can decrease the stroke_width of the lines a little, like this:

def get_two_branches(branch, angle=30*DEGREES, scale_factor=0.7):
    b1, b2 = branch.copy(), branch.copy()
    for b, sign in zip([b1,b2],[1,-1]):
        b.scale(scale_factor,about_point=branch.get_end())
        b.rotate(
            PI + angle * sign,
            about_point=branch.get_end()
        )
        b.rotate(PI) # <-- to mantain branch direction
        b.set_style(
            stroke_width=b.get_stroke_width()*scale_factor
        )
    return VGroup(b1, b2)

class Example(Scene):
    def construct(self):
        branch = Line(DOWN,UP).scale(1.2)
        branch.to_edge(DOWN)
        branch_grp = VGroup(
            VGroup(branch)
        )
        recur_func(branch_grp, 10)
        for level in branch_grp:
            self.play(Create(level,lag_ratio=0))
            self.wait(0.3)

%manim $_RV

It remains as an exercise to try to imitate this animation:

TIP: Create a custom animation that does this.

Conclusion

To make animations of this style in general we need two things:

• Function that generates the next level

• recursive function

If you manage to define those two steps, you already have all the work done.

Hanoi towers

I hope you have already seen this video because we are going to use it to build this animation:

In particular, we are going to use this algorithm to solve the problem:

def pm(start, end):
    print("Take top block from ",start," to ",end)

def h(n, start, end, aux):
    if n == 1:
        pm(start, end)
    else:
        h(n-1, start, aux, end)
        pm(start, end)
        h(n-1, aux, end, start)

h(4,"A","C","B")

Take top block from  A  to  B
Take top block from  A  to  C
Take top block from  B  to  C
Take top block from  A  to  B
Take top block from  C  to  A
Take top block from  C  to  B
Take top block from  A  to  B
Take top block from  A  to  C
Take top block from  B  to  C
Take top block from  B  to  A
Take top block from  C  to  A
Take top block from  B  to  C
Take top block from  A  to  B
Take top block from  A  to  C
Take top block from  B  to  C

Our goal will be to turn this algorithm into an animation, this will be a more complete project as we will learn how to create subscenes with class variables.

Pillars

For this animation we are going to create an object called Pillars, to this object you can add a block or move a block from one pillar to another, it is not complicated:

class Pilar(VGroup):
    def __init__(self):
        super().__init__()
        self.body = Line(DOWN*3,UP*3,stroke_width=20)
        self.add(self.body)

    def add_block(self, block):
        if len(self) == 1: # if pillar is empty
            block.next_to(self.body.get_start(),UP,buff=0)
        else:
            block.next_to(self[-1],UP,buff=0)
        self.add(block)

    def move_block(self, pilar):
        block = self[-1]
        self.remove(block)
        pilar.add_block(block)

As you can see, this object has a body, which is the pillar itself, you can add parameters to the object if you want, I’m going to leave it that way for now.

The add_block method positions the block at the base in case there is only one element (the pillar), or on top of the last block. Don’t forget to add the block to the object.

The move_block method removes the block from the pillar and adds it to another pillar.

Let’s move on to building the scene.

Scene definition

We must define 3 pillars, and to one of them we have to place the blocks, we are going to define the pillars as 1,2,3 instead of “A”,“B”,“C”.

class HanoiScene(Scene):
    MAX_WIDTH_BLOCK = 3
    MIN_WIDTH_BLOCK = 1.3
    HEIGHT_BLOCK = 0.6
    N_BLOCKS     = 3

    INDEX_START_BLOCK = 1
    def get_blocks(self, n_blocks, max_width, min_width, height):
        colors = (c for c in [RED,GREEN,BLUE,YELLOW,TEAL])
        return VGroup(*[
            Rectangle(
                width=interpolate(max_width,min_width,i/(n_blocks-1)),
                height=height,
                fill_opacity=1,
                color=next(colors)
            ).round_corners(0.2)
            for i in range(n_blocks)
        ])

    def get_pillars(self, blocks, index_start_block):
        pillars = VGroup(*[
            Pilar() for _ in range(3)
        ]).arrange(RIGHT,buff=5)
        # add blocks to pillar
        for b in blocks: pillars[index_start_block-1].add_block(b)
        return pillars

    def construct(self):
        blocks = self.get_blocks(
            self.N_BLOCKS, self.MAX_WIDTH_BLOCK,
            self.MIN_WIDTH_BLOCK, self.HEIGHT_BLOCK
        )
        self.pilars = self.get_pillars(blocks, self.INDEX_START_BLOCK)

        self.add(self.pilars)

%%manim $_RV
class Example(HanoiScene):
    N_BLOCKS = 5
    INDEX_START_BLOCK = 2

Now we just have to adjust the algorithm to our scene. The hanoi method is practically identical to the original hanoi function, but it is converted to a method.

class HanoiScene(HanoiScene):
    def pm(self, start, end):
        p_start = self.pilars[start-1]
        p_end   = self.pilars[end-1]
        p_start.move_block(p_end)
        self.wait()

    def hanoi(self, n, start, end, aux):
        if n == 1:
            self.pm(start, end)
        else:
            self.hanoi(n-1, start, aux, end)
            self.pm(start, end)
            self.hanoi(n-1, aux, end, start)

In the pm method I added a pause so that the movement is shown, we just need to redefine the constructor and add the missing class variables:

class HanoiScene(HanoiScene):
    N_BLOCKS          = 3
    INDEX_START_BLOCK = 1
    INDEX_END_BLOCK   = 3
    def construct(self):
        super().construct()
        self.wait()
        self.hanoi(
            self.N_BLOCKS, self.INDEX_START_BLOCK,
            self.INDEX_END_BLOCK, self.get_aux_index()
        )
        self.wait()

    def get_aux_index(self):
        INDEXES = [1,2,3]
        INDEXES.remove(self.INDEX_START_BLOCK)
        INDEXES.remove(self.INDEX_END_BLOCK)
        return INDEXES[0]

%%manim $_RV
class Example(HanoiScene):
    N_BLOCKS  = 5
    INDEX_START_BLOCK = 2
    INDEX_END_BLOCK   = 1

We already have our animation almost finished, it just doesn’t look very good, we are going to add the animation of the movement of the block.

class Pilar(Pilar):
    def __init__(self, scene):
        self.scene = scene
        super().__init__()

    def move_block(self, pilar): # with animation
        mob_ref = pilar.body.get_start() if len(pilar) == 1 else pilar[-1]
        block = self[-1]
        self.remove(block)
        block.generate_target()
        block.target.next_to(mob_ref,UP,buff=0)
        # REMARK:
        self.scene.play(MoveToTarget(block))
        pilar.add(block)

class HanoiScene(HanoiScene):
    def get_pillars(self, blocks, index_start_block):
        pillars = VGroup(*[
            Pilar(self) for _ in range(3) # <== Add self (= Scene) to Pilar
        ]).arrange(RIGHT,buff=5)
        for b in blocks: pillars[index_start_block-1].add_block(b)
        return pillars

%%manim $_RV
class Example(HanoiScene):
    N_BLOCKS  = 4
    INDEX_START_BLOCK = 1
    INDEX_END_BLOCK   = 3

Notice how we passed the Scene object as a parameter to an Mobject and we were also able to perform an animation outside of our Scene class, this is quite a useful technique when we have complex Mobjects.

Homework

Add a path arc to the MoveToTarget so it looks like this: