地形生成(ボロノイ図法)🌏

#🌏母なる大地を創造する🌏

![m1.gif](https://qiita-image-store.s3.amazonaws.com/0/213065/9705715f-0d89-b585-b66a-fb6a5c778670.gif)
**今回は世界を創造する禁断の闇魔術について解説します。**

#🌏実装・環境🌏
**開発言語：C++14**

|コンパイラ|対応度|テスト生成|
|:---|:---|:---|
|MSVC|![cl](https://img.shields.io/badge/cl%2014.10-passing-brightgreen.svg)|None|
|GCC|![gcc](https://img.shields.io/badge/gcc%205.1.0-passing-brightgreen.svg)|[Wandbox](https://wandbox.org/permlink/ptNcR2SIufjeWZJp)|
|Clang|![clang](https://img.shields.io/badge/clang%203.5.0-passing-brightgreen.svg)|[Wandbox](https://wandbox.org/permlink/oWqCZambD9Kx0H0g)|

#🌏ボロノイ図法で作成🌏

![voro.gif](https://qiita-image-store.s3.amazonaws.com/0/213065/97f6ab5b-f56f-24d2-25af-3ade336fa251.gif)
**ボロノイ図**

**世界生成アルゴリズム**はいくつもの種類が存在します。
その中でも今回は**魅力的な形状を生成することに長けている"ボロノイ図法"**を使用します。

#🌏ボロノイ島生成クラス🌏

ボロノイ図の作成と島生成を行う**`SimpleVoronoiIsland`**クラスを作成します。

```cpp:クラス名
namespace dtl {
	template<typename Int>
	class SimpleVoronoiIsland;
}
```

**dtl(Dungeon Template Library)名前空間**に作成します。

```cpp:メンバ変数(private)
std::vector<std::pair<std::size_t, std::size_t>> point;
std::vector<Int> color;
```

メンバ変数には、原点の座標(x,y)を記録する**`point`**
色情報または各ボロノイの地形種類を記録する**`color`**を使用します。

```cpp:コンストラクタ(public)
template<typename T_>
constexpr SimpleVoronoiIsland(T_& t_, const std::size_t count_ = 100, const double rbool_ = 0.4, const Int land_ = 1, const Int sea_ = 0) {
	create(t_, count_, rbool_, land_, sea_);
}
```

コンストラクタから生成関数を呼び出します。

![mu2.png](https://qiita-image-store.s3.amazonaws.com/0/213065/ce6d8b29-d5d6-b97d-02ae-54d3851a0ca1.png)

ひとまず導入する準備が出来ました。
次は**陸地生成**の部分を作ります。


#🌏陸地の形状を作成🌏

```cpp:ボロノイ図の生成(public)
template<typename T_>
constexpr void create(T_& t_, const std::size_t count_ = 100, const double rbool_ = 0.4, const Int land_ = 1, const Int sea_ = 0) {
	for (std::size_t i{}; i < count_; ++i) {
		createPoint((t_.empty()) ? 0 : t_.front().size(), t_.size(), rbool_, land_, sea_);
	}
	createSites(t_, (t_.empty()) ? 0 : t_.front().size(), t_.size());
}
```

**`"create関数"`**は**陸地生成**する関数です。
当記事では、**`create関数`内の`count_変数`を"頂点数PN"**、
**`rbool_変数`を"陸地確率PB"**と呼びます。

![voro2.gif](https://qiita-image-store.s3.amazonaws.com/0/213065/dcc578a7-d93a-dbf1-0fb3-29b47ce23668.gif)
外側に近い部分を海とし、中央に近い部分を陸地とします。

```cpp:陸地か海か決定する
constexpr bool isMakeIsland(const std::size_t w_, const std::size_t h_, const std::size_t numerator_, const std::size_t denominator_) const {
	return (point.back().first > (w_ * numerator_ / denominator_) && point.back().first < (w_ * (denominator_ - numerator_) / denominator_)) && (point.back().second > (h_ * numerator_ / denominator_) && point.back().second < (h_ * (denominator_ - numerator_) / denominator_));
}
```

```cpp:原点を作成する
constexpr void createPoint(const std::size_t w_, const std::size_t h_, const double rbool_, const Int land_, const Int sea_) {
	point.emplace_back((std::size_t)rnd((std::int_fast32_t)w_), (std::size_t)rnd((std::int_fast32_t)h_));
	if (isMakeIsland(w_, h_, 2, 5) || (rnd.randBool(rbool_) && isMakeIsland(w_, h_, 1, 5)))
		color.emplace_back(land_);
	else color.emplace_back(sea_);
}
```

![voro3.gif](https://qiita-image-store.s3.amazonaws.com/0/213065/d6b8170e-a17f-a540-2cb6-404dfd1446f3.gif)
陸と海で2値化します。


```cpp:図形を線画
template<typename T_>
constexpr void createSites(T_& t_, const std::size_t w_, const std::size_t h_)const {
	std::int_fast32_t ds{}, dist{};
	for (std::size_t hh{}, ind{}; hh < h_; ++hh)
		for (std::size_t ww{}; ww < w_; ++ww) {
			ind = std::numeric_limits<std::size_t>::max();
			dist = std::numeric_limits<std::int_fast32_t>::max();
			for (std::size_t it{}; it < point.size(); ++it) {
				const std::pair<std::size_t, std::size_t>& p{ point[it] };
				if ((ds = distanceSqrd(p, (std::int_fast32_t)ww, (std::int_fast32_t)hh)) >= dist) continue;
				dist = ds;
				ind = it;
			}
			if (ind != std::numeric_limits<std::size_t>::max()) t_[hh][ww] = color[ind];
		}
}
```

これで基本的な陸地生成は完了です。
次はより複雑な海岸線を作ります。

![m2.gif](https://qiita-image-store.s3.amazonaws.com/0/213065/d0df7543-d94f-3b67-c97c-25763dc7c3ca.gif)
**頂点数PN=300, 陸地確率PB=0.2, ノイズ確率NB=0.0 の場合**
![m3.gif](https://qiita-image-store.s3.amazonaws.com/0/213065/f7229681-9e8b-413f-8529-f9bf1477f812.gif)
**頂点数PN=100, 陸地確率PB=0.5, ノイズ確率NB=0.0 の場合**


#🌏岸を複雑にする🌏

```cpp:ノイズを発生させる
namespace dtl {
	template<typename STL_>
	constexpr void noiseShoreBool(STL_& vec_, const double rbool_) {
		for (std::size_t i{ 1 }; i < vec_.size(); ++i)
			for (std::size_t j{ 1 }; j < vec_[i].size(); ++j) {
				if (!rnd.randBool(rbool_) || (vec_[i][j] == vec_[i][j - 1] && vec_[i][j] == vec_[i - 1][j])) continue;
				if (vec_[i][j]) vec_[i][j] = false;
				else vec_[i][j] = true;
			}
	}
}
```

```cpp:呼び出し
int main() {
	std::array<std::bitset<96>, 64> col{{}};
	dtl::SimpleVoronoiIsland<bool> diagram(col, 100, 0.5);
	dtl::noiseShoreBool(col, 0.5); //ノイズを生成
	dtl::outputBoolBitSet(col, "*", " ");
}
```

岸の部分を**`noiseShoreBool関数`**によって削り出します。
当記事では、**`noiseShoreBool関数`内の`rbool_変数`を"ノイズ確率NB"**と呼びます。

![m1.gif](https://qiita-image-store.s3.amazonaws.com/0/213065/9705715f-0d89-b585-b66a-fb6a5c778670.gif)
**頂点数PN=300, 陸地確率PB=0.2, ノイズ確率NB=0.5 の場合**
![m4.gif](https://qiita-image-store.s3.amazonaws.com/0/213065/292c5a1d-b143-413c-d066-6ac8ab4a1eaa.gif)
**頂点数PN=100, 陸地確率PB=0.5, ノイズ確率NB=0.5 の場合**







#🌏CUIでの出力🌏

```cpp:指定文字を出力
namespace dtl {
	template<typename STL_>
	constexpr void outputBoolBitSet(const STL_& vec_, const char* const true_str_, const char* const false_str_) {
		for (const auto& i : vec_) {
			for (std::size_t j = 0; j < i.size(); ++j) {
				if (i[j]) std::cout << true_str_;
				else std::cout << false_str_;
			}
			std::cout << std::endl;
		}
	}
}
```

```cpp:呼び出し
int main() {
	std::array<std::bitset<96>, 64> col{{}};
	dtl::SimpleVoronoiIsland<bool> diagram(col, 100, 0.5);
	dtl::noiseShoreBool(col, 0.5);
	dtl::outputBoolBitSet(col, "*", " ");
}
```

コンソールから出力します。

![cui.png](https://qiita-image-store.s3.amazonaws.com/0/213065/0c17037d-fd1e-2fb3-4017-5264c820ce56.png)
**頂点数PN=100, 陸地確率PB=0.5, ノイズ確率NB=0.5 の場合**

**[>> Wandboxで自動生成を試してみる(PC表示で見てね)](https://wandbox.org/permlink/ptNcR2SIufjeWZJp)**

# [🌏実装ライブラリ(ソースコード)🌏](https://github.com/Kasugaccho/DungeonTemplateLibrary)

今回解説した地形の自動生成は**["Dungeon Template Library"](https://github.com/Kasugaccho/DungeonTemplateLibrary)**に**["Simple Voronoi Island"](https://github.com/Kasugaccho/DungeonTemplateLibrary/blob/master/README.md)**として実装されています。
ぜひ、活用してみてください！

[![logo640.gif](https://qiita-image-store.s3.amazonaws.com/0/213065/b84a7834-2042-6704-fbbe-782a31f06091.gif)](https://github.com/Kasugaccho/DungeonTemplateLibrary)

#🌏ソースコードのライセンス🌏

These codes are licensed under CC0.
[![CC0](https://mirrors.creativecommons.org/presskit/buttons/88x31/svg/cc-zero.svg "CC0")](http://creativecommons.org/publicdomain/zero/1.0/deed.ja)

この記事のソースコードはCC0ライセンスとします。
ぜひ、自由に改変して遊んでみてください。

**最後までお読みいただきありがとうございました！**

###関連記事

[[DTL]ローグライク自動生成(ローグライク穴掘り法)💀](https://qiita.com/Gaccho/items/253cb6af577ec11e79cf)
ローグライクダンジョン生成の記事。

[[DTL]地形生成(チャンク&中点変位法)🌽](https://qiita.com/Gaccho/items/2840450460fa6e00a56c)
チャンク&中点変位法の世界生成の記事。