C言語で蟻の巣を作るアルゴリズムを考える

650, 2023-04-25

C言語で蟻の巣を作るアルゴリズム

アルゴリズムを知りたければ検索するかAIに聞くかが話が速い。
だが今回は既存のアルゴリズムなども調べずに1からアルゴリズムを考えてみた。

こういった頭の体操は規模が小さく、自力で解けるレベルであれば面白い。
規模が大きく複雑で自力で解けない場合はつまらない。

蟻の巣を生成するアルゴリズムはかなり単純だ。
やってみたところ初級者～中級者向けと言える。
初級者はちょっと大変かもしれない。

以下のような蟻の巣のようなものを生成する。

............#.................#.................#...........
...........#...................#.................#..........
..........#.....................#...##########....#.........
.........#.......................#.############....####.....
........#.........................##############..#.........
.......#..........................################..........
......#............................############.............
.....#########......................##########..............
....###########.........................#...................
....###########........................#.####...............
.....#########........................####.#................
.......#................................###########.........
......#................................#############........
.....#................................###############.......
....#.................................###############.......
.###...................................#############........
#.......................................###########.........
#....................................######.#...............
.#..................................#........###########....
..########.........................#....#################...
..........#.................#########..###################..
.........#########.........###########.###################..
........###########.......##################################
........#############.....#############.####################
.........#############....################......############
.........##############....################......###########
.........##############.....###############......###########
.........##############.....###############.....############
..........############.......#############......############
.........############............#...............###########
........#.........................#...................#.....
.......#.........................#.....................#....
......#.........................##########..............#...
.......#..................................#..............#..
........#..................................#..............#.
.........######..........................####..............#
.............#............................#................#
............#..............................#......##########
...........#................................#....###########
..........#..................................#...###########

ソースコードだが140行ぐらいである。
今回はこの蟻の巣アルゴリズムを解説したいと思う。

ソースコード全文

ソースコードの全文は以下になる。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

enum {
    WIDTH = 60,
    HEIGHT = 40,
};

typedef enum {
    SAND,
    SPACE,
} Cell;

typedef struct {
    int x, y;
    int ax, ay;
    int time;
} Ant;

Cell canvas[HEIGHT][WIDTH];

void canvas_draw(void) {
    for (int y = 0; y < HEIGHT; y++) {
        for (int x = 0; x < WIDTH; x++) {
            switch (canvas[y][x]) {
            case SAND: putchar('.'); break; 
            case SPACE: putchar('#'); break; 
            }
        }
        putchar('\n');
    }
}

int gen_ax(void) {
    if (rand() % 2 == 0) {
        return -1;
    } else {
        return 1;
    }
}

int gen_ay(void) {
    if (rand() % 2 == 0) {
        return 0;
    } else {
        return 1;
    }
}

void ant_init(Ant *self, int x, int y) {
    self->x = x;
    self->y = y;
    self->ax = gen_ax();
    self->ay = 1;
    self->time = 1;
}

void ant_dig_room(Ant *self) {
    int w = 12 + rand() % 8;
    int h = 4 + rand() % 4;
    int pad = w / 5;
    int threshold = h / 3;
    int subx = w/2;
    int suby = h/2;

    for (int y = 0; y < h; y++) {
        for (int x = pad; x < w - pad; x++) {
            int cx = self->x + x - subx;
            int cy = self->y + y - suby;
            if (cx < 0 || cx >= WIDTH || cy < 0 || cy >= HEIGHT) {
                continue;
            }
            canvas[cy][cx] = SPACE;
        }
        if (y < threshold) {
            pad--;
        } else if (y >= h - threshold - 1) {
            pad++;
        }
    }
}

bool ant_update(Ant *self) {
    canvas[self->y][self->x] = SPACE;

    self->x += self->ax;
    self->y += self->ay;

    if (self->x < 0 || self->x >= WIDTH) {
        self->x -= self->ax;
        self->ax = gen_ax();
    }
    if (self->y >= HEIGHT) {
        return false;
    }
    int seed = 3 + rand() % 3;
    if (self->time % seed == 0) {
        self->time = 1;
        self->ax = gen_ax();
        self->ay = gen_ay();
        if (rand() % 7 == 0) {
            ant_dig_room(self);
        }
    }

    self->time++;

    return true;
}

void dig(int start_x, int start_y) {
    Ant ant;
    ant_init(&ant, start_x, start_y);

    for (;;) {
        if (!ant_update(&ant)) {
            break;
        }
    }
}

int main(void) {
    srand(time(NULL));
    dig(WIDTH * 0.5, 0);
    dig(WIDTH * 0.8, 0);
    dig(WIDTH * 0.2, 0);
    canvas_draw();
    return 0;
}

