2009年12月16日

開放度を計算するぞ!

前回は迷宮をランダムに作成するところまではできたんだけど、ハマリにならないようにはどうしようか、というところで止まっていたと思う。
この問題に対する解決法はわりと簡単で、常にあいている壁がいくつになっているかを把握していればいい。
 
 
あいている壁って?

たとえば初期状態。

WSM000215.JPG

この状態だと、右に1個下に1個あいている壁がある状態だ。この状態を開放度2とする。

次に右に一歩進む。

WSM000217.JPG

今回生成した地図では、左右にだけ通路があり、上下は壁の状態にする。すると左の開放壁は消費してしまって開放度-1、右に新しい開放壁が現れたので+1、今の迷路全体の開放度は全体で2-1+1=2となる。

次にさらに右にもう一歩進もう。

WSM000216.JPG

今度は上だけ壁、左右下に通路がある状態になる。この状態では、左の開放壁を消費したので開放度-1、右と下に新しい開放壁が現れたので+2、今の迷路全体の開放度は2-1+3=3となる。

こんな感じで、新しいマップを生成するごとに開放壁を計算し、隣接する壁がすでに開放壁であると指定されていれば開放度に-1未確定であれば開放度に+1し続けると迷路全体で開放度が判断できる。この開放度が0以下にならないように迷路を生成するのが、自動生成マップのキモになるというわけだ

盲点はないか?

ただ、このアルゴリズムはとっても原始的なので、ハマリ状態みたいなのが存在する。たとえば以下のような場合。

WSM000218.JPG

開放度は4なんだけど、全ての開放壁がゴール地点の右下の方を向いていないので、ゴールできないという・・・
ま、こんなことになる可能性はほとんどないので、いざ起きたらもう一回開始位置からスタートしましょう、っていう感じでいいや。
いいよね?
posted by LoyalTouch at 16:34| Comment(0) | TrackBack(0) | 5つの宝島 | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:


この記事へのトラックバック