Unityのナビゲーションシステムを利用して、迷路を解いてみます
■実行イメージ
■迷路の生成方法
迷路の生成方法はいくつかありますが、今回は穴掘り法という方法を使います。
参考リンク
穴堀り法 迷路生成アルゴリズム | 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
51 x 51
■ナビゲーション準備
Unityエディタのメニューから[Window] -> [Navigation]を選択し、[Navigation]タブを開きます。
迷路の地面となるBoardを十分に大きくし、[Inspector]にて選択した後、[Navigation]タブの[Object]タブにある[Navigation Static]を選択します。
その後、[Bake]タブを選択し、[Bake]をおすと、探索できる範囲が盤面上に表示されます。
その後、自動生成に用いたWallプレハブに[NavMeshObstacle]コンポーネントを追加します。
この状態で盤面を生成すると、探索可能範囲が壁によって分断されます。
■ナビゲーションプレイヤーとターゲット位置の初期化
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