MMDOX(14)オートマップ併用拡張左手法

単純な左手法では対処できない迷路の攻略法をまとめる。ゲームにおいてはこれでも完璧とは言えないが、助けになるはず。

迷路は複雑でワープポイントもある。以前に迷路攻略法として紹介した左手法(右手法も)は使えないようだ。左手法は完璧ではない。例えば「甲」の字型の迷路を考える。下に突き出ているのが外への出入り口だ。左手法を使うと外周を回るばかりで、「田」の字型の中心部へはたどり着けない。

下水道は迷路になっている。左手法とオートマップを使えばさほど問題ない。左手法がそのまま通用しない箇所はこうする。ある地上への出入り口から左手法で出発したところ、同じ地点に戻ってしまった。戻ったらその場所に仮想の壁があると思えばいい。すると引き返すことになり全てを探索できるはずだ。すくなくとも下水道はこれで攻略できる。

ドワーフ鉱山もこれで攻略できる。例として「甲」の字型の迷路を考える。★は現在地点、○は踏破未済、●は踏破済みを示す。

1.初期状態:
○○○○○○○○○
○   ○   ○
○   ○   ○
○   ○   ○
○○○○○○○○○
○   ○   ○
○   ○   ○
○   ○   ○
○○○○○○○○○
....○
....○
....★


2.最初の分岐点:
○○○○○○○○○
○   ○   ○
○   ○   ○
○   ○   ○
○○○○○○○○○
○   ○   ○
○   ○   ○
○   ○   ○
○○○○★○○○○
....●
....●
....●


3.左手法を適用:
○○○○○○○○○
○   ○   ○
○   ○   ○
○   ○   ○
○○○○○○○○○
○   ○   ○
○   ○   ○
○   ○   ○
○○○★●○○○○
....●
....●
....●


4.仮想の壁にぶつかる直前:
●●●●●●●●●
●   ○   ●
●   ○   ●
●   ○   ●
●○○○○○○○●
●   ○   ●
●   ○   ●
●   ○   ●
●●●●●○○★●
....●
....●
....●


5.踏破済み地点へ戻らないように仮想の壁を想定して引き返す(拡張左手法)。仮想の壁として○を残しておく。そのほうが無難。:
●●●●●●●●●
●   ○   ●
●   ○   ●
●   ○   ●
●○○○○○○○●
●   ○   ●
●   ○   ●
●   ○   ●
●●●●●○★●●
....●
....●
....●


6.2つ目の仮想の壁を引き返す:
●●●●●●●●●
●   ○   ●
●   ○   ●
●   ○   ●
●○○○●●●●●
●   ●   ●
●   ★   ●
●   ○   ●
●●●●●○●●●
....●
....●
....●


7.4つ目の仮想の壁を引き返す:
●●●●●●●●●
●   ○   ●
●   ★   ●
●   ●   ●
●○●●●●●●●
●   ●   ●
●   ●   ●
●   ○   ●
●●●●●○●●●
....●
....●
....●


8.以前にぶつかった仮想の壁にぶつかる直前:
●●●●●★●●●
●   ○   ●
●   ●   ●
●   ●   ●
●○●●●●●●●
●   ●   ●
●   ●   ●
●   ○   ●
●●●●●○●●●
....●
....●
....●


9.以前にぶつかった仮想の壁に、再度ぶつかる。:
●●●●★●●●●
●   ○   ●
●   ●   ●
●   ●   ●
●○●●●●●●●
●   ●   ●
●   ●   ●
●   ○   ●
●●●●●○●●●
....●
....●
....●


10.再度ぶつかった仮想の壁は踏破済みにする。それから引き返す。:
●●●●●●●●●
●   ★   ●
●   ●   ●
●   ●   ●
●○●●●●●●●
●   ●   ●
●   ●   ●
●   ○   ●
●●●●●○●●●
....●
....●
....●


11.すべてを踏破済みにした:
●●●●●●●●●
●   ●   ●
●   ●   ●
●   ●   ●
●●●●●●●●●
●   ●   ●
●   ●   ●
●   ●   ●
●●●●●★●●●
....●
....●
....●


12.最終状態:
●●●●●●●●●
●   ●   ●
●   ●   ●
●   ●   ●
●●●●●●●●●
●   ●   ●
●   ●   ●
●   ●   ●
●●●●●●●●●
....●
....●
....★


ある仮想の壁にぶつかるのが初めてなのか、再度なのかはどうやって判別するのか。「4.仮想の壁にぶつかる直前」と「8.以前にぶつかった仮想の壁にぶつかる直前」を比べる。次に進む位置(次に★になる位置)が、踏破未済○なら初めて、踏破済み●なら再度だ。

なお、拡張左手法であっても完璧ではないだろう。高低差(3次元迷路)どころか、条件付きのワープがあっても掟破りではないからだ。アルゴリズムを競うのと違って、ゲームにおける迷路の制約条件は事前にわからない。完璧だと思ってしまうと裏をかかれるかもしれない。