(cache) クラスタリングによる迷路作成アルゴリズム

　クラスタリングアルゴリズムにより、解くと絵が浮かび上がる迷路を作成する方法を紹介する。

注意：ここで言う「クラスタリング」は同値関係をつなぐもので、データ解析で良くでてくるクラスタリング、つまり情報空間上に散らばっているデータ点を適当に似ているもの(近いもの)同士で分類する手法ではありません。

クラスタリングとは

　ウェブのリンク情報や、mixiの友人関係など、ネットワークの性質を知りたいことがよくある。このとき、ネットワークの性質として

　クラスタリングとは、同値関係のリストが与えられたときにグループ分けをすることである。たとえば、

アルゴリズム

　クラスタリングアルゴリズムはいくつか知られているが、そのうち一次元配列を使った簡単な例を紹介する。

　この作業はリンクリストの作成である。下図では、６つの要素からなるリンクリストが、クラスタリングにより２つにグループ分けされた様子を示す。最初、すべての要素のリンクは自分を指しているが、クラスタリングにより、必ず番号の低い側(図では左側)にリンクされる。このとき、自分からたどっていったリンクの終点の要素の番号が自分のクラスタ番号となる。

　以上の作業をコードで書くと以下のようになる。 pair1[i]とpair2[i]に同値関係が入っているとして、関数clusteringを呼んでやればクラスタリングができる。あとは int get_cluster_numberに要素番号を入れればその要素のクラスタ番号が返ってくるので、あとは最大クラスタを探すなり、クラスタの数を数えるなりすることができる。

迷路作成アルゴリズム

　では、クラスタリングを迷路作成に応用してみよう。迷路を作成するには、基本的には枝をつけるだけでよい。しかし、適当に枝を伸ばすと、「入り口からいけない場所(死に領域)ができる」「ループができてしまい、解答が一意でなくなる」などの問題ができてしまう。そこで、クラスタリングを使って解答のパスが一意で、なおかつ死に領域ができないことを保証する。

迷路作成例

　以上のアルゴリズムを用いて、「解くと絵が浮かび上がる迷路」を作ることができる。やり方は簡単で、先に解答のパスを作り、その部分だけクラスタリングしてから壁を壊し始めれば、ループを作らない保証から与えた解答が最短距離となる迷路が出来上がる。以下の図はそのようにして作成した迷路の例である。左図の迷路を解くと、右図のような絵が浮かび上がる。

　上記の迷路は、クラスタリングアルゴリズムによる迷路作成エンジンを実装したソフト「迷次郎」により作成した。

おわりに

　クラスタリングアルゴリズムを応用し、「解くと絵が浮かび上がる迷路」を作成してみた。クラスタリングはあらゆるネットワークの解析に使えるし、コードも２０行もないので知っていて損はないアルゴリズムである。

追記

　誤解している人がいるようなのでいくつか追記。クラスタリングアルゴリズムというのは僕が考えたものではなく、かなり古いアルゴリズム。実装方法はいくつかあるが、上記ではそのうちもっとも簡単なものの一つを紹介してある。また、この記事の主眼は「迷路作成」ではなく、あくまでもクラスタリングアルゴリズムの紹介。

Rubyによるサンプルコード

　上記の説明だけじゃアルゴリズムが分かりにくいようなので、某所用に書いたRubyによる手抜きサンプルを置いておく。実行すると、以下のようなA4一枚の大きさの迷路をeps形式で吐き出す。

　以下はソース。単に実行すれば、同じディレクトリにmaze.epsを作成する。

# maze.rb
# Author: Hiroshi Watanabe
class Maze
def initialize(s)
@lx = s
@ly = @lx*297/210
@bond_h = Array.new((@lx+1)*@ly) { false}
@bond_v = Array.new(@lx*(@ly+1)) { false}
@point = Array.new(@lx*@ly*2) {|i| i}
@GridSize = (600.0-30)/(@lx+4)
@LeftMargin = @GridSize*3
@TopMargin = @GridSize*2
makeMaze
end
def getClusterIndex(x, y)
index = @lx*y+x
while(index != @point[index])
index = @point[index]
end
return index
end
def connect(ix1, iy1, ix2, iy2)
i1 = getClusterIndex(ix1,iy1)
i2 = getClusterIndex(ix2,iy2)
if i1<i2
@point[i2] = i1
else
@point[i1] = i2
end
end
def makeMazeSub
rate = 0.8
for ix in 0..@lx-2
for iy in 0..@ly-1
next if rand <rate
next if getClusterIndex(ix,iy) == getClusterIndex(ix+1,iy)
@bond_h[(@lx+1)*iy+ix+1] = true
connect(ix,iy,ix+1,iy)
end
end
for ix in 0..@lx-1
for iy in 0..@ly-2
next if rand <rate
next if getClusterIndex(ix,iy) == getClusterIndex(ix,iy+1)
@bond_v[(iy+1)*@lx+ix] = true
connect(ix,iy,ix,iy+1)
end
end
end
def makeMazeFinal
for ix in 1..@lx-2
for iy in 1..@ly-1
next if getClusterIndex(ix,iy) == getClusterIndex(ix+1,iy)
@bond_h[iy*(@lx+1)+ix+1] = true
connect(ix,iy,ix+1,iy)
end
end
end
def makeMaze
for i in 0..10
makeMazeSub
end
makeMazeFinal
@bond_h[0] = true
@bond_h[(@lx+1)*@ly-1] = true
end
def exportEPS (filename)
f = open(filename,"w")
f.print "%!PS-Adobe-2.0\n"
f.print "%%BoundingBox: 0 0 600 850\n"
f.print "%%EndComments\n"
f.print "/mydict 120 dict def\n"
f.print "mydict begin\n"
f.print "gsave\n"
g = @GridSize
h = @GridSize*0.5
f.print "/arrow {gsave translate "
f.print "0 0 moveto "
f.print g.to_s + " 0 lineto stroke\n"
f.print g.to_s + " 0 moveto "
f.print h.to_s + " -" + h.to_s + " lineto "
f.print h.to_s + " " + h.to_s + " lineto "
f.print "closepath fill stroke grestore} def\n"
f.print @LeftMargin.to_s + " " + @TopMargin.to_s + " translate \n"
f.print "-" + g.to_s + " " + (g*0.5).to_s + " arrow \n"
f.print "" + (g*@lx).to_s + " " + (g*(@ly-0.5)).to_s + " arrow \n"
for ix in 0..@lx
for iy in 0..@ly-1
x = ix * @GridSize
y = iy * @GridSize
next if @bond_h[iy*(@lx+1)+ix]
f.print x.to_s + " " + y.to_s + " moveto "
f.print x.to_s + " " + (y+@GridSize).to_s + " lineto stroke\n"
end
end
for ix in 0..@lx-1
for iy in 0..@ly
x = ix * @GridSize
y = iy * @GridSize
next if @bond_v[iy*@lx+ix]
f.print x.to_s + " " + y.to_s + " moveto "
f.print ""+(x+@GridSize).to_s + " " + y.to_s + " lineto stroke\n"
end
end
f.print "grestore\n"
f.print "end\n"
end
end
s = 50
if(ARGV.size > 0)
s = ARGV[0].to_i
end
m = Maze.new(s).exportEPS("maze.eps")

クラスタリングによる迷路作成アルゴリズム