見出し画像

Rogueのダンジョン生成アルゴリズムを再現してみる

k466

https://britzl.github.io/roguearchive/,http://www.rots.net/rogue/source/source.htmこれらのサイトにRogueのソースコードが乗っていたので現代風にしてみる


再現方法

かなりのごり押し方法です…
①すべてのファイルをWordにコピペする。
②Map生成アルゴリズムをWordの検索機能で探す。
③コードを再現して実行してみる。

苦労した事

今回初めて他人のコードを一から理解するということを行ったため、ここにすごく苦労した。また、Rogueが現代のC言語とは異なり、当時のより実行速度を速くするような裏技的な書き方や、現在では行わない書き方行っていたためそこを解読するのに苦労した。
以下は一例*ヘッダーの初めと該当部だけ載せてます

/*
 * Maze drawing routines.  Based on the algorithm presented in the
 * December 1981 Byte "How to Build a Maze" by David Matuszek.
 *
 * maze.c	1.4		(A.I. Design)	12/14/84
 */

draw_maze(rp)
struct room *rp;
{
    register int y, x;

基本関数には戻り値がなく、引数も二行目に型宣言がされる。また、registerという現代ではコンパイラが勝手にやっている部分が書かれている。
また、maze.cでの以下の部分が私には理解できなかった。(このヘッダー事態迷路を作成しているがなぜ作っているのかがわかっていない。通路などを作成したらわかる？)

