Nodachisoft Nodachi Sword Icon

@あまじ✎ 2021年5月15日に更新

第４章３ C言語コンソール上で迷路脱出プログラム・迷路の自動生成

#C11仕様 #C言語 #ゲームプログラミング

イチからゲーム作りで覚えるC言語

連載ページ一覧へ

第４章２ C言語コンソール上で迷路脱出プログラム : PREV

NEXT : 第４章４ C言語コンソールで横スクロールシューティングゲーム（１/２） :

概要

前回、簡単な迷路脱出ゲームを作成しました。前回のプログラムを改良して、迷路を自動的に生成するアルゴリズムを確認し、ゲームらしい要素を加えます。

前回のページの続きとなっていますので、このプログラムの基礎的な流れを確認したい場合は前回のページからご確認ください。

ライブラリを含むこのページのソースコードはココをクリックで圧縮された zip 形式でダウンロードできます。

プログラムの実行イメージ

このページで解説していく迷路脱出ゲームを動かした時のイメージです。

地下10F のダンジョンから 1階づつ地上にむかって上っていきます。

地下9F で時間制限でダンジョン脱出をあきらめる時のゲームプレイ・イメージです。

迷路からの脱出失敗パターン

ゲームのルール

作成するゲームのルールを決めておきます。

今回は最低限のゲームステージや、アイテム、時間制限を追加しておきます。

画面は下のような構成と考えておきます。

ルールは下のようにします。

制限時間はリアルタイムに減っていき、 0 秒までに階段に辿り着けなければゲームオーバー
迷路は自動生成される。プレイするたびに迷路は変わる。
階段に辿り着き、0F（地上）まで辿り着いたらクリア
SP（スピードアップ）アイテムに触れるとプレイヤの歩く速度が一定割合上昇する

プログラムの流れ

プログラムを起動してから終了するまでの流れを図にして頭を整理しておきます。

前回の記事から①「ゲームの状況を進行」する機能が大きく拡張された部分です。

具体的には「ゲームの状況を進行」の箇所に下のような追加をしています。

ゲームに制限時間を設けますので、時間切れかをチェックするプログラムを加えています。
プレイヤーが触れると移動速度があがるパワーアップアイテムを追加します。プレイヤーがアイテムに触れていたら、パワーアップする判定をするプログラムを加えています。
地下〇階からゲームが始まり、階段を上って 0 階に辿り着いたら、クリアとなるプログラムを加えています。

ゲームの起動・初期化パート

それでは、ゲームの起動・初期化パートについて、新しく追加したコードを確認してみます。

entry.c

