カオスゲーム

カオスゲーム（英: Chaos game）とは本来、多角形とその内部のランダムな点を使ってフラクタルを作る方法を指す。多角形の辺と前の点をランダムに選び、その距離に所定の分数をかけた位置を新たな点とし、これを繰り返すことでフラクタルな図形を得る。三角形と係数 1/2 を用いるとシェルピンスキーのギャスケットが得られる。この手法を使うと、元の図形が隠れたフラクタルオーダーを持っていれば、様々な図形を生成できる。カオスゲームは、無作為な過程によって事前に定義された結果が得られる例である。
今日では、カオスゲームの意味はより一般化しており、反復関数系 (IFS) のアトラクターまたは不動点を生成する方法を指す。任意の点 x0 を開始点とし、xk+1 = fr(xk) のように反復的に次の点を求める。ここで、fr はIFSから無作為に選択されたメンバーである。この反復によってIFSは不動点に収束する。x0 がIFSのアトラクターに属するなら、反復で得られる全ての xk もアトラクターに属し、稠密な集合を形成する。
n個の関数群についての反復過程を擬似コードで表すと、次のようになる。
 (x,y) = 単位矩形内の無作為な点<br>
 反復 {<br>
 i = 0 以上 n-1 以下の無作為な整数<br>
 (x, y) = Fi(x, y)<br>
 plot(x, y)<br>
 }<br>
プロットされる点の集まりで、アトラクター全体が無作為に描画されていく。これは、順番に点を描画していく普通のフラクタルとは対照的であり、アルゴリズムによって無数の点が描画されることでアトラクターの画像が浮かび上がってくる。