C言語で蟻の巣を作るアルゴリズムを考える
- 作成日: 2023-04-25
- 更新日: 2023-12-24
- カテゴリ: C言語
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とする。
以上。