C++
アルゴリズム
ゲーム制作
迷路
DungeonGeneration

【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_);
}



出力結果

meiro4_2.jpg


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

These codes are licensed under CC0.

CC0


他言語の穴掘り法

Java>> Javaで穴掘り法の迷路作成を実装してみた。

Java>> 小学生のいとこのためにJavaで作った迷路ゲームを簡単に解説する

Java>> Javaのジェネリクス(総称型)って何?

Ruby>> 穴掘り法によるダンジョンの自動生成をRubyで書いてみる

C>> C言語で穴掘り法を使った自動迷路作成を実装してみた

C#>> 穴掘り法によるダンジョンの自動生成 (Unity2Dのサンプルコードつき)