Blender でハノイの塔の動画を自動生成


 上のような動画を作成しました。

 Blender 上で Python スクリプトを走らせることにより大量の画像を生成しています。

 今までの記事で述べたことに比べて新しい点はそこまでありませんが、定期的に記事にまとめた方が技術が身につくのと、誰かの助けになるかもしれないので一応。

オブジェクトの作成

 まずは円盤の集合体を生み出します。手作業で生み出してもいいですが、せっかくのスクリプトなのでそこも自動化しましょう。


import bpy
import numpy as np

np.random.seed(40)

# parameter
height = 4

for i in range(height):
    obj = bpy.ops.mesh.primitive_cylinder_add(vertices=(i+1)*height*5,radius=i+2, depth=1, location=(0,0,height-1-i))
    bpy.context.object.name = f'hanoi{i+1}'
    mat_name = 'material' + str(i)
    bpy.data.materials.new(name = mat_name)
    mat = bpy.data.materials[mat_name]
    mat.use_nodes = False
    mat.diffuse_color = np.random.rand(4)
    mat.diffuse_color[3] = 1
    mat.metallic = 0
    mat.roughness = 1
    bpy.ops.object.material_slot_add()
    bpy.context.object.active_material=mat

 こんな感じになります。段数は height で指定します。色合いが気に食わなければ、np.random.seed(40) の中の数値を変えてください。

動かす

 次に、円盤を一つずつ動かしながらレンダリングしていきます。

a = []
b = []
c = []

for i in range(height):
    a.append(i+1)

a = list(reversed(a))
i = 0

def rendering(a,b,c):
    cnt = 0
    for idx in a:
        obj = bpy.data.objects[f'hanoi{idx}']
        obj.location = (-height*3, 0, cnt)
        cnt += 1
    cnt = 0
    for idx in c:
        obj = bpy.data.objects[f'hanoi{idx}']
        obj.location = (0, 0, cnt)
        cnt += 1
    cnt = 0
    for idx in b:
        obj = bpy.data.objects[f'hanoi{idx}']
        obj.location = (height*3, 0, cnt)
        cnt += 1
    global i
    i += 1
    bpy.context.scene.render.filepath = (f'tmp/{i}.png')
    bpy.ops.render.render(write_still=True)

rendering(a,b,c)

def hanoi(n, start, end, tmp):
    if n <= 0:
        return
    hanoi(n-1, start, tmp, end)
    end.append(start.pop())
    rendering(a,b,c)
    hanoi(n-1, tmp, end, start)

hanoi(height, a, b, c)

 これで Blender のレンダリング先となっているフォルダに大量の画像が投下されます。後はそれを動画編集ソフトなりで動画化すれば、冒頭のツイートのような動画が作成できます。(床や壁などの設定、ライティングやカメラの画角等は個別に設定しています)。


※ライティング等は個別に設定が必要です。

 注意点として、ハノイの塔は初期状態を含めたら $2^n$ 回のステップが必要なので、height=100 などに設定したら、一回のレンダリングに $0.1$ 秒しかかからないとしても $1.2676506*10^{29}$ 秒必要であり、太陽系が終了するまで待っていても終わりません。またHDD容量も約 $10^{26}$ GB 必要です。要は、現実的ではないので height=4 あたりで実験するのがよいでしょう。

ハノイの塔のステップ

 個人的な、簡単な証明。

 まず、円盤が 1 枚である状態を考える。これを別の棒に移す手間は 1 ステップである。

 次に、円盤が 2 枚である状態を考える。上の 1 枚を除けて考えれば状況は 1. と全く同じである。しかし、上の円盤を除けてから載せ直さなければいけない。つまり、上の 1 枚を除ける→下の 1 枚を移す→上の 1 枚をその上に載せる、という手順が必要である。

 これを一般化する。n 枚を移すためには、

  1. n-1 枚を除ける。
  2. 1 枚を移動する。
  3. n-1 枚をその上に載せる。

 さて、2. に 1 ステップかかることはほぼ自明である。1. と 3. については n-1 枚を動かすための必要な手順に等しい。

 つまり、これは以下のような漸化式で表現できる。

f(1) = 1 \\
f(n) = 2f(n-1) + 1

 これを解いて、必要なステップ数は $2^n-1$ 、初期状態を含めたら必要なレンダリング回数は $2^n$ となる。

参考記事

 再帰プログラム部分は以下の記事を参考にさせていただきました。
【初心者向け】再帰関数(ハノイの塔を分かりやすく!)