【C++】中点変位法の世界自動生成アルゴリズム

#世界を創造しませんか？

今回は初代ドラクエやFFなどに出てきそうなワールドマップを簡単に作っていきます。

#条件
マップの大きさは縦横ともに16の倍数 **`(例: 256 * 128)`**
マップの縦横はループする。(上下、左右に接続する)
今回は標高ごとに**"海(青色)"**、**"浅瀬(水色)"**、**"陸(緑色)"**、**"高山(灰色)"**に分けて出力します。

#ソースコード

```cpp:WorldMap.hpp
#pragma once
#include <vector>
#include <iostream>
#include <random>

namespace world {

	using vsize_t = std::vector<size_t>;
	using vvsize_t = std::vector<vsize_t>;
	
	//乱数
	class Rand32 {
	private:
		std::mt19937 mt;
	public:
		void srand(const unsigned int seed_) { mt.seed(seed_); }
		void init() {
			std::random_device rd;
			mt.seed(rd());
		}
		unsigned int operator()(const int max_) {
			std::uniform_int_distribution<> uid(0, max_ - 1);
			return uid(mt);
		}
	};
	static thread_local Rand32 rand32;
	//チャンク生成
	void worldMapMake(const size_t x_, const size_t y_, const size_t size_, const size_t t1_, const size_t t2_, const size_t t3_, const size_t t4_, size_t map_[17][17])
	{
		//再起の終了処理
		if (size_ == 0) return;
		//頂点の高さを決める
		const size_t mapPlus = ((t1_ + t2_ + t3_ + t4_) >> 2) + (const size_t)rand32((const int)size_);
		map_[x_][y_] = (mapPlus >= 255) ? 255 : mapPlus;
		//四角形の2点同士の中点の高さを決定
		const size_t s1 = ((t1_ + t2_) >> 1);
		const size_t s2 = ((t1_ + t3_) >> 1);
		const size_t s3 = ((t2_ + t4_) >> 1);
		const size_t s4 = ((t3_ + t4_) >> 1);
		//4つの地点の座標を決める
		map_[x_ + size_][y_] = s3;
		map_[x_ - size_][y_] = s2;
		map_[x_][y_ + size_] = s4;
		map_[x_][y_ - size_] = s1;
		//分割サイズを半分にする
		const size_t size = size_ >> 1;
		//4つに分割
		worldMapMake(x_ - size, y_ - size, size, t1_, s1, s2, map_[x_][y_], map_);
		worldMapMake(x_ + size, y_ - size, size, s1, t2_, map_[x_][y_], s3, map_);
		worldMapMake(x_ - size, y_ + size, size, s2, map_[x_][y_], t3_, s4, map_);
		worldMapMake(x_ + size, y_ + size, size, map_[x_][y_], s3, s4, t4_, map_);
	}

	//チャンク生成の呼び出し・実行
	void worldMapSimple(size_t map_[17][17])
	{
		worldMapMake(8, 8, 8, map_[0][0], map_[16][0], map_[0][16], map_[16][16], map_);
	}

	constexpr size_t aslib_world_make_seed1 = 0x3220;
	constexpr size_t aslib_world_make_seed2 = 0x292;

	//ワールドマップ生成
	void worldMake(vvsize_t& world_map, size_t seed_ = 0)
	{
		if (seed_ == 0) seed_ = size_t(rand32(65535));
		size_t map_[17][17]{};
		//横画面サイズ
		const size_t map_x = world_map.size();
		//縦画面サイズ
		const size_t map_y = world_map.front().size();

		const size_t chunk_x = (map_x >> 4);
		const size_t chunk_y = (map_y >> 4);

		for (size_t i = 0; i < chunk_x; ++i) {
			for (size_t j = 0; j < chunk_y; ++j) {
				//四角形の4点の高さを決定
				rand32.srand((unsigned int)(seed_ + i + (j * aslib_world_make_seed1) + ((i^j) * aslib_world_make_seed2)));
				map_[0][0] = size_t(rand32(255));
				rand32.srand((unsigned int)(seed_ + ((i + 1) % chunk_x) + (j * aslib_world_make_seed1) + ((((i + 1) % chunk_x) ^ j) * aslib_world_make_seed2)));
				map_[16][0] = size_t(rand32(255));
				rand32.srand((unsigned int)(seed_ + i + (((j + 1) % chunk_y) * aslib_world_make_seed1) + ((i ^ ((j + 1) % chunk_y)) * aslib_world_make_seed2)));
				map_[0][16] = size_t(rand32(255));
				rand32.srand((unsigned int)(seed_ + ((i + 1) % chunk_x) + (((j + 1) % chunk_y) * aslib_world_make_seed1) + ((((i + 1) % chunk_x) ^ ((j + 1) % chunk_y)) * aslib_world_make_seed2)));
				map_[16][16] = size_t(rand32(255));
				//チャンク生成
				worldMapSimple(map_);
				//生成したチャンクをワールドマップにコピペ
				for (size_t i2 = 0; i2 < 16; ++i2)
					for (size_t j2 = 0; j2 < 16; ++j2)
						world_map[(i << 4) + i2][(j << 4) + j2] = map_[i2][j2];
			}
		}
	}
}
```

