ふつーの迷路乱数生成

アバター
usao
記事: 1492
登録日時: 5年前

ふつーの迷路乱数生成

投稿記事 by usao » 4週間前

表題のようなことをやる.
方眼紙に線引いて書いたような迷路を乱数で作るやつ.
(ウィザードリィのマップみたいな)

初期状態:
マップ外周が壁になっているが迷路の出入口(スタートとゴール)の部分だけは壁が無く空いてるという状況.
つまり外周が2つの壁の集合に分かれてる.

やること:
迷路の内側の壁を乱数で作っていけばいい.
まだ判定してない箇所をランダムに選んで,そこに壁を作るか否かを判定する.
ある箇所に壁を作ってよいかどうかの判定は,
・そこに壁を作ったら閉所ができてしまうならダメ
・そこに壁を作ることで初期の2つの壁集合が繋がってしまうならダメ
という単純ルール.
(最終的に全ての壁は初期の2つの集合のどちらかに繋がった状態になる)


実装の簡便さのため,スタートとゴールの位置は左上と右下に固定で設けた.
GridMaze_2pt.png
ランダム迷路
GridMaze_2pt.png (3.09 KiB) 閲覧数: 27 回
これは前回の迷路から思ってたことだが,
大抵の場合,正解ルートが スタート→ゴール の直線に近い形になり,
他の部分(今回の場合だと,迷路の右上付近と左下付近)は立ち寄る必要がない不毛なエリアになるというのが悲しい.



スタートからゴールに行くという【ルールの方を捻じ曲げて】出入口を4つにすれば右上と左下にも用事ができるね!
GridMaze_4pt.png
出入口4個
GridMaze_4pt.png (3.07 KiB) 閲覧数: 27 回
とか強引に考えても,結局,
大抵の場合に経路は2本の対角線からなる「X」に近い経路になり
外周の4辺の中点付近を通る率が低いという話には変わりがない.

要するに 「良い迷路」を生成する という観点が抜けている.
最後に編集したユーザー usao on 2018年12月19日(水) 15:02 [ 編集 1 回目 ]

アバター
usao
記事: 1492
登録日時: 5年前

Re: ふつーの迷路乱数生成

投稿記事 by usao » 4週間前

迷路生成関数の宣言はこんな感じ.
ランダムで作るんだから乱数生成器を引数に受けたいのだが,そこをどう書けばいいのかわからん.
(templateにしないとダメ?)
実装では単にこの引数をstd::shuffleに渡したいだけなのだが.

CODE:

//グリッド状の迷路の作成.
//[Args]
//  nVtxX, nVtxY :
//      迷路の規模を,X,Y方向の頂点の個数で指定.どちらも3以上の値を指定する必要がある.
//      (両者の値が3のとき,グリッドサイズは2*2[マス])
//  Rnd :
//      乱数生成器.
//      (この型に限定する必要は無いのだが,乱数生成器を引数に受けるのをどう書けばいいのかわからん)
//  Is4PointMaze :
//      迷路の形式.
//      trueを指定すると,迷路の出入口が四隅4カ所に作られる.
//      falseを指定すると,迷路の出入口は左上と右下の2か所.
//[Ret]
//  迷路の壁を表すデータ.各要素が1つの「壁」を表し,「壁」は連結する2頂点のindexで表される.
//  頂点indexの範囲は[0, nVtxX*nVtxY-1]
std::vector< std::pair<unsigned int,unsigned int> > CreateGridMaze(
    unsigned int nVtxX, unsigned int nVtxY,
    std::mt19937 &Rnd,
    bool Is4PointMaze
    );
ここで「頂点のindex」ってのは,あれだ.2次元配列を1次元配列で実装したときの配列indexなやつ.
indexから(X,Y)を得る手段は単純にこんな.

CODE:

