見出し画像

【ゲーム開発】不思議なダンジョンを生成する

UNLUCKY


完成図

不思議なダンジョン生成について、具体的に書いていく。（覚え書き）

方法

マップをエリアに分割し、エリア内に部屋を作り、部屋同士を通路で繋ぐ。
参考サイト↓

今回のサンプルソース

手順

  1. エリアに分割する

  2. エリア内に部屋を作る

  3. 部屋と部屋を通路で繋ぐ

前準備

今回は、C++で作成した。UnityやWebアプリなどで利用する場合は、各言語に直して利用できるはず。

Main.cpp

#include "MapGenerator.h"

int main()
{
	MapGenerator generator = MapGenerator();
	generator.Generate(64, 64, 10);
	generator.ShowMap();
	return 0;
}

今回はダンジョンを生成して、どんな感じになるかを見るだけ。

Vector.h / .cpp

#pragma once
class Vector
{
public:
	static const Vector zero;

public:
	int x;
	int y;

public:
	// コンストラクタ
	Vector();
	Vector(int x, int y);

	// コピーコンストラクタ
	Vector(const Vector& other);

	bool operator ==(const Vector& other)
	{
		return (this->x == other.x && this->y == other.y);
	}

	bool operator !=(const Vector& other)
	{
		return (this->x != other.x || this->y != other.y);
	}

};
#include "Vector.h"

const Vector Vector::zero = Vector();

Vector::Vector()
{
	this->x = 0;
	this->y = 0;
}

Vector::Vector(int x, int y)
{
	this->x = x;
	this->y = y;
}

Vector::Vector(const Vector& other)
{
	this->x = other.x;
	this->y = other.y;
}

Unityで言うところのVector2やVector3。ベクトル。

Rect.h / .cpp

#pragma once
#include "Vector.h"

class Rect
{
public:
	Vector start;
	Vector end;

public:
	Rect();
	Rect(Vector start, Vector end);
	Rect(int lx, int ly, int rx, int ry);

	int GetWidth();
	int GetHeight();

	bool operator ==(const Rect& other)
	{
		return (this->start == other.start && this->end == other.end);
	}

	bool operator !=(const Rect& other)
	{
		return (this->start != other.start || this->end != other.end);
	}
};
#include "Rect.h"

Rect::Rect()
{
	this->start = Vector::zero;
	this->end = Vector::zero;
}

Rect::Rect(Vector start, Vector end)
{
	this->start = start;
	this->end = end;
}

Rect::Rect(int lx, int ly, int rx, int ry)
{
	this->start = Vector(lx, ly);
	this->end = Vector(rx, ry);
}

int Rect::GetWidth()
{
	return this->end.x - this->start.x;
}

int Rect::GetHeight()
{
	return this->end.y - this->start.y;
}

エリア、部屋、通路に利用する。２点の情報を管理する。

Random.h / .cpp

#pragma once

class Random
{
public:
	Random();

	int Range(int min, int max);
	bool Jadge(int rate);
};
#include "Random.h"
#include <random>

Random::Random()
{
}

int Random::Range(int min, int max)
{
	int ans = -1;
	std::random_device rd;
	std::mt19937 mt(rd());
	std::uniform_int_distribution<> r(min, max);
	ans = r(mt);
	return ans;
}

bool Random::Jadge(int rate)
{
	return (Range(0, 100) <= rate);
}

min～maxまでのランダムな値を生成するRange。
30%で死ぬ、など確率を使う際に利用するJadge。

RougeUtils.h / .cpp

#pragma once
#include <string>
#include <vector>

class RougeUtils
{
public:
	static std::string CreateString(std::string fmt_str, ...);

	template <typename T>
	static bool Contains(std::vector<T> vec, T value);
};

template<typename T>
inline bool RougeUtils::Contains(std::vector<T> vec, T value)
{
	for (T& element : vec)
	{
		if (element == value)
		{
			return true;
		}
	}
	return false;
}
#include "RougeUtils.h"
#include <memory>

#include <stdarg.h>

#pragma warning(disable:4996)


