More than 5 years have passed since last update.

直進迷路覚え書き

Posted at 2017-12-25

今回は，私が中間発表会で発表した，直進迷宮のアルゴリズムについてお話ししようと思います．

直進迷路とは

スタートからゴールを目指すのは普通の迷路と同じですが，プレイヤーが迷路を移動する際，壁にぶつかるまで止まることができないという制約を課した迷路のことを直進迷路と呼びます．なお，公式の資料があるわけではなく，ただなんとなくみんなそう呼んでいるだけです．

要約すると，ポケモンでよく見るやつです．

直進迷路を作成する手順は，以下の４つに分解できます．

盤面を定義する
↓
正解のルートをデザインする
↓
デザインの通りに動けるよう，壁を配置する
↓
デザインのルートが最短になるよう，壁を配置する

これらそれぞれについて流れを解説しながら，自動化へのポイントを話せていけたらなと思います．

これは初期条件を決めるということですね．
初めに必要なのは，

になります．今回は10×10の盤面で，左上をスタート，右下をゴールと定義します．
これは普通の迷路と変わりませんね

これも普通の迷路とそんなに変わらないですが，デザインの際は直進しかできないことを忘れてはいけません．それなりに気を付けてデザインしないと，次の段階でエラーになってしまいます．
エラーにならない条件は，以下の通りです．

ここからが直進迷路特有のアルゴリズムです．上記の図の矢印の先に，壁を置きます．こうすることで，このデザインの通りに動けばゴールにたどり着くことが保証されます．

ですが，これで迷路が完成したわけではありません．見てわかる通り，まだ最短ルートが残されているからです（図の場合は↓からの→）

他の最短ルートが成り立たないよう壁を配置します．ここを美しくすると，迷路の評価が高くなる傾向があります．

美しい迷路を作るためのコツとして，以下が挙げられます．

上2つは簡単に自動化できそうです．でも露骨な行き止まりの判定はちょっと複雑そうですね．

直進迷路の解を求める方法は，わかってしまえばとても単純です．
ただ，私が片手間に考えたものなので，もっと素早く計算できるアルゴリズムがあるかもしれません．そのときはご一報ください．

それぞれのマスを表すint型の配列を用意して，中身を"100"で初期化します．以下の画像では，単純化のために"0"を入れてますが，実際には"100"が入っていると思ってください．

その処理をしたのが下の図

ゴールの左側からしかゴールできないので，Gの左側のマスが"1"になったことが確認できます．

その処理(ry

なんとなく感覚はつかめたでしょうか．実は，3の処理を繰り返すと，この迷路を解くことができます．

それでは，3の処理をもう一度行った図を見てみましょう．

このときに注意して見てほしいのが，"2"の振られているマスには"3"が振られていないことです．

この数字はズバリ__そのマスからゴールにたどり着ける最短手数__を表しているのです！

つまり，このアルゴリズムは__ゴールまでの最短距離をゴールから逆算することで求めて__います．

このアルゴリズムで最後まで探索を行うと，以下のようになります．

この時点でSのマスには"7"が振られており，最短手数は7手であることがわかります．

そして，最短経路はSから見て赤字を踏むように進むというわけです．(ちなみに，この盤面には別解があります．別解を防ぐ作り方はいつかやろうかなと思ってますが今回は触れません)

以上が基本的な直進迷路になります．

さて，一番最初に直進迷路の利用例としてポケモンを挙げたわけですが，実は，ポケモンの直進迷路はさらにアレンジが加えられることがあります．
かいりきで動く岩なんかがいい例です．あれがあると，直進迷路の幅が広がります．

直進迷路の応用例として，以下の3つなんかは面白いと思いますね！