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

前提・実現したいこと

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

該当のソースコード

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

C#
1        for (int i = 0; i < max * 5; i++)
2        {
3            MakeDungeonMap(tmpStart);
4            tmpStart = GetStartPosition();
5        }

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

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

C#
1  walls[tmpPos[0], tmpPos[1]] = 1;
2  walls[xPos, yPos] = 1;

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

C#
1  walls[tmpPos[1], tmpPos[0]] = 1;
2  walls[yPos, xPos] = 1;

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

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

・質問5。

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

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

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

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

追記

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

C#
1    int[] MakeDungeonMap(int[] _startPos)
2    {
3        //スタート位置配列を複製
4        int[] tmpStartPos = new int[2];
5        _startPos.CopyTo(tmpStartPos, 0);
6        //移動可能な座標のリストを取得
7        Dictionary<int, int[]> movePos = GetPosition(tmpStartPos);
8
9        //移動可能な座標がなくなるまで探索を繰り返す
10        while (movePos != null)
11        {
12            //移動可能な座標からランダムで1つ取得し通路にする
13            int[] tmpPos = movePos[Random.Range(0, movePos.Count)];
14            walls[tmpPos[0], tmpPos[1]] = 1;
15
16            //元の地点と通路にした座標の間を通路にする
17            int xPos = tmpPos[0] + (tmpStartPos[0] - tmpPos[0]) / 2;
18            int yPos = tmpPos[1] + (tmpStartPos[1] - tmpPos[1]) / 2;
19            int xPos2 = tmpStartPos[0] + (tmpPos[0] - tmpStartPos[0]) / 2;
20            int yPos2 = tmpStartPos[1] + (tmpPos[1] - tmpStartPos[1]) / 2;
21            
22            Debug.Log(xPos+","+yPos);
23            Debug.Log(xPos2+","+yPos2);
24            walls[xPos, yPos] = 1;
25            Debug.Log("---");
26
27            //移動後の座標を一時変数に格納し、再度移動可能な座標を探索する
28            tmpStartPos = tmpPos;
29            movePos = GetPosition(tmpStartPos);
30        }
31        //探索終了時の座標を返す
32        return tmpStartPos;
33    }

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

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

新たな疑問。

C#
1    int[] MakeDungeonMap(int[] _startPos)
2    {
3        //スタート位置配列を複製
4        int[] tmpStartPos = new int[2];
5        _startPos.CopyTo(tmpStartPos, 0);
6        //移動可能な座標のリストを取得
7        Dictionary<int, int[]> movePos = GetPosition(tmpStartPos);
8
9        //移動可能な座標がなくなるまで探索を繰り返す
10        while (movePos != null)
11        {
12            //移動可能な座標からランダムで1つ取得し通路にする
13            int[] tmpPos = movePos[Random.Range(0, movePos.Count)];
14            walls[tmpPos[1], tmpPos[0]] = 1;

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

行動規範の内容に同意します

回答1件

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

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

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

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

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

投稿2019/01/22 02:30

izmktr

総合スコア2856

退会済みユーザー

2019/01/23 16:57 編集

ご回答ありがとうございます。 >質問4 >_startPosは配列ですから、_startPos[0]は呼び出し元のメモリ領域です >ですから、これを書き換えると呼び出し元の_startPos[0]の値が変わります呼び出し元の値が変わっても今回の迷路生成では問題ないように思えるのですが、引数の_startPosをtmpStartPosにコピーする必要ってありますか？ MakeDungeonMapメソッド内でも、tmpStartPosの箇所を_startPosで書いてもいいのではないかと思いました。無駄にコピーする処理を書いているように思えるのですが、何か意味はありますか？それとも今回の迷路生成ではコピーする必要がなかったとしても、引数に配列を渡す場合は、コピーして呼び出し元の配列を変更しないようにしておく慣習みたいなものがあるのでしょうか？質問5 xpos, yposの値が変わらないと考えていました。実際、ログを出して変わってないように見えました。どういった問題がありますか？詳細は質問に追記しました。また、追記で書きましたが、質問3に関してなぜか不具合が生じました。 walls[tmpPos[1], tmpPos[0]] = 1 に書き換えたらゲーム実行時に停止したような状態になりました。この書き換えに問題はありますか？ (迷路の生成がおかしくなる不具合以前に、Unityが実行時に停止したようになるのが不思議です。)

izmktr

2019/01/23 18:19

質問4 設計の話なのですが、引数の値は内部で壊す必要がない限りは壊さないのが原則です質問5 書き換える前は迷路の生成ができていて、書き換えたあとにできなくなったのなら、 xpos, yposの値が変わってないとおかしいわけですそれに、プログラムの流れを見た感じ、同じ結果にはならないと私は判断しました

退会済みユーザー

2019/01/25 18:10 編集

>書き換える前は迷路の生成ができていて、書き換えたあとにできなくなったのなら、 >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; この書き換えのコードに問題点があれば、具体的に教えていただきたいです。 >それに、プログラムの流れを見た感じ、同じ結果にはならないと私は判断しましたこちらも具体的にどこのコードがおかしいか教えていただけませんか？

行動規範の内容に同意します