 /*
 * Maze drawing routines.  Based on the algorithm presented in the
 * December 1981 Byte "How to Build a Maze" by David Matuszek.
 *
 * maze.c	1.4		(A.I. Design)	12/14/84
 */
 switch(which)
    {
    	when 0: which = 1; ydelt = -1;
    	when 1: which = 0; ydelt = 1;
    	when 2: which = 3; xdelt = -1;
    	when 3: which = 2; xdelt = 1;
    }

if (maze_at(ny-2, nx) > 0)
    	choice[cnt++] = 0;
    if (maze_at(ny+2, nx) > 0)
    	choice[cnt++] = 1;
    if (maze_at(ny, nx-2) > 0)
    	choice[cnt++] = 2;
    if (maze_at(ny, nx+2) > 0)
    	choice[cnt++] = 3;

whenはマクロで(#define when (break;case))とbreak;が入っているにもかかわらず、条件のwhichにそれぞれ代入しているのか。
なぜ迷路の作成時はindexを二つずつずらすのか(1にするとすべてのマスが通路になる)

完成したマップ

完成マップ

内容の説明

階層を3*3の部屋に分割を行い、四つ以下ランダムな数の部屋を消す。
消した部屋には最終的に通路を入れるが、レベルと乱数によってはdraw_mazeを実行する。この関数は再現に時間がかかったが結局何をやっているのかがわからなかった。(迷路のようなものを作成する。完成マップの背景のドット)
残っている部屋はdraw_roomを実行し、その部屋内に乱数を用いてランダムな大きさ、実際の部屋を生成する

感想

今回Rogueのマップ生成を復元してみたが、まだまだ分からないことが多かった。これは通路生成の部分も復元したら解決するものなのか…時間があるときに通路のほうもやってみたいと思う。また、ローグライクは好きでよくプレイするが本家Rogueはプレイをしたことがないのでやってみたら、なぜ迷路を作成しているのかなどわかったりするのかな？また、アルゴリズムは私が初めてランダムなマップを作製したときに使っていた方法と同じだったため何かうれしくなった。

作成したコード

なおC言語で作っても同じコードになるので直せる場所はC++のスマートポインタなどを使用している。

#include <iostream>
#include <memory>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>

#define MAX_HEIGHT	(51)
#define MAX_WIDTH	(51)
#define MAX_ROOM	(9)
#define NULL	0
#define TRUE 	1
#define	FALSE	0


enum CellInfo {
	NOTHING,
	PASS,
	FLOOR,
	VWALL,
	HWALL,
	ULWALL,
	URWALL,
	LLWALL,
	LRWALL,
	ISMAZE,
	ISGONE
};

struct coord {	//二次元座標
	int x;
	int y;
	coord(int x2,int y2):x(x2),y(y2){}
	coord():x(0),y(0){}
	bool operator == (coord temp){
		return (x == temp.x && y == temp.y);
	}
};

struct room {
	coord r_pos;	//左上の角
	coord r_max;	//部屋のサイズ
	int r_flag;
	room():r_pos(0,0),r_max(0,0),r_flag(0){}
};

char cell[MAX_HEIGHT][MAX_WIDTH];	//情報を入れておく
std::vector<coord>frontierArray;
coord fr;
std::shared_ptr<room> pRoom;
int maxx, maxy;

// 関数のプロトタイプ宣言
void do_room();
void draw_maze(std::shared_ptr<room> pRoom);
void draw_room(std::shared_ptr<room> pRoom);
void con_front();
void new_frontier(int y, int x);
void add_frnt(int y, int x);
void splat(int y, int x);
bool maze_at(int y, int x);
void remove_vec(int num);
bool offmap(int y, int x);
void rnd_pos(const std::shared_ptr<room> pRoom, coord* pPos);
void vert(std::shared_ptr<room> rp, int startx);
void horiz(std::shared_ptr<room> rp, int starty);

void do_room() {	//部屋を作成する関数
	int endline = MAX_HEIGHT + 1;
	int rm = 0;
	coord bsze = { MAX_HEIGHT / 3,MAX_WIDTH / 3 };
	coord top;

	std::vector<std::shared_ptr<room>>roomArray;
	for (int e = 0; e < MAX_ROOM-rand()%4; e++) {
		roomArray.push_back(std::make_shared<room>());
	}

	int left_out = rand() % 4;
	for (int e = 0; e < left_out; e++) {
		do {
			pRoom = roomArray[rm = rand() % (int)roomArray.size()];
		} while (pRoom->r_flag & ISMAZE);	//isMazeじゃなかったら抜ける
		pRoom->r_flag |= ISGONE;
		//ここでレベル設定が本当は入る
		if (rm > 2) {
			pRoom->r_flag |= ISMAZE;
		}
	}

	for (int e = 0; e < (int)roomArray.size(); e++) {
		pRoom = roomArray[e];
		top.x = (e % 3)*bsze.x + 1;
		top.y = e / 3 * bsze.y;
		if(pRoom->r_flag&ISGONE) {
			if (pRoom->r_flag&ISMAZE) {
				pRoom->r_pos.x = top.x;
				pRoom->r_pos.y = top.y;
				//std::cout << "迷路" << std::endl;
				draw_maze(pRoom);
			}
			else {	//ここに部屋は作らない 通路を作る
				do {
					pRoom->r_pos.x = top.x + rand() % (bsze.x - 2) + 1;
					pRoom->r_pos.y = top.y + rand() % (bsze.y - 2) + 1;
					pRoom->r_max.x = -MAX_HEIGHT;
					pRoom->r_max.y = -endline;
				} while (!(pRoom->r_pos.y > 0 && pRoom->r_pos.y < endline - 1));
			}
			continue;
		}
		do {
			pRoom->r_max.x = rand() % (bsze.x - 4) + 4;
			pRoom->r_max.y = rand() % (bsze.y - 4) + 4;
			pRoom->r_pos.x = top.x + rand() % (bsze.x - pRoom->r_max.x);
			pRoom->r_pos.y = top.y + rand() % (bsze.y - pRoom->r_max.y);
		} while (pRoom->r_pos.y == 0);
		//std::cout << "部屋" << std::endl;
		draw_room(pRoom);
	}
}

void draw_maze(std::shared_ptr<room> pRoom) {
	maxx = maxy = 0;
	//ランダムなフロンティアを生成
	fr = { rand() % MAX_WIDTH , rand() % MAX_HEIGHT };
	splat(fr.y, fr.x);
	new_frontier(fr.y, fr.x);

	while ((int)frontierArray.size() > 0) {	//フロンティアがある間
		con_front();
		new_frontier(fr.y, fr.x);
	}
	// 迷路にループを追加するコード
	coord* cp;
	int sh, psgcnt;
	coord spos;
	std::cout << std::endl;
	pRoom->r_max.x = maxx - pRoom->r_pos.x + 1;
	pRoom->r_max.y = maxy - pRoom->r_pos.y + 1;
	do {
		static coord ld[4] = {
			{-1, 0},
			{0, 1},
			{1, 0},
			{0, -1}
		};
		rnd_pos(pRoom, &spos);  // ランダムな位置を選択
		for (psgcnt = 0, cp = ld, sh = 1; cp < &ld[4]; sh <<= 1, cp++) {
			int y = cp->y + spos.y;
			int x = cp->x + spos.x;
			if (!offmap(y, x) && cell[y][x] == PASS) {
				psgcnt += sh;
			}
		}
	} while (cell[spos.y][spos.x] == PASS || psgcnt % 5);
	splat(spos.y, spos.x);  // ループの開始点を通路に変換
}

void draw_room(std::shared_ptr<room> rp) {
	vert(rp, rp->r_pos.x);
	vert(rp, rp->r_pos.x + rp->r_max.x - 1);
	horiz(rp, rp->r_pos.y);
	horiz(rp, rp->r_pos.y + rp->r_max.y - 1);
	cell[rp->r_pos.y][rp->r_pos.x] = ULWALL;
	cell[rp->r_pos.y][rp->r_pos.x + rp->r_max.x - 1] = URWALL;
	cell[rp->r_pos.y + rp->r_max.y - 1][rp->r_pos.x] = LLWALL;
	cell[rp->r_pos.y + rp->r_max.y - 1][rp->r_pos.x + rp->r_max.x - 1] = LRWALL;

	for (int y = rp->r_pos.y + 1; y < rp->r_pos.y + rp->r_max.y - 1; y++) {
		for (int x = rp->r_pos.x + 1; x < rp->r_pos.x + rp->r_max.x - 1; x++) {
			cell[y][x] = FLOOR;
		}
	}
}

void con_front() {	//フロンティアからランダムなセルを選択し、既存の迷路に接続する
	//std::vector<coord>choice;
	int xdelt = 0, ydelt = 0;
	int choice[4];
	int count = 0;
	int randNum = rand() % (int)frontierArray.size();
	fr = frontierArray[randNum];

	//フロンティアから削除する
	remove_vec(randNum);

	if (maze_at(fr.y - 2, fr.x) == true) {
		choice[count++] = 0;
	}
	if (maze_at(fr.y + 2, fr.x) == true) {
		choice[count++] = 1;
	}
	if (maze_at(fr.y, fr.x - 2) == true) {
		choice[count++] = 2;
	}
	if (maze_at(fr.y, fr.x + 2) == true) {
		choice[count++] = 3;
	}
	int which = choice[rand() % count];
	splat(fr.y, fr.x);
	switch (which)
	{
	case 0: which = 1; ydelt = -1; break;
	case 1: which = 0; ydelt = 1; break;
	case 2: which = 3; xdelt = -1; break;
	case 3: which = 2; xdelt = 1; break;
	}
	splat(fr.y + ydelt, fr.x + xdelt);
}

void new_frontier(int y, int x) {	//現在の迷路から新たなフロンティアを追加する
	add_frnt(y + 2, x);
	add_frnt(y - 2, x);
	add_frnt(y, x + 2);
	add_frnt(y, x - 2);
}

void add_frnt(int y, int x) {	//フロンティアに追加する
	//範囲チェック
	if (y >= 0 && y < MAX_HEIGHT&&x >= 0 && x < MAX_WIDTH&&cell[y][x] == NOTHING) {
		if (std::find(frontierArray.begin(), frontierArray.end(), coord(x, y)) == frontierArray.end()) {
			frontierArray.push_back(coord(x, y));
		}
		return;
	}
	return;
}

void splat(int y, int x) {
	if (cell[y][x] == NOTHING) {
		cell[y][x] = PASS;
	}
	if (x > maxx) {
		maxx = x;
	}
	if (y > ｈmaxy) {
		maxy = y;
	}
}

bool maze_at(int y, int x) {	//そこには通路か
	if (cell[y][x] == PASS) {
		return true;
	}
	return false;
}

void remove_vec(int num) {　//ベクトルを消す
	frontierArray.erase(frontierArray.begin() + num);
}

bool offmap(int y, int x) {　//マップ内か
	return x < 0 || x >= MAX_WIDTH || y < 0 || y >= MAX_HEIGHT;
}

void rnd_pos(const std::shared_ptr<room> pRoom, coord* pPos) {
	pPos->x = pRoom->r_pos.x + rand() % (pRoom->r_max.x - 2) + 1;
	pPos->y = pRoom->r_pos.y + rand() % (pRoom->r_max.y - 2) + 1;
}

void vert(std::shared_ptr<room>rp, int startx) {
	for (int y = rp->r_pos.y + 1; y <= rp->r_max.y + rp->r_pos.y - 1; y++) {
		cell[y][startx] = VWALL;
	}
}

void horiz(std::shared_ptr<room> rp, int starty) {
	for (int x = rp->r_pos.x + 1; x <= rp->r_max.x + rp->r_pos.x - 1; x++) {
		cell[starty][x] = HWALL;
	}
}

int main(void) {
	srand((unsigned)time(NULL));
	for (int y = 0; y < MAX_HEIGHT; y++) {
		for (int x = 0; x < MAX_WIDTH; x++) {
			cell[y][x] = NOTHING;
		}
	}
	do_room();
	for (int y = 0; y < MAX_HEIGHT; y++) {
		for (int x = 0; x < MAX_WIDTH; x++) {
			switch (cell[y][x]) {
			case 2:
				std::cout << ' ';
				break;

			case PASS:
				std::cout << '.';
				break;
			case 0:
				std::cout << ' ';
				break;
			default:
				std::cout << '*';
				break;
			}
			std::cout << ' ';
		}
		std::cout << std::endl;
	}
}

いいなと思ったら応援しよう！