std::string RougeUtils::CreateString(std::string fmt_str, ...)
{
	int final_n, n = ((int)fmt_str.size()) * 2;
	std::unique_ptr<char[]> formatted;
	va_list ap;
	while (true)
	{
		formatted.reset(new char[n]);
		strcpy(&formatted[0], fmt_str.c_str());
		va_start(ap, fmt_str);
		final_n = vsnprintf(&formatted[0], n, fmt_str.c_str(), ap);
		va_end(ap);
		if (final_n < 0 || final_n >= n)
		{
			n += abs(final_n - n + 1);
		}
		else
		{
			break;
		}
	}
	std::string result = std::string(formatted.get());
	return result;
}

デバッグログを流すためのCreateString。（ゲーム中にログを流す場合にも使えるかも）JavaやC#では必要ない。（C++では文字列操作が面倒）
vector（配列、リスト）内にvalue（値）が存在するかどうかチェックするためのContains。JavaやC#に存在するコンテナ管理用クラス（Listなど）には標準装備されていた記憶。

マップ生成

準備 MapGenerator class

#pragma once
#include <vector>
#include <string>

#include "Vector.h"
#include "Rect.h"

class MapGenerator
{
public:
	enum MapState
	{
		None = -1,
		Wall = 0,
		Room = 1,
		Pass = 2
	};

private:
	// 最小エリアサイズ
	const int MINIMUM_AREA_SIZE = 10;

	// マップサイズ
	int mapWidth;
	int mapHeight;

	// 最大部屋数
	int maxRoomNum;

	// マップデータ本体
	std::vector<std::vector<MapState>> map;

	// エリア
	std::vector<Rect> areaList;
	// 部屋
	std::vector<Rect> roomList;
	// 通路
	std::vector<Rect> passList;
	// 部屋が存在するエリアを記憶しておく
	std::vector<int> areaWhereRoomExists;
};

まずは、必要な情報を持たせる。

次に、外部で利用するメソッドを持たせる。

class MapGenerator
{
// --- 省略 ---
public:
	// コンストラクタ
	MapGenerator();

	// デストラクタ
	~MapGenerator();

	// マップ生成エントリ
	void Generate(int width, int height, int maxRoomNum);

	std::vector<std::vector<MapState>> GetMapData();

	void ShowMap();
};

コンストラクタ、デストラクタでは特に何もしないため無くてもOK。

コンストラクタ：オブジェクト生成時に呼ばれる。
デストラクタ：オブジェクトの命が尽きるときに呼ばれる。

Generateの引数に、マップサイズと最大部屋数を渡す。（部屋数をランダムにするため）

本来はGetMapDataをして、床を設置したりする。
今回はあくまでマップ生成をするためだけなので、ShowMapで中身を確認する。

void MapGenerator::Generate(int width, int height, int maxRoomNum)
{
	_generate(width, height, maxRoomNum);
}

std::vector<std::vector<MapGenerator::MapState>> MapGenerator::GetMapData()
{
	return this->map;
}

void MapGenerator::ShowMap()
{
	for (int y = 0; y < this->map.size(); y++)
	{
		for (int x = 0; x < this->map[y].size(); x++)
		{
			switch (this->map[y][x])
			{
			case MapState::None:
				std::cout << "■";
				break;
			case MapState::Wall:
				std::cout << "?";
				break;
			case MapState::Room:
				std::cout << "　";
				break;
			case MapState::Pass:
				std::cout << "　";
				break;
			}
		}
		std::cout << "\n";
	}
}


次に、手順通りのメソッドを追加する。

class MapGenerator
{
// --- 省略 ---
private:
	// マップ生成
	void _generate(int width, int height, int roomNum);

	// マップ初期化
	void _mapInitialize();

	// マップ削除
	void _deleteMap();

	// マップを特定の値で埋める
	void _fill(MapState fill);

	// エリア作成
	void _createArea();

	// エリア分割
	bool _splitArea(bool isVertical);

	// 部屋作成
	void _createRoom();

	// 通路作成
	void _createPass();

	// 作成した情報をマップに反映する
	void _reflectListIntoMap();
};

