質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.61%

穴掘り法迷路生成の処理の流れ。

受付中

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 959

score 350

前提・実現したいこと

こちらのサイトで穴掘り法の迷路生成の勉強をしているのですが、
処理の流れやコードの組み方に関して疑問点があるので、ご教示お願いします。

該当のソースコード

・質問1。
実装されているコードは、「穴掘り法とは」の図の通りの実装ではないと思うのですが、いかがでしょうか?
図の最後を見ると、わずか11マスの通路ができた所で、右端の[0, 6]の位置で行き詰まって
探索終了とみなしているように見えますが、
実際に実装しているコードでは、
さらに②に戻り、ランダムなスタート地点を設定して、また探索を開始してというふうに
この繰り返しを行っているように見えます。
つまり、1回の探索終了までの流れが、MakeDungeonMap()で、
この探索の繰り返しが、下記コードになると思うのですが、いかがですか?

        for (int i = 0; i < max * 5; i++)
        {
            MakeDungeonMap(tmpStart);
            tmpStart = GetStartPosition();
        }

・質問2。
質問1と関係するのですが、この繰り返しが「max * 5」とされてますが、この5の数字は何か意味がありますか?
繰り返す数を適当に決めているだけでしょうか?
試しに3とか100とか入れてみましたが、特に変わりないように見えました。
5じゃなくても問題ないですか?

・質問3。
2次元配列の構造上、y軸を縦、x軸を横とみなすならば、walls[y, x]で座標が指定できる気がするので、
下記コードは

  walls[tmpPos[0], tmpPos[1]] = 1;
  walls[xPos, yPos] = 1;


正しくは以下のように書くべきだと思うのですが、いかがでしょうか?
(ただし、生成する迷路にy方向やx方向の概念はないので、生成する上では何の問題もないと思いますが、
サイトの図の通りに忠実にコードを書くならば、配列オブジェクト[y, x]で正しく座標を指定できるように思えました。) 

  walls[tmpPos[1], tmpPos[0]] = 1;
  walls[yPos, xPos] = 1;

