RPGでお馴染みの 迷宮 ！道順が不明ですが、「とにかく右側を辿っていけば、いつかはゴールにたどり着く（右手法アルゴリズム）」という噂があります。本当かな、ということで検証のために、シミュレーターを作ってみました。
直感的にわかるとは思いますが、操作方法を以下に記しておきます。
⚙️ 各部コントロールの使い方
- 難易度（迷路サイズ）の選択
- 左上のセレクトボックスから、迷宮の大きさを3段階で変更できます。
- 初級（11×11）： 右手法の基本的な動き（三拍子のテンポ）が一番分かりやすいおすすめサイズです。
- 中級（17×17）： 少し複雑な分岐や、長い一本道が登場します。
- 上級（25×25）： 画面いっぱいに広がる本格的な大迷宮です。
- ※サイズを変更すると、自動的に新しい迷宮がランダム生成（自動生成）されます。
- 速度調整
- シミュレーションが進むスピードを「遅い（1秒）」「普通（0.5秒）」「速い」「超高速」の4段階から選べます。
- 探索者が「①向きを変える」→「②進む先を照らす」→「③進む」という丁寧な3ステップを踏むため、まずは「普通（0.5秒）」でじっくりロジックを目で追うのがおすすめです。全体のルートを確認したいときは「超高速」が便利です。
- 操作ボタン
- START： 探索を開始します。
- STOP： 探索を一時停止します。途中でじっくり盤面を観察したいときにお使いください。（作動中はSTARTボタンがSTOPボタンに切り替わります）
- RESET： 探索者をスタート地点に戻し、全く別の新しい迷宮を再生成します。もう一度最初から楽しみたいときや、別のマップで試したいときに押してください。
🎨 画面の見方（色のヒント）
- 🔵 青い丸 ＆ ▲（探索者）： 迷宮に挑むプレイヤーです。「▲」の向きが今見ている方向を表しています。
- 🟢 緑の線（右手法センサー）： 探索者の右側に常に表示されているセンサーです。このセンサーを「右側の壁」にベッタリと沿わせながら進んでいきます。
- 🟩 START（緑のマス）： 迷宮の入り口です。
- 🟥 GOAL（赤のマス）： 迷宮の出口です。ここに辿り着けば脱出成功となります。
- 🟧 橙色のマス（足跡）： 探索者が一度でも通り過ぎた「歩いた軌跡」です。松明の明かりが残り続けるように、一度通った場所は明るくマッピングされます。
- ⚪ 誘導灯・白（通路の発見）： 探索者が前方を照らしたとき、そこが「進める通路」であれば明るいグレーにライトアップされます。
- 🔴 誘導灯・赤（壁の警告）： 探索者が前方を照らしたとき、そこが「行き止まり（壁）」であれば、光が遮られた警告として赤く妖しくフラッシュ発光します。
課題 右手法の弱点と無限ループ（島の構造）について
本シミュレーターで採用している「右手法」は、シンプルながらも確実に迷路を解く強力なアルゴリズムですが、実は万能ではなく構造的な弱点が存在します。
・「島」がある迷路では無限ループになる 右手法が確実に成立するのは、「迷路のすべての壁が、外周の壁と1本に繋がっていること」が前提条件です。 もし、迷路の中に外壁と一切繋がっていない独立した壁（通称：島の形、アイランド構造）が存在し、その島の中にゴールが配置されていた場合、右手法では以下のような問題が発生します。
・無限ループの発生：外壁からスタートした探索者は、島に飛び移ることができず、外壁の凹凸に沿って同じルートを永久にぐるぐる回り続けてしまいます。
・島からスタートした場合：逆に島側の壁からスタートした場合、今度は島の周囲を無限に回り続けるだけで、外壁側にあるゴールにたどり着くことができません。
今後の開発課題
今回のシミュレーターでは、自動生成される迷路の構造上、右手法で解けるマップを前提としていますが、実際のRPGのダンジョンなどに見られる「島の形」のループを回避するには、さらに高度なロジックが必要です。
・通ったルートの交差を検知してループを回避する処理
・「トレモー法（足跡をつけながら進み、袋小路やループを識別する手法）」など、より高度な探索アルゴリズムへの拡張
これらの無限ループへの対策や、別アルゴリズムへの対応については、本シミュレーターの今後のアップデート課題としたいと思います。
コメント