_generateを、Generate内で呼んでいるだけ。

_generate内では、マップ初期化を行い、その後
1.エリア作成
2.エリア分割
3.部屋作成
4.通路作成
5.ここまでで作成した部屋、通路をマップに反映
と進んでいく。

_generate（Generate：エントリ部分から呼ばれるメソッド）

void MapGenerator::_generate(int width, int height, int roomNum)
{
	// 初期化
	this->mapWidth = width;
	this->mapHeight = height;
	this->maxRoomNum = roomNum;
	_mapInitialize();

	// マップに必要な情報作成
	_createArea();
	_createRoom();
	_createPass();

	// 各情報の反映
	_reflectListIntoMap();

	ShowList();
}

引数で受け取った値を設定し、マップを初期化する。

void MapGenerator::_mapInitialize()
{
	_deleteMap();

	for (int y = 0; y < this->mapHeight; y++)
	{
		this->map.push_back(std::vector<MapGenerator::MapState>());
		for (int x = 0; x < this->mapWidth; x++)
		{
			// とりあえずNoneで埋める
			this->map[y].push_back(MapState::None);
		}
	}
}

void MapGenerator::_deleteMap()
{
	for (int i = 0; i < map.size(); i++)
	{
		map[i].clear();
	}
	map.clear();

	this->areaList.clear();
	this->roomList.clear();
	this->passList.clear();

	this->areaWhereRoomExists.clear();
}

マップ初期化メソッド。

そして、エリア、部屋、通路、と順に生成していく。

_createArea（エリアを作成する大枠）

エリアを作成する。大きなエリアを、小さいエリアに分割していく。

void MapGenerator::_createArea()
{
	// 最初にマップ全体をエリアとして設定
	this->areaList.push_back(Rect(0, 0, this->mapWidth - 1, this->mapHeight - 1));
	bool isDevided = true;
	while (isDevided)
	{
		// 縦→横　の順に分割していく
		isDevided = _splitArea(false);
		isDevided = _splitArea(true) || isDevided;

		// 最大部屋数に達したら終了
		if (this->areaList.size() >= this->maxRoomNum)
		{
			break;
		}
	}
}

_splitArea（エリアを分割する）

bool MapGenerator::_splitArea(bool isVertical)
{
	bool isDevided = isVertical;
	Random rand = Random();
	std::vector<Rect> new_area_list = std::vector<Rect>();
	for (Rect& area : this->areaList)
	{
		// これ以上分割できない場合スキップする
		if (isVertical && area.GetHeight() < MINIMUM_AREA_SIZE * 2 + 1)
		{
			continue;
		}
		else if (!isVertical && area.GetWidth() < MINIMUM_AREA_SIZE * 2 + 1)
		{
			continue;
		}

		std::this_thread::sleep_for(std::chrono::milliseconds(1));

		// 40%の確率で分割しない
		// 区画が1つしかない場合は分割する
		if (areaList.size() > 1 && rand.Jadge(40))
		{
			continue;
		}

		// 分割方向
		int length = isVertical ? area.GetHeight() : area.GetWidth();
		int margin = length - MINIMUM_AREA_SIZE * 2;
		int base_index = isVertical ? area.start.y : area.start.x;
		int devide_index = base_index + MINIMUM_AREA_SIZE + rand.Range(1, margin) - 1;

		Rect new_area = Rect();

		// 分割した新しいエリアを作成し、分割元エリアのサイズを更新する
		if (isVertical)
		{
			new_area = Rect(area.start.x, devide_index + 1, area.end.x, area.end.y);
			area.end.y = devide_index - 1;
		}
		else
		{
			new_area = Rect(devide_index + 1, area.start.y, area.end.x, area.end.y);
			area.end.x = devide_index - 1;
		}
		// new_area_listに保存しておく
		new_area_list.push_back(new_area);
		isDevided = true;
	}

	// 分割したエリアを登録
	for (int i = 0; i < new_area_list.size(); i++)
	{
		this->areaList.push_back(new_area_list[i]);
	}

	return isDevided;
}

エリアの分割を行う。

_createRoom（部屋を作成する）

