Help us understand the problem. What is going on with this article?

【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のサンプルコードつき)

gis
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away