ラングトンのアリの描画 in C++ DouKaku?

ラングトンのアリの描画

ラングトンのアリを描画してください。ラングトンのアリは、以下のような動きをする、セル・オートマトンです。(Wikipediaより引用)
- 黒いマスにアリがいた場合、90°右に方向転換し、そのマスの色を反転させ、1マス前進する。
- 白いマスにアリがいた場合、90°左に方向転換し、そのマスの色を反転させ、1マス前進する。
詳しくはWikipedia等で調べるか、参考ページに拙作のデモがありますのでご覧下さい。

see: JavaScriptでラングトンの蟻

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html lang="ja">
<head>
       <meta http-equiv="content-type" content="text/html;charset=utf-8">
       <meta http-equiv="content-script-type" content="text/javascript">
       <meta http-equiv="content-style-type" content="text/css">
       <title>ラングトンの蟻</title>
<style type="text/css">
#canvas{
       border: 1px solid #999;
       width: 300px;
       height: 300px;
}
#canvas div{
       width: 3px;
       height: 3px;
       float: left;
}
</style>
<script>
var earth = [];
var WORLD_SIZE = 100;
var lang_ant;

function Ant(){}
Ant.prototype = {
    age : 0,
    ageDisplay : undefined,
    id : undefined,
    speed: 200,
    direction: [0,-1],//向き。x軸 y軸。最初は上に動く
    position: [60,40],//初期位置
    world: [],
    start: function(){
        var self = this;
        this.id = setInterval(function(){self.move()}, 1000/this.speed);
    },
    move: function(){
        this.ageDisplay.innerHTML = ++this.age;
        this.moveNextCell();
        var cell = this.getCellInfo();
        var color = cell.getAndToggleColor();
        this.setNextDirection(color);
    },
    moveNextCell: function(){
        this.position[0] += this.direction[0];
        this.position[1] += this.direction[1];
        if(this.position[0] < 0 || this.position[1] < 0 ||
           this.position[0] >= WORLD_SIZE || this.position[1] >= WORLD_SIZE){
            clearInterval(this.id);
            this.die();
        }
    },
    getCellInfo: function(){
        var idx = this.position[0] + this.position[1] * WORLD_SIZE;
        return this.world[idx];
    },
    setNextDirection: function(bool){//colorがfalse(白)なら右へ、true(黒)なら左へ転回
        if(bool){//黒
            var tmp = this.direction[0];
            this.direction[0] = this.direction[1];
            this.direction[1] = -tmp;
        }
        else{//白
            var tmp = this.direction[0];
            this.direction[0] = -this.direction[1];
            this.direction[1] = tmp;
        }
    },
    die: function(){
        alert('Langton\'s ant is dead.');
        throw true;
    }
};

function Cell(elm){
    this.elm = elm;
}
Cell.prototype = {
    elm: undefined,
    color: false, //colorは2値なのでbooleanで表す
    colorList: ['#FFF','#000'],
    getAndToggleColor: function(){
        this.color = !this.color;
        var i = this.color ? 1 : 0;
        this.elm.style.backgroundColor = this.colorList[i];
        return !this.color;
    }
}
window.onload = function(){
    var canvas = document.getElementById('canvas');
    var div = '<div></div>';
    var inner_canvas = "";
    for(var i=0; i< WORLD_SIZE*WORLD_SIZE; i++){
        inner_canvas += div;
    }
    canvas.innerHTML = inner_canvas;
    
    var cells = canvas.childNodes;
    for(var i=0; i<cells.length; i++){//世界の誕生
        earth[i] = new Cell(cells[i]);
    }
    lang_ant = new Ant();//蟻の誕生
    lang_ant.world = earth;//地球に降り立つ
    lang_ant.ageDisplay = document.getElementById('step');
    
    document.getElementById('run').disabled = false;
}
</script>
</head>
<body>
<p><input type="button" value="run" onclick="lang_ant.start();this.disabled=true;" id="run" disabled="disabled">　<span id="step"></span>
　<input type="button" value="stop &amp; refresh" onclick="location.reload();"></p>
<div id="canvas"></div>

post comment

Posted feedbacks - C++

C++でWTL使いました。GDIで描画、Windowsのタイマーメッセージ (WM_TIMER) を使って回数を進めるようにしています。高速に結果を見たかったので、1度のタイマイベントで複数回進めるようにしています。

ありを進める部分はなんの工夫もないですが。

