【C++】穴掘り法の迷路自動生成アルゴリズム

#はじめに
今回は穴掘り法の迷路自動生成アルゴリズムを作ります。
C++11以降で動きます。

#ソースコード

Maze.hpp

#pragma once
#include <ctime>
#include <iostream>
#include <vector>
#include <memory>

namespace maze {

	using vsize_t = std::vector<size_t>;
	using vvsize_t = std::vector<vsize_t>;

	//生成チェック
	const bool mapCheck(const vvsize_t& map_) {
		if (map_.size() <= 2 || map_.data()->size() <= 2) return false;
		if ((map_.size() & 1) == 0 || (map_.data()->size() & 1) == 0) return false;
		return true;
	}
	//穴掘り
	void mazeDig(vvsize_t& map_, size_t x_, size_t y_, const size_t id_wall_, const size_t id_empty_)
	{
		if (!mapCheck(map_)) return;
		int32_t dx, dy;
		size_t random = size_t(rand()), counter = 0;
		while (counter < 4) {
			switch ((random + counter) & 3)
			{
			case 0:dx = 0; dy = -2; break;
			case 1:dx = -2; dy = 0; break;
			case 2:dx = 0; dy = 2; break;
			case 3:dx = 2; dy = 0; break;
			default:dx = 0; dy = 0; break;
			}
			if (x_ + dx <= 0 || y_ + dy <= 0 || x_ + dx >= map_.size() - 1 || y_ + dy >= map_.data()->size() - 1 || map_[x_ + dx][y_ + dy] == id_empty_) {
				++counter;
			}
			else if (map_[x_ + dx][y_ + dy] == id_wall_) {
				map_[x_ + (dx >> 1)][y_ + (dy >> 1)] = id_empty_;
				map_[x_ + dx][y_ + dy] = id_empty_;
				x_ += dx;
				y_ += dy;
				counter = 0;
				random = size_t(rand());
			}
		}
		return;
	}
	//経路探索
	void mazeRootLoop(vvsize_t& map_, const size_t x_, const size_t y_, const size_t id_empty_, const size_t id_root_)
	{
		//経路探索状況
		static bool b = true;

		map_[x_][y_] = id_root_;
		if (x_ == map_.size() - 2 && y_ == map_.data()->size() - 2) b = false;
		//上
		if (b && map_[x_][y_ - 1] == id_empty_) mazeRootLoop(map_, x_, y_ - 1, id_empty_, id_root_);
		//下
		if (b && map_[x_][y_ + 1] == id_empty_) mazeRootLoop(map_, x_, y_ + 1, id_empty_, id_root_);
		//左
		if (b && map_[x_ - 1][y_] == id_empty_) mazeRootLoop(map_, x_ - 1, y_, id_empty_, id_root_);
		//右
		if (b && map_[x_ + 1][y_] == id_empty_) mazeRootLoop(map_, x_ + 1, y_, id_empty_, id_root_);

		if (b) map_[x_][y_] = id_empty_;
		return;
	}
	void mazeRoot(vvsize_t& map_, const size_t id_empty_, const size_t id_root_)
	{
		if (!mapCheck(map_)) return;
		mazeRootLoop(map_, 1, 1, id_empty_, id_root_);
	}
	//出力
	void mazeOutput(const vvsize_t& map_, const size_t id_wall_, const size_t id_empty_)
	{
		if (!mapCheck(map_)) return;
		const size_t i_max = map_.size();
		const size_t j_max = map_.data()->size();
		for (size_t i = 0; i < i_max; ++i) {
			for (size_t j = 0; j < j_max; ++j) {
				if (map_[i][j] == id_empty_) std::cout << "　";
				else if (map_[i][j] == id_wall_) std::cout << "■";
				else std::cout << "・";
			}
			std::cout << std::endl;
		}
	}
	//迷路生成
	const size_t mazeMakeLoop(vvsize_t& map_, const size_t id_wall_, const size_t id_empty_, std::unique_ptr<size_t[]>& select_x, std::unique_ptr<size_t[]>& select_y)
	{
		size_t ii = 0;
		const size_t i_max = map_.size() - 1;
		const size_t j_max = map_.data()->size() - 1;

		for (size_t i = 1; i < i_max; i += 2)
			for (size_t j = 1; j < j_max; j += 2) {
				if (map_[i][j] != id_empty_) continue;
				if ((i >= 2 && map_[i - 2][j] == id_wall_) || (j >= 2 && map_[i][j - 2] == id_wall_)) {
					select_x[ii] = i;
					select_y[ii] = j;
					++ii;
				}
				else if ((j == map_.data()->size() - 2) && (i == map_.size() - 2)) break;
				else if ((i + 2 < map_.size() && map_[i + 2][j] == id_wall_) || (j + 2 < map_.data()->size() && map_[i][j + 2] == id_wall_)) {
					select_x[ii] = i;
					select_y[ii] = j;
					++ii;
				}
			}
		return ii;
	}
	void mazeMake(vvsize_t& map_, const size_t id_wall_, const size_t id_empty_)
	{
		if (map_.size() <= 2 || map_.data()->size() <= 2) return;
		if ((map_.size() & 1) == 0 || (map_.data()->size() & 1) == 0) return;

		map_[1][1] = id_empty_;

		size_t a, ii;
		std::unique_ptr<size_t[]> select_x(new size_t[map_.size()*map_.data()->size()]);
		std::unique_ptr<size_t[]> select_y(new size_t[map_.size()*map_.data()->size()]);

		//座標を選ぶ
		while (true)
		{
			ii = mazeMakeLoop(map_, id_wall_, id_empty_, select_x, select_y);
			if (ii == 0) break;
			srand((unsigned int)time(nullptr));
			a = size_t(rand()) % ii;
			mazeDig(map_, select_x[a], select_y[a], id_wall_, id_empty_);
		}
		return;
	}
	//迷路生成
	int createMaze(const size_t x_, const size_t y_, const size_t id_empty_, const size_t id_wall_, const size_t id_root_) {
		if (x_ <= 2 || y_ <= 2) return 1;
		if ((x_ & 1) == 0 || (y_ & 1) == 0) return 2;

		//迷路マップ(全ての位置を壁にする)
		vvsize_t map_{ vvsize_t(y_, vsize_t(x_, id_wall_)) };
		//迷路を生成
		mazeMake(map_, id_wall_, id_empty_);
		//経路探索
		mazeRoot(map_, id_empty_, id_root_);
		//出力
		mazeOutput(map_, id_wall_, id_empty_);
		return 0;
	}
	//迷路マップを返す
	const vvsize_t createMazeMap(const size_t x_, const size_t y_, const size_t id_empty_, const size_t id_wall_, const size_t id_root_) {
		//迷路マップ(全ての位置を壁にする)
		static thread_local vvsize_t map_;
		map_.clear();
		map_ = vvsize_t{ vvsize_t(y_, vsize_t(x_, id_wall_)) };
		//迷路を生成
		mazeMake(map_, id_wall_, id_empty_);
		//経路探索
		mazeRoot(map_, id_empty_, id_root_);
		return map_;
	}
}

#サンプルコード

Source.cpp

#include "Maze.hpp"

//迷路の横幅
constexpr size_t size_x = 41;
//迷路の縦幅
constexpr size_t size_y = 21;

//迷路に設置する物体のID
enum :size_t {
	id_empty_,//通路
	id_wall_,//壁
	id_root_,//ゴールまでの道
};

int main()
{
	//迷路生成
	return maze::createMaze(size_x, size_y, id_empty_, id_wall_, id_root_);
}

#出力結果

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

These codes are licensed under CC0.

##他言語の穴掘り法
Java>> Javaで穴掘り法の迷路作成を実装してみた。
Java>> 小学生のいとこのためにJavaで作った迷路ゲームを簡単に解説する
Java>> Javaのジェネリクス(総称型)って何？
Ruby>> 穴掘り法によるダンジョンの自動生成をRubyで書いてみる
C>> C言語で穴掘り法を使った自動迷路作成を実装してみた
C#>> 穴掘り法によるダンジョンの自動生成 (Unity2Dのサンプルコードつき)