・質問4。
引数の_startPosをtmpStartPosにコピーする必要ってありますか?
MakeDungeonMapメソッド内でも、tmpStartPosの箇所を_startPosで書いてもいいのではないかと思いました。

   int[] MakeDungeonMap(int[] _startPos)
    {
        //スタート位置配列を複製
        int[] tmpStartPos = new int[2];
        _startPos.CopyTo(tmpStartPos, 0);

・質問5。

  //元の地点と通路にした座標の間を通路にする
  int xPos = tmpPos[0] + (tmpStartPos[0] - tmpPos[0]) / 2;
  int yPos = tmpPos[1] + (tmpStartPos[1] - tmpPos[1]) / 2;


と書くよりも、(元の地点) + (通路-元の地点)/2 のほうが直感的な気がして、
質問4も踏まえて書くと、下記のように書き換えても問題ないですか?
(元の地点から通路にした方向に向かって、間の座標を通路にするという感覚で。
下記のように書き換えても問題ないならば、自分としてはこちらのコードの方がしっくりきます。)

  //元の地点と通路にした座標の間を通路にする
  int xPos = _startPos[0] + (tmpPos[0] - _startPos[0]) / 2;
  int yPos = _startPos[1] + (tmpPos[1] - _startPos[1]) / 2;

一応、これらの疑問点のコードを書き替えて、実行してみても迷路生成はできました。
しかし、稀にスタート地点とゴール地点が繋がらないケース(スタートとゴールの間が壁で塞がっているケース)が発生します。
もしかしたら、この中のどれかの書き換えが不具合を起こす可能性がありますか?

追記

質問5に関して、ログをとって確かめてみました。

    int[] MakeDungeonMap(int[] _startPos)
    {
        //スタート位置配列を複製
        int[] tmpStartPos = new int[2];
        _startPos.CopyTo(tmpStartPos, 0);
        //移動可能な座標のリストを取得
        Dictionary<int, int[]> movePos = GetPosition(tmpStartPos);

        //移動可能な座標がなくなるまで探索を繰り返す
        while (movePos != null)
        {
            //移動可能な座標からランダムで1つ取得し通路にする
            int[] tmpPos = movePos[Random.Range(0, movePos.Count)];
            walls[tmpPos[0], tmpPos[1]] = 1;

            //元の地点と通路にした座標の間を通路にする
            int xPos = tmpPos[0] + (tmpStartPos[0] - tmpPos[0]) / 2;
            int yPos = tmpPos[1] + (tmpStartPos[1] - tmpPos[1]) / 2;
            int xPos2 = tmpStartPos[0] + (tmpPos[0] - tmpStartPos[0]) / 2;
            int yPos2 = tmpStartPos[1] + (tmpPos[1] - tmpStartPos[1]) / 2;

            Debug.Log(xPos+","+yPos);
            Debug.Log(xPos2+","+yPos2);
            walls[xPos, yPos] = 1;
            Debug.Log("---");

            //移動後の座標を一時変数に格納し、再度移動可能な座標を探索する
            tmpStartPos = tmpPos;
            movePos = GetPosition(tmpStartPos);
        }
        //探索終了時の座標を返す
        return tmpStartPos;
    }


すると、毎回、xPosとyPosの出力がxPos2とyPos2の出力と同じでした。
tmpPos[0]とtmpStartPos[0]の間の通路が正しく取得できているように思えるのですが、
問題ありますか?

そして、このログをとって新たな疑問点が生まれてしまいました。 1回目と2回目の出力がいつも同じ座標になるみたいです。3回目以降はバラつきます。 なぜでしょうか?
違いました。毎回ではなかったです。たまに1回目と2回目の出力の座標が同じになる場合がありました。
しかし、たまにでも1回目と2回目が同じ座標になってしまうのは疑問です。

新たな疑問。

    int[] MakeDungeonMap(int[] _startPos)
    {
        //スタート位置配列を複製
        int[] tmpStartPos = new int[2];
        _startPos.CopyTo(tmpStartPos, 0);
        //移動可能な座標のリストを取得
        Dictionary<int, int[]> movePos = GetPosition(tmpStartPos);

        //移動可能な座標がなくなるまで探索を繰り返す
        while (movePos != null)
        {
            //移動可能な座標からランダムで1つ取得し通路にする
            int[] tmpPos = movePos[Random.Range(0, movePos.Count)];
            walls[tmpPos[1], tmpPos[0]] = 1;


このように、[y, x]で表現したくて、
walls[tmpPos[0], tmpPos[1]] = 1 を
walls[tmpPos[1], tmpPos[0]] = 1 に書き換えたら、
ゲームを実行すると停止状態(もしかして無限ループにはまってる状態?)になってしまいます。
なぜでしょうか?

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

0

質問1
そのとおりです
(そのへんは適当に省略したのでしょう)

質問2
正しくは((max-1)/2)^2 かなー
(自信がないのでパス)

質問3
プログラム全体で統一されていて、不具合がないならどっちでもいいです
ただ、直感的にはx,yの順ですから、そっちを優先したのでしょう

質問4
_startPosは配列ですから、_startPos[0]は呼び出し元のメモリ領域です
ですから、これを書き換えると呼び出し元の_startPos[0]の値が変わります

質問5
書き換えても問題ない、とは、xpos, yposの値が変わらない、と考えていますか?
それなら、自分の式ををxpos2,ypos2として、デバッガなどで値を表示しながら実行してみるといいでしょう
(結論から言えば、問題あります)

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/01/24 01:55 編集

    ご回答ありがとうございます。

    >質問4
    >_startPosは配列ですから、_startPos[0]は呼び出し元のメモリ領域です
    >ですから、これを書き換えると呼び出し元の_startPos[0]の値が変わります
    呼び出し元の値が変わっても今回の迷路生成では問題ないように思えるのですが、
    引数の_startPosをtmpStartPosにコピーする必要ってありますか?
    MakeDungeonMapメソッド内でも、tmpStartPosの箇所を_startPosで書いてもいいのではないかと思いました。無駄にコピーする処理を書いているように思えるのですが、何か意味はありますか?
    それとも今回の迷路生成ではコピーする必要がなかったとしても、引数に配列を渡す場合は、コピーして呼び出し元の配列を変更しないようにしておく慣習みたいなものがあるのでしょうか?

    質問5
    xpos, yposの値が変わらないと考えていました。
    実際、ログを出して変わってないように見えました。
    どういった問題がありますか?
    詳細は質問に追記しました。

    また、追記で書きましたが、質問3に関してなぜか不具合が生じました。
    walls[tmpPos[1], tmpPos[0]] = 1 に書き換えたら
    ゲーム実行時に停止したような状態になりました。
    この書き換えに問題はありますか?
    (迷路の生成がおかしくなる不具合以前に、Unityが実行時に停止したようになるのが不思議です。)

    キャンセル

  • 2019/01/24 03:19

    質問4
    設計の話なのですが、引数の値は内部で壊す必要がない限りは壊さないのが原則です

    質問5
    書き換える前は迷路の生成ができていて、書き換えたあとにできなくなったのなら、
    xpos, yposの値が変わってないとおかしいわけです
    それに、プログラムの流れを見た感じ、同じ結果にはならないと私は判断しました

    キャンセル

  • 2019/01/24 23:44 編集

    >書き換える前は迷路の生成ができていて、書き換えたあとにできなくなったのなら、
    >xpos, yposの値が変わってないとおかしいわけです
    最初の質問にも書きましたが、一応、迷路生成はできているけど、稀におかしくなるという感じでした。
    ただ改めて、xPosとyPosの書き換え後のコードを30回くらい実行して確認してみましたが、
    毎回、スタート地点とゴール地点はうまく繋がっていました。
    もしかしたら、最初の質問時に確認したときは、見る角度によって壁が塞がっていたような見間違えを
    していたのかもしれません。失礼しました。
    また、書き換え後の
    Debug.Log(xPos+","+yPos);
    Debug.Log(xPos2+","+yPos2);
    が常に同じ値をとっているので、やはり書き換えても大丈夫な気がするのですが、
    int xPos2 = tmpStartPos[0] + (tmpPos[0] - tmpStartPos[0]) / 2;
    int yPos2 = tmpStartPos[1] + (tmpPos[1] - tmpStartPos[1]) / 2;
    この書き換えのコードに問題点があれば、具体的に教えていただきたいです。

    >それに、プログラムの流れを見た感じ、同じ結果にはならないと私は判断しました
    こちらも具体的にどこのコードがおかしいか教えていただけませんか?

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.61%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る