C言語：棒倒し法でダンジョン(迷路)を表現する

C言語での解説ですが、アルゴリズム部分はどの言語でも対応できるよう図を使って分かりやすく解説しています。

棒倒し法とは？

2次元のダンジョン(迷路)を表現するためのアルゴリズムの1つ。
柱を作って倒すように見えることから棒倒し法と呼ばれる。

棒倒し法の考え方
C言語による棒倒し法のソースコード
ソースコードの解説

棒倒し法の考え方

周囲を壁にします。

壁の内側に1つおきに柱を立てます。

作った柱の上下左右の方向のどれか1つに柱を倒します。
これにはルールがあります。ここが棒倒し法のアルゴリズムのポイントとなる部分です。
ルールは以下の通りです。

左端の柱だけは上下左右の4方向に倒すことができる
それ以外の柱は上下右の3方向に柱を倒すことができる

倒す方向に関してはランダムで1つの方向に決めます。

以上のルールを踏まえると、この様なダンジョン風の迷路が出来上がります！

全ての柱を4方向に倒してしまうと…

ちなみに左端の柱だけでなくすべての柱で上下左右の4方向にランダムに倒すと最悪このような壁に囲まれた通路ができてしまいます。（こういうダンジョンが作りたい方なら話は別ですが…）

棒倒し法を利用すれば、ダンジョンの大きさを変えるだけで、もっと迷路っぽいものも作成できます。

イメージ

C言語による棒倒し法のソースコード

実行イメージ

@@@@@@@@@
@ @   @ @
@ @ @@@ @
@ @ @   @
@ @ @ @ @
@     @ @
@@@@@@@@@

C言語では、これまでの解説に使ったカラー画像のようなダンジョン表示はできません！
だからテキスト（＠を壁として表現）でダンジョンを出力しています。しょぼいっすね！

もし、これまでの解説に使ったようなテキストではないグラフィックのダンジョン描画をご希望でしたら以下のJavaScriptでのダンジョン描画記事をご覧ください。

create_dungeon.c

/*
	迷路を作るアルゴリズム：棒倒し法
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* ダンジョンの大きさ（行ROWと列COLUMNは、ともに5以上の奇数が望ましい） */
#define ROWS 7
#define COLUMNS 9

/* ブロックの種別 */
#define SPACE	0
#define WALL	1

/* ダンジョンを生成する関数 */
void initializeDungeon(int dungeon[ROWS][COLUMNS]) {
	int x, y, r;
	
	/* 柱を倒す方向（上右下左の順） */
	int dx[] = {0, 1, 0, -1};
	int dy[] = {-1, 0, 1, 0};

	/* ダンジョン配列を空にする */
	for(y=0; y<ROWS; y++){
		for(x=0; x<COLUMNS; x++){	
			dungeon[y][x] = SPACE;
		}
	}
	
	/* ダンジョン生成 */
	for(y=0; y<ROWS; y++){
		for(x=0; x<COLUMNS; x++){
			/* 周囲を壁にする */
			if(y == 0 || y == ROWS-1 || x == 0 || x == COLUMNS-1){
				dungeon[y][x] = WALL;
			}
			/* 壁の内側に1つおきに柱を立てる */
			else if(x >= 2 && x <= COLUMNS-1 && y >= 2 && y <= ROWS-1 && x%2 == 0 && y%2 == 0){
				dungeon[y][x] = WALL;

				/* 1つおきに立てた柱をランダム（上下左右いづれか）方向に倒す */
				if(x == 2){		/* 左端の柱は4方向（上右下左） */
					r = rand() % 4;
				}
				else{			/* 左端以外の柱は3方向（上右下） */
					r = rand() % 3;
				}

				/* 柱を設置（1つおきに立てた柱を倒す） */
				dungeon[y + dy[r]][x + dx[r]] = WALL;
			}
		}
	}
}

/*
	ダンジョンを表示する関数
*/
void displayDungeon(int dungeon[ROWS][COLUMNS]){
	int x, y;
	
	for(y=0; y<ROWS; y++){
		for(x=0; x<COLUMNS; x++){
			if(dungeon[y][x] == WALL){
				printf("@");
			}
			else{
				printf(" ");
			}
		}
		printf("\n");
	}
}

int main(void){
	/* ダンジョンデータ格納用 */
	int dungeon[ROWS][COLUMNS];	

	/* 乱数系列を初期化 */
	srand((unsigned)time(NULL));

	/* ダンジョンを生成する */
	initializeDungeon(dungeon);

	/* ダンジョンを表示する */
	displayDungeon(dungeon);

	return 0;
}

ソースコードの解説

ダンジョン外周の内側に柱を作るという考え方のため、ダンジョンの大きさ（行と列）は奇数にした方がきれいなダンジョンとなります。
サンプルでは、行をROWS、列をCOLUMNSとして定数宣言しています。

