LoginSignup
196

More than 3 years have passed since last update.

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

Last updated at Posted at 2018-12-17

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

m1.gif
今回は世界を創造する禁断の闇魔術について解説します。

🌏実装・環境🌏

開発言語:C++14

コンパイラ 対応度 テスト生成
MSVC cl None
GCC gcc Wandbox
Clang clang Wandbox

🌏ボロノイ図法で作成🌏

voro.gif
ボロノイ図

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

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

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

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

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

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

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

コンストラクタ(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

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

🌏陸地の形状を作成🌏

ボロノイ図の生成(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
外側に近い部分を海とし、中央に近い部分を陸地とします。

陸地か海か決定する
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_));
}
原点を作成する
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
陸と海で2値化します。

図形を線画
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
頂点数PN=300, 陸地確率PB=0.2, ノイズ確率NB=0.0 の場合
m3.gif
頂点数PN=100, 陸地確率PB=0.5, ノイズ確率NB=0.0 の場合

🌏岸を複雑にする🌏

ノイズを発生させる
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;
            }
    }
}
呼び出し
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
頂点数PN=300, 陸地確率PB=0.2, ノイズ確率NB=0.5 の場合
m4.gif
頂点数PN=100, 陸地確率PB=0.5, ノイズ確率NB=0.5 の場合

🌏CUIでの出力🌏

指定文字を出力
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;
        }
    }
}
呼び出し
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
頂点数PN=100, 陸地確率PB=0.5, ノイズ確率NB=0.5 の場合

>> Wandboxで自動生成を試してみる(PC表示で見てね)

🌏実装ライブラリ(ソースコード)🌏

今回解説した地形の自動生成は"Dungeon Template Library""Simple Voronoi Island"として実装されています。
ぜひ、活用してみてください!

logo640.gif

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

These codes are licensed under CC0.
CC0

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

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

関連記事

[DTL]ローグライク自動生成(ローグライク穴掘り法)💀
ローグライクダンジョン生成の記事。

[DTL]地形生成(チャンク&中点変位法)🌽
チャンク&中点変位法の世界生成の記事。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
196