はじめに
たまたま職場で自動迷路作成の話題が出て、そういえば作ったことないと思って調べてみたら、穴掘り法というアルゴリズムがすぐに出てきました。一番分かりやすかったので、とりあえずこれを実装してみることにしました。
私は以下のサイトが分かりやすかったので解説をもとに実装をしてみました。
ソースコードは特になかったので、参照実装なくゼロからの実装となって極めて自信がない状態からのスタートでした。
穴掘り法
アルゴリズムの詳細な説明はここでは割愛しますが、簡単にいうと、壁に穴を掘っていくスタイルの作成法です。詳しい説明は上記サイトや他の詳細な解説のあるサイトに譲ります。
実装的には、迷路全体を2次元配列で確保して、その配列中の任意の位置をランダムで指定し、そこを起点にして各方向に穴を掘り進む＝壁を道に変えていく、という作業を繰り返します。すべて掘り進めることができなくなった時点で自動生成は終了となります。
実行環境
clangやgccなどで実行ファイルにコンパイルできるPOSIX準拠な環境であれば問題ないかと思います。
% cc maze.c
% ./a.out
ソースコード
githubに実装があります。このソースをもとに以下解説を試みます。
設計
常々私は「実装3割、設計6割、デバッグ1割」という考え方をもっています。これが適正かどうかはさておき、コードを書く前に設計をしておく必要があります。
ここでのおおまかな設計ポイントは以下のとおりです。
- どのような形でデータを保持するか
- データの種類は何か
- どのような実装手法を用いるか
データの保持
すでに説明しているとおり、平面のマップを生成するには2次元配列が都合がよさそうです。
もちろん1次元配列でも可能ですが、その場合には座標からスカラーを算出する必要があります。
C言語では2次元配列簡便かつ直感的な2次元配列を使用することにします。
データの種類
データは「壁」「道」の2種類を想定。これらの表現には整数でよさそうです。したがって、整数の2次元配列を用います。
壁と道はそれぞれ定数ですので、この定数も設定しましょう。
また、掘り「進む」わけですから、進行方向を判断する要素が必要です。これはベクトル(座標)で持つ必要があるでしょう。
実装手法
穴掘り法のアルゴリズムは、同じ作業を繰り返し実施しますので、ループか再帰のどちらかを使用することになるでしょう。
「掘りすすめることができなかったら、1つ手前まで戻る」という作業が入るため、前の座標を思えておく必要があります。これにはスタックか再帰のどちらかが必要となるでしょう。前者は自前でスタックを持つ方法で、後者は関数内で自分自身を呼ぶのでプログラム自身のスタック領域を使う方法で、結果的にはどちらもスタックを使っていることにはなります。分かりやすい、あるいは自分で実装しやすい方を選ぶことになります。
私の場合は、再帰を使うことにしました。
実装
実際に私がたどった実装を追ってみます。実装自体はmaze.cという1ファイルに収まっています。これを書いた時点で97行程度です。実装中にコメントはほぼありません(普段の実装では入れています)。
定数・変数・ヘッダファイル
設計に基づき、定数や変数を実装します。includeするヘッダファイルも、とりあえず必要そうなものを列挙します。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define WIDTH 59 /** gt or eq 5 */
#define HEIGHT 25 /** gt or eq 5 */
#define ROAD 0
#define WALL 1
int map[WIDTH][HEIGHT];
printf()などを使うのでstdio.hを、rand()などを使うのでstdlib.hを、そしてsrand()のseedでtime()を使うのでtime.hを、それぞれインクルードしています。
定数は4つ用意しています。2つはマップサイズ。幅と高さ(長さ)、つまり横と縦を規定しています。掘りすすめるには最低でも5×5が必要そうなのでコメントに書いてあります。
本来ならこの値の判定をする必要があるはずですが、定数をプログラム中で判定しても意味がないので省略しています。これを定数で用意せず別の形で提供する場合は、大小判断などが必要になりそうです。
のこりの2定数は「道」「壁」の値です。これはenumで用意してもいいかもしれません。
そしてデータを保持する2次元配列です。map[][]を用意して、ここに壁や道を記録していきます。道や壁をenumで用意する場合は、ここがintではなくenumになることとなるでしょう。
map[][]は、コンピュータ屋が(たぶん)直感的で分かりやすいように設定しています。
つまり、左上をmap[0][0]、map[WIDTH][HEIGHT]を右下ととるような座標系にしています。
掘り進む方向
掘り進む方向を示すベクトルを用意します。
平面なので方向は4方向(上下左右)です。座標は構造体を設定し、この配列で示すようにしました。
struct {
int x;
int y;
} dir[] = {
{0, -1}, /** UP */
{0, 1}, /** DOWN */
{-1, 0}, /** LEFT */
{1, 0} /** RIGHT */
};
ここは定数を設定しなかったのですが(if文など一部でしか使用しないので定数化の意味がないと思ってしていません)、dir[]の添字が0は上に進む、1は下に、2は左に、3は右にというようにしています。定数化していないのでコメントを添えています。
方向の指定の例です。上に進む場合は方向が「0」ですので、map[][]の2次元目の添字を-1することになります。これは先ほど説明したmap[][]配列の座標系の定義からわかります。
上に進むのでdir[0]を参照し、その構造体には{0, -1}、すなわちx=0, y=-1が入っているので、dir[0].x、dir[0].yとして取り出して利用することにします。
必要な定数や変数は揃いましたので、いよいよプログラム本体の実装に入ります。
メイン関数
まず、メイン関数を最初に書きました。
どういう順番で機能を呼び出すか、という点から頭を整理しつつ書き始めました。
int main()
{
init();
for (int i = 0; i < 3; i++) {
maze_init();
maze();
print();
}
return 0;
}
最初からこの形で用意したわけではないのですが、ほぼ変わらない状態です。
for文は単に3つ連続で生成しているだけなので、なくてもよいでしょう。
init()とmaze_init()を分離したのは、乱数の初期化(srand)とマップ初期化を分離したためです。for文を入れず1回だけしか実行しないのであれば、共存してても問題ありません。
maze()関数は迷路の生成起点です。
print()関数は迷路の出力(表示)をしています。
初期化とマップ表示
特に解説はいらないと思いますが、一応書いておきます。
init()では、乱数初期化をしています。main()に書けばいいじゃんという人もおられるかとは思いますが、なるべく関数化して拡張に備える(今回のは拡張ないですけど)という実装スタイルなので、ご容赦ください。あとは見通しの観点からも関数化したほうが良いかと思っています。
time()とsrand()の使い方はtime(3)、rand(3)をご覧ください。
void init()
{
time_t t;
time(&t);
srand(t);
}
maze_init()関数で、map[][]を初期化します。要するに「壁」で埋め尽くします。
void maze_init()
{
int x, y;
for (y = 0; y < HEIGHT; y++)
for (x = 0; x < WIDTH; x++)
map[x][y] = WALL;
}
for文を2段でネストさせて初期化する一般的なやり方です。
void print()
{
int x, y;
for (y = 0; y < HEIGHT; y++) {
for (x = 0; x < WIDTH; x++)
printf("%c", (map[x][y] == WALL) ? '#' : ' ');
printf("\n");
}
}
表示も特に凝っていません。壁なら「#」、道なら「 (半角空白)」を表示するようにしています。これは2段目のループのprintf()の中で条件式で判定して切り分けています。Goなどの3項演算子を持たない言語仕様の場合はif文など別の方法を使う必要があるでしょう。
なおここではコンソール出力での表示を意図していますが、スマホなど他の出力デバイスなどを用いる場合は、それぞれにあった出力を行うことになります。あくまでもこの関数はここでの実装確認用となります。
迷路生成の起点
迷路作成の起点となる関数です。
再帰を使って迷路を作成するため、再帰させる関数を別に持ち、そのトリガーを引く関数をmaze()とします。
void maze()
{
int x = rand_odd(WIDTH - 2);
int y = rand_odd(HEIGHT - 2);
printf("(%d, %d)\n", x, y);
make_maze(x, y);
}
再帰させる関数はmake_maze()です。どの座標から掘りすすめるかを指定する引数x, yを持ちます。座標は構造体を作って(あるいはdir[]を定義している構造体を流用して)引数に構造体を用いても良いかと思います。
ここでは簡便のためにintの2パラメータで処理しています。
rand_odd()関数は奇数だけの乱数を生成するために作りました。これは、最初の道の生成位置をランダムにとるために使用しています。
int rand_odd(int mod)
{
int r = 1 + rand() % mod;
if (r % 2 == 0)
r++;
if (r > mod)
r -= 2;
return r;
}
なぜ奇数かというと、道を作る場所がmap[][]の奇数座標のみになるからです。言葉の説明より、以下の簡単なマップのほうが理解しやす以下と思います。
01234
0#####
1# # #
2# # #
3# #
4#####
横方向の0〜4はmap[x][y]のx、縦方向はyを示します。道ができる場所は常に添字の奇数位置になるので、起点となる座標も奇数でないと困るというわけです。
rand_odd()に戻ると、最初のif文で奇遇判定をして、偶数なら+1して奇数にします。
2つ目のif文で添字の範囲をオーバーするのを防いでいます。ここでは簡単に-2させて1つ前の奇数値に丸めています。ここの実装は他の形で凝ってもよいと思いますが、あまり意味がなさそうなので安直に丸め処理を実装したにすぎません。
なお、座標をrand_odd()で生成したあとにprintf()文で座標値を表示させていますが、これは確認用なので無くても構いません。
実際の迷路生成
さて実際に迷路を生成するmake_maze()関数です。このプログラムの本質であり、アルゴリズムの実装そのものであり、解説の最後になります。
まずは全体像から。
void make_maze(int x, int y)
{
int d = rand() % 4;
int dd = d;
while (1) {
int px = x+dir[d].x*2;
int py = y+dir[d].y*2;
if (px < 0 || px >= WIDTH || py < 0 || py >= HEIGHT || map[px][py] != WALL) {
d++;
if (d == 4)
d = 0;
if (d == dd)
return;
continue;
}
map[x+dir[d].x][y+dir[d].y] = ROAD;
map[px][py] = ROAD;
make_maze(px, py);
d = dd = rand() % 4;
}
}
それほどコード量はありません。
関数最初の1行は乱数を使って掘り進む方向を決定しています。決めた方向は覚えておく必要があるので変数ddに保存します。
int d = rand() % 4;
int dd = d;
なぜ覚えておく必要があるかというと、4方向試したかどうかを判定するためです。
この実装では、方向チェックと切り替えを0〜3の数値を用いて順に行なっています。すなわち0→1→2→3のような順でチェックします。
しかし最初の方向は乱数のため、どの値から始まるかはわかりません。つまり、0→1→2→3ではなく、2→3→0→1というパターンで判定することになる場合もあります。
そのため、最初に掘り進めようとした位置を記録しておき、その値まで戻って来たら全方位とも掘り進められないという判定を下すことになります。そのための変数ddとなります。
while文で無限ループを作ります。このループを抜けるのは4方向とも掘り進められなくなったときのみです。
この実装では再帰を用いているので、ループ脱出はすなわち関数呼び出し元に戻る(return)になります。
int px = x+dir[d].x*2;
int py = y+dir[d].y*2;
if (px < 0 || px >= WIDTH || py < 0 || py >= HEIGHT || map[px][py] != WALL) {
d++;
if (d == 4)
d = 0;
if (d == dd)
return;
continue;
}
while文最初の2行で、さきほど決定した掘り進める方向から、判定用の座標を算出しています。
dir[d].xとdir[d].yの値は倍(*2)にしています。これは、掘りたい位置のさらに向こう側が道だった場合は掘り進めない、というアルゴリズムに基づく実装です。
次のif文で実際に掘り進めるかどうかの判定をしています。mapの範囲を超える場合(px < 0 || px >= WIDTH || py < 0 || py >= HEIGHT)、もしくは掘りたい位置のその1つ先が壁ではない場合(map[px][py] != WALL)です。
余談ですが、ここの条件処理の負担軽減のためのテクニックとして、マップの外周をすべて道にしておくという方法があるようです。この場合、欲しいマップサイズより一回り小さいマップになるので、外周分を考慮した配列を確保しておくことになるでしょう。一般的な処理速度とメモリのトレードオフの構図ですね。
「map[px][py] == ROAD」としていないのは、たとえば壁と道以外の要素が出て来た場合に備えています。今回に限って言えば特に実装拡張しないので「== ROAD」でも潜在的なバグにはならないと思います。
if文の条件を満たした場合は、ある方向に掘り進められなかったことを意味します。
したがって方向を切り替えます。
d++して方向を切り替え、その結果が4だったら0に戻します。
方向を切り替えた結果、最初の位置に戻った場合は4方向全滅ということなので関数をreturnで抜けます。
まだ全方向を調べていなければ、while文の先頭って別の方向に掘り進められるかどうかの判定を続行します。
map[x+dir[d].x][y+dir[d].y] = ROAD;
map[px][py] = ROAD;
make_maze(px, py);
d = dd = rand() % 4;
掘り進めることが可能であれば、map[][]をROADで上書きします。掘り進む方向の座標と、さきほどチェックした1つ先の座標の両方をROADで上書きします。これもアルゴリズムに基づいた実装となっています。
無事に掘り進むことができましたので、次は1つ先の座標を起点としてさらに掘り進めていくことになります。
ここで、現時点の座標をスタックに積むか再帰を使うかで処理が分かれる部分ですが、この実装では再帰呼び出しを用いるため、make_maze()関数、すなわち自分自身を、新しく決定した座標をもとに呼び出しています。
この関数から戻って来たときはどういうときかというと、4方向とも掘り進められなかったときです。
つまり、(px, py)の座標の4方向ともすでに掘れない状況の場合に、この再帰呼び出しの次のコードが実行されます。
そして、この関数から戻って来た場合は、掘り進めようとした前の座標を起点として他の方向に掘り進められるかどうかを判定して方向切り替えをすることになりますので、dおよびddの値を乱数で決定した値をもとに処理を継続することになります。
おわりに
シンプルなアルゴリズムだったので実装も比較的簡単に終わりました。Cは自分にとっては比較的慣れている言語なので、実装自体も1〜2時間程度で終わったほどです。
参考にしたコードは特になかったので実装が正しいかどうかの判断基準がなかったのですが、コンパイルしていきなり迷路がでてきたので思わず声を出して笑ったほどです(笑)。
ちょうどいい頭の体操になったので、Go修行僧の私としては教材に都合が良いと思い、さっそくGoに移植しました。
それについては、また時間ができたら解説を書いてみたいと思います。