アカデメイア実験室のラボノートには勉強したことのメモを書いていきます。
目標はUnity Learnで3Dを学んで面白そうな何か作ってみることです(雑)
最終的には記事にも価値が出るようなものにしたいですが、何しろ不慣れなので、当面は行動記録として「投稿すること」を優先しようと思います。
こうしたほうがいいぞ!とかあればTwitterで絡んでください。
今日の内容は3DGameを作る(C#編8)です
今回は「チェックポイント配置アルゴリズム」です。
やりたいこと
ユーザーの探索範囲がなるべく広くなるようにチェックポイントを配置したい。
方法としては、以前考えた距離マップ(リンク)の発想で行きたいと思います。
まず、以前作成した距離マップアルゴリズムをそのまま適用しようとすると、以下の問題が発生します。
問題点1と原因:
以前に使用した単純距離マップ生成では壁をまたいだ反対側も近いと判断されてしまう。
ユーザーは通路しか移動できないため、「見た目に均等」な前回と異なり、実際の探索を反映するには通路を移動したときの距離を知る必要がある。
そこで、迷路をノード見立て、幅優先探索を使って迷路上での移動距離を出すことにしました。
問題点1の解決策:
幅優先探索を用いて通路移動距離マップを作成し、スタートと配置済みチェックポイントからの最遠点を採用する。
さて、とりあえずの実装はできましたが、迷路は自動生成のため、形状によっては新たな問題点が発生することが分かりました。
迷路の長い1本道に複数のチェックポイントが置かれてしまう問題です。
問題点2と原因:
1本のとても長い通路があり、他が比較的短い場合、1の通路内にチェックポイントが集中する。
例えば1本のスタートからの距離がほかの迷路の4倍ある時、1つ目のチェックポイントを置いた後の通路上、中間点付近に「最遠点」が出現してしまう。これは探索を広くする目的からは不適切。
解決策2
チェックポイントを置いた場合にその通路をさかのぼって分岐点まで迷路を閉鎖(マスク)しそれ以外の最遠点を採用する。
以上とりあえず解決しました。
通路が配置チェックポイント以上だった場合に配置できなくなるのですが、それはまた別のお話。
幅優先探索と通路閉鎖方法(実際の処理上はさかのぼっていない)についてもまたまとめようと思います。
今日はここまで。