各クラスの実現

迷路データ格納クラス - maze_map

迷路データを格納するクラスを maze_map と名付ける。
迷路データとしては、縦・横のサイズと、M×Nの平面上で壁となる部分と通路となる部分の情報(以下、マップ情報と呼ぶ)を保持する必要があり、これをメンバ変数として格納する。
縦横のサイズはそれぞれ int型変数として保持し、1マス分の壁や通路の情報は char型のデータとして表現することにし、それを M×Nの2次元配列情報としてマップ情報を保持することにする。

さらに、壁と通路のそれぞれを表す文字を定数として定義しておく。ここでは、壁のデータとして、'*' とし、通路のデータとして、 ' ' (空白)と定義することにする。

以上を考慮して、メンバ変数部分は以下のように書くことが出来る。
直接メンバ変数の値を勝手に書き換えできないように、private属性にする。
マップ情報を格納する２次元配列は動的にメモリを確保することを想定し、 char型のポインタのポインタとして宣言している。

class maze_map {
    int     _width;                                // 迷路の横のサイズ
    int     _height;                               // 迷路の横のサイズ
    char    **_tab;                                // 迷路のマップ情報

    enum {
        _wall = '*',                               // 「壁」の文字
        _passage = ' ',                            // 「通路」の文字
    };

public:
    ...
};

次に、maze_map クラスのコンストラクタを考える。
本クラスのオブジェクトをインスタンス化(実体化)する際に、縦・横のサイズを引数として指定するものとし、一度インスタンス化した後は迷路のサイズは変更しないものとして実装する。
コンストラクタが呼び出された際は、引数として渡されたサイズ情報をメンバ変数に格納し、指定されたサイズに必要なマップ情報の領域を確保するようにする。
以上を考慮して、コンストラクタは以下のように書くことが出来る。
(ここで、サイズ情報に関して、迷路の縦横のサイズは奇数にしかならないので、コンストラクタに与えるサイズは迷路の通路の行・列の数に相当する値を与えるものとする。つまり、実際の迷路のサイズは、引数として受け取った縦横のサイズを２倍して１足したものになる。例えば、縦横のサイズとして(2,3)を与えた場合、迷路のサイズとしては(5,7)になる)

    // コンストラクタ
    maze_map(int w, int h) {
        _width  = w * 2 + 1;
        _height = h * 2 + 1;
        _tab = new char *[_width];
        for (int i = 0; i < _width; i++)
            _tab[i] = new char[_height];
    }

次に、maze_map クラスのデストラクタを考える。
今回のプログラムでは、明示的にデストラクタを呼び出すことはないが、コンストラクタの中で動的にメモリを確保している場合は、デストラクタも忘れずに作っておくように習慣付けておくこと。

デストラクタが定義されていない場合、デフォルトとなるデストラクタが呼び出されることになるが、デフォルトのデストラクタはコンストラクタの中で動的に格納したメモリの解放までは面倒を看てくれない。そのため、オブジェクトを newしたり deleteしたりすることを頻繁に繰り返すと、メモリリークする(メモリを解放しても再利用されない)ことになり、最悪の場合、実行に必要なメモリを確保できずに、プログラムが実行できなくなることもある。
デストラクタは以下のように書くことが出来る。

    // デストラクタ
    ~maze_map() {
        for (int i = 0; i < _width; i++)
            delete _tab[i];
        delete _tab;
    }

最後に、メンバ関数を考える。
必要になりそうなメンバ関数としては以下のものが考えられる。

マップの横のサイズを得る
マップの縦のサイズを得る
縦・横の２つの座標 (x, y)の位置がマップの範囲内かどうかを調べる
縦・横の２つの座標 (x, y)の位置が「壁」であるかどうかを調べる
縦・横の２つの座標 (x, y)にデータをセットする。
縦・横の２つの座標 (x, y)の位置のデータを得る
マップを全てクリアする(全て「壁」にしてしまう)

それぞれのメンバ関数の宣言は以下のようになる。

int    width();
int    height();
bool   is_inside(int x, int y);
bool   is_wall(int x, int y);
void   set(int x, int y, char c = _passage);
char   get(int x, int y);
void   clear();

※ set() の３つ目は省略可能で、省略した場合は「通路」のデータをセットする。
また、is_wall()は、迷路の範囲外については「壁ではない」として判定すること。

迷路データ作成クラス - maze_maker

迷路データを作成するクラスを maze_maker と名付ける。
迷路作成のアルゴリズムは、ここで説明している 「穴掘り法」の簡易アルゴリズムを用いている。

