曲がった壁を持つ迷路の生成 - その1

いろんなものが途中なのに、また気まぐれに違うものをはじめてしまう。
こういう人はえらくなれません。良い子はマネをしないように。

はじめに

久しぶりにタブレットでBezier曲線を描く話を進めて、簡単なSmoothingのアルゴリズムを見つけた。この方法はとびとびに与えられた2次元平面上の点列を、それを端点にするなめらかなBezier曲線を生成するというものだった。ある端点での曲線の傾きがその前後ふたつの端点の位置だけで決まってしまうミニマルなアルゴリズムで、厳密な内挿に使おうとすると苦しいけど、簡単で破綻が少ないので見た目をなめらかにするには便利。

これが結構気に入ったので、ちょっと脇道にそれて、その簡単な応用として迷路の自動生成を考えてみる。

迷路の自動生成はいくつかのアルゴリズムがあってたくさんのソフトが作られている。しかしほとんどが東西南北の4方向だけに道がある方形のものである。

そこで、そういうのとはちょっと違って壁が曲がって、道がうねっている迷路の自動生成を考えてみたい。

うまい曲がり方の揺らぎを与えられれば、人が作ったような迷路が生成できるかもしれない。そういうのを目指すことにする。

これから行き当たりばったりにアルゴリズムを考えて、うまくいきそうだったら、あとでObjective-Cで実装してみることにする。行き詰まったらシレッ、と何事もなかったかのように他の話題に切り替えることにする。

さて、何から始めよう。