//頂点の2次元平面上の座標(X,Y)を取得
//[Args]
//  VtxIndex : 頂点のindex
//  nVtxX : 迷路のX方向の頂点個数.CreateGridMaze()に指定したものと同じ値を指定すること.
//[Ret]
//  (X,Y)座標:
//      一番左上の頂点の座標は(0,0).
//      そこから右に1個進む毎にXが,下に一個進む毎にYが1ずつ増加する.
inline
std::pair<unsigned int, unsigned int> VtxPos( unsigned int VtxIndex, unsigned int nVtxX )
{   return std::pair<unsigned int,unsigned int>( VtxIndex%nVtxX, VtxIndex/nVtxX );  }

アバター
usao
記事: 1492
登録日時: 5年前

Re: ふつーの迷路乱数生成

投稿記事 by usao » 4週間前

具体実装.呆れるほどベタ書きである.
・初期状態の準備はもっときれいに書けないのか?
・頂点のラベル番号を更新する処理が遅そう(毎回全探索だぜ!)
・迷路完成の判断くらいは入れてもよいのではないかと

CODE:

//頂点(X,Y)に対応する頂点index
inline
unsigned int VtxIndex( unsigned int X, unsigned int Y, unsigned int nVtxX )
{   return ( Y*nVtxX + X ); }

//非常にシンプルなアルゴリズムによる迷路生成.
//グリッドの外周矩形をNか所の(スタートやゴールみたいな)出入口で切ってできる,N個の外壁グループを考えたとき,
//グリッドの内側の壁を作っていく際に,異なるグループが壁で連結されないようにすれば,各出入口間の経路が失われないよね,っていう方法.
std::vector< std::pair<unsigned int,unsigned int> > CreateGridMaze(
    unsigned int nVtxX, unsigned int nVtxY,
    std::mt19937 &Rnd,
    bool Is4PointMaze
    )
{
    if( nVtxX<3 || nVtxY<3 ){   throw std::invalid_argument( "nVtx must be Greater or Equal 3" );   }

    std::vector< std::pair<unsigned int,unsigned int> > Ret;    //結果用
    std::vector< unsigned int > Labels( nVtxX * nVtxY );    //ラベリング処理用
    std::vector< std::pair<unsigned int, unsigned int> > WallConds; //内壁候補

    //初期状態の準備.
    //・外壁グループ群を構成する壁をRetに追加
    //・全ての頂点にラベリング用のラベルを付与.外壁グループのラベル値には{0,1,2,3}を使用.グリッド内側の頂点には4以上の初期ラベル値を付与.
    //  (MEMO:グリッドの{左上,右上,左下,右下}の4頂点のラベル値は以降の処理で参照されないから,ここで特に設定しとかなくてもOK)
    //・WallCondsを,全ての取り得る内壁候補の集合にする
    for( unsigned int x=1; x+1<nVtxX; ++x )
    {
        unsigned int i = VtxIndex( x,0, nVtxX );
        Ret.emplace_back( i, i+1 );
        Labels[i] = 0;

        i = VtxIndex( x,nVtxY-1, nVtxX );
        Ret.emplace_back( i, i-1 );
        Labels[i] = 1;

        WallConds.emplace_back( VtxIndex(x,nVtxY-1,nVtxX), VtxIndex(x,nVtxY-2,nVtxX) );
    }
    for( unsigned int y=1; y+1<nVtxY; ++y )
    {
        unsigned int iu = VtxIndex( 0,y-1, nVtxX );
        unsigned int id = VtxIndex( 0,y, nVtxX );
        Ret.emplace_back( iu, id );
        Labels[id] = ( Is4PointMaze ? 3 : 1 );

        iu = VtxIndex( nVtxX-1,y, nVtxX );
        id = VtxIndex( nVtxX-1,y+1, nVtxX );
        Ret.emplace_back( iu, id );
        Labels[iu] = ( Is4PointMaze ? 2 : 0 );
    }
    if( !Is4PointMaze )
    {
        unsigned int iu = VtxIndex( 0,nVtxY-2, nVtxX );
        unsigned int id = VtxIndex( 0,nVtxY-1, nVtxX );
        Ret.emplace_back( iu, id );

        iu = VtxIndex( nVtxX-1,0, nVtxX );
        id = VtxIndex( nVtxX-1,1, nVtxX );
        Ret.emplace_back( iu, id );
    }
    {
        unsigned int LabelNo = 4;
        for( unsigned int y=1; y+1<nVtxY; ++y )
        {
            for( unsigned int x=1; x+1<nVtxX; ++x )
            {
                unsigned int i = VtxIndex(x,y,nVtxX);
                WallConds.emplace_back( i, i-1 );
                WallConds.emplace_back( i, VtxIndex(x,y-1,nVtxX) );
                Labels[ i ] = LabelNo++;
            }

            unsigned int i = VtxIndex(nVtxX-1,y,nVtxX);
            WallConds.emplace_back( i, i-1 );
        }
    }

    //迷路生成
    std::shuffle( WallConds.begin(), WallConds.end(), Rnd );
    for( auto &WC : WallConds )
    {
        unsigned int i1 = Labels[ WC.first ];
        unsigned int i2 = Labels[ WC.second ];
        //閉所を作らず,且つ,外周グループを連結しないなら,壁として採用
        if( !(   i1==i2  ||  (i1<4 && i2<4)   ) )
        {
            Ret.push_back( WC );

            //ラベル更新.若い方のラベル番号を残す
            unsigned int Before = i1;
            unsigned int After = i2;
            if( Before<After )std::swap( Before,After );
            for( unsigned int &v : Labels ){    if( v==Before ){    v=After;    }   }
        }
    }
    return Ret;
}
(今さらだが,「出入口4つ」って,それ,単に出入口2つ迷路の結果から壁を2つ差っ引けば良いだけちゃうんかと問い詰めたい…)
最後に編集したユーザー usao on 2018年12月19日(水) 15:30 [ 編集 1 回目 ]

