お久しぶりです。アドベントカレンダー12/25(兼11/21)担当のtsukatomoと申します。今回は最終日担当ということで去年や前回と趣向を変え、最近取り組んだ迷路自動生成プログラムについて書いていこうと思います。
※ところどころ料理番組の「出来上がったものがこちらになります」的な感じで解説を省いているのでご了承ください。
11/21の記事はこちら → 「た の し い 算 数 パ ズ ル」 /post/313/
（以前指摘された別解はちゃんと追記しました）
自動生成する迷路について
生成する迷路は下図のようないたって普通の平面でカクカクした迷路です。
上の迷路は各要素が「道」または「壁」である二次元配列をコンソール画面へ出力させることにより表示しています。今回も二次元配列へ書き込みながら迷路を作成しています。
使用した言語
今回使用したのは王道を征くC言語です。理由はただ一つ、他の言語を全く知らないからです。せっかく迷路を作るなら可視化し易いjavascriptとかを使うべきだとは思いますが、一から勉強しているようでは流石に投稿〆切に間に合わないので、学校ですでに学習したC言語を使うことにしました。C言語のここがよかったから採用しました、ということは全くありません。許して。
気を取り直して本題に入りましょう。
1.迷路の自動生成の実装
まずは迷路がランダムに自動生成されるアルゴリズムを実際に書き起こしていきます。このアルゴリズムには様々な種類がありますが、今回はランダム性が高い「壁延ばし法」を採用しました。
「壁延ばし法」とは？
名前の通り「迷路の壁を延ばす」、何処かの誰かが考えたすごいアルゴリズムです。
上のGIF画像のように一マスおきに置かれた「柱」を次々に結んでいくと、見事に「解が１通りしかない」迷路が出来上がります。なんでだろうね。
ここでは詳しい説明は省略します。詳細は今回お世話になった以下のサイト様をご覧ください。
自動生成迷路 - Biglobe http://www5d.biglobe.ne.jp/stssk/maze/make.html
今回は次のようにして実装することにしました（説明下手なので非常にわかりづらいです…）。
-
「壁の延びていない『柱』の座標の集合」として配列nodesを、「探索済みの『柱』の座標の集合」として配列pathをそれぞれ用意する。
-
配列nodesからランダムに1つ「柱」を選択し取り出す。
-
選択中の「柱」の座標から上下左右いずれかに移動する。
-
移動した先が「探索済みの（＝pathに含まれる）柱」の時は方向を選び直す。上下左右全てで試した場合は現在選択中の「柱」をnodesに入れ直し、一つ前の「柱」へ戻って方向を選び直す。
-
移動した先が「未探索の（＝nodesに含まれる）柱」の時はその「柱」を選択し、nodesから取り出してpathに記録する。その後、3に戻って操作を繰り返す。
-
移動した先がすでに「壁（＝nodesに含まれない「柱」または外壁）」である時、ここまで移動してきた道のりを全て「壁」に置き換え、pathを空にする。続いて2まで戻り、一連の操作をnodesが空になるまで繰り返す。
-
nodesが空になったら終了する。
(ソースコードはこの記事の一番最後にまとめて載せておきます。関数choose_nodeを再帰呼び出し（クソ重い）することで自動生成を実現していますが、突貫工事のため出来は悪いです。許してヒヤシンス。)
実際に作ってプログラムを実行してみた画像がこちらになります。"@@"が壁です。
やったぜ。
これで自動生成は完成ですが、このままだとちょっと物足りないので少しずつ改良していきましょう。
2.見栄えを良くする
先ほどの画像ではアスキーアートで迷路を表示していたため、壁に隙間があって見づらかったと思います。そこで「エスケープシーケンス」というものを使って、もっと見栄え良く表示させてみることにします。
「エスケープシーケンス」は簡単に説明するとコンソールヘの表示を制御する文字列のことで、これを用いることで出力する文字に色をつけたり、特殊な文字を入力することができるようになります。
例えば次のように書くと、文字の背景色を赤色に、文字自体の色（前景色）を白にすることができます。
/* 文字に色を付ける例 */
#include <stdio.h>
int main(void){
printf("\x1b[41m"); // 背景色を赤色にする
printf("\x1b[37m"); // 前景色を白色にする
printf("このように 文字の色が変わります。\n");
printf("\x1b[0m"); // デフォルトに戻す
printf("元に 戻りました。\n");
return 0;
}
実行結果
これを利用して迷路の壁を見やすくしてみましょう。先ほどは"@@"を壁としていましたが、代わりにエスケープシーケンスを用いて背景色を緑色に変化させた" "（空白2つ）を出力させます。
壁の隙間がなくなってだいぶ見栄えが良くなったと思います。一方でターミナルのスクロールが遅くなるという問題点がありますが、今回は目を瞑りましょう。
3.答えを表示する
せっかくなので迷路を出力すると同時に答えも表示できるようにします。
今回は勉強も兼ねて「幅優先探索」により答えのルートを求めるようにしてみました。
「幅優先探索」の手順は概ね次の通りです。
- 「探索キュー」を準備し、スタートの座標を入れる。
- 「探索キュー」の先頭の座標を取り出す。
- 取り出した座標がゴールと一致するなら終了する。
- 取り出した座標と上下左右で隣接する座標を求め、それらがもし未探索の道ならキューに入れる。
- 2~4の操作を「探索キュー」に何も入らなくなるまで繰り返す。
これだけではゴールに到達して探索が終了しても「道順」が記憶されていないので、それを記憶するための配列direction[w][h]を準備しておきます。これに「探索で辿って来た方向」を座標ごとに記録しておき、ゴールに到達したらこの記録を基にして来た道を逆に辿ります。
下図は実装して実行した結果です。ちゃんと経路が表示されるようになりました。
4.スタートとゴールを決定する
先ほどまではスタートとゴールをランダムに決定していました。しかしこのままでは、
あっ！プログラムを実行したら迷路が出て来たゾ！！
今回の正解ルートは…
簡単スギィ！！！！！
1.145148931919810秒で分かったゾ〜！（瞬殺）
…となることがよくあります。これでは少々つまらないので、スタートとゴールをなるべく引き離して配置するようにプログラムしてみました。
その実装を大まかに説明すると、
- 迷路の道の中からランダムに1地点を選ぶ
- その地点から最も遠い地点を幅優先探索によって求め、そこをスタートにする
- スタートから最も遠い地点を幅優先探索によって求め、そこをゴールにする
という感じです。こうすると迷路の中で最も遠い2地点をスタートとゴールに設定してくれるみたいなのですが、なぜそうなるのか証明していないのでよくわかりません。教えて偉い人
実装して実行した結果は次のようになりました。
迷路として面白いかどうかはともかく、少なくとも「つまらない迷路」は生成されなくなりました。
今現在、迷路自動生成プログラム開発の進捗はここまでです。気が向いたら画像ファイルへの出力とかにも挑戦するかもしれません。
ソースコード
先に述べた通り、ここに作成したプログラムのソースコードを置いておきます。グローバル配列を多用しすぎて色々とアレだったり、ここまで説明してきたことと違ったりとツッコミどころ満載だと思います。
コピーして自分のパソコンで動かしたり、書き換えたりしても構いません。
/*
* long_meiro.c
* by Tsukatomo
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXX 256
#define MAXY 256
/***********/
/* 自動生成 */
/***********/
// 迷路盤面の座標は構造体で管理
typedef struct{
int x;
int y;
}coord_t;
int meiro[MAXX][MAXY]={{0}}; // 迷路盤
coord_t nodes[MAXX*MAXY]; // 未開発の（壁が伸びていない）柱のリスト
int nodend = 0; // nodesリストの長さ
coord_t path[MAXX*MAXY]; // 探索した柱のリスト（スタック）
int pathend = 0; // pathリストの長さ
// 構造体の値を設定する
coord_t newcoord(x, y){
coord_t new;
new.x = x;
new.y = y;
return new;
}
// リストに新たな要素を追加(nodes)
void insert_node(coord_t c){
nodes[nodend] = c;
nodend++;
}
// リストに新たな要素を追加(path)
void insert_path(coord_t c){
path[pathend] = c;
pathend++;
}
// nodesリストの任意の要素を取り出す
coord_t remove_node(int k){
coord_t out;
if (k > nodend){
printf("error: Not found");
return newcoord(-1, -1);
}
else{
out = nodes[k]; // 取り出す
for(int i=k; i < nodend - 1; i++) // 取り出したぶん詰める
nodes[i] = nodes[i + 1];
nodend--;
}
return out;
}
// pathリストの†末尾†の要素を取り出す
coord_t remove_path(void){
coord_t out;
out = path[pathend - 1]; // 取り出す
pathend--;
return out;
}
// リスト総当たり検索(nodes)
int search_node(coord_t c){
for(int i = 0; i <= nodend-1; i++){
if((nodes[i].x == c.x) && (nodes[i].y == c.y))
return i;
}
return -1;
}
// リスト総当たり検索(path)
int search_path(coord_t c){
for(int i = 0; i <= pathend-1; i++){
if((path[i].x == c.x) && (path[i].y == c.y))
return i;
}
return -1;
}
// 上下左右シャッフル
void shuffle(coord_t *direction){
int j;
coord_t tmp;
for(int i=0; i < 4; i++){
j = rand()%4;
tmp = direction[i];
direction[i] = direction[j];
direction[j] = tmp;
}
}
// 柱を探索（再帰）
int choose_node(coord_t c){
int s, r;
coord_t p_1, p_2;
coord_t d[4] = {newcoord(0, 2),
newcoord(0, -2),
newcoord(2, 0),
newcoord(-2, 0)}; // 壁を伸ばす方向
// printf("x:%d, y:%d\n", c.x, c.y);
if(search_path(c) != -1){ // cが探索済の時
return 1; // 生成失敗
}
else{
insert_path(c); // pathに追加
s = search_node(c);
if(s != -1){ // cが未探索の時
remove_node(s); // nodeから消す
// 上下左右のいずれかに壁を伸ばす
shuffle(d);
for(int i = 0; i < 4; i++){
r = choose_node(newcoord(c.x + d[i].x, c.y + d[i].y));
if (r == 0) break;
}
if(r == 1)
insert_node(remove_path());
return r;
}
else{ // cがすでに壁の時
// pathリストの末尾から一つずつ取り出し壁を作る
p_2 = remove_path();
do{
p_1 = p_2;
p_2 = remove_path();
// printf("wall(%d, %d)\n",(p_1.x + p_2.x) / 2, (p_1.y + p_2.y) / 2);
meiro[(p_1.x + p_2.x) / 2][(p_1.y + p_2.y) / 2] = 1;
}while(pathend);
return 0;
}
}
}
// 迷路の自動生成
void make_meiro(int w, int h){
coord_t c;
while (nodend) {
choose_node(nodes[rand()%nodend]);
}
// 外壁
for(int j=0; j < h; j++){
meiro[0][j] = 1;
meiro[w-1][j] = 1;
}
for(int i=0; i < w; i++){
meiro[i][0] = 1;
meiro[i][h-1] = 1;
}
}
/*******/
/* 探索 */
/*******/
/** 迷路作成に用いたpathスタックの領域をキューとして再利用 **/
// pathリストの†先頭†の要素を取り出す
coord_t remove_path_h(void){
coord_t out = path[0]; // 取り出す
for(int i = 0; i < pathend; i++) // 詰める
path[i] = path[i + 1];
pathend--;
return out;
}
// 地点pから最も遠い点を検索(幅優先)
coord_t search_far(int w, int h, coord_t p){
coord_t n;
int sx, sy;
coord_t d[4] = {newcoord(0, 1),
newcoord(0, -1),
newcoord(1, 0),
newcoord(-1, 0)}; // 進む方向
// 迷路をコピー
int meiro_2[w][h];
for(int j = 0; j < h; j++){
for(int i = 0; i < w; i++){
meiro_2[i][j] = meiro[i][j];
}
}
// スタートを追加
pathend = 0;
insert_path(p);
// 繰り返し探索
while(pathend){
n = remove_path_h();
// printf("search = (%d, %d)\n", n.x, n.y);
// printf ("%d\n", pathend);
meiro_2[n.x][n.y] = 2; // 対応する座標を探索済みにする
shuffle(d); // ランダム性を持たせるためシャッフル
// printf("%d,%d\n",d[0].x,d[0].y);
for(int i = 0; i < 4; i++){
sx = n.x + d[i].x; // 隣接マスのx座標
sy = n.y + d[i].y; // 隣接マスのy座標
if(meiro_2[sx][sy] == 0){ // 隣接マスが未探索の道のとき
insert_path(newcoord(sx, sy));
}
}
}
return n;
}
// 幅優先探索
int search_meiro(int w, int h, coord_t start, coord_t goal){
coord_t n;
int sx, sy;
coord_t direction[w][h]; // 辿ってきた方向を記憶する配列(要素はd[4]のどれか)
coord_t d[4] = {newcoord(0, 1),
newcoord(0, -1),
newcoord(1, 0),
newcoord(-1, 0)}; // 進む方向
// スタートを追加
pathend = 0;
insert_path(start);
// 繰り返し探索
while(pathend){
n = remove_path_h();
// printf("search = (%d, %d)\n", n.x, n.y);
// printf ("%d\n", pathend);
meiro[n.x][n.y] = 2; // 対応する座標を探索済みにする
if(n.x == goal.x && n.y == goal.y){ // ゴール処理
while(n.x != start.x || n.y != start.y){
// 値を更新
sx = n.x;
sy = n.y;
// printf("PATH = (%d, %d)\n", n.x, n.y);
// マーキング
meiro[n.x][n.y] = 3;
// 来た道を戻る
n.x -= direction[sx][sy].x;
n.y -= direction[sx][sy].y;
}
return 0;
}
else{ // 探索処理
for(int i = 0; i < 4; i++){
sx = n.x + d[i].x; // 隣接マスのx座標
sy = n.y + d[i].y; // 隣接マスのy座標
if(meiro[sx][sy] == 0){ // 隣接マスが未探索の道のとき
insert_path(newcoord(sx, sy));
direction[sx][sy] = d[i];
}
}
}
}
printf("I cannot find the goal...\n");
return 1;
}
// 迷路を表示
void show_meiro(int w, int h, coord_t start, coord_t goal){
for(int j=0; j < h; j++){
for(int i=0; i < w; i++){
if((i == start.x) && (j == start.y)){
printf("\x1b[41m");
printf("\x1b[37m");
printf("S "); // スタート
}
else if((i == goal.x) && (j == goal.y)){
printf("\x1b[41m");
printf("\x1b[37m");
printf("G "); // ゴール
}
else{
switch(meiro[i][j]){
case 0: // 探索されていない道
printf("\x1b[0m");
break;
case 1: // 壁
printf("\x1b[42m");
break;
case 2: // 探索された道
printf("\x1b[0m");// [47mでうっすら表示できるよ
break;
case 3: // 正解ルート
printf("\x1b[45m");
break;
default:
printf("\x1b[0m");
}
printf(" ");
}
}
printf("\x1b[0m");
printf("\n");
}
printf("\n\n");
}
/***********/
/* メイン */
/***********/
int main(void){
srand((unsigned)time(NULL));
int i, j;
int width, height; //壁の厚さを0、道の太さを1とした時の迷路の幅、高さ
printf("width> ");
scanf("%d", &width);
printf("height> ");
scanf("%d", &height);
// 柱リストの作成
for(j=1; j < height; j++){
for(i=1; i < width; i++){
insert_node(newcoord(2 * i, 2 * j));
// printf("%d\n", nodend);
meiro[2 * i][2 * j] = 1;
}
}
// 迷路盤の使用領域を設定
int w = 2 * width + 1; // 迷路盤の幅
int h = 2 * height + 1; // 迷路盤の高さ
// 迷路の自動生成
make_meiro(w, h);
// スタート、ゴールを設定
coord_t start = search_far(w, h, newcoord((rand() % width) * 2 + 1, (rand() % height) * 2 + 1));
coord_t goal = search_far(w, h, start);
// 迷路の表示
show_meiro(w, h, start, goal);
// 迷路の探索
char yn[2];
printf("Show the answer? (y/n)> ");
scanf("%s", yn);
if (yn[0] == 'y'){
search_meiro(w, h, start, goal);
show_meiro(w, h, start, goal);
}
printf("[end of 'long_meiro.c']\n");
return 0;
}
閲覧ありがとうございました。traPアドベントカレンダー2017は本日が最終日となります。
みなさん、良いお年を！
