生成した迷路のスタートとゴールを決める【前編】
はじめに
迷路を生成した次には、スタートとゴールの位置を決定する必要があります。その位置を決定する方法には少し工夫が必要です。この【前編】では、位置を決める上での問題点を説明します。
まず、説明用に以下の簡単な迷路を例に上げます。
黒: 壁(wall), 白: 道(path)
この迷路での最適なスタートとゴールの位置は以下のようになります。
赤: スタート位置, 青: ゴール位置, 橙色: 経路
このようにスタートとゴールの位置を設定すれば、生成した迷路を最大限に活かせていると言えるでしょう。
スタートとゴールを決定する方法の”問題点”
完全ランダムで決める
これは実装がとても容易です。道の中で、重複しないようにスタートとゴールを決めるだけです。
しかし、以下のような問題点があります。
スタートとゴールの位置がとても近くなってしまうことがあるということです。
これでは、一瞬でゴールにたどり着いてしまいます。スタートとゴールが隣り合っていなかったとしても、経路が短くなってしまう可能性は十分あります。
スタートを決めて、スタートからの最長経路でゴールを決める
この方法を使えば、完全ランダムの場合のようにスタートとゴールの位置が隣り合ってしまうことはなくなります。ある程度長さのある経路となりそうです。
しかし、この方法でも以下のような問題点があります。
最長となる経路の半分の位置にスタートがあると、経路として使われない部分が半分近く出来てしまうということです。最初の分岐でゴールがある方を選択するのかどうかで、ゴールに辿り着くまでの時間が大きく変わってきそうです。
良い方法は？
スタートとゴールをどのように決定したら、生成した迷路を最大限に活かせるのか。悩んだ末に、いくつか方法を考えました。その方法については【後編】で解説したいと思います。
【後編】はこちら！
