ラングトンのアリ

前回書いたライフゲームを調べていたら、「ラングトンのアリ」というものを知りました。ライフゲームよりももっと簡単なたった２個のルールで、まさにアリが歩いた跡のような、複雑な図形が生成されます。

もっと興味深いのは、10000ステップを過ぎたあたりから、それまで混沌（カオス）としていた足跡が、急に規則正しく変化して、右下に一直線に走って行ってしまうように変化することです。

「カオスの縁」というのだそうですが、局所的な単純なルールから、全体的には混沌が生じ、その混沌から突然秩序が生じるわけです。なぞです。

これまた、ルールだけを頼りに自前でコーディングしてみました。またncursesを使いましたが、アリにはもっと広いフィールドが必要な感じです。ncursesだとどうしても表示の分解能が文字単位になってしまうので粗いです。

前回のライフゲームでは、フィールドの大きさを #define で決めうちにしていたのですが、今回は、ターミナルの大きさいっぱいを使うようにしました。起動時のターミナルサイズを取得しmallocしました。アリがフィールドから飛び出るとプログラムが止まるようにしました。

あと、Linuxではループごとにusleepで少し待たないとあっという間に終わってしまうのですが、Cygwinでは何秒に指定しようがusleepを呼ぶだけのオーバーヘッドが数十msくらいある感じで非常に遅いです。下の例ではusleepをコメントアウトしています。

//
// langton's ant
//

#include    <stdlib.h>
#include    <ncurses.h>
#include    <unistd.h>
#define     USLEEP      1

int     **array;
int     width, height;
enum    DIR { NORTH, EAST, SOUTH, WEST };

void    alloc_mem( void );
void    def_color( void );
void    init_array( void );

// allocate memory
void    alloc_mem() {
    int i;
    array = (int **)malloc( sizeof(int *)*width );
    if ( array == NULL ) {
        printf("memory allocation failed.\n");
        exit(EXIT_FAILURE);
    }
    for ( i = 0; i < width; i++ ) {
        array[i] = (int *)malloc( sizeof(int)*height );
        if ( array[i] == NULL ) {
            printf("memory allocation failed.\n");
            exit(EXIT_FAILURE);
        }
    }
}

// define color
void    def_color() {
    start_color();
    init_pair( 0, COLOR_WHITE,  COLOR_BLACK );
    init_pair( 1, COLOR_BLACK,  COLOR_WHITE );
}

// init array
void    init_array() {
    int i, j;

    for ( i = 0; i < width; i++ ) {
        for ( j = 0; j < height; j++ ) {
            array[i][j] = 0;
        }
    }
}

// main
int main(){
    int     i;
    int     x, y;
    int     counter = 0;
    enum DIR    dir;

    // init screen
    initscr();
    getmaxyx( stdscr, height, width );

    // define color
    def_color();

    // allocate memory
    alloc_mem();

    // init array
    init_array();

    // init position
    x = width / 2;
    y = height / 2;
    dir = NORTH;
    mvprintw( y, x, "Hit any key" );
    getch();
    erase();

    // endless loop
    for (;;) {
        if ( array[x][y] == 1 ) {
            array[x][y] = 0;
            attrset( COLOR_PAIR(0) );
            mvaddstr( y, x, " " );
            switch ( dir ) {
                case NORTH:
                    dir = EAST;
                    x = x + 1;
                    break;
                case EAST:
                    dir = SOUTH;
                    y = y + 1;
                    break;
                case SOUTH:
                    dir = WEST;
                    x = x - 1;
                    break;
                case WEST:
                    dir = NORTH;
                    y = y - 1;
                    break;
            }
        } else {
            array[x][y] = 1;
            attrset( COLOR_PAIR(1) );
            mvaddstr( y, x, " " );
            switch ( dir ) {
                case SOUTH:
                    dir = EAST;
                    x = x + 1;
                    break;
                case WEST:
                    dir = SOUTH;
                    y = y + 1;
                    break;
                case NORTH:
                    dir = WEST;
                    x = x - 1;
                    break;
                case EAST:
                    dir = NORTH;
                    y = y - 1;
                    break;
            }
        }

        // judge overflow
        if ( x < 0 || y < 0 || x > width-1 || y > height-1 ) {
            break;
        }

        // draw
        mvprintw( 0, 0, "%d", counter );
        refresh();
        counter++;
        //usleep( USLEEP );
    }

    // finalize
    attrset( COLOR_PAIR(0) );
    mvprintw( 1, 0, "Hit any key" );
    getch();
    endwin();
    return(0);
}

動かすとこんな感じ。