マインクラフトやテラリアのようなゲームでは地形をランダムで生成しているのだけど、たまたまダンジョンや迷路のランダム生成アルゴリズムを調べてる際に発見した中点変位法によるフラクタル地形を見て、先述したゲームのような地形を生成できるのではないかと思いやってみた。
フラクタル地形とは?
基本的には2次元形式のフラクタルによる海岸線であり、コッホ曲線の確率論的生成と見なすことができる。
なんだそりゃ？という感じである。じゃーフラクタルってなんだろう。
フラクタルの具体的な例としては、海岸線の形などが挙げられる。海岸線は微視的にみると複雑に入り組んだ形状をしているが、これを拡大するとさらに細かい形状が見えてくるようになり、結果として拡大しても同じように複雑に入り組んだ形状をしている。これに対して、一般的な図形は、拡大するにしたがって、その細部は変化が少なくなり、なめらかな形状になっていく。
拡大し続けても複雑であり続ける図形、ということなのだろうか。ここを掘り下げていくといくら時間があっても足りなそうなので省略しよう。
中点変位法を使用してフラクタル地形を実装
正方形を4つの同じ大きさの小さい正方形に分割し、その中心の点を無作為な値で垂直方向に変位させる。この過程を4つに分けられた各正方形についても繰り返し、再帰的に実施して必要な詳細レベルに到達するまで行う。
なんか引用が多くなってきた。。
要するに、
- 地形を2次元の正方形とする
- その四隅の値をランダムに決める
- その中点の値を四隅の平均値+ランダムな値とする
- その中点で正方形を4分割し、値の決まってない頂点に他の頂点の平均値+ランダムな値をいれる
- 生成された正方形に対して上記処理を繰り返し行う
という感じに作る。
作るといっても ActionScript入門Wiki - 中点変位法でハイトマップを生成する にあるスクリプトがほぼそのまま使える。ありがたや。
#pragma strict
var blockPrefab:GameObject;
private var MAP_HEIGHT:int = 16;
private var MAP_SIZE:int = 32;
private var MIN_SIZE:int = 1;
private var MAX:Number = 1.0;
private var MIN:Number = 0.0;
private var gene_map:Number[,] = new Number[MAP_SIZE,MAP_SIZE];
private var map:int[,,] = new int[MAP_SIZE,MAP_SIZE,MAP_HEIGHT];
function Start () {
generateHeightmap(0, 0, MAP_SIZE, Random.Range(0.0, 1.0), Random.Range(0.0, 1.0), Random.Range(0.0, 1.0), Random.Range(0.0, 1.0));
for (var i=0; i<MAP_SIZE; i++) {
for (var j=0; j<MAP_SIZE; j++) {
var height = Mathf.RoundToInt(gene_map[i,j] * MAP_HEIGHT);
for (var k=0; k<height; k++) {
map[i,j,k] = 1;
var position:Vector3 = Vector3(j,k,i);
var rotation = transform.rotation;
Instantiate(blockPrefab, position, rotation);
}
}
}
}
function Update () {
}
function generateHeightmap(x:int, y:int, size:Number, tl:Number, tr:Number, bl:Number, br:Number) {
// minSize未満のサイズになったら分割を終了させる
if (size < MIN_SIZE) {
// 平均値を出す
var val:Number = (tl + tr + bl + br) / 4;
gene_map[x,y] = val;
} else {
// 四隅から見て中央にあるピクセルに平均値 + 変位させるランダムな値を入れる
var midPoNumber:Number = (tl + tr + bl + br) / 4 + getRandomHeight(size);
// min～max(0.0～1.0)までの値に収まるように調整
if (midPoNumber < MIN) midPoNumber = MIN;
if (MAX < midPoNumber) midPoNumber = MAX;
// 中央から見て上下左右にあるピクセルにも平均値を入れる
var top:Number = (tl + tr) / 2;
var bottom:Number = (bl + br) / 2;
var left:Number = (tl + bl) / 2;
var right:Number = (tr + br) / 2;
// 2*2に分割するのでサイズ(幅, 高さ)を半分にする
size /= 2;
generateHeightmap(x, y, size, tl, top, left, midPoNumber);
generateHeightmap(x + size, y, size, top, tr, midPoNumber, right);
generateHeightmap(x, y + size, size, left, midPoNumber, bl, bottom);
generateHeightmap(x + size, y + size, size, midPoNumber, right, bottom, br);
}
}
public function getRandomHeight(val:Number):Number {
return (Random.Range(0.0, 1.0) - 0.5) * val / MAP_SIZE;
}
これでテクスチャ貼れば見た目だけはマイクラっぽい。