今回はC言語で「迷路」を作成する方法およびそのプログラムの紹介をしていきたいと思います。
「迷路」を作成する上では「穴掘り法」と呼ばれる方法が有名だそうです。
なので、このページでもこの「穴掘り法」で迷路を作成していきたいと思います。
Contents
穴掘り法とは
穴掘り法とはまさに「壁に穴を掘っていく」ことで迷路を作成する方法になります。
穴を掘り、その穴からさらにランダムに決めた方向に穴を掘るを繰り返すことで迷路を作成します。
全てが壁の迷路を用意する
最初に用意するのは「全てが壁のマスである迷路」です。もはや迷路でもないですが…。
ここに穴を掘っていくことで迷路を作ります。
決まりがあって、マス数は縦横ともに 5 以上の奇数である必要があるそうです。
今後説明しやすいように、縦軸と横軸には数値を割り振っており、各マスを座標で管理できるようにしています。
例えば下図で示した色のついたマスの座標は、
それぞれ下記になります。
- 赤色のマスの座標：(0, 0)
- 緑色のマスの座標：(9, 1)
- 黄色のマスの座標：(5, 4)
- 青色のマスの座標：(11, 6)
- 紫色のマスの座標：(12, 8)
スポンサーリンク
ランダムな位置に穴を掘る
次にランダムな位置に穴を掘ります。下の図のように一箇所だけ穴が空きます。
この穴を開けた位置を「現在地」とします。
ただし、穴を掘る座標は完全にランダムではなく、縦方向と横方向両方の座標が「奇数」になる位置の中からランダムに決定します。
これは、外壁になるマスが全て縦方向 or 横方向の座標が偶数になるいるためです（縦横のマス数を奇数にしているため）。この穴掘り法では外壁には穴を掘らないことが１つのポイントになっています。
最初の穴の縦方向と横方向両方の座標が奇数であれば、最初に穴を掘るマスは絶対に外壁にはなりません。
また、以降で説明する「穴を掘る」を行う際にも、最初の穴の座標が縦方向と横方向両方の座標が奇数であれば、外壁に穴を掘ることなく迷路を作成することができます
穴を掘る方向を決める
ここからガンガン穴を掘っていきます。
まずは穴を掘る方向を決めます。その方向はランダムに決定します（これにより作成できる迷路を毎回異なるものにすることができます）。
穴が掘れる場合は穴を掘る
次は、現在地から決定した方向に２マス分穴を掘ります。
ただし穴掘り法で穴が掘れるのは下記の場合のみです。
- 掘ろうとしているマスが迷路の外にはみ出していない
- 掘ろうとしているマスにはまだ穴が掘られていない
ランダムに決定した方向の２マス先の穴が上記を満たしている場合のみ、現在地からその方向に２マス分穴を掘ります（例えば上の図の場合、下方向は「迷路の外にはみ出す」ことになるので穴が掘れないことになります）。
この時、堀った２つの穴の内、現在地から遠い方の穴の位置を新たな現在地とします（２マス分現在地が移動する）。
そして現在地を変更した状態で、再度穴を掘る方向を決めるに戻り、ここで決めた方向に対して再度この穴が掘れる場合は穴を掘るを行います。
そしてまた現在地を変更し、同じことを繰り返します。
するとガンガン穴が掘られていくことになります。
スポンサーリンク
穴が掘れない場合は他の方向を決定する
ですが、いずれランダムに決定した方向のマスが下記を満たさないケースにたどり着きます。
- 掘ろうとしているマスが迷路の外にはみ出していない
- 掘ろうとしているマスにはまだ穴が掘られていない
この場合は穴を掘らずに、穴を掘る方向を決めるに戻り、穴を掘る方向を再度決定します。ここでも方向をランダムに決定します。
もしかしたら、またランダムに決定したマスが掘れない or また同じ方向だった場合もありえますが、その場合はさらにもう一度ランダムに方向を決めます。
もし方向が変わって穴が掘れる場合は、穴が掘れる場合は穴を掘るを行います。つまり、その方向に対してガンガン穴を掘り進めていきます。
全方向穴が掘れない場合は現在地を一段階もどす
ただし、いずれはどの方向にも穴が掘れないマスが現在地となるケースに到達します。
この場合は現在地を一段階戻し、一段階戻した現在地から、穴を掘る方向を決めるを実施します。
一段階現在地を戻してもまだ穴が掘れる方向がない場合は、穴が掘れるマスに到達するまで「一段階現在地を戻す」を繰り返します。
穴が掘れるマスに到達すれば、また穴を掘る方向を決めるから方向を決定し、その方向に穴を掘り進めるを繰り返していきます。
上記は簡易アルゴリズムのようです
穴を掘れなくなった際には、既に穴を空けたマスから１つランダムにマスを選び、そのマスを現在地として穴を掘る方向を決めるをやり直す方法が一般的なようです
が、今回は簡単のため、穴が掘れなくなった際には現在地を１段階戻して穴を掘る方向を決めるをやり直すようにしています
全ての穴が全方向穴が掘れなくなったら終了する
最終的には現在地となり得る全ての穴が「全方向穴が掘れない」状態になります。
つまり、現在地となり得る全ての穴が下記を満たさなくなります。
- 掘ろうとしているマスが迷路の外にはみ出していない
- 掘ろうとしているマスにはまだ穴が掘られていない
こうなったら、迷路が完成したことになりますので、迷路を作成するプログラムは終了です。
スポンサーリンク
穴掘り法で迷路を作成するプログラム
それでは穴掘り法で説明した方法に従って迷路を作成するプログラムを紹介していきたいと思います。
ソースコード
迷路を作成するプログラムのソースコードが下記になります。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* 迷路の横サイズ(奇数) */
#define MEIRO_WIDTH 13
/* 迷路の縦サイズ(奇数) */
#define MEIRO_HEIGHT 9
/* 迷路の各マス表す値の定義 */
#define PATH 0
#define WALL 1
/* 方向を表す値の定義 */
#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3
/* 迷路の各マスの情報を格納する配列 */
static int maze[MEIRO_HEIGHT][MEIRO_WIDTH] = {};
/* 関数のプロトタイプ宣言 */
void initRand(void);
void printMaze(int, int);
void createMaze(int, int);
void dig(int, int);
/**
* 乱数の初期化
*
* 引数
* なし
*
* 返却値
* なし
*/
void initRand(void) {
time_t now;
/* 現在の時刻を取得 */
now = time(NULL);
/* 現在の時刻を乱数の種として乱数の生成系列を変更 */
srand((unsigned int)now);
}
/**
* 迷路を表示する
*
* 引数
* w：迷路の横幅（マス数）
* h：迷路の高さ（マス数）
*
* 返却値
* なし
*/
void printMaze(int w, int h) {
int i, j;
for (j = 0; j < h; j++) {
for (i = 0; i < w; i++) {
/* 配列の値に応じて記号/文字を表示 */
if (maze[j][i] == PATH) {
printf(" ");
}
if (maze[j][i] == WALL) {
printf("#");
}
}
printf("\n");
}
printf("\n");
}
/**
* 穴を掘る
*
* 引数
* i：穴を掘る起点座標（横方向）
* j：穴を掘る起点座標（縦方向）
*
* 返却値
* なし
*/
void dig(int i, int j) {
/* どの方向を掘ろうとしたかを覚えておく変数 */
int up, down, left, right;
up = 0;
down = 0;
left = 0;
right = 0;
/* 全方向試すまでループ */
while (up == 0 || down == 0 || left == 0 || right == 0) {
/* 0 - 3 の乱数を取得 */
int d = rand() % 4;
switch(d) {
case UP:
/* 上方向が掘れるなら掘る */
if (j - 2 >= 0 && j - 2 < MEIRO_HEIGHT) {
if (maze[j - 2][i] == WALL) {
maze[j - 2][i] = PATH;
maze[j - 1][i] = PATH;
dig(i, j - 2);
}
}
up++;
break;
case DOWN:
/* 下方向が掘れるなら掘る */
if (j + 2 >= 0 && j + 2 < MEIRO_HEIGHT) {
if (maze[j + 2][i] == WALL) {
maze[j + 2][i] = PATH;
maze[j + 1][i] = PATH;
dig(i, j + 2);
}
}
down++;
break;
case LEFT:
/* 左方向が掘れるなら掘る */
if (i - 2 >= 0 && i - 2 < MEIRO_WIDTH) {
if (maze[j][i - 2] == WALL) {
maze[j][i - 2] = PATH;
maze[j][i - 1] = PATH;
dig(i - 2, j);
}
}
left++;
break;
case RIGHT:
/* 右方向が掘れるなら掘る */
if (i + 2 >= 0 && i + 2 < MEIRO_WIDTH) {
if (maze[j][i + 2] == WALL) {
maze[j][i + 2] = PATH;
maze[j][i + 1] = PATH;
dig(i + 2, j);
}
}
right++;
break;
}
}
}
/**
* 迷路を作成する
*
* 引数
* w：迷路の横幅（マス数）
* h：迷路の高さ（マス数）
*
* 返却値
* なし
*/
void createMaze(int w, int h) {
int i, j;
/* 全マス壁にする */
for (j = 0; j < h; j++) {
for (i = 0; i < w; i++) {
maze[j][i] = WALL;
}
}
/* 開始点をランダム（奇数座標）に決定する */
i = 2 * (rand() % (MEIRO_WIDTH / 2)) + 1;
j = 2 * (rand() % (MEIRO_HEIGHT / 2)) + 1;
/* i, j を通路に設定 */
maze[j][i] = PATH;
/* マス(i,j)を起点に穴を掘る */
dig(i, j);
}
int main(void) {
/* 乱数の初期化 */
initRand();
/* 迷路の作成 */
createMaze(MEIRO_WIDTH, MEIRO_HEIGHT);
/* 迷路の表示 */
printf("Create MAZE\n");
printMaze(MEIRO_WIDTH, MEIRO_HEIGHT);
return 0;
}
設定
ソースコードの下記では作成する迷路のサイズを設定することができます。
MEIRO_WIDTH と MEIRO_HEIGHT には 5 以上の奇数を設定するようにしてください。
/* 迷路の横サイズ(奇数) */
#define MEIRO_WIDTH 13
/* 迷路の縦サイズ(奇数) */
#define MEIRO_HEIGHT 9スポンサーリンク
実行結果
プログラムを実行すれば、下記のように作成した迷路が表示されます。
#############
# # # # #
# # # # # # #
# # # # #
# ######### #
# # # # #
# # # # # # #
# # # #
#############“#” は壁を表しており、スペースは通路を表しています。
穴を最初に掘る位置や穴を掘る方向をランダムに決定していますので、実行するたびに結果は異なると思います。
あとは通路となる場所から適当にスタートとゴールを選んでやれば、迷路の出来上がりになります。
プログラムの解説
最後に簡単にプログラムの解説を行なっておきます。
乱数を初期化する（initRand）
穴掘り法では下記をランダムに決定する必要があります。
- 最初に掘る穴の位置
- 穴を掘る方向
このランダムな決定を行うために乱数を利用しています。
その乱数の初期化を行っているのが initRand 関数になります。
乱数については下記ページで詳しく解説していますので、乱数について知りたい方は是非下記ページも読んでみてください！
C言語で乱数を扱う方法（rand関数とsrand関数）
スポンサーリンク
迷路を作成する（createMaze）
createMaze 関数では、穴掘り法とはで解説した下記の処理を行っています。
マスの管理
各マスが壁 or 穴（通路）のどちらであるかは２次元配列 maze で管理するようにしています。
maze[j][i] に (i, j) 座標のマスが壁（WALL）であるか、穴（PATH）であるかを格納し、後から配列 maze を参照することで、各座標が壁であるか穴であるかを判断できるようにしています。
全てが壁の迷路を用意する
createMaze 関数では最初に「全てが壁の迷路を用意する」ために、下記で maze の全ての要素に WALL を格納しています。
/* 全マス壁にする */
for (j = 0; j < h; j++) {
for (i = 0; i < w; i++) {
maze[j][i] = WALL;
}
}ランダムな位置に穴を掘る
続いてランダムに決定した座標 (i, j) に対応する maze の要素に対して PATH を格納しています。
/* 開始点をランダム（奇数座標）に決定する */
i = 2 * (rand() % (MEIRO_WIDTH / 2)) + 1;
j = 2 * (rand() % (MEIRO_HEIGHT / 2)) + 1;
/* i, j を通路に設定 */
maze[j][i] = PATH;そして、最後に決定した開始点 (i, j) を現在地として dig 関数を実行させています。
これにより、現在地から穴を掘る処理が行われていくことになります。
穴を掘る（dig）
dig 関数は引数で指定された (i, j) を現在地とし、そこから穴を掘り進める関数になります。
dig 関数では穴掘り法とはで解説した下記の５つの処理を行っています。
穴を掘る方向を決める
まずは穴を掘る方向を rand 関数を用いて決定しています。
/* 0 - 3 の乱数を取得 */
int d = rand() % 4;d に格納されるのは 0 〜 3 の整数になりますが、それぞれを下記で定義し、方向を表す値として扱っています。
/* 方向を表す値の定義 */
#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3決定した方向に対し、switch 文で分岐を行うことで、各方向ごとに処理を記述できるようにしています。
穴が掘れる場合は穴を掘る
次に、決定した方向に穴が掘れるかどうかの判断を行い、掘れる場合には穴を掘る処理を行います。
ここでは、説明を簡単にするために穴を掘る方向として上方向が選ばれたと仮定して解説します。
この判断を行っているのが下記部分になります。
/* 上方向が掘れるなら掘る */
if (j - 2 >= 0 && j - 2 < MEIRO_HEIGHT) {
if (maze[j - 2][i] == WALL) {座標 (i, j) に穴を掘るとは、前述の通り maze[j][i] に PATH を格納する処理になります。
これを行っているのが下記部分になります。
maze[j - 2][i] = PATH;
maze[j - 1][i] = PATH;さらに、上記で穴を掘った後に、 dig 関数を再帰呼び出しを行っています。
dig(i, j - 2);この再帰呼び出しの時に、dig 関数の引数には掘った穴の座標（現在地から遠い方の穴の座標）を指定しますので、穴を掘った位置を新たな現在地としてさらに「穴を掘る」を実行することができます（上方向に穴を掘った場合は j - 2 した座標が新たな現在地となる）。
その実行される dig 関数の中ではさらに dig 関数の再帰呼び出しが行われますので「穴を掘る→現在地を変更する」が繰り返し実行され、どんどん穴が掘られていくことになります。
穴が掘れない場合は他の方向を決定する
もし下記で穴が掘れないと判断した場合は、再度穴を掘る方向の決定を行います。
/* 上方向が掘れるなら掘る */
if (j - 2 >= 0 && j - 2 < MEIRO_HEIGHT) {
if (maze[j - 2][i] == WALL) {dig 関数では「穴を掘る方向を決定する」処理をループの中で実行していますので、上記の if 文が成立しなければ直ちに次の方向を決めるために rand 関数が実行され、再度穴を掘る方向が決定されることになります。
/* 全方向試すまでループ */
while (up == 0 || down == 0 || left == 0 || right == 0) {
/* 0 - 3 の乱数を取得 */
int d = rand() % 4;
/* 〜略〜 */
}全方向穴が掘れない場合は現在地を一段階もどす
さらに、dig 関数の中ではどの方向への穴掘りを行った（もしくは穴掘り出来なかった）かを下記の変数で管理するようにしています。
/* どの方向を掘ろうとしたかを覚えておく変数 */
int up, down, left, right;これらは while ループ開始前に 0 で初期化を行い、switch 文の中でこれらの変数をインクリメントするようにしていますので、各方向ごとに穴を掘ることを試した回数が格納されることになります。
switch(d) {
case UP:
/* 〜略〜 */
up++;
break;
case DOWN:
/* 〜略〜 */
down++;
break;
case LEFT:
/* 〜略〜 */
left++;
break;
case RIGHT:
/* 〜略〜 */
right++;
break;
}したがって、これらの変数が全て 0 でなくなれば、全方向への穴掘りを試したことになります。
穴が掘れた場合はもうその方向への穴掘りが完了したことになりますし、穴が掘れなかった場合はその方向へは穴が掘れないということになります。
つまり、現在地からはもう穴が掘れる方向が無いということになります。
この場合は下記でループを抜け、dig 関数を終了するようにしています。
while (up == 0 || down == 0 || left == 0 || right == 0) {関数は終了すると呼び出し元に処理が戻ることになります。
dig 関数は初回のみは createMaze 関数から呼び出されますが、それ以外は dig 関数から呼び出されます。
後者の場合は、一段階前の現在地として実行された dig 関数から呼び出されていることになりますので、dig 関数が終了すれば自然と一段階前の現在地に戻り、dig 関数のループによりまた新たな方向に穴を掘っていくことになります。
全ての穴が全方向穴が掘れなくなったら終了する
前述の通り、dig 関数が終了するのは、現在地から全方向への穴掘りを試し、どの方向にも穴掘りができなくなった場合になります。
dig 関数は再帰呼び出しによりどんどん穴を掘っていくことになりますが、迷路のマス数は有限ですので、いずれはどの方向にも穴掘りができなくなります。
したがっていずれは再帰呼び出しした全ての dig 関数が終了し、さらには最初に dig 関数を実行した createMaze 関数に処理が戻ることになります。
この時には現在地となり得る全ての穴が「全方向穴が掘れない」状態になったことになりますので、迷路が完成したことになります。
迷路を表示する（printMaze）
printMaze 関数は作成した迷路をコンソールに表示する関数です。
壁と穴（通路）をそれぞれ “#” と ” ” で表示しています。
スポンサーリンク
参考ページ
穴掘り法については下記ページを参考にさせていただきました。
http://www.ced.is.utsunomiya-u.ac.jp/lecture/2009/prog/p3/kadai4/5.html
まとめ
このページでは穴掘り法を用いて迷路を作成する方法の解説およびそのプログラムの紹介を行いました。
今回紹介した方法であれば、再帰呼び出しを使えば簡単にプログラミングすることができますので、是非ご自身でも試してみることをオススメします！
ただこのアルゴリズムで作成される迷路は「答えとなる経路が１パターンのみ」になってしまいます。
ただ、作成した迷路にちょっとした工夫を行うことでもっと難しい迷路も簡単に作ることもできると思います。例えば外壁以外の壁にランダムに複数の穴を掘れば、「答えとなる経路が複数パターン」となる迷路も作れます。
こういった工夫に挑戦してみることもプログラミング上達への近道になりますので、是非試してみてください！
また、下記ページでは「迷路を解く」プログラムも紹介しています。
【C言語】「再帰呼び出しの動き・メリット・書き方」を迷路を解いて理解する
今回紹介した「迷路を作成する」プログラムと上手く組み合わせることで「迷路を作成する → 迷路を解く」を一括で行うようなプログラムも簡単に作れます。
「再帰呼び出しの動き・メリット・再帰関数の作り方」の解説にも力を入れていますので、迷路に興味がある方だけでなく、再帰呼び出しについてもっと学びたい方にもオススメのページです！
オススメの参考書（PR）
C言語学習中だけど分からないことが多くて挫折しそう...という方には、下記の「スッキリわかるC言語入門」がオススメです！
まず学習を進める上で、参考書は２冊持っておくことをオススメします。この理由は下記の２つです。
- 参考書によって、解説の仕方は異なる
- 読み手によって、理解しやすい解説の仕方は異なる
ある人の説明聞いても理解できなかったけど、他の人からちょっと違った観点での説明を聞いて「あー、そういうことね！」って簡単に理解できた経験をお持ちの方も多いのではないでしょうか？
それと同じで、１冊の参考書を読んで理解できない事も、他の参考書とは異なる内容の解説を読むことで理解できる可能性があります。
なので、参考書は２冊持っておいた方が学習時に挫折しにくいというのが私の考えです。
特に上記の「スッキリわかるC言語入門」は、他の参考書とは違った切り口での解説が豊富で、他の参考書で理解できなかった内容に対して違った観点での解説を読むことができ、オススメです。題名の通り「なぜそうなるのか？」がスッキリ理解できるような解説内容にもなっており、C言語入門書としてもかなり分かりやすい参考書だと思います。
もちろんネット等でも色んな観点からの解説を読むことが出来ますので、分からない点は別の人・別の参考書の解説を読んで解決していきましょう！もちろん私のサイトも参考にしていただけると嬉しいです！
入門用のオススメ参考書は下記ページでも紹介していますので、こちらも是非参考にしていただければと思います。
https://daeudaeu.com/c_reference_book/