メンバ変数としては、作成作業を行なう対象となる maze_mapクラス のオブジェクトへのポインタ変数を保持しており、 maze_makerクラス のオブジェクトを生成する際に実行されるコンストラクタに、引数として渡しておく。
(コンストラクタの仕事は、maze_map クラスのオブジェクトへのポインタをメンバ変数に格納しておくだけである)

メンバ関数としては、public なものが generate() の1つ、 private なものが check_direction()と check_point() の2つを持つ。
迷路作成作業は、メンバ関数 generate() を呼び出すことで行なわれる。
メンバ関数 generate() は、中で、check_point() と check_direction() を呼び出しながら迷路を作成していく。

check_point()では、現在位置からランダムに通路を延ばす方向を決定し、時計周りあるいは反時計周り方向に、check_direction()を呼び出すことで、２マス先が壁かどうかをチェックしながら通路を延ばしていく。

check_direction()では、引数により指定された方向の２マス先が壁かどうかを調べ、壁であったら(＝通路でなかったら)通路を２マス分進める。そん後、check_point()を呼び出すことで、通路を延ばした先のマスで延ばせるだけの通路を延ばす処理を行なう。

check_point() と check_direction() の２つのメンバ関数がそれぞれお互いを呼び出し合いながら、深さ優先で通路を延ばす処理を行なっている。

class maze_maker {
    maze_map  *_maze;

    // 座標(x,y)において dで指定された方向をチェック
    void check_direction(int x, int y, int d) {
        static const struct pos {
            int x, y;
        } steps[] = {{0,1}, {1,0}, {0,-1}, {-1,0}};  // 相対位置の一覧

        int dx = steps[d & 3].x;
        int dy = steps[d & 3].y;

        if (_maze->is_wall(x + dx*2, y + dy*2)) {    // 壁の場合は通路を延ばす
            _maze->set(x + dx,   y + dy);
            _maze->set(x + dx*2, y + dy*2);

            // 延ばした先で更にチェック
            check_point(x + dx*2, y + dy*2);
        }
    }

    // 座標(x,y)において全方向をチェック
    void check_point(int x, int y) {
        if (!_maze->is_inside(x, y)) return;         // 迷路の領域外

        _maze->set(x, y);                            // 通路に設定

        int d = rand();
        int dd = (rand() & 1) * 2 - 1;    // -1 or 1

        // 時計回りまたは反時計回りに全ての方向をチェック
        check_direction(x, y, d); d += dd;
        check_direction(x, y, d); d += dd;
        check_direction(x, y, d); d += dd;
        check_direction(x, y, d); d += dd;
    }

public:
    // コンストラクタ
    maze_maker(maze_map *m) { _maze = m; }

    // メンバ関数
    void generate() {
        // ランダムに迷路開始地点を選択
        int x = rand() % (_maze->width() / 2) * 2 + 1;
        int y = rand() % (_maze->height()/ 2) * 2 + 1;

        _maze->clear();                          // 迷路マップ情報をクリア

        check_point(x, y);                       // 迷路作成

        _maze->set(0, 1, 'S');                   // スタート地点を設定
        _maze->set(_maze->width() - 1,
                   _maze->height() - 2, 'G');    // ゴール地点を設定
    }
};

迷路データ表示クラス - maze_printer

迷路データを表示するクラスを maze_printer と名付ける。
迷路の表示は単に画面に出す以外にも、ファイルとして出す場合もある。また、ファイルの形式も、ただのテキストファイルの場合もあれば、HTMLファイルとして出力しておいて、WWWブラウザで見る場合もある。
以上のどんな場合にも対応できるようにするため、迷路データを表示する処理のうち、「１マス出力処理」と「改行処理」を独立させ、別のクラスとして実装する。

例えば、画面に表示する場合は、標準出力(cout)に対して文字出力をするように実装したクラスを用意しておき、ファイルに出力する場合は、ファイルに対して文字出力を行なうように実装したクラスを用意しておけば、出力したい形態に応じて適切なクラスを使うことで、どの要求にも対応出来るようになるわけである。

この「１マス出力処理」と「改行処理」を実装する各クラスは、以下の(抽象クラス) displayクラスを継承して実現する。

// 抽象クラス
class display {
public:
    virtual void put(char c) = 0;             // 1マス出力 (純粋仮想関数)
    virtual void newline() = 0;               // 改行処理 (純粋仮想関数)
};

「１マス出力処理」はメンバ関数 put() により行ない、「改行処理」はメンバ関数 newline() により行なう。
どちらのメンバ関数も先頭に virtual と、後ろに "= 0"が付いており、純粋仮想関数となっていることに注意する。
そのため、displayクラス は抽象クラスとなっており、このクラスのオブジェクトを実体化(インスタンス化)することは出来ない。
displayクラスを継承したクラスは、抽象クラスへのポインタを経由して扱うことで多態を実現することが出来、これによって、画面への表示やファイルへの出力を切り替えることが出来るようになる。