void MapGenerator::_createRoom()
{
	DebugLog("create room.");
	std::mt19937 mt;
	std::shuffle(this->areaList.begin(), this->areaList.end(), mt);

	Random rand = Random();

	for (int i = 0; i < this->areaList.size(); i++)
	{
		std::this_thread::sleep_for(std::chrono::milliseconds(1));
		if (this->roomList.size() > this->maxRoomNum / 2 && rand.Jadge(30))
		{
			continue;
		}
		Rect& area = areaList[i];

		int marginX = area.GetWidth() - MINIMUM_AREA_SIZE + 2;
		int marginY = area.GetHeight() - MINIMUM_AREA_SIZE + 2;

		int randomX = rand.Range(1, marginX);
		int randomY = rand.Range(1, marginY);

		int startX = area.start.x + randomX;
		int endX = area.end.x - rand.Range(0, (marginX - randomX)) - 1;
		int startY = area.start.y + randomY;
		int endY = area.end.y - rand.Range(0, (marginY - randomY)) - 1;

		Rect room = Rect(startX, startY, endX, endY);
		this->roomList.push_back(room);
		this->areaWhereRoomExists.push_back(i);
	}
}

作成したエリアに、確率で部屋を作成する。
偏らないように、エリアリストはシャッフルしておく。

_createPass（通路を作成する大枠）

ここでは、
1.部屋からエリア枠まで通路を伸ばす
2.伸ばした通路同士を接続する
２つの手順を行う。

class MapGenerator
{
// --- 省略 ---
private:
    // 部屋から通路を伸ばす
	void _extendPassFromRoom();
	// 伸ばした通路を繋ぐ
	void _connectPass();
	void __connectPass(int i, int k);
};

_extendPassFromRoom（部屋から通路を伸ばす）

void MapGenerator::_extendPassFromRoom()
{
	Random rand = Random();
	int count = 0;
	for (int i = 0; i < this->areaList.size(); i++)
	{
		// 部屋の存在しないエリアは無視する
		if (!RougeUtils::Contains(this->areaWhereRoomExists, i))
		{
			continue;
		}

		const Rect& room = this->roomList[count];
		// 部屋の中でのランダムな点を取る
		int randomX = rand.Range(room.start.x, room.end.x);
		int randomY = rand.Range(room.start.y, room.end.y);

		int startX = randomX;
		int startY = randomY;
		int endX = randomX;
		int endY = randomY;

		// 部屋の右側
		if (this->areaList[i].end.x < this->mapWidth - 1)
		{
			int target_x = areaList[i].end.x + 1;
			while (endX != target_x)
			{
				endX++;
			}
			Rect pass = Rect(startX, startY, endX, endY);
			this->passList.push_back(pass);

			startX = randomX;
			startY = randomY;
			endX = randomX;
			endY = randomY;
		}
		// 部屋の左側
		if (areaList[i].start.x > 0)
		{
			int target_x = areaList[i].start.x - 1;
			while (startX != target_x)
			{
				startX--;
			}
			Rect pass = Rect(startX, startY, endX, endY);
			this->passList.push_back(pass);

			startX = randomX;
			startY = randomY;
			endX = randomX;
			endY = randomY;
		}
		// 部屋の下側
		if (areaList[i].end.y < this->mapHeight - 1)
		{
			int target_y = areaList[i].end.y + 1;
			while (endY != target_y)
			{
				endY++;
			}
			Rect pass = Rect(startX, startY, endX, endY);
			this->passList.push_back(pass);

			startX = randomX;
			startY = randomY;
			endX = randomX;
			endY = randomY;
		}
		// 部屋の上側
		if (areaList[i].start.y > 0)
		{
			int target_y = areaList[i].start.y - 1;
			while (startY != target_y)
			{
				startY--;
			}
			Rect pass = Rect(startX, startY, endX, endY);
			this->passList.push_back(pass);
		}

		count++;
	}
}

部屋の無いエリアは無視する。
そして、部屋内にランダムな点を１つ取る。その点を、各方向に伸ばす通路の始点に設定。

次に、上下左右それぞれの方向へ通路を伸ばしていく。