蟻の巣アルゴリズムの解説

このアルゴリズムはアルゴリズムと言っていいのか。
やってることは座標の更新と道、部屋の作成ぐらいである。
乱数を使っており、毎回違う結果を生成する。

アルゴリズムは以下の通りだ。

キャンバスを作成する
キャンバス上部から蟻を下方向に向けて歩かせる
蟻の現在位置に乱数の確立で円形の部屋を作成する
蟻がキャンバス最下部に到達したら終了
2から4を蟻の数だけ行う

キャンバスを作成する

まず描画先のキャンバスを2次元配列で作成する。

enum {
    WIDTH = 60,
    HEIGHT = 40,
};

typedef enum {
    SAND,
    SPACE,
} Cell;

Cell canvas[HEIGHT][WIDTH];

canvasは2次元配列である。
型は列挙型を型にしたCell型だ。
これはSANDとSPACEの定数を格納する。
もっともenumのtypedefはただのintだからこれらの定数以外も格納はできる。

WIDTHが横幅、HEIGHTが高さだ。
canvasの1次元目がHEIGHTで2次元目がWIDTHである。

キャンバスの関数

canvasに関連する関数はcanvas_draw()がそうだ。

void canvas_draw(void) {
    for (int y = 0; y < HEIGHT; y++) {
        for (int x = 0; x < WIDTH; x++) {
            switch (canvas[y][x]) {
            case SAND: putchar('.'); break; 
            case SPACE: putchar('#'); break; 
            }
        }
        putchar('\n');
    }
}

この関数ではcanvasの値に応じて文字を描画している。
入れ子のループで外側がy軸、中側がx軸になる。
switch文でcanvas[y][x]の値を見て、SANDだったら「.」を描画し、SPACEだったら「#」を描画する。
x軸の描画が終わったら改行を入れて行を作る。

キャンバス上部から蟻を下方向に向けて歩かせる

このアルゴリズムでは蟻を実際に歩かせるので蟻を定義しないといけない。
蟻の定義は以下のとおりである。

typedef struct {
    int x, y;
    int ax, ay;
    int time;
} Ant;

Antは構造体で、メンバ変数を持つ。
x, yは座標。ax, ayは座標に加えるスピードである。
timeは蟻が持つローカル時間で、整数だ。時間と言ってもただのカウント変数である。
蟻はローカル時間に応じて部屋を作成する。

main関数

main関数を見てみる。

int main(void) {
    srand(time(NULL));
    dig(WIDTH * 0.5, 0);
    dig(WIDTH * 0.8, 0);
    dig(WIDTH * 0.2, 0);
    canvas_draw();
    return 0;
}

main関数では最初に乱数のシードを初期化している。
乱数の生成ではrand()関数を使うが、この関数はシードを乱数などで初期化しないと同じ乱数列を作成する。
そのためsrand()にtime(NULL)の返り値を与えてシードを初期化している。

dig()というのがキャンバスを蟻に掘らせる関数だ。
3回呼び出しているが、これは蟻を3匹召喚するということになる。

dig()の引数は第1引数が開始x座標、第2引数が開始y座標になる。

dig関数

dig()関数では最初に蟻を一匹作り、ant_init()で初期化している。

void dig(int start_x, int start_y) {
    Ant ant;
    ant_init(&ant, start_x, start_y);

    for (;;) {
        if (!ant_update(&ant)) {
            break;
        }
    }
}

そのあとに無限ループに入り、ant_update()を実行し、ant_update()の返り値が真の間、ループ処理を継続する。
ant_update()は蟻を更新する関数である。

ant_init関数

ant_init()関数はAntのメンバを引数に応じて初期化する。

void ant_init(Ant *self, int x, int y) {
    self->x = x;
    self->y = y;
    self->ax = gen_ax();
    self->ay = 1;
    self->time = 1;
}

初期化する際にgen_ax()等を使っている。

gen_ax, gen_y関数

gen_ax()関数とgen_ay()関数は乱数によってx軸のスピードとy軸のスピードをそれぞれ生成する。

int gen_ax(void) {
    if (rand() % 2 == 0) {
        return -1;
    } else {
        return 1;
    }
}

int gen_ay(void) {
    if (rand() % 2 == 0) {
        return 0;
    } else {
        return 1;
    }
}

どちらの関数もrand() % 2 == 0で乱数が偶数か奇数かチェックし、分岐しているだけである。
gen_ax()の方は-1か1を返し、gen_ay()の方は0か1を返す。

ant_update, ant_dig_room関数

アルゴリズムの本丸であるこの2つの関数は以下になる。

