--- title: ハミルトン閉路でおもちが動く date: 2020-11-17T00:00:00.000Z updated: 2026-01-08T14:50:56.576Z tags: - making-of - study - "2020" - 2020/11 - 2020/11/17 url: https://baku89.com/ja/2020/11/17/hamiltonian-mochi --- # ハミルトン閉路でおもちが動く ![](https://wp.baku89.com/wp-content/uploads/2020/11/ogp.jpg) ![](https://wp.baku89.com/wp-content/uploads/2020/11/2020-11-17-21-57-58.2020-11-17-21_59_17.gif) [🍡🍡🍡🍡🍡🍡🍡🍡](https://s.baku89.com/hamiltonian-mochi/) [グラフ構造について考えている](/2020/11/09/glisp-dag)うちに思いついたアイディアで Web 作品を作ってみました。もち的な何かが上下左右に気まぐれに動きます。もちイジりは自分の手癖になりつつあるのでいい加減やめたいんですが、こういう動きを作る考え方がちょっと面白かったのでメモしておきます。 --- もちは格子状に配置されていて、それぞれ上下左右に 1 つづつ動くことができます。もちの場所を黒丸で表し、移動できる場所同士を線でつなぐとこんなグラフになります。今回の Web サイトでは上下左右がタイル状に反復しているので、両端の黒丸同士も繋がります。 ![](https://wp.baku89.com/wp-content/uploads/2020/11/hamiltonian_00-1440x960.png) トーラス状になっています 一つのもちが動くことで、移動先にあったもちが押し出され、さらに別のもちが押し出され…という連鎖がおきますが、このグラフ上では各点を一度だけ通るジグザグした矢印として図示できます。そして全てのもち同士がお互いにぶつからずに動けるということは、この矢印がループになっていて、そのループが隙間なく全部の点を埋め尽くしている状態として考えることができます。一筆書きと違い、このループは何本あっても構いません。 ![](https://wp.baku89.com/wp-content/uploads/2020/11/hamiltonian_04-1440x960.png) それぞれの黒丸が矢印の方向にうごく こうしたループを作るのは案外簡単です。まず、もちがぶつからずに動ける「正しい」矢印パターンから始めます。全部のもちが一斉に下に動くのが一番単純でしょうか。一旦移動の向きを忘れて、もちが動く道筋だけを考えます。 ![](https://wp.baku89.com/wp-content/uploads/2020/11/hamiltonian_01-1-1440x960.png) このとき、下図の左のような「一組の対辺が繋がっているがもう一組は繋がっていない」格子を見つけたら、右のように繋ぎ変えるという操作をランダムに行います。 ![](https://wp.baku89.com/wp-content/uploads/2020/11/hamiltonian_02-1440x960.png) 元のパターンが「正しい」限り、この変換で新しくできるパターンも正しいものとなります。こうして出来上がったループにランダムに向きつけをすれば完成です。 ![](https://wp.baku89.com/wp-content/uploads/2020/11/hamiltonian_gen.gif) Web サイトでは、もちが移動する毎に少しずつこの繋ぎ変えをして動きに変化を出しています。 制作するなかで知ったのですが、これは[ハミルトン閉路問題](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%9F%E3%83%AB%E3%83%88%E3%83%B3%E9%96%89%E8%B7%AF%E5%95%8F%E9%A1%8C)にも似ています。ざっくりいうと、このような線と点からなる「グラフのすべての頂点を一度ずつ通って最初の場所へと巡る方法はあるか?」という問題だそうですが、今回の例だと何人かで手分けして巡っても構わないという少し条件の緩いバージョンになるのでしょうか。現に、この方法を考えるのに[ハミルトン路をランダムに生成するアルゴリズム](https://stackoverflow.com/questions/7371227/algorithm-to-find-a-random-hamiltonian-path-in-a-grid)を参考にしていたりします。 また、このやり方だと一旦向きつけを無視して道筋だけを考えますが、向きつけを維持したままループを作る方法もあります。この場合、偶数列のもち達は下に、奇数列のもち達は上に互い違いに動くパターンから始めて、「一組の対辺が逆方向の矢印で繋がった格子」を繋ぎ替える変換を繰り返せば完成です。言葉だと説明が難しいですね…。この方法は、もちが引き返す動作が無くなるのでスムーズに見えるうえに必要な素材動画が減るのでロードも軽くなって一石二鳥なのですが、むしろ気迷ったように三歩進んで二歩戻ってくれたほうが可愛いらしいので、あえて先に説明したような方法をとることにしました。 --- これ、僕はあんまし数学の素地が無いので作りながらほぇ〜ってなってたんですが、もっと賢い方法や、関連する概念があればぜひ教えてほしいです。 グラフ構造に対する操作として一般化して実装したので、格子に限らず色んなパターンに応用できそうです。ハニカム構造みたいな充填図形でも良いですし、シェルピンスキーのギャスケットのような再帰図形の辺上を、縦横の移動だけではなく大きさが変わりながら跳ねるのも不思議そう。あと思いつくのは、別に動画にしなくても、経路自体を[Trunchet tiles](https://en.wikipedia.org/wiki/Truchet_tiles)のようなグラフィックに仕立てても素敵かなと思いました。だれかお願いします。 --- また、今回のサイトはプリレンダ―で作りこんだ動画をスプライト再生する方法をとっています。ただただ重い上にカクつくので Web 系の方からは敬遠されるのですが、映像作家が本分なもので、趣味としては好きです。 こんな感じの動画をうまい具合に再生しているんですが、面白いのは動画全体が状態遷移図のように枝分かれしたタイムラインを持っているところです。 ![](https://wp.baku89.com/wp-content/uploads/2020/11/hamiltonian_07-1440x960.png) これぞ本当の“ノンリニア”な映像 このサイトを作るのに、ここまでに説明したように空間上の移動をグラフとして考えましたが、時間軸でもまた別のグラフ構造が登場しています。これもまた掘れそうな映像技法なので、[ここに色々書いてみました](/2020/11/18/state-machine-animation)。