再帰呼び出しの最後の題材は、迷路の経路探索です。
迷路を作り、スタートからゴールまでの経路を探索するプログラムを作ります。
まずは迷路から作りたいと思いますが、簡単な自動生成プログラムを作ってみましょう。
まず、↓のような迷路の枠組みを作ります。
■■■■■■■■■■■ ■□□□□□□□□□■ ■□■□■□■□■□■ ■□□□□□□□□□■ ■□■□■□■□■□■ ■□□□□□□□□□■ ■□■□■□■□■□■ ■□□□□□□□□□■ ■□■□■□■□■□■ ■□□□□□□□□□■ ■■■■■■■■■■■
周りを壁で囲み、内部には１マス置きに壁を配置します。
便宜上、内部の壁を「柱」と呼びます。
柱を中心にして、乱数を使って上下左右のどこかに壁を追加します。
■■■■■■■■■■■ ■□□□□□□□□□■ ■□■□■□■□■□■ ■□□□□□□□□□■ ■□■□■□■□■□■ ■□□□□□□□□□■ ■□■□■□■□■□■ ■□□□□□□□□□■ ■□■□■□■□■□■ ■□□□□□□□□□■ ■■■■■■■■■■■
青いのが「柱」で、赤い部分のどこかに壁が追加されます。
全ての「柱」について同じ処理をすると、
■■■■■■■■■■■ ■□□□■□□□■□■ ■■■□■□■■■□■ ■□□□□□□□□□■ ■□■□■■■■■■■ ■□■□□□□□■□■ ■□■□■■■■■□■ ■□■□■□□□□□■ ■■■□■□■□■□■ ■□□□□□■□■□■ ■■■■■■■■■■■
このような迷路が生成されます。
基本的に４隅のマスはつながっているため、左上をスタート、右下をゴールとします。
■■■■■■■■■■■ ■Ｓ□□■□□□■□■ ■■■□■□■■■□■ ■□□□□□□□□□■ ■□■□■■■■■■■ ■□■□□□□□■□■ ■□■□■■■■■□■ ■□■□■□□□□□■ ■■■□■□■□■□■ ■□□□□□■□■Ｇ■ ■■■■■■■■■■■
↑が迷路の最終イメージです。
※この生成方法の場合、縦横のマスは奇数にする必要があります。
まずは必要なデータを考えmain関数を作ります。
<sample program 156-01>
#include <stdio.h> #include <stdlib.h> #include <time.h> #define ROW 11 /* 縦のマス */ #define COL 11 /* 横のマス */ #define MAP_KIND 4 /* マップ用の絵の種類 */ #define DIRECTION 4 /* 方向（乱数用） */ /* スタート地点 */ #define START_X 1 #define START_Y 1 /* ゴール地点 */ #define GOAL_X (COL - 2) #define GOAL_Y (ROW - 2) enum { UP, RIGHT, DOWN, LEFT, }; enum { FLOOR, START, GOAL, WALL, }; int main(void) { int maze[ROW][COL]; srand((unsigned int)time(NULL)); return 0; } |
ゴール地点は縦横のマスの数が変わっても対応できるようにしてあります。
１．迷路の初期化
関数名 InitializeMaze 戻り値 なし 引 数 迷路 機 能 迷路を初期化する |
void InitializeMaze(int maze[ROW][COL])
{
int i;
int j;
for (i = 1; i < ROW - 1; i++) {
for (j = 1; j < COL - 1; j++) {
maze[i][j] = FLOOR;
}
}
for (i = 0; i < ROW; i++) {
maze[i][0] = WALL;
maze[i][COL - 1] = WALL;
}
for (j = 1; j < COL - 1; j++) {
maze[0][j] = WALL;
maze[ROW - 1][j] = WALL;
}
for (i = 2; i < ROW - 2; i += 2) {
for (j = 2; j < COL - 2; j += 2) {
maze[i][j] = WALL;
}
}
maze[START_Y][START_X] = START;
maze[GOAL_Y][GOAL_X] = GOAL;
}
|
最初の２重ループで迷路の外周以外を床（FLOOR）で埋めます。
次の２つのループで外周に壁（WALL）を設置します。
２つ目の２重ループで「柱（WALL）」を設置します。
最後に、スタート地点とゴール地点を設定して終わりです。
main関数への追加部分を書いておきましょう。
<sample program 156-02>
int main(void)
{
int maze[ROW][COL];
srand((unsigned int)time(NULL));
InitializeMaze(maze);
return 0;
}
|
２．迷路の表示
関数名 ShowMaze 戻り値 なし 引 数 迷路 機 能 迷路を表示する |
void ShowMaze(const int maze[ROW][COL])
{
const char GRAPHIC[MAP_KIND][3] = { "□", "Ｓ", "Ｇ", "■" };
int i;
int j;
for (i = 0; i < ROW; i++) {
for (j = 0; j < COL; j++) {
printf("%s", GRAPHIC[maze[i][j]]);
}
printf("\n");
}
printf("\n");
}
|
単純に配列の中身を表示する関数です。
<sample program 156-03>
int main(void)
{
int maze[ROW][COL];
srand((unsigned int)time(NULL));
InitializeMaze(maze);
ShowMaze(maze);
return 0;
}
|
<実行結果>
■■■■■■■■■■■ ■□□□□□□□□□■ ■□■□■□■□■□■ ■□□□□□□□□□■ ■□■□■□■□■□■ ■□□□□□□□□□■ ■□■□■□■□■□■ ■□□□□□□□□□■ ■□■□■□■□■□■ ■□□□□□□□□□■ ■■■■■■■■■■■ 続行するには何かキーを押してください・・・
３．迷路の自動生成
関数名 GenerateMaze 戻り値 なし 引 数 迷路 機 能 迷路を自動生成する |
void GenerateMaze(int maze[ROW][COL])
{
int i;
int j;
for (i = 2; i < ROW - 2; i += 2) {
for (j = 2; j < COL - 2; j += 2) {
switch (rand() % DIRECTION) {
case UP:
maze[i - 1][j] = WALL;
break;
case RIGHT:
maze[i][j + 1] = WALL;
break;
case DOWN:
maze[i + 1][j] = WALL;
break;
case LEFT:
maze[i][j - 1] = WALL;
break;
}
}
}
}
|
最初の「柱」はＸ座標２、Ｙ座標２から始まります。
縦横に２ずつカウントすることで「柱」を全て辿ることが出来ます。
「柱」ごとに乱数を生成し、出た数によって上下左右のどこかに壁を設置します。
<sample program 156-04>
int main(void)
{
int maze[ROW][COL];
srand((unsigned int)time(NULL));
InitializeMaze(maze);
GenerateMaze(maze);
ShowMaze(maze);
return 0;
}
|
<実行結果>
■■■■■■■■■■■ ■Ｓ□□■□□□■□■ ■■■□■□■■■□■ ■□□□□□□□□□■ ■□■□■■■■■■■ ■□■□□□□□■□■ ■□■□■■■■■□■ ■□■□■□□□□□■ ■■■□■□■□■□■ ■□□□□□■□■Ｇ■ ■■■■■■■■■■■ 続行するには何かキーを押してください・・・
これで迷路が完成しました。
何度か実行して、毎回変化することを確認してください。
４．経路のクリア
スタートからゴールまでの経路は別の配列に格納します。
今回の初期値は↓を使います。
#define NONE -1 |
定数のところに追加しておいてください。
関数名 ClearPath 戻り値 なし 引 数 経路 機 能 経路をNONEでクリアする |
void ClearPath(int path[ROW][COL])
{
int i;
int j;
for (i = 0; i < ROW; i++) {
for (j = 0; j < COL; j++) {
path[i][j] = NONE;
}
}
}
|
迷路はInitialize（初期化）で経路はClear（クリア）にしました。
個人的なイメージで申し訳ないのですが、何か１つのデータで埋め尽くすのをClear、色々な設定も含めるのをInitializeと付けています。
<sample program 156-05>
int main(void)
{
int maze[ROW][COL];
int path[ROW][COL];
srand((unsigned int)time(NULL));
InitializeMaze(maze);
GenerateMaze(maze);
ShowMaze(maze);
ClearPath(path);
return 0;
}
|
５．経路の表示
関数名 ShowPath 戻り値 なし 引 数 経路 機 能 経路を表示する |
void ShowPath(const int path[ROW][COL])
{
int i;
int j;
for (i = 0; i < ROW; i++) {
for (j = 0; j < COL; j++) {
printf("%3d", path[i][j]);
}
printf("\n");
}
printf("\n");
}
|
経路情報を３ケタの数値で表示するだけです。
<sample program 156-06>
int main(void)
{
int maze[ROW][COL];
int path[ROW][COL];
srand((unsigned int)time(NULL));
InitializeMaze(maze);
GenerateMaze(maze);
ShowMaze(maze);
ClearPath(path);
ShowPath(path);
return 0;
}
|
<実行結果>
■■■■■■■■■■■ ■Ｓ□□■□□□■□■ ■■■□■□■■■□■ ■□□□□□□□□□■ ■□■□■■■■■■■ ■□■□□□□□■□■ ■□■□■■■■■□■ ■□■□■□□□□□■ ■■■□■□■□■□■ ■□□□□□■□■Ｇ■ ■■■■■■■■■■■ -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 続行するには何かキーを押してください・・・
６．経路の調査
ここが再帰呼び出しの関数になります。
スタート地点から移動可能なマスを探し、歩数を格納しながら自分自身を呼び出します。
関数名 CheckPath 戻り値 なし 引 数 迷路、経路、Ｘ座標、Ｙ座標、歩数 機 能 再帰を使って経路を調査する |
void CheckPath(const int maze[ROW][COL], int path[ROW][COL], const int x, const int y, const int count)
{
if (path[y][x] != NONE && path[y][x] < count) {
return;
}
path[y][x] = count;
if (maze[y][x] == GOAL) {
return;
}
if (maze[y - 1][x] != WALL) {
CheckPath(maze, path, x, y - 1, count + 1);
}
if (maze[y][x + 1] != WALL) {
CheckPath(maze, path, x + 1, y, count + 1);
}
if (maze[y + 1][x] != WALL) {
CheckPath(maze, path, x, y + 1, count + 1);
}
if (maze[y][x - 1] != WALL) {
CheckPath(maze, path, x - 1, y, count + 1);
}
}
|
ここでも最初のｉｆ文がポイントになります。
if (path[y][x] != NONE && path[y][x] < count) {
return;
}
|
NONEは未チェックですから、
path[y][x] != NONE |
は、チェック済みのマスとなります。
これに、
path[y][x] < count |
の条件を組み合わせていますので、チェック済みで今の歩数より少ない値が入っているマスということになります。
今の歩数よりも少ないということは、そちらの方がより短い経路ということなので関数を終えます。
<sample program 156-07>
int main(void)
{
int maze[ROW][COL];
int path[ROW][COL];
srand((unsigned int)time(NULL));
InitializeMaze(maze);
GenerateMaze(maze);
ShowMaze(maze);
ClearPath(path);
CheckPath(maze, path, START_X, START_Y, 1);
ShowPath(path);
return 0;
}
|
<実行結果>
■■■■■■■■■■■ ■Ｓ□□■□□□■□■ ■■■□■□■■■□■ ■□□□□□□□□□■ ■□■□■■■■■■■ ■□■□□□□□■□■ ■□■□■■■■■□■ ■□■□■□□□□□■ ■■■□■□■□■□■ ■□□□□□■□■Ｇ■ ■■■■■■■■■■■ -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 2 3 -1 9 10 11 -1 13 -1 -1 -1 -1 4 -1 8 -1 -1 -1 12 -1 -1 7 6 5 6 7 8 9 10 11 -1 -1 8 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 9 -1 7 8 9 10 11 -1 21 -1 -1 10 -1 8 -1 -1 -1 -1 -1 20 -1 -1 11 -1 9 -1 15 16 17 18 19 -1 -1 -1 -1 10 -1 14 -1 18 -1 20 -1 -1 13 12 11 12 13 -1 19 -1 21 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 続行するには何かキーを押してください・・・
色々な経路があると思いますが、ゴールから１ずつ歩数を減らしながら辿っていくとスタートに戻れます。
スタートから辿ると分岐点があり、ゴールに通じていない経路も存在します。
ゴールから辿ることによって、分岐があったとしても必ずスタートへ戻ることが出来ます。
これで経路は完成しましたが、今回は「おまけ」を付けておきます。