#サンプルコード(文字で表示)

```cpp:Source.cpp
#include "WorldMap.hpp"

constexpr size_t size_x = 304;
constexpr size_t size_y = 160;

int main() {
	//乱数初期化
	world::rand32.init();
	//世界生成
	world::vvsize_t wmap(size_y, world::vsize_t(size_x, 255));
	world::worldMake(wmap);

	//表示
	for (size_t i = 0; i < size_y; ++i) {
		for (size_t j = 0; j < size_x; ++j) {

			if (wmap[i][j] <= 30) std::cout << "▲";
			else if (wmap[i][j] <= 110) std::cout << "■";
			else if (wmap[i][j] <= 120) std::cout << "□";
			else std::cout << "△";
		}
		std::cout <<  std::endl;
	}
	return 0;
}
```

#出力結果

![スクリーンショット 2018-09-06 22.45.21.png](https://qiita-image-store.s3.amazonaws.com/0/213065/335435ba-3c85-ca1c-f945-d2f904d5b806.png)

しっかりと生成できていますね！

#サンプルコード(色付きで表示)

```cpp:Source.cpp
#include "WorldMap.hpp"

constexpr size_t size_x = 304;
constexpr size_t size_y = 160;

int main() {
	//乱数初期化
	world::rand32.init();
	//世界生成
	world::vvsize_t wmap(size_y, world::vsize_t(size_x, 255));
	world::worldMake(wmap);

	//表示
	for (size_t i = 0; i < size_y; ++i) {
		for (size_t j = 0; j < size_x; ++j) {

			if (wmap[i][j] <= 30) std::cout << "\x1b[47m" << "　";
			else if (wmap[i][j] <= 110) std::cout << "\x1b[42m" << "　";
			else if (wmap[i][j] <= 120) std::cout << "\x1b[46m" << "　";
			else std::cout << "\x1b[44m" << "　";
		}
		std::cout << "\x1b[0m" << "　" << std::endl;
	}
	return 0;
}
```

#出力結果
![スクリーンショット 2018-09-06 21.14.36.png](https://qiita-image-store.s3.amazonaws.com/0/213065/722c1fbe-635b-08c3-be03-6d948255ec8d.png)


ちゃんと画像はループしています。
![スクリーンショット 2018-09-06 21.14.36_2.png](https://qiita-image-store.s3.amazonaws.com/0/213065/42bf0c55-c732-d13d-bf85-34e71b0d955b.png)

#ゲーム制作に使ってみる

![スクリーンショット 2018-08-13 06.34.31.png](https://qiita-image-store.s3.amazonaws.com/0/213065/26c889da-de27-2957-7484-0122dc1e9b30.png)
![スクリーンショット 2018-08-13 14.32.00.png](https://qiita-image-store.s3.amazonaws.com/0/213065/485a70c1-2208-d46b-c81b-48e5069100b1.png)


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

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)