void ant_dig_room(Ant *self) {
    int w = 12 + rand() % 8;
    int h = 4 + rand() % 4;
    int pad = w / 5;
    int threshold = h / 3;
    int subx = w/2;
    int suby = h/2;

    for (int y = 0; y < h; y++) {
        for (int x = pad; x < w - pad; x++) {
            int cx = self->x + x - subx;
            int cy = self->y + y - suby;
            if (cx < 0 || cx >= WIDTH || cy < 0 || cy >= HEIGHT) {
                continue;
            }
            canvas[cy][cx] = SPACE;
        }
        if (y < threshold) {
            pad--;
        } else if (y >= h - threshold - 1) {
            pad++;
        }
    }
}

bool ant_update(Ant *self) {
    canvas[self->y][self->x] = SPACE;

    self->x += self->ax;
    self->y += self->ay;

    if (self->x < 0 || self->x >= WIDTH) {
        self->x -= self->ax;
        self->ax = gen_ax();
    }
    if (self->y >= HEIGHT) {
        return false;
    }
    int seed = 3 + rand() % 3;
    if (self->time % seed == 0) {
        self->time = 1;
        self->ax = gen_ax();
        self->ay = gen_ay();
        if (rand() % 7 == 0) {
            ant_dig_room(self);
        }
    }

    self->time++;

    return true;
}

ant_update()はループが一回回るごとに呼ばれる。
関数が呼ばれたらx, yの値をax, ayで加算する。
こうすることで蟻の座標が更新される。

if文でxがキャンバスの範囲から出てないか調べる。
出ていたらxの値を戻し、axの値を再度生成する。

yもキャンバスの高さを超えていたらreturn false;で偽を返す。
ant_update()が偽を返すとループが終了する。

    int seed = 3 + rand() % 3;

というコードはシードを計算している。
3 + rand() % 3という式は「3以上、6より下の整数」を生成する式になる。
シードでtimeの値を剰余算し、結果が0だったらtimeを初期化する。

    if (self->time % seed == 0) {
        self->time = 1;
        self->ax = gen_ax();
        self->ay = gen_ay();
        if (rand() % 7 == 0) {
            ant_dig_room(self);
        }
    }

この時にax, ayの値も更新する。
再びrand() % 7して結果が0だったらant_dig_room()を呼び出す。
ant_dig_room()は蟻の現在位置に部屋を作る関数だ。

void ant_dig_room(Ant *self) {
    int w = 12 + rand() % 8;
    int h = 4 + rand() % 4;
    int pad = w / 5;
    int threshold = h / 3;
    int subx = w/2;
    int suby = h/2;

    for (int y = 0; y < h; y++) {
        for (int x = pad; x < w - pad; x++) {
            int cx = self->x + x - subx;
            int cy = self->y + y - suby;
            if (cx < 0 || cx >= WIDTH || cy < 0 || cy >= HEIGHT) {
                continue;
            }
            canvas[cy][cx] = SPACE;
        }
        if (y < threshold) {
            pad--;
        } else if (y >= h - threshold - 1) {
            pad++;
        }
    }
}

ant_dig_room()ではいろいろやっているが、やっていることは部屋の大きさの計算。
それから部屋の角を丸めるためのpadの計算、padを更新するためのthresholdの計算。
それからsubx, subyは部屋の大きさの半分の値になる。これは座標の生成の計算で使われる。

ループだが基本的にはこれは入れ子のループでキャンバスを描画するときに使ってるものと一緒である。
違うのはpadによりx軸の範囲が動的に狭まったり広がったりしている点である。
この狭まりと広まりは部屋の角を丸めるために行われる。

         for (int x = pad; x < w - pad; x++) {   
            ...
        }

このpadの計算は1つ目のループの後方で行われる。

        if (y < threshold) {
            pad--;
        } else if (y >= h - threshold - 1) {
            pad++;
        }

1つ目のループのカウント変数yがthresholdより低ければpadを減算し、h - threshold - 1以上であれば加算する。

前後するが2つ目のループでは

        for (int x = pad; x < w - pad; x++) {
            int cx = self->x + x - subx;
            int cy = self->y + y - suby;
            if (cx < 0 || cx >= WIDTH || cy < 0 || cy >= HEIGHT) {
                continue;
            }
            canvas[cy][cx] = SPACE;
        }

cxとcyを計算し、その座標がキャンバスの範囲内ならSPACEを代入している。
こうすることで部屋の空間ができる。

ソースコードの解説は以上だ。

おわりに

蟻の巣を生成してみたかったのでアルゴリズムを考えてみた。
もしかしたら先人がもっと良いアルゴリズムを考えている可能性もあるが、ホビーなので自分で考えるのが楽しいのである。
ソースコードのライセンスはMITとする。
以上。

C言語で蟻の巣を作るアルゴリズムを考える

目次

関連記事