まっはまん２の最短経路を求める
過去ブログの転載です。
まっはまん２とはコンパクで受賞されたツクール2000製のアクションゲームで、私がむかし多大な影響を受けたゲームです。主人公が一定時間だけまっはまんに変身でき、その間はすごい速さで動けて敵を倒せるようになるというシステムです。それでコース内にある宝石を５つ見つけてゴールを目指すのです。
コースによってはゴールが２つあって、通るゴールによって進むコースが分岐するわけですが、どの分岐を通っていけば最短でクリアできるか、ダイクストラ法を使って大雑把ですが求めてみました。
グラフの生成
各ステージはグラフに改めることが可能です。各々の頂点がコースで、辺は重み付きにしておきます。重みは、その辺を通るためにクリアしなければならないコースをゴールするのに掛かる時間としますが、これを求めることは困難です。TASでもして一つ一つやっていけば良いのかもしれませんが、そんなことしていられませんので、概算します。
まっはまん２では作者さんがコースをクリアしたときのタイムが作者タイムとしてすべて記録されております。これはゴールしたときに残っていた制限時間ですので、コースの制限時間から作者タイムを引けばゴールまでに掛かる時間の指標が得られます。ただし、例外がいくつかありますので、以下に述べます。
分岐コース
分岐コースではゴール位置が異なるので、作者タイムだけでは厳密には求まりません。しかし宝石を５個取らなければゴールが現れないことから、ゴールに行くまでの時間は誤差の範囲として考えないこととします。即ち、基本的に分岐コースではどちらのゴールへ行く時間も同じとします。（後に述べる強制スクロールステージのみ例外です）
時計アイテム
コース中には取ることで制限時間が３０秒アップする時計が置いてあることがあり、それを取ると制限時間が上がるので、正確なタイムにはなりません。しかしそもそも制限時間が基本的に作者タイムから求められているようですので、ここでは時計については基本的に考慮しません。
例外として２－１３は制限時間が６０秒で、時計を取ること前提なタイムになっていますので、そこだけは時計による制限時間アップを考慮しています。具体的には、取れる時計は最大１１個ですので、全部取ると制限時間は６０＋３０×１１＝３９０秒になります。そのとき作者タイムは１１個の時計を取ってクリアしたものだと考え、３９０秒から作者タイムを減算することで求めています。
強制スクロールステージ
２－９と３－７は強制スクロールステージであり、制限時間がありません。そのため、スクロールが完了するまでの時間を求めてそれをクリアに掛かる時間とします。
２－９は上に78マス、右に9マス、下に77マス進むので、合計165マスだけスクロールします。
スクロール速度は1／4倍速であり、1／4倍速で1マス進むには32／60秒掛かるので、32／60×165＝88秒掛かります。
従って、２－９のクリアに掛かる時間は88秒とします。
３－７では途中の主人公の体力値によってスクロール方向が変化します。上に進む場合は上に225マス進むので、225×32／60＝120秒です。
右に進む場合は上に106マス、右に20マス、下に106マス進むので、合計232マス進むことから、232×32／60≒123.73秒です。
TASとか使うと正直スクロールを無視してクリアすることも可能になりますが、ゴールまでの間にスクロール方向が反対になる場面ではスクロールが反対になるまで待たなければゴールできないので、あまり細かいことは気にせず、スクロール歩数だけで計算しました。
クリアに掛かる時間の表
以上より、クリアに掛かる時間の表が作成できます。
これらをもとにグラフの辺に重みを付け、最短経路を導きます。
最短経路を導く
最短経路はダイクストラ法によって得ることとします。ダイクストラ法は、その頂点にたどり着くまでの辺の重みを足していき、暫定の重みを使いながら、それがそれぞれ最小になるようにして最短経路を求めるアルゴリズムです。詳しくはここでは述べません。
ここで用いるグラフは一方通行ですので、分岐が戻って合流する地点でそれぞれの重みの和を比較し、重みが小さい方を採用してその方が短い経路としていきます。そうすれば、最短経路が求まることになります。
ステージ１
これをグラフにすると次のようになります。
頂点の数字がコース番号、辺にある赤い数字が重みです。この重みの値は先程の表にある「クリアに掛かる時間」の値です。まっはまん２では分岐コースが一方通行ではなく、反対側から進んでいくことが可能なので、分岐の方向を逆走できます。しかし見たところ、すべてのコースで分岐を逆走することはかえって遠回りになることが分かっているので分岐の方向は一方通行であるとします。
↑ダイクストラ法によって得られた最短経路はこの通りです。１－２の分岐で１－４へ繋がる方へ行くのが短くなりますが、８秒の差しかないため誤差によって逆転する可能性もあります。あまり変わらないという結果になりました。
ステージ２
グラフにするとこうなります。
分岐の数が増えてそろそろどれが最短になるか分からなくなるところです。
結果このようになりました。強制スクロールステージである２－９がやはりネックになって２－９を通る経路は選ばれませんでした。
また、コース数的にも２－５の方向へ進む分岐は採用されないことが分かります。
……とか思いましたが、コース数はどの分岐を選んでも同じになるように出来てるみたいです。そうするとやはりタイムの差で選ばれていないのでしょう。
ステージ３
グラフにするとこうなります。
実際には分岐を逆走することが出来ますので実質矢印はないようなものですが、逆走すると遠回りになることから、矢印をつけています。どっちのコースのクリアに掛かる時間を重みにするかが変わってしまうので、矢印をつけて方向を決めなければならないのです。
最短経路はこのようになりました。
３－４へ進む方向を選んだほうが３０秒ぐらい速くなるようです。また、３－９へ進む方向よりも３－８を経由した方が２０秒ぐらい速そうです。また、３－１９は長いので、３－１８を通る方向が選ばれました。またしても強制スクロールステージである３－７は選ばれませんでした。
以上より、それぞれのステージの最短経路が大雑把に求まりました。さっき試しにこの経路で進んでみましたが、気持ち速くクリアできた気がします＾＾；今まで一日でクリアしたことなかったので、一日でできただけ速そうですね！
もちろん厳密にはこれらの経路は異なる可能性もあります。厳密な最短経路を求めるのでしたら、それぞれのコースをTASなどを用いて最短でクリアし、そのタイムを比較して重みとして採用してください。後は上記の方法と同様にして最短経路が求められます。
これでタイムアタックとかできそうですね！
