📽️

【Python】Manimでバブルソートのアニメーションを作ってみる

2022/09/27に公開

Manimとは

Manimとは、3Blue1BrownというYouTubeチャンネルの数学の解説動画を作成するために設計されたエンジンで、プログラムによって精密なアニメーション表現が可能です。
https://www.youtube.com/watch?v=r6sGWTCMz2k

準備

私の環境がMacなのでMac用のインストール方法です。
Windows,Linux,Docker,Jupyter Notebooksなど、公式ドキュメントにはさまざまなパターンのインストール方法があるのでご参照ください。
https://docs.manim.community/en/stable/installation.html

brew install py3cairo ffmpeg

Apple Siliconの場合は、以下も必要です。

brew install pango scipy
pip3 install manim

LaTeXを使った方程式のレンダリングを行いたい場合は、LaTeXをインストールする必要があります。
Mac OSの場合は、MacTexをインストールすれば良いです。

brew install --cask mactex-no-gui

チュートリアルの一番最初にあるプログラムを試してみます。

from manim import *

class CreateCircle(Scene):
    def construct(self):
        circle = Circle()
        circle.set_fill(PINK, opacity=0.5)
        self.play(Create(circle))
manim -pql scene.py CreateCircle

オプション

オプション 説明
-p レンダリング後のシーンを再生する
-ql 低画質でレンダリング
-qm 中画質でレンダリング
-qh 高画質でレンダリング
-i gifで出力

バブルソート

バブルソートのアルゴリズム。

def bubble_sort(seq):
    n = len(seq) - 1
    for i in range(n):
        for j in range(n - i):
            if seq[j] > seq[j+1]:
                seq[j] , seq[j+1] = seq[j+1], seq[j]

Manimを使ってこれをアニメーションにしていきます。

数の列を円で表現する

ランダムな数の配列を作成し、値を円の半径として利用しています。

import random
class SortAnimation(Scene):
    def construct(self):
        g = Group()
        numbers = list(range(1,11))
        random.shuffle(numbers)
        for number in numbers:
            g.add(Circle(radius=number/2*0.1))
        self.add(g.arrange_in_grid(col_widths=[1]*10))

交換する

バブルソートで大事なのがSwapです。
ManimにはSwapというクラスが用意されているので、これを利用すれば簡単に交換のアニメーションを作ることができます。

class SwapAnimation(Scene):
    def construct(self):
        square, circle = Square(), Circle()
        g = Group(square, circle)
        self.add(g.arrange(buff=1))
        self.wait(1)
        self.play(Swap(square,circle))


また、バブルソートのアルゴリズムで交換が行われる度に、アニメーションを実行したいです。
そこで、yieldを使ってどの位置の数を交換したのかを、関数の実行途中に都度返すようにしました。

def bubble_sort(seq):
    n = len(seq) - 1
    for i in range(n):
        for j in range(n - i):
            if seq[j] > seq[j+1]:
                seq[j] , seq[j+1] = seq[j+1], seq[j]
                yield (j,j+1)

ソートアニメーション

bubble_sortyieldを使っているので、ジェネレータ関数になっています。
ジェネレータ関数は、for文と組み合わせることができるので、以下のように書くことでソートのアニメーションを作ることができました。

class SortAnimation(Scene):
    def construct(self):
        g = Group()
        numbers = list(range(1,11))
        random.shuffle(numbers)
        for number in numbers:
            g.add(Circle(radius=number/2*0.1))

        self.add(g.arrange_in_grid(rows=1,col_widths=[1]*10))
	# 追加分↓
        for i,j in bubble_sort(numbers):
            self.play(Swap(g.submobjects[i], g.submobjects[j]))
            g.submobjects[i], g.submobjects[i+1] = g.submobjects[i+1], g.submobjects[i]

g.submobjectsは、addメソッドで追加された円のリストです。
ijに交換した配列の添字が入ってくるので、Swapに交換したい円を渡すことで交換のアニメーションを再生することができます。

また、最後の行が重要です。
bubble_sort関数でソートしているのはnumbersの数のリストだけなので、g.submobjects内の円のリストも同様にソートする必要があります。
これで、バブルソートのアニメーションを作ることができました。

Discussion