アルゴリズム

C言語における迷路生成と探索: バックトラッキングとBFS/DFSアルゴリズムを解説

2025-04-15更新日: 2025-04-15

このブログ記事では、C言語を使って迷路の生成と探索を行う方法を解説します。

バックトラッキングによる迷路生成アルゴリズムと、BFSやDFSを用いた経路探索の仕組みについて、わかりやすく説明します。

迷路作成プログラムの例を通して、各手法の応用方法を学ぶことができます。

目次から探す

迷路生成アルゴリズム
- バックトラッキング法による生成
- C言語での実装ポイント
迷路探索アルゴリズム
実装例と応用
まとめ

迷路生成アルゴリズム

バックトラッキング法による生成

アルゴリズムの基本構造

バックトラッキング法は、初期位置からスタートし、ランダムに隣接するセルへ移動しながら迷路を生成する手法です。

現在位置のセルを訪問済みとし、行き止まりになった場合は1つ前のセルに戻る処理を行います。

基本の流れは以下となります。

初期セルを決定し、訪問済みフラグを立てる
ランダムな順序で隣接セルを選択し、未訪問であれば壁を取り除きながら進む
移動可能な隣接セルが無くなったら、前のセルにバックトラックする

これにより、全体にランダム性が加わった迷路が生成されます。

再帰処理の活用方法

再帰処理は、バックトラッキング法の実装に非常に適しています。

各セルから隣接セルへ進む際に再帰的に関数を呼び出すことで、自然なバックトラッキングが実現できます。

再帰呼び出しの深さが増すと、システム側でスタックオーバーフローのリスクがありますので、入力サイズに応じた配慮が必要です。

処理が終了した際に、関数が自動的に前の状態に戻る仕組みを利用するため、コードの記述が簡潔になります。

迷路データの表現方法

迷路データは、2次元配列を利用してセルごとの情報を管理するのが一般的です。

各セルは、壁の有無や訪問状態などを保持するために、構造体と組み合わせて表現します。

例えば、セル内部に「上」「下」「左」「右」の壁情報を数値で管理し、壁が取り除かれると値を変更することでパスの生成を行います。

また、隣接セルの判定には、方向を示す数式 $δ = + 1, - 1$ を応用する方法もあります。

C言語での実装ポイント

配列と構造体の利用

C言語では、迷路全体を管理するために2次元配列を利用し、各セルを構造体で表現するのが有効です。

セル構造体には、壁の状態(たとえば、top, bottom, left, right)や訪問済みフラグなどのフィールドを持たせます。

これにより、コードの可読性が向上し、各セルへのアクセスや更新が容易になります。

ランダム生成の工夫

迷路生成にはランダム性が不可欠です。

C言語の rand()関数を利用して乱数を生成し、隣接セルの選択をランダムに行います。

乱数の初期化には srand() を使用し、通常は time(NULL) をシードに設定することで、実行するたびに異なる迷路が生成できるよう工夫します。

エラー処理の注意点

実装時には、配列の添え字が範囲外にならないか、再帰呼び出しによるスタックオーバーフローが起こらないかなど、エラー処理に十分注意する必要があります。

動的メモリを利用する場合は、確保に失敗した際のエラーチェックを行うなど、実装全体の堅牢性を意識して設計することが大切です。

迷路探索アルゴリズム

幅優先探索 (BFS) の解説

キューを用いた探索手法

幅優先探索 (BFS) は、探索開始地点から各セルまでの最短経路を見つけるために、キューを利用して探索を行います。

探索開始セルをキューに格納し、キューからセルを取り出してその隣接セルを順次チェックします。

先入れ先出しの性質により、距離の近いセルから順番に訪問するため、目的地に到達したときには必ず最短経路となる点が特長です。

探索経路の管理方法

BFSでは、各セルに前のセルの情報や探索距離(レベル)を付加することで、到達経路を記録します。

この情報に基づき、目的地に到達した場合は経路を逆順にたどることで正しいパスを復元できます。

管理には、追加の配列や構造体のメンバを利用して、各セルの状態を詳細に保持することが有効です。

深さ優先探索 (DFS) の解説

スタックと再帰の活用

深さ優先探索 (DFS) は、ある方向へできるだけ探索を進め、行き止まりになった時点でバックトラックする手法です。