#define WINVER 0x0400
#define _WIN32_WINDOWS 0
#define _WIN32_WINNT 0
#define _WIN32_IE 0x0300 // IE3以上を指定しないとWTLがコンパイルエラーを起こす。

#define WIN32_LEAN_AND_MEAN
#define _ATL_NO_AUTOMATIC_NAMESPACE
#define _WTL_NO_AUTOMATIC_NAMESPACE

#include <cassert>
#include <sstream>

#include <tchar.h> // _tWinMain

#include <windows.h>
#include <atlbase.h> // ATL共通ヘッダ
#include <atlwin.h> // CWindowImplほか
#include <atlcrack.h> // MSG_*
#include <atlapp.h> // <atlmisc.h>
#include <atlmisc.h> // CPoint

const int ID_TIMER = 1;

enum Direction {Up, Right, Down, Left};

class MainWindow :
    public ATL::CWindowImpl<MainWindow, ATL::CWindow, ATL::CFrameWinTraits>
{
public:
    MainWindow() : field(), x(100), y(100), direction(Up), step() {} // このxとyの値が初期位置

    // ウィンドウクラス名を登録
    DECLARE_WND_CLASS(TEXT("Langton's ant"));

    // メッセージマップ
    BEGIN_MSG_MAP(MainWindow)
        MSG_WM_TIMER(OnTimer)
        MSG_WM_PAINT(OnPaint)
        MSG_WM_CREATE(OnCreate)
        MSG_WM_DESTROY(OnDestroy)
    END_MSG_MAP()
private:
    void OnTimer(UINT /*idEvent*/)
    {
        for (int i = 0; i < 16; ++i) // 1度のタイマイベントで複数回進める。
        {
            NextStep();
            ++step;
        }
        std::basic_ostringstream<TCHAR> oss;
        oss << TEXT("Langton's ant - step: ") << step;
        SetWindowText(oss.str().c_str());
        Invalidate(FALSE);
    }

    static const int TILE_WIDTH = 2, TILE_HEIGHT = 2;
    static const int X = 200, Y = 200;

    void OnPaint(HDC)
    {
        WTL::CPaintDC dc(m_hWnd);
        for (int i = 0; i < Y; ++i)
        {
            for (int j = 0; j < X; ++j)
            {
                dc.FillSolidRect(j * TILE_WIDTH, i * TILE_HEIGHT,
                    TILE_WIDTH, TILE_HEIGHT,
                    field[i][j] ? RGB(255, 255, 255)
                                : RGB(0, 0, 0));
            }
        }
    }

    LRESULT OnCreate(CREATESTRUCT const* pcs)
    {
        RECT rc = {0, 0, TILE_WIDTH * X, TILE_HEIGHT * Y};
        AdjustWindowRectEx(&rc, pcs->style, FALSE, pcs->dwExStyle);
        SetWindowPos(0, &rc, SWP_NOMOVE | SWP_NOZORDER);
        SetTimer(ID_TIMER, 10, 0);
        return 0;
    }

    void OnDestroy()
    {
        PostQuitMessage(0);
    }

    void NextStep()
    {
        if (field[y][x]) // trueが白、falseが黒としている
        {
            if (direction == Up)
            {
                direction = Left;
            }
            else
            {
                --direction;
            }
        }
        else
        {
            if (direction == Left)
            {
                direction = Up;
            }
            else
            {
                ++direction;
            }
        }
        field[y][x] = !field[y][x];
        switch (direction)
        {
        case Up:
            y--;
            if (y == -1)
            {
                y = Y - 1;
            }
            break;
        case Right:
            x++;
            if (x == X)
            {
                x = 0;
            }
            break;
        case Down:
            y++;
            if (y == Y)
            {
                y = 0;
            }
            break;
        case Left:
            x--;
            if (x == -1)
            {
                x = X - 1;
            }
            break;
        default:
            assert(0);
        }
    }

    bool field[Y][X];
    int y;
    int x;
    int direction; //Direction（列挙）型では++と--できない（できるようにするのが面倒）。
    int step;
};

int WINAPI _tWinMain(HINSTANCE, HINSTANCE, LPTSTR, int cmdShow)
{
    MainWindow wnd;
    wnd.Create(NULL, ATL::CWindow::rcDefault, TEXT("Langton's ant"),
        WS_CAPTION | WS_SYSMENU | WS_DLGFRAME | WS_MINIMIZEBOX
        | WS_OVERLAPPED | WS_SYSMENU, WS_EX_APPWINDOW);
    wnd.ShowWindow(cmdShow);
    wnd.UpdateWindow();

    WTL::CMessageLoop msgLoop;
    return msgLoop.Run();
}

