この記事では、Godot4でダイヤモンド・スクエアアルゴリズムを実装するためのプログラムと地形生成に深くかかわるフラクタル地形という概念について紹介していきます。
プログラムのみ確認する場合、「実装（Godot4）」まで読み飛ばしてください。
はじめに
Minecraftや、No Man's Skyでは、無限に生成される世界で遊ぶことができます。
これらの世界は、地形生成アルゴリズムと総称される現実の山や川、海や谷のような地形をコンピュータで再現できるアルゴリズムを活用し作られています。
私はこのアルゴリズムの存在を知ったとき、まるで天地創造で神様みたいだなと思いました。実装できたら、神様気分を味わえるかもしれません（？）
この記事では、フラクタル地形を生成するアルゴリズムの一つである「ダイヤモンド・スクエアアルゴリズム」を紹介します。
フラクタル地形ってなに？
ここで、３行ほど前に突然出現したフラクタル地形という言葉に引っ掛かった方がいるかもしれません。少なくとも私は引っ掛かりました。地形生成アルゴリズムについて調べているといつも「フラクタル地形」の記事が一緒にヒットしたりサジェストに出たりします。
私は、フラクタルに対して、下の図のような再帰の勉強で実装させられまくるきしょい画像というイメージを強く持っていました。
しかし、フラクタルはただのきしょいだけの図形ではなかったようです。
実は、現実の山や海岸線はフラクタルなのです。
そもそも、「フラクタル」とは、物体の拡大された部分が全体と同じ、あるいは類似しているという性質を有する構造のことです。これらの性質は、「自己相似性」と呼ばれています。
例えば、山を遠方から眺めるとたくさんの峰（山の頂上）が連なっていることがわかります。さらに、その山に登頂したり、あるいは望遠レンズなどで覗いてみると、山にはいろいろな方向へ流れる丘がたくさんあることに気が付くかもしれません。
もっと山を間近で見てみると、平面やなだらかな丘に見えた地形も意外とボコボコと隆起していることに気が付きます。（この画像は、多くの人が行き来する場所で撮影されたため100%自然のものであるとも言い難いですが、なんとなくのイメージです。）
これらは、まさに「自己相似性」と呼ばれるものです。大きな山は複数の小さな小山のような地形が集まってできています。
このような自己相似性は、海岸線などにもみられます。大きな地形には、
よく見ると小さなボコボコがたくさんあります。
ダイヤモンド・スクエアアルゴリズムでは、同じ処理（ダイヤモンドステップとスクエアステップ）で大まかな地形から細かな地形を生成します。つまり、どの処理でもいじくる地形の細かさが異なるだけでやってることは同じなのです。先ほど山の話で、
大きな山は複数の小さな小山のような地形が集まってできています。
と記述しましたが、これはダイヤモンド・スクエアアルゴリズムで実装した地形でも似たような特徴を持ちます。
ダイヤモンド・スクエアアルゴリズム
1. 概要
ダイヤモンド・スクエアアルゴリズムは、
2Dの格子状の点に高さを設定して、各点の中間点を計算することで新しい高さを決定し、その後、地形のスケールを小さくしながらこれを繰り返す。 by ChatGPT
というアルゴリズムです。
スライドで詳しく説明します。
このアルゴリズムでは「ダイヤモンドステップ」と「スクエアステップ」という処理をスクエアの大きさを小さくしながら繰り返し行います。
それぞれのステップは以下のような処理です。
| 名称 | 説明 | 該当するスライド |
|---|---|---|
| ダイヤモンドステップ | スクエアの中心の点の値を計算 | 5, 15~18 |
| スクエアステップ | ダイヤモンドの中心の点（スクエアの辺の中点）の値を計算 | 6~12, 19~30 |
どちらのステップでも、スクエアやダイヤモンドの点が持つ値の平均値に-th ~ thの間の乱数が足される形で中心の点が計算されます。thは地形の激しさを決める閾値で、スクエアの辺の長さに比例して小さくなっていきます。
実装（Godot4）
1. 二次元配列🤬
まずは、準備のために二次元配列を作成します。
が、
GOdotには二次元配列が用意されていません。2Dに強いゲームエンジンなのになんで？？
一次の配列のインデックスを毎回考えながら扱うのは面倒に感じたので、私の実装では二次元配列を行うクラスを用意してプログラムを書きました。
ここで便利なのは、class_nameです。これを使うと、「スクリプトを名前を持つグローバルにアクセス可能なクラスとして定義」することができます。
参照：GDScriptリファレンス
https://docs.godotengine.org/ja/4.x/tutorials/scripting/gdscript/gdscript_basics.html
ファイルシステムの中のよさげな位置にArray2d.gdやarray2D.gdのようないい感じの名前を付けたGDScriptを作成して、
@icon("res://assets/arr2.png")
class_name Array2d
と書き込みます。一行目のicon()は、class_nameで定義するクラスのアイコンを指定するために使います。なくても問題ありませんがあるとワクワクします。私は絵文字ジェネレーターというサイトで絵文字を作成してアイコンとして利用しています。
その下には、二次元配列の操作に使いそうなコードを書いていきます。
具体手的には、コンストラクタ的なやつを作ったり、
func _init(num: int):
init(num)
func init(num: int):
_size = num
for i in range(_size ** 2):
pool.append(DEFAULT_NUM)
データを得る関数を作ったり、
func get_data(x: int, y: int) -> float:
return pool[y * _size + x]
func get_data_from_index(index: int) -> float:
return pool[index]
func get_row(y: int) -> Array:
return pool.slice(y * _size, (y + 1) * _size)
func get_column(x: int) -> Array:
var result: Array
for i in range(_size):
result.append(pool[i * _size + x])
return result
値を設定する関数を用意したり、
func set_data(num: float, x: int, y: int) -> void:
pool[y * _size + x] = num
func set_row(y: int, row: Array) -> void:
if(len(row) == _size):
for x in range(_size):
set_data(row[x], x, y)
func set_column(x: int, row: Array) -> void:
if(len(row) == _size):
for y in range(_size):
set_data(row[y], x, y)
func set_data_by_index(num: float, index: int) -> void:
pool[index] = num
しました。あとは、デバッグ用に出力する関数もあると便利でした。
2. メインシーンを作る
メインシーンはNode3Dにして以下のような子ノードをぶら下げておけば最低限動くと思います。
Node3D/
├── DirectionalLight3D
├── GridMap
├── Camera3D
└── WorldEnvironment
今回は、説明のために最低限の機能で実装したいのでGridMapに直接スクリプトをアタッチします。
extends GridMap
変数はスライドの内容と同じく、配列のサイズと地形の激しさを決めるthを用意しておきます。
var size: int = 2 ** 8 + 1
@export var th: float = 1.0
それでは、アルゴリズムを実装していきます。基本的にはスライドの内容とやっていることに違いはありません。
get_terrain_data()では、配列を用意して四つ角に同じ乱数を入れています。（スライドの1, 2ページ目に対応）。それ以降は、関数名のままなので、スライドを見ながらコードを読んだほうがわかりやすいと思います。
func get_terrain_data(num: int) -> Array2d:
var terrainMap = Array2d.new(num)
var init_num = randf_range(-th, th)
terrainMap.set_data(init_num, 0, 0)
terrainMap.set_data(init_num, 0, num - 1)
terrainMap.set_data(init_num, num - 1, 0)
terrainMap.set_data(init_num, num - 1, num - 1)
apply_diamond_square(terrainMap)
return terrainMap
func apply_diamond_square(array2: Array2d):
var size = array2.size() - 1
var scale = th
while size > 1:
var half_step = size / 2
apply_diamond_step(size, half_step, scale, array2)
apply_square_step(size, half_step, scale, array2)
size /= 2
scale /= 2.0
func apply_diamond_step(size: int, half_step: int, scale: float, array2: Array2d):
for y in range(0, array2.size() - 1, size):
for x in range(0, array2.size() - 1, size):
var avg = (
array2.get_data(x, y) +
array2.get_data(x + size, y) +
array2.get_data(x, y + size) +
array2.get_data(x + size, y + size)
) / 4.0
array2.set_data(avg + randf_range(-scale, scale), x + half_step, y + half_step)
func apply_square_step(size: int, half_step: int, scale: float, array2: Array2d):
for y in range(0, array2.size(), half_step):
for x in range((y + half_step) % size, array2.size(), size):
var avg = (
array2.get_data((x - half_step + array2.size()) % array2.size(), y) +
array2.get_data((x + half_step) % array2.size(), y) +
array2.get_data(x, (y + half_step) % array2.size()) +
array2.get_data(x, (y - half_step + array2.size()) % array2.size())
) / 4.0
array2.set_data(avg + randf_range(-scale, scale), x, y)
あとは、地形をGridMap上に置いていきます。GridMapで使うmeshLibraryを作成するためには、適当なNode3Dが親のシーンを作成してその子にMeshInstance3Dを作成し、適当に名前を変更したのち、
それぞれの
MeshInstance3DにMeshからBoxMeshを割り当て、
そのBoxMeshにMaterialからStandardMaterial3Dを割り当て、
そのStandardMaterial3DからAlbedo->Colorで好きな色を割り当ててください。
Meshinstance3DにMeshやMaterialを割り当てたのちに複製すると、複製されたノードは同じアドレスを持つMeshとMaterialを引き継いでしまいます。 この状態だと、一つのMaterialやMeshに変更を加えるだけですべてに変更が加わってしまいます。これは、それぞれのMeshを右クリックしてユニーク化（再帰的）を選択することで解消できます。
それが終わったら、左上のシーン -> エクスポート -> メッシュライブラリの順にクリックすることでメッシュライブラリを作成できます。
最後に、生成された地形データからグリッドにセルアイテムを置くプログラムを書いたり、
func create_terrain():
clear()
var worldMap : Array2d = get_terrain_data(size)
set_terrain_blocks(worldMap)
func set_terrain_blocks(worldMap : Array2d):
var half_size = size / 2
position = Vector3(half_size * -1, 0, half_size * -1)
for y in range(size):
for x in range(size):
var h_data : float
h_data = worldMap.get_data(x, y)
if(h_data != 0):
set_block(x, y, h_data)
func set_block(x: int, y: int, h_data: float):
var locate: Vector3i = Vector3i(x, h_data * size / 10, y)
var id = 4
if(0.6 < h_data):
id = 3
elif(0.2 < h_data):
id = 0
elif(-0.2 < h_data):
id = 1
elif(-0.6 < h_data):
id = 2
set_cell_item(Vector3i(locate.x, locate.y, locate.z), id, 0)
プロジェクトの実行時に、地形生成を始める関数を割り当てれば完成です。
func _ready():
create_terrain()
後は、アルゴリズムを区切りながら実行できる仕組みを作ったり、メッシュリブラリを豪華にしたり、カメラを回転させたり、メッシュに当たり判定を付けたり、、、、
様々な遊び方ができると思います。
以下のようにノードを配置してからmeshLibraryとしてエクスポートすることで、簡単にブロックの当たり判定を実装できます。
MeshInstance3D/
└── StaticBody3D/
└── CollisionShape3D
ひとこと
ダイヤモンド・スクエアアルゴリズムを理解することで、自己相似性やフラクタルという概念の面白さを知ることができたので、皆さんもぜひ実装してみてください！
（この投稿のスライドは2025年3月に参加した日本大学文理学部、日本大学工学部、会津大学の３サークル合同LT会で発表したスライドを抜粋して利用しています。）