スタックを用いて実装する方法や、再帰呼び出しで自然にバックトラックする方法があり、どちらもシンプルで実装しやすいのが特徴です。

各セルの探索が完了するまでその方向に進むため、全体を網羅的に探索できるのも良い点です。

探索パターンの特徴

DFSでは、一度深く探索することで、広範囲にわたる経路を一気に検出することが可能です。

ただし、最短経路が得られるとは限らないため、経路の最適性が求められる場合には、BFSとの検討が必要です。

探索パターンとしては、セクションごとに深く進むため、全体像の把握が難しくなる場合もあるため、用途に合わせた選択が重要です。

探索アルゴリズムの比較

BFSとDFSのメリット・デメリット

BFSは、必ず最短経路が見つかるというメリットがあり、特定の終了条件下で堅実な探索を行えます。

一方、探索に使用するメモリが増大しがちな点が注意点です。

対してDFSは、比較的メモリ使用量が少なく済み、シンプルな実装が可能ですが、迷路全体を網羅する際には最短経路が得られない可能性があります。

各アルゴリズムの特徴を理解し、用途に応じて選択することが大切です。

適用シーンの検証

迷路探索において、経路の最短性が重要な場合にはBFSが適しており、広範囲の探索やメモリ制約がある場合にはDFSが有効です。

また、実装の複雑さや目的に合わせ、二種類の手法を組み合わせることも検討できます。

シナリオごとにどちらのアルゴリズムがより効率的かを事前に評価することで、最適な探索結果を得ることができます。

実装例と応用

迷路生成のサンプルコード解説

バックトラッキング法の実装例

以下は、バックトラッキング法を用いた迷路生成のシンプルなサンプルコードです。

セルの状態を示す構造体を定義し、ランダムな順序で隣接セルを選択することで、壁の取り除きと迷路の生成を実現しています。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define WIDTH 10
#define HEIGHT 10
// セル構造体: 各セルの状態を保持
typedef struct {
    int visited;    // 訪問済みかを示すフラグ
    int top;        // 上の壁が存在するか
    int bottom;     // 下の壁が存在するか
    int left;       // 左の壁が存在するか
    int right;      // 右の壁が存在するか
} Cell;
Cell maze[HEIGHT][WIDTH];
// セルの初期化処理
void initMaze() {
    for (int i = 0; i < HEIGHT; i++) {
        for (int j = 0; j < WIDTH; j++) {
            maze[i][j].visited = 0;
            maze[i][j].top = 1;
            maze[i][j].bottom = 1;
            maze[i][j].left = 1;
            maze[i][j].right = 1;
        }
    }
}
// バックトラッキング法による迷路生成
void generateMaze(int x, int y) {
    maze[y][x].visited = 1;
    // 上下左右の方向を表す配列
    int directions[4] = {0, 1, 2, 3};
    // ランダムに方向をシャッフル
    for (int i = 0; i < 4; i++) {
        int j = rand() % 4;
        int temp = directions[i];
        directions[i] = directions[j];
        directions[j] = temp;
    }
    // 各方向へ再帰的に探索を進める
    for (int i = 0; i < 4; i++) {
        int nx = x;
        int ny = y;
        if (directions[i] == 0) { ny = y - 1; }  // 上
        else if (directions[i] == 1) { nx = x + 1; } // 右
        else if (directions[i] == 2) { ny = y + 1; } // 下
        else if (directions[i] == 3) { nx = x - 1; } // 左
        // 配列範囲内かチェック
        if (nx >= 0 && nx < WIDTH && ny >= 0 && ny < HEIGHT && maze[ny][nx].visited == 0) {
            // 壁を取り除く処理
            if (directions[i] == 0) {
                maze[y][x].top = 0;
                maze[ny][nx].bottom = 0;
            } else if (directions[i] == 1) {
                maze[y][x].right = 0;
                maze[ny][nx].left = 0;
            } else if (directions[i] == 2) {
                maze[y][x].bottom = 0;
                maze[ny][nx].top = 0;
            } else if (directions[i] == 3) {
                maze[y][x].left = 0;
                maze[ny][nx].right = 0;
            }
            generateMaze(nx, ny);
        }
    }
}
int main() {
    srand((unsigned)time(NULL));
    initMaze();
    // 初期位置(0,0)から迷路生成開始
    generateMaze(0, 0);
    // 生成結果を簡単に表示
    for (int i = 0; i < HEIGHT; i++) {
        for (int j = 0; j < WIDTH; j++) {
            printf("%c ", maze[i][j].visited ? '.' : '#');
        }
        printf("\n");
    }
    return 0;
}

. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .

迷路探索のサンプルコード解説

BFS/DFSアルゴリズムの実装例

以下は、幅優先探索 (BFS) と深さ優先探索 (DFS) を用いた迷路探索のサンプルコードです。

BFSではキューを利用して探索を進め、DFSは再帰的に隣接セルの探索を行っています。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define WIDTH 10
#define HEIGHT 10
#define MAX_QUEUE 100
// セル構造体: 基本的な属性を保持
typedef struct {
    int x, y;
    int visited;
} Cell;
// 迷路全体の定義(空の迷路として扱う)
Cell maze[HEIGHT][WIDTH];
// キュー構造体の定義
typedef struct {
    int front, rear;
    Cell items[MAX_QUEUE];
} Queue;
// キューの初期化
void initQueue(Queue *q) {
    q->front = 0;
    q->rear = 0;
}
// キューへのエンキュー処理
void enqueue(Queue *q, Cell item) {
    if ((q->rear + 1) % MAX_QUEUE != q->front) {
        q->items[q->rear] = item;
        q->rear = (q->rear + 1) % MAX_QUEUE;
    }
}
// キューからのデキュー処理
Cell dequeue(Queue *q) {
    Cell item = q->items[q->front];
    q->front = (q->front + 1) % MAX_QUEUE;
    return item;
}
// BFSによる探索
void bfs(int startX, int startY) {
    Queue queue;
    initQueue(&queue);
    maze[startY][startX].visited = 1;
    enqueue(&queue, maze[startY][startX]);
    // キューが空になるまで探索
    while (queue.front != queue.rear) {
        Cell current = dequeue(&queue);
        // 現在のセルの探索状態を表示
        printf("BFS visiting: (%d, %d)\n", current.x, current.y);
        // 上、右、下、左の順で隣接セルを確認
        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {-1, 0, 1, 0};
        for (int i = 0; i < 4; i++) {
            int nx = current.x + dx[i];
            int ny = current.y + dy[i];
            if (nx >= 0 && nx < WIDTH && ny >= 0 && ny < HEIGHT && maze[ny][nx].visited == 0) {
                maze[ny][nx].visited = 1;
                enqueue(&queue, (Cell){nx, ny, 1});
            }
        }
    }
}
// DFSによる探索(再帰形式)
void dfs(int x, int y) {
    maze[y][x].visited = 1;
    printf("DFS visiting: (%d, %d)\n", x, y);
    // 上、右、下、左の順で探索
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {-1, 0, 1, 0};
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < WIDTH && ny >= 0 && ny < HEIGHT && maze[ny][nx].visited == 0) {
            dfs(nx, ny);
        }
    }
}
int main() {
    // 迷路の初期化: 各セルに座標を設定
    for (int y = 0; y < HEIGHT; y++) {
        for (int x = 0; x < WIDTH; x++) {
            maze[y][x].x = x;
            maze[y][x].y = y;
            maze[y][x].visited = 0;
        }
    }
    // BFS探索実行
    printf("BFS Exploration:\n");
    bfs(0, 0);
    // 探索結果をリセット
    for (int y = 0; y < HEIGHT; y++) {
        for (int x = 0; x < WIDTH; x++) {
            maze[y][x].visited = 0;
        }
    }
    // DFS探索実行
    printf("DFS Exploration:\n");
    dfs(0, 0);
    return 0;
}

BFS Exploration:
BFS visiting: (0, 0)
BFS visiting: (0, 1)
BFS visiting: (1, 0)
BFS visiting: (0, 2)
BFS visiting: (1, 1)
BFS visiting: (2, 0)
...
DFS Exploration:
DFS visiting: (0, 0)
DFS visiting: (0, 1)
DFS visiting: (0, 2)
DFS visiting: (0, 3)
DFS visiting: (0, 4)
...