/* ダンジョンの大きさ（行ROWと列COLUMNは、ともに5以上の奇数が望ましい） */
#define ROWS 7
#define COLUMNS 9

ソースコード9～10行目の定数ROWSとCOLUMNSの数値をそれぞれ変えて生成できるダンジョンの大きさを変更できます。色々と変えてみてください。

プログラムのエントリーポイントとなるmain関数から解説します。

int main(void){
	/* ダンジョンデータ格納用 */
	int dungeon[ROWS][COLUMNS];	

	/* 乱数系列を初期化 */
	srand((unsigned)time(NULL));

	/* ダンジョンを生成する */
	initializeDungeon(dungeon);

	/* ダンジョンを表示する */
	displayDungeon(dungeon);

	return 0;
}

まずダンジョンデータ格納用として2次元配列dungeonを宣言しています。

int dungeon[ROWS][COLUMNS];

ROWSとCOLUMNSはそれぞれ7と9でdefine文で定義されているため、7行9列のダンジョンを表すことになります。

棒倒し法に乱数を利用するため、srand関数を利用して毎回異なる乱数を発生させるようにしています。

srand((unsigned)time(NULL));

srand関数を無くしてこのプログラムを実行してしまうと毎回同じダンジョンになってしまいます。
C言語では乱数を利用する際にsrand関数を最初に1回実行しておけば大丈夫です。

initializeDungeon関数でダンジョンデータを2次元配列dungeonに生成します。

initializeDungeon(dungeon);

例えば、7行9列のdungeonであれば、initializeDungeon関数実行後、ランダムで次のようなイメージの2次元配列データが生成されます。

最後にdungeon配列の0と1のデータを元に0を通路、1を壁としてダンジョン画面を表示します。

displayDungeon(dungeon);

0の場合は半角スペース、1の場合は@を画面に表示することでダンジョンを表現します。

@@@@@@@@@
@   @   @
@@@ @ @@@
@       @
@ @ @@@ @
@ @   @ @
@@@@@@@@@

大きな流れは以上です。

次は関数ごとに解説にうつります。
まずは棒倒し法を実践しているinitializeDungeon関数です。

/* ダンジョンを生成する関数 */
void initializeDungeon(int dungeon[ROWS][COLUMNS]) {
	int x, y, r;
	
	/* 柱を倒す方向（上右下左の順） */
	int dx[] = {0, 1, 0, -1};
	int dy[] = {-1, 0, 1, 0};

	/* ダンジョン配列を空にする */
	for(y=0; y<ROWS; y++){
		for(x=0; x<COLUMNS; x++){	
			dungeon[y][x] = SPACE;
		}
	}
	
	/* ダンジョン生成 */
	for(y=0; y<ROWS; y++){
		for(x=0; x<COLUMNS; x++){
			/* 周囲を壁にする */
			if(y == 0 || y == ROWS-1 || x == 0 || x == COLUMNS-1){
				dungeon[y][x] = WALL;
			}
			/* 壁の内側に1つおきに柱を立てる */
			else if(x >= 2 && x <= COLUMNS-1 && y >= 2 && y <= ROWS-1 && x%2 == 0 && y%2 == 0){
				dungeon[y][x] = WALL;

				/* 1つおきに立てた柱をランダム（上下左右いづれか）方向に倒す */
				if(x == 2){		/* 左端の柱は4方向（上右下左） */
					r = rand() % 4;
				}
				else{			/* 左端以外の柱は3方向（上右下） */
					r = rand() % 3;
				}

				/* 柱を設置（1つおきに立てた柱を倒す） */
				dungeon[y + dy[r]][x + dx[r]] = WALL;
			}
		}
	}
}

ローカル変数として3つ宣言しています。

int x, y, r;

xとyは、2次元配列dungeonをループ処理するためのものです。xは列（横方向のブロック数）、yは行（縦方向のブロック数）に対応します。
rはランダムに柱を倒す方向を決めるための乱数として利用します。

配列dxとdyは棒倒し法のポイントとなる変数ですが後述します。

/* 柱を倒す方向（上右下左の順） */
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};

ダンジョンデータはまず初めに全て0（壁がない状態）に初期化しておきます。
ROWS、COLUMNSそれぞれ7と9なので7行9列と読み換えると分かりやすいかと思います。
SPACEは0にdefine宣言されています。SPACEは通路と読み換えてください。

/* ダンジョン配列を空にする */
for(y=0; y<ROWS; y++){
	for(x=0; x<COLUMNS; x++){	
		dungeon[y][x] = SPACE;
	}
}

上記処理を実行したときのdungeon配列のイメージです。

次にダンジョンの周囲を壁にする処理です。
具体的にはdungeon配列の中身を以下のようにしたい訳です。