_connectPass（伸ばした通路同士をつなぐ）

void MapGenerator::_connectPass()
{
	int nowPassSize = this->passList.size();
	for (int i = 0; i < nowPassSize; i++)
	{
		for (int k = 0; k < nowPassSize; k++)
		{
			// 自分自身は無視
			if (i == k)
			{
				continue;
			}
			// 同じroomから伸びている通路は無視
			if (passList[i].start == passList[k].start ||
				passList[i].start == passList[k].end ||
				passList[i].end == passList[k].start ||
				passList[i].end == passList[k].end)
			{
				continue;
			}
			__connectPass(i, k);
		}
	}
}
void MapGenerator::__connectPass(int i, int k)
{
	const Rect& v1 = passList[i];
	const Rect& v2 = passList[k];
	Rect pass;
	{
		if (v1.start.x == v2.start.x)
		{
			if (v1.start.y < v2.start.y)
			{
				pass = Rect(v1.start, v2.start);
				this->passList.push_back(pass);
				return;
			}
			if (v1.start.y > v2.start.y)
			{
				pass = Rect(v2.start, v1.start);
				this->passList.push_back(pass);
				return;
			}
		}
		if (v1.start.x == v2.end.x)
		{
			if (v1.start.y < v2.end.y)
			{
				pass = Rect(v1.start, v2.end);
				this->passList.push_back(pass);
				return;
			}
			if (v1.start.y > v2.end.y)
			{
				pass = Rect(v2.end, v1.start);
				this->passList.push_back(pass);
				return;
			}
		}
		if (v1.end.x == v2.end.x)
		{
			if (v1.end.y < v2.end.y)
			{
				pass = Rect(v1.end, v2.end);
				this->passList.push_back(pass);
				return;
			}
			if (v1.end.y > v2.end.y)
			{
				pass = Rect(v2.end, v1.end);
				this->passList.push_back(pass);
				return;
			}
		}
	}
	{
		if (v1.start.y == v2.start.y)
		{
			if (v1.start.x < v2.start.x)
			{
				pass = Rect(v1.start, v2.start);
				this->passList.push_back(pass);
				return;
			}
			if (v1.start.x > v2.start.x)
			{
				pass = Rect(v2.start, v1.start);
				this->passList.push_back(pass);
				return;
			}
		}
		if (v1.start.y == v2.end.y)
		{
			if (v1.start.x < v2.end.x)
			{
				pass = Rect(v1.start, v2.end);
				this->passList.push_back(pass);
				return;
			}
			if (v1.start.x > v2.end.x)
			{
				pass = Rect(v2.end, v1.start);
				this->passList.push_back(pass);
				return;
			}
		}
		if (v1.end.y == v2.end.y)
		{
			if (v1.end.x < v2.end.x)
			{
				pass = Rect(v1.end, v2.end);
				this->passList.push_back(pass);
				return;
			}
			if (v1.end.x > v2.end.x)
			{
				pass = Rect(v2.end, v1.end);
				this->passList.push_back(pass);
				return;
			}
		}
	}
}

ｘ軸が重なっていてｙ軸が異なる通路同士、ｙ軸が重なっていてｘ軸が異なる通路同士をそれぞれ接続する。

_reflectListIntoMap（作成したデータを反映する）

void MapGenerator::_reflectListIntoMap()
{
	for (const Rect& pass : this->passList)
	{
		for (int y = pass.start.y; y <= pass.end.y; y++)
		{
			for (int x = pass.start.x; x <= pass.end.x; x++)
			{
				this->map[y][x] = MapState::Pass;
			}
		}
	}
	for (const Rect& room : this->roomList)
	{
		for (int y = room.start.y; y <= room.end.y; y++)
		{
			for (int x = room.start.x; x <= room.end.x; x++)
			{
				this->map[y][x] = MapState::Room;
			}
		}
	}
}

作成した部屋、通路を反映する。

完成


実行すると、このようなマップデータが生成できる。
不要な通路も多く生成されてしまうが、ランダムに通路を作成するようにすれば解決できるかもしれない。


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