アカデメイア実験室のラボノートには勉強したことのメモを書いていきます。
目標はUnity Learnで3Dを学んで面白そうな何か作ってみることです(雑)
最終的には記事にも価値が出るようなものにしたいですが、何しろ不慣れなので、当面は行動記録として「投稿すること」を優先しようと思います。
こうしたほうがいいぞ!とかあればTwitterで絡んでください。
今日の内容は3DGameを作る(C#編4)です
Roll-a-ballを基準にゲームを作ろうとしています。今日は
迷路形式の相互変換の記録です。
経緯
お疲れ様です。
前回、壁伸ばし式迷路を修復する話をしましたが、「壁伸ばし式でない場合は適用できない」という問題点がありました。これを解決したいですね。
やりたいこと
先日実装した壁伸ばし法限定ダンジョン修復をほかの形式の迷路でも使用するために
壁伸ばし式でない迷路と壁伸ばし法準拠迷路を1:1変換したい。
迷路表現方法は以下のようなものがあります。
解析用:ノードグラフ方式。トポロジー解析はしやすいが壁や形状情報はなくなる
目視用:matrix方式。マップに対応したセルがある。IntArrayや画像画素など。解法解析などで周囲の情報を知るには実際に順にアクセスする必要がある。壁伸ばし法迷路はこのうちの1つ。
描画用:壁リスト方式。経路情報は作成が必要。
保存用:迷路圧縮(Run-Length Encoding等)。保存しやすいが、見るのも経路解析も大変。
生成用:Union-find,Kruskal法等。成長させる方式と間引きする方式がある。一般に生成時の差分を記録するので、最終的な形は一目ではわからない。
このほか人が見るためににtextで、1通路数マスを使って記載する方法もあります。
基本的には生成後の状態ではノードグラフ以外は壁に1マス使うものです。つまりIntArray迷路までは普通にできるということです。
ということは、IntArray同士で、壁伸ばし法迷路と変換すればいいわけですね。
さて、壁伸ばし法準拠迷路は以下のような特性があります。
最外周は必ず壁
(偶数、偶数)マスは必ず通路 ※1始まり
(奇数、奇数)マスは必ず壁 ※1始まり
通路数nに対してマス目は必ず2n+1になる。
したがって、3x3で1マスとして、全体幅を2n+1倍した状態で元の迷路に対応するように壁を塞げば1:1対応できます。
下図は壁を1で示しています。
非壁伸ばし法迷路のIntArray表現
1, 0, 0
0, 1, 0
0, 0, 0
↓
対応する壁伸ばし法準拠迷路(赤色は元の通路の中心マス、黄色は元の壁の中心マス)
1, 1, 1, 1, 1, 1, 1
1, 0, 1, 0, 0, 0, 1
1, 1, 1, 1, 1, 0, 1
1, 0, 1, 0, 1, 0, 1
1, 0, 1, 1, 1, 0, 1
1, 0, 0, 0, 0, 0, 1
1, 1, 1, 1, 1, 1, 1
逆に変換も可能なので、壁伸ばし法迷路の修復に入れて、出てきた迷路を戻せば修復が完了です。
ただし、壁だったところにはもともと個室ができるので、そのまま修復系に入れてしまうと「孤立1個まで減らす」終了条件を満たしません。そこでアルゴリズム側を、系に入ってきた時の数まで減らす、にすれば大丈夫そうです。
以上、今日はここまで
またよろしくお願いします。