アバター
もるも
記事: 37
登録日時: 3年前

Re: ふつーの迷路乱数生成

投稿記事 by もるも » 3週間前

>>立ち寄る必要がない不毛なエリアになるというのが悲しい。

アイテムが置けるありがたいスペースだと思います(`・ω・´)

アバター
いわん
記事: 28
登録日時: 2年前

Re: ふつーの迷路乱数生成

投稿記事 by いわん » 3週間前

壁を作っていくタイプの迷路作成アルゴリズムですね。
私は穴掘りタイプのアルゴリズムをよく使います。
未踏地帯をなるべく作らないようにするなら、最初に正解ルートをなるべく全体を
通るように設定して、そこからランダムに枝分かれ通路を掘るようなアルゴリズムに
するかな?その最初のルートをどう作るかが問題ですが。

アバター
usao
記事: 1492
登録日時: 5年前

Re: ふつーの迷路乱数生成

投稿記事 by usao » 3週間前

なるほど「アイテム」……
「扉と鍵」みたいな簡単なルールを持つ迷路を作るとかの方向も面白そう.

プレイヤが{自主的に(?),仕方なく(?)}広域を彷徨う必要がある用途に使う迷路データを作るならば,
こういう「難しくない迷路」ができる処理でも役に立つのかもしれませんね.


最初に「良い正解経路」を人手を介さずに用意するのは難しい問題になりそう.
(ランダムでN点の通過点を設けてそれを一筆書きで通る経路を算出……とかだと,できる自信がない)
なので,
・形状だけ作った迷路に対して,なるべくいい感じの位置にスタートとゴールを後から選ぶ
だとか
・作った迷路の正解経路を改変して難しくする
とかの方が考えるのが簡単かも.

後者的な方法なら,今回作った迷路にはループが無いから,例えば,
「正解ルートのどこかを壁で塞いで代わりに他の箇所を開けて別ルートを開通させ,正解経路長が長くなったら採用」
みたいな処理を後段に加えればいいのかも.
(ほしい経路長に関する閾値みたいな引数を指定できるようにすれば良いかな.)