ゲーム開発 – 地形生成 アルゴリズム

こんにちは。開発担当のマットです。
 
以前の記事でも言ったことはありますが、ゲームが大好きです。
いろんなのゲームの中でも、とくに街づくりゲームが好きです。
 
街づくりゲームは沢山ありますが、内容はほとんどが似ていて何らかのマップの上で街を作っていきます。
しかし、一度成功すると二度目が面白くないので、毎回違う場所で街づくりをすることがポイントです。
 
そのため、ほとんどの街づくりゲームには、ランダム地形生成の機能が付いています。
なお、街づくりだけではなく、近年は多くのアクション・アドベンチャーゲームにも付くようになりました。
 

 
このランダム地形生成機能に興味を持って調べたので、今回の記事では３つのアルゴリズムを紹介したいと思います。
 
今回紹介します3つのアルゴリズムを使えば、ランダムマップを生成するゲームをより簡単に作ることができると思います。

私のようにゲーム作成に興味をお持ちの方は、ぜひ読んでみてください。

１:フラクタル・アルゴリズム

個人的な意見ですが、フラクタルアルゴリズムは島や海岸の生成に向いているアルゴリズムだと思うので、島を作っていきます。
 
まずはグリッドを想像します。
5×5を使いますが、思いのままに作っても問題ありません。

 
次は、島の大体の形を決めます。
私は、ちょっと丸目の島が欲しいので角のセル（A1,E1,E5,A5)を削ります。

 
各セルの中のランダムな箇所に点（ポイント）を置いて、繋げていきます。

 
少し島の形に近づきましたが、まだ直線が多すぎて不自然です。
次は、各ポイントの間の位置を計算します。（以下で緑の点で表します）

 
それぞれの新しいポイントをランダムに左右上下にずらして、繋げ直すと島がよりギザギザになります。

 
先ほどよりも島の形が見えてきました。
 
このステップを何度か繰り返せば、本当に海岸のような線が出来上がります。
実際に作ったものはこちらです。

２:ダイヤモンド・スクエア・アルゴリズム

ダイヤモンド・スクエア・アルゴリズムはとても簡単で、上記のフラクタル・アルゴリズムのような島づくりには適していると思います。
また、フラクタル・アルゴリズムと違って地形の高度を獲得することができます。
 
前回と同じようにグリッドを作ります。
サイズは 2ⁿ+1 × 2ⁿ+1 にするのが1番無難なので、このサイズをおススメします。
(つまり、5×5(2²+1 × 2²+1),9×9(2³+1 × 2³+1),1025×1025(2¹⁰+1 × 2¹⁰+1)など）
 
グリッドが出来上がったら、縁のセルの値を全部0にして真ん中のセルの値を1にします。
簡単な5×5のグリッドを例に説明したいと思います。

 
次は真ん中のセルと縁のセルの間のセルの値を計算します。
上記の例では、「真ん中のセルと縁のセルの間のセル」はB3,C2,D3,C4に当てはまります。

もちろん「間」と言ったら、「横縦の間」もありますし、「斜めの間」もあります。
この例では、「縦横の間」を使っていますが、実際に実装するときは両手段を併用するといいと思います。
ちなみに、このアルゴリズムの名前（ダイヤモンド・スクエア）はこの斜め、横縦を因んでいます。

間のセル（B3,C2,D3,C4）に、周囲のセルの数値の中間のランダム数値（もしくは平均値に近いランダム数値）を入れます。
C1が0で、C3が1となっているので、C2は0と1の間のランダム数値となります。

 
そのステップを繰り返し、全てのセルに値が入るまで続けます。
今、B3,C2,D3,C4の値を入れたので、次はB3,C2,D3,C4と縁の間のセルを埋めていきます。（つまりB2,D2,B4,D4)

やり方は色々あります。
例えばB2ですが、C2とA2の間のランダム数値を取ることもできますし、B3とB1の間のランダム数値を取ることもできます。
A2,B1,C2,B3の平均値に近い数値を取ることもできますし、A1,C1,B3,A3の平均値に近い数値を取ることもできます。
実装方法はプログラマーのお好み次第です。

 
最後に、全てのセルが埋まったら、高度の定義を行います。
例えば、0.2以下は海、0.7以上は山、その間は草、など。

 
上記の例はあまり綺麗ではないですが、ちゃんと実装すると以下のような島をランダムで生成できます。

先ほど言った通り、島に適しているアルゴリズムだと思いますが、縁や真ん中の値を0,1ではなくて、ランダムな数値で始めると、山と谷のような結果になります。

３：パーリン・ノイズ・アルゴリズム

ゲームの地形生成では、パーリン・ノイズ・アルゴリズムは1番使用されているかもしれません。

パーリン・ノイズの詳細を説明することは本記事の範囲外となりますが（詳しくはWikipedia）、簡単に説明すると、波の生成アルゴリズムです。

多くのプラットフォームにライブラリーが存在し、使うことによって、ランダム波のノイズを生成することができます。

 
ダイヤモンド・スクエア・アルゴリズムと同じように、海や山の閾値を設定することによって、地形を作成することができます。
以下の地図は上のパーリンノイズをベースにして作成しました。

まとめ

ゲームを作成するとき、リプレイアビリティ（繰り返し遊べること）は重視すべき要素だと思います。

この記事は街づくりのゲームの前提でアルゴリズムを紹介しましたが、これらのアルゴリズムを使えばRPG用の洞窟や宇宙ゲームの小惑星帯など、多くのエリアを自然に生成することができます。

毎回遊ぶとき、エリアが同じだとリプレイアビリティがなくなりユーザさんは遊ばなくなってしまうので、そうならないように、ぜひ上記の地形アルゴリズムを使って頑張って開発してみてください！