WCE blog

ゲーム制作サークル 早稲田コンピュータエンタテインメント

セルオートマトンを用いた幾何学模様の生成

f:id:WCE:20130401212821p:plain

プログラミング班2年のアゲハマです。
今回は砂山モデルの紹介と、それを使ったきれいな模様の作り方を書きたいと思います。

1.セルオートマトンとは

セルオートマトンとはセルによって構成される計算モデルです。
代表的なものにライフゲームが挙げられます。

詳しくは http://ja.wikipedia.org/wiki/セル・オートマトン へ。

2.砂山モデルの説明

今回用いる砂山モデルについて説明をします。
砂山モデルとは2次元セルオートマトンの一種で、砂山が崩れ落ちる様子をモデル化したものです。

f:id:WCE:20130401211607p:plain

エクセルのような、各セルが整数の値を持つ2次元平面を想像してください。
各セルの値はそこに積まれている砂粒の数を表したものです。
ここで、平面上の適当な場所に砂粒を落としていき、高さが4になったら隣接する4つのセルに1ずつ移動させる、という操作を繰り返します。
すると、この隣接セルへの移動が連鎖反応を引き起こし、大きな雪崩につながることがあります。
この雪崩の頻度と規模は、べき乗に分布することが知られており、べき乗法則に従う自然現象(地震など)の研究に用いられることもあるようです。

3.砂山モデルのプログラミング

では、この砂山モデルをプログラムに書き起こしてみましょう。
ここではSiv3Dライブラリを用いていますが、画像データをピクセルごとに参照できれば何を使っても大丈夫です。

#include <Siv3D.hpp>

const int repsize = 4;
const Point replacer[repsize] = 
{
    Point(-1,0),Point(1,0),Point(0,-1),Point(0,1)
};
const Color backcolor = Palette::Skyblue;
const Color sandcolor = Color(239,228,176,0);
const double scale = 1.0;
const Point size(512,512);

class SandHill
{
    std::vector<std::vector<unsigned>> m_cells,m_temp;
    Image m_image;
    DynamicTexture m_texture;

    //移動するセルの値をm_tempに保存する
    void calcFlow()
    {
        for( unsigned y=0; y<m_image.height; ++y )
        {
            for( unsigned x=0; x<m_image.width; ++x )
            {
                unsigned& cell = m_cells[y][x];
                if( repsize <= cell )
                {
                    const int plus = cell / repsize;
                    cell %= repsize;
                    
                    for(int i=0; i<repsize; ++i)
                    {
                        Point p = replacer[i]+Point(x,y);
                        p.x = Clamp<int>(p.x,0,m_image.width-1);
                        p.y = Clamp<int>(p.y,0,m_image.height-1);
                        m_temp[p.y][p.x] += plus;
                    }
                }
            }
        }
    }
    //m_tempに保存した値をセルに加える
    void updateCells()
    {
        for( unsigned y=0; y<m_image.height; ++y )
        {
            for( unsigned x=0; x<m_image.width; ++x )
            {
                m_cells[y][x] += m_temp[y][x];
                m_temp[y][x] = 0;
            }
        }
    }
    void updateImage()
    {
        for( unsigned y=0; y<m_image.height; ++y )
        {
            for( unsigned x=0; x<m_image.width; ++x )
            {
                m_image[y][x].a = 255*m_cells[y][x]/repsize;
            }
        }
    }
public:
    SandHill(int w, int h, const Color& c)
        :m_cells(h,std::vector<unsigned>(w)),m_temp(m_cells),m_image(w,h,c),m_texture(m_image){}
    void drop(const Point& pos, unsigned value)
    {
        Point p = pos;
        p.x = Clamp<int>(p.x,0,m_image.width-1);
        p.y = Clamp<int>(p.y,0,m_image.height-1);
        m_cells[p.y][p.x] += value;
    }
    void update()
    {
        calcFlow();
        updateCells();
        updateImage();
    }
    void draw()
    {
        m_texture.fill(m_image);
        m_texture.scale(scale).draw(size*(1-scale)/2);
    }
};

void Main()
{
    Window::Resize(size.x,size.y);
    Graphics::SetBackGround(backcolor);

    SandHill sandhill(size.x,size.y,sandcolor);
    
    while(System::Update())
    {
        if(Input::MouseL.pressed)//クリックした場所に砂を落とす
        {
            sandhill.drop(size/2+(Mouse::Pos()-size/2)/scale,500);
        }
        sandhill.update();
        sandhill.draw();
    }
}

実行結果:
f:id:WCE:20130401212750p:plain
なんとなく上から砂を落としているように見えますね。

4.模様を作る

先ほどのプログラムでマウスの位置を固定していると、対称的な図形が現れてきます。
初期値も行う操作も対称的なので当然と言えば当然な気もしますが、少しルールを変えればもっと綺麗な模様が作れそうです。
ということで、先ほどのソースコードの以下の部分を書き換えてみましょう。

const int repsize = 4;
const Point replacer[repsize] = 
{
    Point(-1,0),Point(1,0),Point(0,-1),Point(0,1)
};
const Color backcolor = Palette::Skyblue;
const Color sandcolor = Color(239,228,176,0);
const double scale = 1.0;

ここを以下のように書き換えてください。

const int repsize = 24;
const Point replacer[repsize] = 
{
    Point(-3,-3),Point(-2,-3),Point(-1,-3),Point(0,-3),Point(0,-2),Point(0,-1),
    Point(3,-3),Point(3,-2),Point(3,-1),Point(3,0),Point(2,0),Point(1,0),
    Point(3,3),Point(2,3),Point(1,3),Point(0,3),Point(0,2),Point(0,1),
    Point(-3,3),Point(-3,2),Point(-3,1),Point(-3,0),Point(-2,0),Point(-1,0)
};
const Color backcolor = Palette::Black;
const Color sandcolor = Alpha(0);
const double scale = 3.0;

書き換え前のreplacerは、現在のセルを中心とした相対座標で、上下左右の4つの隣接するセルを表しています。
それに対して書き換え後のreplacerは、下の画像の黒い場所を表しています。

つまり、セルに24個の砂粒が積まれたら、この画像の黒い部分に1つずつ割り振るという操作になります。
もはや砂山でも何でもないですが、実行結果は次のようになります。

実行結果:
f:id:WCE:20130401223804p:plain
面白い模様がいくつかできました。
画像がなんとなくぼやけて見えるのは、自動で補間がかかっているからです。
ちなみに、このようなドット絵を拡大する時はニアレストネイバー法を用いるとぼやけずに拡大できます。

5.まとめ

先ほどのreplacerを画像から読み込めるようにしたものがこちらです。
これで生成される画像はグレースケールなので、Photoshopのグラデーションマップなどで適切に加工すると良いと思います。