高難易度の3Dパズルを自動設計する技術

高難易度の3Dパズルを自動設計する技術

テクノロジーの最新研究を紹介するWebメディア「Seamless」を主宰する山下裕毅氏が執筆。新規性の高い科学論文を山下氏がピックアップし、解説する。

シンガポールのSingapore University of Technology & Design(SUTD)、スイスのEPFLとETH Zurich、オーストリアのInstitute of Science and Technology Austria(ISTA)による研究チームが開発した「Computational Design of High-level Interlocking Puzzles」は、高度な3Dパズルを設計するためのボクセルベースの計算フレームワークだ。ユーザーはパズルの形状やピース数、難易度などを指定でき、独自の3Dパズルを設計できる。

異なる4つのパーツが組み合わさった3Dパズル。最短8回の移動で全てを分解できる

組み立てるとバラバラにならないインターロッキングパズルがある。ジグソーパズルもその一種で、立体的にした3Dインターロッキングパズルも存在する。異なる複雑なパーツが複数絡み合い、留め具を必要とせず一体となり固定される。簡単に分解できるものから難易度の高いものもある。

今回は分解過程をより複雑にし、指定した難易度の高さにあったインターロッキングパズルを設計できる計算フレームワークを提案する。難易度だけでなく、パズルの形状とピース数も指定することができる。

この問題を扱いやすくするために、パズルの形状をボクセル化されたモデルとして表現する。難易度は、ルートノード(組み立てられ一体となったパズル)からターゲットノード(分解された1つの各パーツ)までの最短パスの長さに対応する。

以下の図では上段が難易度レベル1、下段がレベル5を指し、水色の枠から中のパーツを外へ取り出す工程を示している。上段のレベル1は1手で1つ目のパーツを取り出せるが、レベル5は5回目でやっと1つ目のパーツを取り出せる。このように最短で1つ目のパーツが取り出せる回数をレベル数にしている。同じパーツ数でも各パーツの形状で難易度を上げられる。

上段がレベル1の難易度で、下段がレベル5の難易度

今回の計算フレームワークは高い難易度でも分解工程を導き出す。以下の図では5つのパーツで構成するパズルを用いたシミュレーションで、27回目で最初のパーツが外せるレベル27が指定されている。

 

最短27手で1つ目のパーツを取り出せるレベル27の3Dパズル(全5ピース)

この手法を拡張し、ボクセルではなく滑らかな外観を持つパズルの生成にも挑戦した。これは同等の精度を維持したまま、組み立てたときにボクセル以外の外観に形成するというものだ。例えば、フクロウやモアイ像など、組み立てると表面が湾曲したフィギュアになる。

 

上段がキューブフレームで、下段が滑らかな外観の3Dパズル

 

シミュレーションだけでなく、実際に3Dプリンタで印刷し造形物として出力した。組み立てと分解ができ、その実用性を示した。

 

Source and Image Credits: Rulin Chen, Ziqi Wang, Peng Song and Bernd Bickel. “Computational Design of High-level Interlocking Puzzles”.