スマゲ

スマートなゲームづくりを目指して日々精進

Unityのナビゲーションを使って自動生成した迷路を解かせる

Unityのナビゲーションシステムを利用して、迷路を解いてみます

■実行イメージ
f:id:sanukin39:20170507154807g:plain

■迷路の生成方法
迷路の生成方法はいくつかありますが、今回は穴掘り法という方法を使います。

参考リンク
穴堀り法 迷路生成アルゴリズム | Miga's Hobby Programming

■実装
・盤面の生成
生成する迷路の規模を可変にするため、入力された盤面の幅と高さからカメラの位置を調整し、各盤面を壁で初期化します

    /// <summary>
    /// 迷路の盤面の位置とサイズ、カメラの位置を初期化する
    /// </summary>
    private void InitializeBoardAndCamera()
    {
        float boardPosX = boardWidth / 2f - 0.5f;
        float boardPosZ = boardHeight / 2f - 0.5f;

        Camera.main.transform.position = new Vector3(boardPosX * 2, boardWidth + boardHeight, boardPosZ * 2);

        board = new bool[boardWidth, boardHeight];

        for (int i = 0; i<boardWidth; i++)
        {
            for (int j = 0; j<boardHeight; j++)
            {
                board[i, j] = true;
            }
        }
    }

・迷路データの生成
盤面内の点(幅、高さそれぞれ数えて偶数の場所)を無作為に選んで道をほっていきます

    /// <summary>
    /// 迷路データを初期化する
    /// </summary>
    private void CreateLabyrinthData()
    {
        var digCandidate = new List<Vector2>();
        for (int i = 0; i < boardWidth; i++)
        {
            for (int j = 0; j < boardHeight; j++)
            {
                if (i != 0 && j != 0 && i % 2 != 0 && j % 2 != 0 && board[i, j])
                {
                    digCandidate.Add(new Vector2(i, j));
                }
            }
        }

        foreach (var vec in digCandidate.OrderBy(v => Guid.NewGuid()))
        {
            if (board[(int)vec.x, (int)vec.y])
            {
                Dig(vec);
            }
        }
    }

・迷路を掘る
ある特定の場所から上下左右ランダムに掘る方向を決め、掘る方向の向こう2マスが壁であったらあいだの壁を掘り、さらに掘った先から同様に処理を行います。
掘れなくなったら、道を戻って他の方向を試してみます。

    /// <summary>
    /// 迷路を掘る
    /// </summary>
    /// <param name="pos">掘る場所</param>
    private void Dig(Vector2 pos)
    {
        board[(int)pos.x, (int)pos.y] = false;

        var searchDir = dir.OrderBy(i => Guid.NewGuid()).ToList();

        foreach (var d in searchDir)
        {
            var checkPos = pos + d * 2;
            if (IsInBoard(checkPos) && board[(int)checkPos.x, (int)checkPos.y])
            {
                var c = pos + d;
                board[(int)c.x, (int)c.y] = false;
                Dig(checkPos);
            }
        }
    }

■生成した迷路
21 x 21
f:id:sanukin39:20170507171058p:plain

51 x 51
f:id:sanukin39:20170507171109p:plain

■ナビゲーション準備
Unityエディタのメニューから[Window] -> [Navigation]を選択し、[Navigation]タブを開きます。
迷路の地面となるBoardを十分に大きくし、[Inspector]にて選択した後、[Navigation]タブの[Object]タブにある[Navigation Static]を選択します。
その後、[Bake]タブを選択し、[Bake]をおすと、探索できる範囲が盤面上に表示されます。
f:id:sanukin39:20170507164926p:plain

その後、自動生成に用いたWallプレハブに[NavMeshObstacle]コンポーネントを追加します。
この状態で盤面を生成すると、探索可能範囲が壁によって分断されます。
f:id:sanukin39:20170507170315p:plain

■ナビゲーションプレイヤーとターゲット位置の初期化
NavMesh Agentをアタッチしたplayerを作成し、スクリプトで初期位置を決定します

    private void Start()
    {
        var width = 21;
        var height = 21;
        labyrinthGenerator.CreateLabyrinth(width, height);
        player.transform.position = new Vector3(2, 0.5f, (height * 2 - 4));
        target.transform.position = new Vector3((width * 2 - 4), 0.5f, 2);

        player.GetComponent<NavMeshAgent>().destination = target.transform.position;
    }

■まとめ
Unityのナビゲーションを利用して、作成した迷路を溶かせることができました。
しかし、上記のような[NavMeshObstacle]を利用した移動範囲の生成は[NaviMesh]が細かく分断され、結果探索のための計算量が膨大になってしまいます。
この方法で箱庭系などのゲームを作るのは厳しそうです。

■コード確認用リポジトリ
github.com

■参考リンク
Unity - マニュアル: ナビゲーションと経路探索
穴堀り法 迷路生成アルゴリズム | Miga's Hobby Programming