以上を考慮して、maze_printerクラスは以下のように定義できる。

class maze_printer {
    display    *_disp;
public:
    // コンストラクタ
    maze_printer(display *disp) { _disp = disp; }

    // メンバ関数
    virtual void output(maze_map *maze) {
        for (int y = 0; y < maze->height(); y++) {
            for (int x = 0; x < maze->width(); x++)
                _disp->put(maze->get(x, y));
            _disp->newline();
        }
    }
};

maze_printerクラス のコンストラクタで、displayクラスのオブジェクトへのポインタを引数として受け取り、これをメンバ変数に保存しておく。
displayクラスを継承したクラスのうち、必要な動作を行なうクラスのオブジェクトを生成し、その生成したオブジェクトへのポインタをコンストラクタに受け渡すことで、maze_printerクラスで迷路を出力する先が切り替わることになる。

メンバ関数 output() は引数として与えられた maze_mapクラス のオブジェクトに格納された迷路情報に応じて迷路を表示する。
「１マス出力」や「改行」は、全て displayクラスのポインタを介して行なわれており、メンバ変数 _dispで指されたオブジェクトに実装されているメンバ関数の定義によって動作が変わるようになっている。

displayクラスを継承して作るクラスとして以下のようなものが考えられる。

画面に表示するクラス - display_screenクラス
画面にワイド表示するクラス - display_screen_wideクラス
ファイルに出力するクラス - display_fileクラス
ファイルにワイドで出力するクラス - display_file_wideクラス
HTMLファイルに出力するクラス - display_htmlクラス

それぞれのクラスの具体的な定義として以下のようなものを考えることが出来る。

// 画面表示クラス
class display_screen: public display {
public:
    virtual void put(char c);                // (中身を実装する)
    virtual void newline();                  // (中身を実装する)
};

// 画面表示クラス (ワイド)
class display_screen_wide: public display_screen {
public:
    void put(char c) { cout << c << c; }
};

// ファイル出力クラス
class display_file: public display {
protected:
    ofstream out;
public:
    display_file(char *fname);               // (中身を実装する)
    ~display_file();                         // (中身を実装する)

    virtual void put(char c);                // (中身を実装する)
    virtual void newline();                  // (中身を実装する)
};

// ファイル出力クラス (ワイド)
class display_file_wide: public display_file {
public:
    display_file_wide(char *name): display_file(name) { }

    void put(char c) { out << c << c; }
};

// HTML出力クラス
class display_html: public display_file {
public:
    display_html(char *name): display_file(name) {
        out << "<html><body>\n<table>\n<tr>\n";
    }
    ~display_html() { out << "</tr>\n</table>\n</body></html>" << endl; }

    void put(char c) { out << "<td>" << c << "</td>"; }
    void newline() { out << "</tr>\n<tr>" << endl; }
};

その他

一通り必要なクラスが揃ったら、残りは main関数を作って迷路作成プログラムを完成させることになる。
以下のコードはプログラムの main関数と、迷路の出力先を選択する(補助的な) 関数 select_display()である。
関数 select_display()は、出力先をユーザに訊ね、対応するクラスのオブジェクトを生成して、そのポインタを displayクラスのポインタとして返す関数である。

// 表示先の選択
display *select_display()
{
    int omode;
    display *disp = NULL;

    do {
        cout << "output mode (1..5) ? = ";
        cin >> omode;

        switch (omode) {
        case 1: disp = new display_screen; break;
        case 2: disp = new display_screen_wide; break;
        case 3: disp = new display_file("output.txt"); break;
        case 4: disp = new display_file_wide("outputW.txt"); break;
        case 5: disp = new display_html("output.html"); break;
        default:
            cout << "illegal output mode" << omode << endl; break;
        }
    } while (disp == NULL);

    return disp;
}
    

// main
int main()
{
    // サイズの入力
    int sz_x, sz_y;
    cout << "size (x, y) ? = ";
    cin >> sz_x >> sz_y;

    // 迷路情報
    maze_map        maze(sz_x, sz_y);

    // 迷路の作成
    maze_maker      maker(&maze);
    maker.generate();

    // 迷路の出力
    maze_printer printer(select_display());
    printer.output(&maze);

    return 0;
}

ここまでで作成してきた各クラスと、上記のmain関数その他のコードを組み合わせれば、迷路作成プログラムは完成である。

※ ヘッダファイルとして iostreamと fstreamと cstdlibの３つをインクルードすること。

文責：大津