周囲の壁は上端、下端、左端、右端で設置しますが、2次元配列では上端はyが0、左端はxが0のときです。
if文の判定として下端と右端でそれぞれROWS-1、COLUMNS-1と1マイナスしているのは配列の添え字が0から開始するためです。（define文で1と宣言されているWALLは壁と読み換えてください）

/* ダンジョン生成 */
	for(y=0; y<ROWS; y++){
		for(x=0; x<COLUMNS; x++){
			/* 周囲を壁にする */
			if(y == 0 || y == ROWS-1 || x == 0 || x == COLUMNS-1){
				dungeon[y][x] = WALL;
			}
		　:
		つづく

次に「壁の内側に1つおきに柱を立てる」という処理ですが、配列の添え字に置き換えると「行と列がそれぞれ2以上から最後の行と列（ROWS-1またはCOLUMNS-1以内）の範囲にある2で割り切れるもの」と具体的に表せます。（ちょっと文が長いかな？）

イメージ

これをソースコードに直したif文が以下の処理です。

	:
/* 壁の内側に1つおきに柱を立てる */
else if(x >= 2 && x <= COLUMNS-1 && y >= 2 && y <= ROWS-1 && x%2 == 0 && y%2 == 0){
	dungeon[y][x] = WALL;
	:
	:

最後に説明を省いたdx, dyの配列の意味と考え方について解説します。
棒倒し法では壁の内側に1つおきに立てた柱を起点に上下左右のいずれか1方向に柱を倒します。

イメージ

4方向どの方向に倒すかは、ランダムで0～4の数値で対応させます。
左端の柱は4方向（0～3の数値）で、それ以外の柱は3方向（0～2の数値）を生成します。
ソースコード以下の部分です。

/* 1つおきに立てた柱をランダム（上下左右いづれか）方向に倒す */
if(x == 2){		/* 左端の柱は4方向（上右下左） */
	r = rand() % 4;
}
else{			/* 左端以外の柱は3方向（上右下） */
	r = rand() % 3;
}

変数rに生成した0～4の数値には意味を持たせます。

r	意味
0	上方向
1	右方向
2	下方向
3	左方向

配列dxは列側（左右）への増分を表し、dyは行側（上下）への増分を表します。
dx、dyの添え字が方向に対応しています。

dx(列方向増分）	dy（行方向増分）	意味
0	0	柱の上方向への列方向増分(dx)、列方向増分(dy)
1	1	柱の右方向への列方向増分(dx)、列方向増分(dy)
2	2	柱の下方向への列方向増分(dx)、列方向増分(dy)
3	3	柱の左方向への列方向増分(dx)、列方向増分(dy)

柱を上方向に倒す場合を考えてみます。
柱から見ると、上方向は行の添え字を-1したものになります。列はそのままです。

ここでdxとdyの登場です。

/* 柱を倒す方向（上右下左の順） */
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};

dx[0]=0 と定義されています。上方向（添え字0）の列の増分はなし、ということで列はそのまま。

dy[0]=-1 と定義されています。上方向（添え字0）の行の増分は-1、ということで行は1つ上の行を表します。

柱を立てる＝壁にする　ということですから、上方向を壁にするには行と列の各方向に増分であるdx, dyを足した場所を壁にするということになります。

以下が行と列の増分方向を壁にしている部分です。

/* 柱を設置（1つおきに立てた柱を倒す） */
dungeon[y + dy[r]][x + dx[r]] = WALL;

rはランダムで0～4または0～3の範囲となります。
右端の柱の時だけ r = rand() % 4; としているのは上右下左の4方向にするためです。

/* 1つおきに立てた柱をランダム（上下左右いづれか）方向に倒す */
if(x == 2){		/* 左端の柱は4方向（上右下左） */
	r = rand() % 4;
}
else{			/* 左端以外の柱は3方向（上右下） */
	r = rand() % 3;
}

initializeDungeon関数の解説は以上です。

最後に配列dungeonに生成された情報を元にダンジョンを表示するdisplayDungeon関数です。

/*
	ダンジョンを表示する関数
*/
void displayDungeon(int dungeon[ROWS][COLUMNS]){
	int x, y;
	
	for(y=0; y<ROWS; y++){
		for(x=0; x<COLUMNS; x++){
			if(dungeon[y][x] == WALL){
				printf("@");
			}
			else{
				printf(" ");
			}
		}
		printf("\n");
	}
}

2次元配列dungeonに保存されたデータ1と0の情報を元に、1なら壁として＠を0なら通路として　（半角スペース）を表示しているだけです。

printf関数でテキストとして表示するため、内側の列ループ（xのループ）の最後に改行をいれてダンジョンが1行で表示されてしまうのを防いでいます。

printf("\n");

ダンジョンデータを生成しているinitializeDungeon関数部分は他のプログラミング言語にもおきかえがしやすいかと思います。

以上、C言語：棒倒し法でダンジョン(迷路)を表現するでした。