int main() {
    hideCursor();   // カーソルの点滅を隠す
    setConsoleWindowTitle("ぷらんくの迷路探索！");  // ウィンドウのタイトルバー変更

    // プレイヤが操作するキャラクタを作成
    GameObject player;
    player.posx = 2;
    player.posy = 1;
    player.speed = 12.0;

    // ゲームデータの初期化
    GameData gamedata;
    gamedata.player = player;
    gamedata.screensize_x = 60;
    gamedata.screensize_y = 21;
    gamedata.level = 10;            // 10 階からスタート    gamedata.restTime = 1000 * 15;  // 15秒が一つの階層の時間制限
    // マップデータを初期化する    gamedata.map = (char*)calloc(sizeof(char), gamedata.screensize_x * gamedata.screensize_y);
    // 最初のマップデータを作成する    generateMap(&gamedata, gamedata.screensize_x - 40, gamedata.screensize_y - 14);
    long deltaTime;
	initNdcGameLib(gamedata.screensize_x, gamedata.screensize_y);
    BOOL isClearGame = FALSE;
    BOOL isTimeup = FALSE;

184 行目ではゲームデータの設定を追加しています。

entry.c

    gamedata.level = 10;            // 10 階からスタート

GameData 構造体にメンバ level を追加し、level = 10 と定義しています。 gamedata.level は現在、プレイヤが冒険している階層を表していて、ステージをクリアするたびに、1 ずつカウントダウンしていきます。 gamedata.level が 0 になったら、迷宮から脱出できたとしてクリアになります。

続いて185 行目です。

entry.c

    gamedata.restTime = 1000 * 15;  // 15秒が一つの階層の時間制限

gamedata.restTime で１つの階層をクリアするまでの時間制限を定義しています。ミリ秒単位で計算に使うので、15*1000ミリ秒（つまり15秒）が時間制限としています。

続いて 187 行目です。

entry.c

    // マップデータを初期化する
    gamedata.map = (char*)calloc(sizeof(char), gamedata.screensize_x * gamedata.screensize_y);
    // 最初のマップデータを作成する
    generateMap(&gamedata, gamedata.screensize_x - 40, gamedata.screensize_y - 14);

新しく作成した generateMap 関数を呼び出しています。この関数は指定したサイズのマップを生成します。

使い方は以下になります。

generateMap関数の宣言

void generateMap(GameData* gamedata, int screenSizeX, int screenSizeY);

第１引数には、ランダムで自動生成したマップデータの結果を格納する先を指定します。
第２引数には、生成するマップデータの横幅を指定します。
第３引数には、生成するマップデータの縦幅を指定します。

10階から 0 階に進むにつれて大きな迷路にしたいので、最初は小さいマップデータを生成することにします。

階段までたどり着いて、10階から 0 階（地上）に辿り着くにつれて、だんだんと迷路が大きくなっていき、最終的には画面いっぱいのサイズの迷宮となります。

迷路生成アルゴリズム

では、指定された迷路をランダムに生成する generateMap 関数の中身をのぞいてみましょう。

entry.c

// マップを自動生成する
void generateMap(GameData* gamedata, int screenSizeX, int screenSizeY) {
    // マップ初期化
    for (int y = 0; y < gamedata->screensize_y; y++) {
        for (int x = 0; x < gamedata->screensize_x; x++) {
            gamedata->map[y * gamedata->screensize_x + x] = ' ';
        }
    }

    // マップ生成元の node データサイズを定義
    int mx = screenSizeX / 4;
    int my = screenSizeY / 2;

    // マップ生成中のデータを格納する先を確保
    // ビットで上下左右の通路, アイテム有無、階段有無を管理します。
    // 0: 何もなし, 1:上, 2:右, 4:下, 8:左, 16: 階段, 32: スピードアップアイテム
    char* roomnodes = (char*)calloc(sizeof(char), mx * my);

    // 初期ノード
    roomnodes[0] = 1;  // もっとも左上の部屋（node）を上に通路があるように仮設定
    
    // ダンジョンの通路をランダム生成
    while (TRUE) {
        int offset = getPostionOfConnectable(roomnodes, 1, mx, my);
        if (offset == -1) {
            offset = getPostionOfConnectable(roomnodes, 2, mx, my);
            if (offset == -1) {
                offset = getPostionOfConnectable(roomnodes, 3, mx, my);
                if (offset == -1) break;    // すべての node と接続が完了した
            }
        }
        connectToNewNode(roomnodes, offset, mx, my);  // 部屋からダンジョンを掘る
    }

    // 階段とスピードアップアイテムを配置
    roomnodes[getRand(1, mx * my - 2)] |= 32;   // スピードアップアイテムをランダムに設置
    int levelOffset = getRand(1, mx * my - 2);
    if ((roomnodes[levelOffset] & 32) > 0) {
        levelOffset++; // アイテムと重複したら階段をずらす
    }
    roomnodes[levelOffset] |= 16;   // 階段をランダムに設置

    // 出来上がったマップデータを見た目を整えて gamedata->map 内に書き込む
    int offsetx = 2;
    int offsety = 1;
    for (int y = 0; y < my; y++) {
        for (int x = 0; x < mx; x++) {
            char node = roomnodes[y * mx + x];
            if (!(node & 2)) { // 右は壁
                gamedata->map[(y * 2 + offsety) * gamedata->screensize_x + (x * 4 + 2) + offsetx] = '[';
                gamedata->map[(y * 2 + offsety) * gamedata->screensize_x + (x * 4 + 3) + offsetx] = ']';
            }
            if (!(node & 4)) { // 下は壁
                gamedata->map[(y * 2 + 1 + offsety) * gamedata->screensize_x + (x * 4) + offsetx] = '[';
                gamedata->map[(y * 2 + 1 + offsety) * gamedata->screensize_x + (x * 4+1) + offsetx] = ']';
            }
            gamedata->map[(y * 2 + 1 + offsety) * gamedata->screensize_x + (x * 4 + 2) + offsetx] = '[';
            gamedata->map[(y * 2 + 1 + offsety) * gamedata->screensize_x + (x * 4 + 3) + offsetx] = ']';
            if (node & 32) {  // スピードアップアップあり
                gamedata->map[(y * 2 + offsety) * gamedata->screensize_x + (x * 4) + offsetx] = 'S';
                gamedata->map[(y * 2 + offsety) * gamedata->screensize_x + (x * 4 + 1) + offsetx] = 'P';
            }
            if (node & 16) {  // 階段あり
                gamedata->map[(y * 2 + offsety) * gamedata->screensize_x + (x * 4) + offsetx] = '=';
                gamedata->map[(y * 2 + offsety) * gamedata->screensize_x + (x * 4 + 1) + offsetx] = '=';
            }
        }
    }
    for (int x = 0; x < mx * 2 + 1; x++) {  // マップ上端の壁を作成する
        gamedata->map[x * 2] = '[';
        gamedata->map[x * 2 + 1] = ']';
    }
    for (int y = 1; y < my * 2 + 1; y++) {  // マップ左端の壁を作成する
        gamedata->map[gamedata->screensize_x * y] = '[';
        gamedata->map[gamedata->screensize_x * y + 1] = ']';
    }
    free(roomnodes);
}

この関数から、 getPostionOfConnectable 関数やconnectToNewNode関数といった、別の関数が呼び出しされていますが、そちらは後で確認するとして、全体のプログラムの流れを確認していきます。

generateMap 関数の中は図にすると下のような流れで実行されていきます。

初期化

関数の中で最初に、関数の実行に必要となるメモリの初期化を行っておきます。マップデータ（最終的に画面に出力するデータ）と、マップを生成するときに使用する部屋データの両方を初期化します。

また、最初に迷路の開始地点として、最も左上の迷路を通路 1 としておきます。

ダンジョン作成のアルゴリズム

ダンジョンが出来上がっていく過程をアニメーションにしてみると以下のようになります。

create_maze_path.apng

わかりやすいように簡単なグラフィックをつけています。

実際に Web 上でダンジョンをブラウザ上でボタン一つで生成できるように、下のページからダンジョンが生成される過程を確認できます。

ダンジョン生成確認用アプリ

部屋データ

ダンジョンは部屋データを組み合わせて生成しています。

例えば、上のマップのように、横13マス、縦11マスのダンジョンを作成したい場合は、横方向に 6 個の部屋データ、縦方向に 5 個の部屋データ、全部で 6 × 5 = 30 個の部屋データが必要となります。

それぞれの部屋データは、東西南北の他の部屋に接続しているかの情報を持たせます。

必ずどの部屋からでも、ほかのどの部屋にでもつながるようにすべての部屋を接続します。

部屋と部屋を接続するルール

部屋と部屋を接続するルールは generateMap 関数の中の下の箇所で決めています。

entry.c

    // ダンジョンの通路をランダム生成
    while (TRUE) {
        int offset = getPostionOfConnectable(roomnodes, 1, mx, my);
        if (offset == -1) {
            offset = getPostionOfConnectable(roomnodes, 2, mx, my);
            if (offset == -1) {
                offset = getPostionOfConnectable(roomnodes, 3, mx, my);
                if (offset == -1) break;    // すべての node と接続が完了した
            }
        }
        connectToNewNode(roomnodes, offset, mx, my);  // 部屋からダンジョンを掘る
    }

ここでは、”すでに他の部屋とつながっている各部屋”を対象に、東西南北に繋ぐ先を探してみて、またどの部屋とも接続していない場所があれば、接続をしてくアルゴリズムとなっています。

なお、”すでに他の部屋とつながっている各部屋” のうち、なるべく通路の数が少ないものを優先して、他の部屋と接続します。

具体例を見てみます。 generateMap 関数の中の 350 行目の while 文を 4 回ほどループして、部屋と部屋を 4 回、接続した後の状態です。

”すでに他の部屋とつながっている各部屋” は下の図の箇所です。

このとき、次に while 文の中身が実行されたとき、通路の数が少ない部屋から、東西南北の部屋（まだどことも繋がっていない部屋）に接続します。

通路の数を数字にしてみると下のようになります。

左上隅の通路の数が 2 になっているのは、初期化の時に、北に通路を持っているという情報を与えているためです。（画面上は北に通路は内容に見えますが、データ上は実は通路を北に持っています）

これは一番最初に通路を持っている部屋が少なくとも 1 つ必要なため、適当に設定したものです。

さて、アルゴリズムでは、通路の数が少ない部屋から別の部屋に通路を作ります。 1 つのみ通路を持っている、部屋が 1 つ存在します。

この部屋を取得する時のプログラムは以下で取得しています。

entry.c

    // ダンジョンの通路をランダム生成
    while (TRUE) {
//next-highlight
        int offset = getPostionOfConnectable(roomnodes, 1, mx, my);
        if (offset == -1) {
            offset = getPostionOfConnectable(roomnodes, 2, mx, my);
            if (offset == -1) {
                offset = getPostionOfConnectable(roomnodes, 3, mx, my);
                if (offset == -1) break;    // すべての node と接続が完了した
            }
        }
        connectToNewNode(roomnodes, offset, mx, my);  // 部屋からダンジョンを掘る
    }

getPositionOfConnectable 関数は、以下のような呼び出し方をしています。

getPositionOfConnectable宣言

int getPostionOfConnectable(部屋データ, 通路の数, 部屋の横サイズ, 部屋の縦サイズ);

部屋データ（roomnodes）を渡して、通路を 1 つ持っており、かつ、ちゃんと部屋から隣接する部屋に接続できるものがあれば、対象の roomnode の添え字（offset）を返します。もしなければ、-1 が返ってくる、対象の部屋が複数あればランダムで一つを返す、といった仕組みです。

具体的に見てみます。

次に部屋から部屋を接続するとき、1 つ通路をもった部屋が 1 つ存在するので、この部屋から東西南北の部屋で、かつまだどこともつながっていない部屋と接続をします。

接続をする処理は connectToNewNode 関数で実施しています。

connectToNewNode 関数の中では、北（上方向）、東（右方向）、南（下方向）のどれでも接続できる状態であることを確認し、ランダムで３方向から１つを選び接続します。

以下が connectToNewNode 関数の中身です。

entry.c

// 指定した node（部屋）から edge（通路）を作成して、新しい node （部屋）に接続する
void connectToNewNode(char* nodes, const int offset, const int width, const int height) {
    int y = offset / width;
    int x = offset % width;
    int pathCount = 0;  // 接続可能な方角がいくつ存在するかをカウントする
    if (x > 0          && nodes[offset - 1] == 0) pathCount++; // 左のチェック
    if (x < width - 1  && nodes[offset + 1] == 0) pathCount++; // 右のチェック
    if (y > 0          && nodes[offset - width] == 0) pathCount++; // 上のチェック
    if (y < height - 1 && nodes[offset + width] == 0) pathCount++; // 下のチェック
    
    int curvePathDirection = getRand(1, pathCount); // 接続可能な方角からランダムに一つ選択する
    int dirCount = 0;
    // 左との接続可能をチェックし、接続方向が一致するなら通路を作成
    if (x > 0 && nodes[offset - 1] == 0) {
        dirCount++;
        if (curvePathDirection == dirCount) { // 接続したい方角が一致
            nodes[offset] |= 8;     // 左への接続
            nodes[offset - 1] |= 2; // 右への接続
        }
    }
    // 右との接続可能をチェックし、接続方向が一致するなら通路を作成
    if (x < width - 1 && nodes[offset + 1] == 0) {
        dirCount++;
        if (curvePathDirection == dirCount) { // 接続したい方角が一致
            nodes[offset] |= 2;     // 右への接続
            nodes[offset + 1] |= 8; // 左への接続
        }
    }
    // 上との接続可能をチェックし、接続方向が一致するなら通路を作成
    if (y > 0 && nodes[offset - width] == 0) {
        dirCount++;
        if (curvePathDirection == dirCount) { // 接続したい方角が一致
            nodes[offset] |= 1;         // 上への接続
            nodes[offset - width] |= 4; // 下への接続
        }
    }
    // 下との接続可能をチェックし、接続方向が一致するなら通路を作成
    if (y < height - 1 && nodes[offset + width] == 0) {
        dirCount++;
        if (curvePathDirection == dirCount) { // 接続したい方角が一致
            nodes[offset] |= 4;         // 下への接続
            nodes[offset + width] |= 1; // 上への接続
        }
    }
}

接続できるかを確認するときは、迷路全体のサイズからはみ出さないように、境界チェックをすることに注意します。

例えば、286行目では、左側（西側）の部屋の状態をチェックしようとしています。

具体的な例として、位置(x 方向, y方向 )について、部屋 (0,3) から左方向に接続できるかをチェックするとき、なにも境界チェックをしないと、部屋(-1,3) のデータを確認することになります。もしこんなデータの中身を確認しようとすると、エラーとなってしまいます。

それを防ぐために、if ( x > 0 ) { … 左の部屋の情報を確認する処理 } のように条件を書いてあげています。

さて、1 つの通路を持っており、周囲に接続できる部屋が 1 つもないときは、 2 つの通路を持っており、周囲に接続できる部屋を探します。

具体例では下のような状況です。

ソースコードでは下のハイライト部分です。

entry.c

    // ダンジョンの通路をランダム生成
    while (TRUE) {
        int offset = getPostionOfConnectable(roomnodes, 1, mx, my);
        if (offset == -1) {
//next-highlight
            offset = getPostionOfConnectable(roomnodes, 2, mx, my);
            if (offset == -1) {
                offset = getPostionOfConnectable(roomnodes, 3, mx, my);
                if (offset == -1) break;    // すべての node と接続が完了した
            }
        }
        connectToNewNode(roomnodes, offset, mx, my);  // 部屋からダンジョンを掘る
    }

こうやって、次々に通路を伸ばしていき、最終的にすべての部屋が通路で結ばれます。

そのとき、すべての部屋から、他に接続できる部屋（どことも接続していない部屋で隣接している部屋）がなくなるため、while 文から抜けることとなります。

ソースコードでは、以下の部分です。

entry.c

    // ダンジョンの通路をランダム生成
    while (TRUE) {
        int offset = getPostionOfConnectable(roomnodes, 1, mx, my);
        if (offset == -1) {
            offset = getPostionOfConnectable(roomnodes, 2, mx, my);
            if (offset == -1) {
                offset = getPostionOfConnectable(roomnodes, 3, mx, my);
                if (offset == -1) break;    // すべての node と接続が完了した            }
        }
        connectToNewNode(roomnodes, offset, mx, my);  // 部屋からダンジョンを掘る
    }

これで通路の状態を持った部屋データが完成です！

アイテム、プレイヤ、階段を配置

マップデータの地形部分（部屋と通路）が完成しましたので、できあがったマップの部屋にランダムでアイテムやプレイヤ、階段を配置します。

entry.c

    // 階段とスピードアップアイテムを配置
    roomnodes[getRand(1, mx * my - 2)] |= 32;   // スピードアップアイテムをランダムに設置
    int levelOffset = getRand(1, mx * my - 2);
    if ((roomnodes[levelOffset] & 32) > 0) {
        levelOffset++; // アイテムと重複したら階段をずらす
    }
    roomnodes[levelOffset] |= 16;   // 階段をランダムに設置

部屋のどこかにランダムでスピードアップアイテムと階段を配置します。スピードアイテムが部屋に存在することとして、ランダムで選ばれた部屋データ（roomnodes）に 32（つまり、6ビット目）をOR演算で加えています。

階段についても同様に、16（つまり、5ビット目）をOR演算で加えています。

これで必要なマップデータはすべて揃いましたので、出来上がった部屋データを元に、画面への描画を行います。

想定外のマップ生成パターン

今回はシンプルなアルゴリズムで見やすさ優先のため、「プレイヤの位置と、階段やスピードアップアイテムが重複して生成されたか」などのチェックは実施していません。

お互いが重複しないようにランダム生成するなど、ぜひご自身で改良してみてください。

部屋データを描画

部屋データ1つで東西南北への接続状態を持っています。グラフィカルな例では、部屋データ一つを画面上に描画する時は、横2マス、縦2マスぶんのデータを描画できます。

コンソール画面上では部屋データ一つを画面上に描画する時は、横4マス(文字)、縦2マス(文字)ぶんをつかって描画しています。

これでマップの描画が完了しました。コンソール画面では、「o」はプレイヤー、「SP」はスピードアップ（LvUPアイテム）、「== 」は階段としています。

記号	意味	グラフィック版なら
o	プレイヤー。キーボードで操作できる
SP	スピードアップ。プレイヤーが触れると移動速度がアップ
==	階段。プレイヤーが触れるとステージをクリア
[]	壁。プレイヤーはここに移動できない

その他追加されているゲーム要素

今回は前ページのプログラムに加えて、時間制限を設けていたり、階段やスピードアップアイテムの要素を追加しています。

特にこのあたりは目新しいい仕組みは追加されていませんので、詳細は割愛します。実際の動きはソースコードを見て、動かして確認していただければと思います。

補足

グラフ理論

部屋と部屋を線で繋ぐ効率の良い方法や扱い方はグラフ理論と呼ばれています。今回はダンジョンの迷路生成で使ってみましたが、データの圧縮アルゴリズムや文字や数字の並び替え（ソート）アルゴリズムなど様々な問題を解決することに使える、非常に便利なものです。

マップのランダム生成アルゴリズム

ローグライクのマップ生成など、今回のアルゴリズムを少し変更しすれば似たようなものを生成できます。少し工夫すると2Dのマップだけでなく、3Dのマップも作ることができます。

迷路を生成するアルゴリズムは様々なものが公表されています。このページで紹介したものは筆者のオリジナルであり、"depth-first search(DFS)" アルゴリズムや "recursive backtracker" というアルゴリズムに似ており、わかりやすさ優先の非常にシンプルなものです。（ただ、迷路生成のアルゴリズムは歴史が古いので、筆者が思いつくアルゴリズムはきっと世の中のどこかで先人が作成していると思います）