OpenGL/GLUTで。

ウィンドウの表示と描画がコードの半分以上orz。

作成はMac OS Xでしています。他の環境の場合には調整してください。

コンパイルは、

g++ -ansi -Wall -framework OpenGL -framework GLUT -framework Foundation -o doukaku276 doukaku276.cpp

終了条件はないので、ESCキーかQキーで終了させてください。

#include <bitset>
#include <GLUT/glut.h>

class Field
{
public:
    virtual ~Field() {}

    virtual bool operator () (int x, int y) const = 0;
    virtual void set(int x, int y) = 0;
    virtual void unset(int x, int y) = 0;
};

template<int Width, int Height>
class ConcreteField : public Field
{
public:
    ConcreteField() : bits_() {}

    bool operator () (int x, int y) const { return bits_[y * Width + x]; }
    void set(int x, int y) { bits_[y * Width + x] = true; }
    void unset(int x, int y) { bits_[y * Width + x] = false; }
private:
    std::bitset<Width * Height> bits_;
};

class Direction
{
public:
    static const int North = 0;
    static const int East  = 1;
    static const int South = 2;
    static const int West  = 3;

    Direction(int dir) : dir_(dir) {}

    void set(int dir) { dir_ = dir; }
    int get() const { return dir_; }

    void turnRight()
    {
        dir_ += 1;
        dir_ %= 4;
    }

    void turnLeft()
    {
        dir_ += 3;
        dir_ %= 4;
    }

private:
    int dir_;
};

class Ant
{
public:
    Ant(int x, int y, Direction direction) : x_(x), y_(y), direction_(direction) {}

    void move(Field& field)
    {
        if(field(x_, y_))
        {
            field.unset(x_, y_);
            direction_.turnRight();
            moveForward();
        }
        else
        {
            field.set(x_, y_);
            direction_.turnLeft();
            moveForward();
        }
    }

    void moveForward()
    {
        switch(direction_.get())
        {
        case Direction::North: --y_; break;
        case Direction::East:  ++x_; break;
        case Direction::South: ++y_; break;
        case Direction::West:  --x_; break;
        default:                     break;
        }
    }

private:
    int       x_;
    int       y_;
    Direction direction_;
};

static const int Interval = 0;
static const int Width    = 320;
static const int Height   = 240;

static ConcreteField<Width, Height> field;
static Ant                          ant(Width / 2, Height / 2, Direction::North);

void display()
{
    glClear(GL_COLOR_BUFFER_BIT);

    static const GLdouble black[] = { 0.0, 0.0, 0.0 };
    glColor3dv(black);

    glBegin(GL_POINTS);
    for(int y = 0; y < Height; ++y)
    {
        for(int x = 0; x < Width; ++x)
        {
            if(field(x, y))
            {
                glVertex2f(x, y);
            }
        }
    }
    glEnd();

    glutSwapBuffers();
}

void resize(int w, int h)
{
    glViewport(0, 0, w, h);
    glLoadIdentity();
    glOrtho(-0.5, w - 0.5, h - 0.5, -0.5, -1.0, 1.0);
}

void key(unsigned char key, int x, int y)
{
    switch(key)
    {
    case 'q':
    case 'Q':
    case '\033':
        std::exit(0);
        break;

    default:
        break;
    }
}

void timer(int n)
{
    ant.move(field);
    display();
    glutTimerFunc(Interval, timer, 0);
}

void initWindow(int argc, char* argv[])
{
    glutInitWindowPosition(100, 100);
    glutInitWindowSize(Width, Height);
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_RGBA | GLUT_DOUBLE);

    glutCreateWindow("doukaku#276");

    glClearColor(1.0, 1.0, 1.0, 1.0);
}

void initEvent()
{
    glutDisplayFunc(display);
    glutReshapeFunc(resize);
    glutKeyboardFunc(key);
    glutTimerFunc(Interval, timer, 0);
}

int main(int argc, char* argv[])
{
    initWindow(argc, argv);
    initEvent();

    glutMainLoop();

    return 0;
}

DouKaku?

ラングトンのアリの描画

Posted feedbacks - C++

Index

Feed

Other

Link

Pathtraq