2D迷路データとその解を自動生成する(1):仕様策定

ひさびさの更新です。予告していた「2D迷路データを作成する」の件についてのエントリを連続投稿します。

ここでの論点は次の2つです。

1. どんな迷路を、どのようにつくるか
2. どのように迷路の解をつくるか

1つめの「どんな迷路を、どのようにつくるか」については、次のような仕様を考えました。

• 今回作成しているゲーム The Flame Kinght は、単なる迷路脱出ゲームではなく、 迷路上で敵と遭遇した場合に、炎で攻撃して戦ったり、すり抜けて避けたりするような、 アクション要素を持ったゲームです。そのため、フィールド内には 大きな広間のような場所があったり、廊下のような場所があったりといったように、 大きな構造としては変化のあるマップが作られることが望ましいです。
• 今回使用するマップチップはenchant.js組み込みで提供されている限られた種類の画像です。 そのため、ゲーム世界は基本的には「人工的に作られたダンジョン」とし、 小さな構造としては変化の少ないリアルっぽくないマップでも構わないものとします。
• 斜め上から見下ろすような視界とし、キャラクタの上半身が奥の壁に重なって表示されたり、 下半身が手前の壁に隠れたりするようにしたいです。

そういうわけで、これを、「穴掘り法」と呼ばれるアルゴリズムを基本に手を加えつつ、 (1)大きな構造の生成、(2)実際のMapに与えるdata生成、(3)細部の構造の生成、という 3段階に分けて、いろいろ作りながら試した結果を説明していくことにします。

次に、2つめの「どのように迷路の解をつくるか」です。

ここでは、単に複雑な迷路データを作るだけでなく、それと同時に、 この迷路上をスタート地点からゴール地点まで通り抜けるような経路データを作成する必要があるのです。 そうすれば、マップの自動生成時に、スタート地点から一番離れた場所にボスキャラやゴール地点を配置するなどの、 さまざまなニーズを満たすことができるはずです。このしくみを、 「ポテンシャル法」と呼ばれるアルゴリズムで実現する方法について、基本的な考え方、具体的な実装に分けて説明していきます。