だいぶ空きましたが久々にgodot触ってみることに。
godotも4.6になってましたのでこの記事の内容はgodot4.6.2で実行しています。
今回からはGemini先生の協力のもと作られてます。
１．二分空間分割（BSP）とは
BSP（Binary Space Partitioning：二分空間分割）は、「大きなエリアをバッサリ2つに分ける」 という操作を再帰的に繰り返して、空間を細かく管理する技術です。
ランダムダンジョン生成においては、迷路のような複雑な構造を作るための「下書き（区画分け）」として活用されます。
- 主な目的: 重なりのない個別の部屋スペースの確保と、それらを繋ぐ論理的な経路（ツリー構造）の構築。
- 特徴: 分割を繰り返す性質上、すべての部屋がどこかで必ず繋がる（孤立した部屋ができない）構造を作りやすいメリットがあります。
２．ダンジョン生成の３ステップ
- 空間を分割する
まずは大きな長方形を用意し、それを「縦」か「横」にランダムな位置で分割します。分かれた2つの空間を、さらにそれぞれ分割していきます。これを数回繰り返すと、画面が大小さまざまな「区画」で埋め尽くされます。 - 部屋を配置する
分割してできた一番小さな区画の中に、一回り小さい「部屋」を作ります。区画いっぱいに作らずに少し余裕を持たせることで、部屋同士がくっつかない独立した空間が生まれます。 - 道（通路）でつなぐ
最後に、分割したときに出きた「ペア（兄弟）」の区画同士を細い通路でつなぎます。これを繰り返すと、すべての部屋がどこかでつながっている、歩き回れるダンジョンの完成です！
３．【step1】空間の分割
# ダンジョンエリアの分割
# ダンジョン生成の１段階目、部屋を作成するためにダンジョンエリアを分割していく
# @area : 分割前のエリア
# @times : あと何回内側を分割するかの回数
func split_rect(area: Dictionary, times):
# 分割前のエリア面積（マス数）
var area_mass = area["rect"].size.x * area["rect"].size.y
# 3％かの確率で、それ以上分割せずに「ここを末端の部屋にする」
if randf() < 0.03 + (SPLIT_COUNT - times) * 0.05:
return
# 分割回数が終わったか、エリアがこれ以上割れないほど小さい場合は終了する
if times <= 0 or area_mass < MIN_AREA_SIZE:
return
# エリアを分割する
var a1: Rect2i
var a2: Rect2i
# 【分割】長い方の辺を割る（バランスを保つため）
var split_horizontal = area["rect"].size.x > area["rect"].size.y
if split_horizontal:
# 縦に分割線を入れる（左右に分かれる）
# 極端な分割を避けるため、中心から20%〜80%の範囲内でランダムに決定
var margin = int(area["rect"].size.x * 0.20)
var split_x = randi_range(margin, area["rect"].size.x - margin)
a1 = Rect2i(area["rect"].position.x, area["rect"].position.y, split_x, area["rect"].size.y)
a2 = Rect2i(area["rect"].position.x + split_x, area["rect"].position.y, area["rect"].size.x - split_x, area["rect"].size.y)
else:
# 横に分割線を入れる（上下に分かれる）
var margin = int(area["rect"].size.y * 0.20)
var split_y = randi_range(margin, area["rect"].size.y - margin)
a1 = Rect2i(area["rect"].position.x, area["rect"].position.y, area["rect"].size.x, split_y)
a2 = Rect2i(area["rect"].position.x, area["rect"].position.y + split_y, area["rect"].size.x, area["rect"].size.y - split_y)
# 分割して、新しい辞書を left と right に入れる
area["left"] = { "rect": a1, "left": null, "right": null, "room": null }
area["right"] = { "rect": a2, "left": null, "right": null, "room": null }
# 【再帰】さらに深く分割し、戻り値として「各エリア内の部屋の地点」を受け取る
split_rect(area["left"], times -1)
split_rect(area["right"], times -1) 最初にダンジョン全体のエリアを渡すとエリアを分割しtimesの回数分分割したエリアをさらに分割していきます。
エリアは辞書型になっていて以下のように定義しています。
var root_area = {
"rect": Rect2i(2, 2, MAP_WIDTH - 4, MAP_HEIGHT - 4),
"left": null,
"right": null,
"room": null # 通路作成用
}最初に渡すエリアをダンジョン全体エリはではなく外側2周分を外した内側にしています。外側2周分は常に壁ということにしてます。このため分割と部屋生成時に外側の壁は考慮してません。
BSPのアルゴリズム的には縦と横の長い方をランダムの長さ（20％～80％の間）で分けて二つのエリアにしてます。
分けた二つのエリアをarea[“left”]area[“right”]に設定し同じ関数を再帰的に実行しています。
終了判定は最初に渡されたtimes回数再帰されるか分割前のエリアが最低サイズ（マス数）より低いと処理が止まります。
分割され他エリア情報は最初の全体エリアからツリー構造のデータとして作成されます。
11行目の if randf() < 0.03 + (SPLIT_COUNT – times) * 0.05:はダンジョンのランダム性を増す為というか、大部屋を作るために確率で分割処理を途中で止めるための判定です。
４．【step2】部屋の生成
# エリアの中に小部屋を作る関数
# ツリーの末端エリア（子エリアが無いエリア）に部屋を作成
func create_room_in_area(area: Dictionary):
# 1. 再帰処理：子エリア（left/right）がある場合は、さらに深く潜る
if area["left"] != null and area["right"] != null:
create_room_in_area(area["left"])
create_room_in_area(area["right"])
return # 子を持つ親エリアには部屋を作らない
# 2. 末端エリア（葉ノード）に到達した場合の処理
var rect = area["rect"]
# 【サイズ決定】
# 2x2を最小とし、最大はエリアの幅・高さピッタリまで
var w = randi_range(2, rect.size.x)
var h = randi_range(2, rect.size.y)
# 【座標決定】
# 「エリアの開始位置 + 余白（エリア幅 - 部屋幅）の範囲でランダム」
# これにより、wが最小でも最大でも、絶対に rect の範囲を飛び出しません
var x = rect.position.x + randi_range(0, rect.size.x - w)
var y = rect.position.y + randi_range(0, rect.size.y - h)
# データを保持(通路作成用)
area["room"] = Rect2i(x, y, w, h)
# 3. 指定範囲を「床」で塗りつぶす
# map_data辞書に座標を登録し、TileMapLayerで描画できるようにする
for ty in range(area["room"].position.y, area["room"].end.y):
for tx in range(area["room"].position.x, area["room"].end.x):
map_data[Vector2i(tx, ty)] = Tile.FLOOR
step1で分割したエリアに部屋を作成します。
分割処理で作成されたエリアのツリー情報をさかのぼっていき、小エリアが無いエリア（末端エリア）に部屋を1個作成していきます。
部屋のサイズと位置はランダムに設定していますがエリアをはみ出さないように判定しいます。
エリアの端と端に部屋が作られると部屋がくっついた状態になりますが、四角以外の部屋も有りかと思ってそのまま作成しています。
５．【step3】通路の接続
# 全エリアを巡回して、分割されたペア（leftとright）を通路で繋ぐ
func connect_areas(area: Dictionary):
# 子エリアがない（末端）なら、繋ぐ相手がいないので終了
if area["left"] == null or area["right"] == null:
return
# 再帰的に下の方から先に繋いでいく
connect_areas(area["left"])
connect_areas(area["right"])
# このエリアの left と right の「代表地点」を取得して通路を引く
var start_pos = get_representative_point(area["left"])
var end_pos = get_representative_point(area["right"])
# 50%の確率で「横→縦」か「縦→横」の曲がり方を決める
if randf() > 0.5:
# 横に動いてから縦に動く
while start_pos.x != end_pos.x:
map_data[start_pos] = Tile.FLOOR
start_pos.x += 1 if end_pos.x > start_pos.x else -1
while start_pos.y != end_pos.y:
map_data[start_pos] = Tile.FLOOR
start_pos.y += 1 if end_pos.y > start_pos.y else -1
else:
# 縦に動いてから横に動く
while start_pos.y != end_pos.y:
map_data[start_pos] = Tile.FLOOR
start_pos.y += 1 if end_pos.y > start_pos.y else -1
while start_pos.x != end_pos.x:
map_data[start_pos] = Tile.FLOOR
start_pos.x += 1 if end_pos.x > start_pos.x else -1
# エリア内の「通路の起点」となる座標を返す
func get_representative_point(area: Dictionary) -> Vector2i:
# 部屋がすでにあるなら、その中心を返す
if area["room"] != null:
return area["room"].get_center()
# 部屋がない（もっと深く分割されている）なら、さらに下から座標を持ってくる
# ここでは適当に left 側を代表として追いかける
return get_representative_point(area["left"])
分割した「親」が持っている2つの「子」の部屋同士を最短距離で接続。
この処理の肝はget_representative_pointかな？小エリアを複数持つ大親間は各一番右（上）の部屋を繋ぐようになっています。その結果、大エリア内の他の部屋を貫通してつないでいます。
貫通問題は気にはなったのですが、今回の規模だとそこまで違和感なかったのでコード追加の労力と天秤にかけてスルーすることにしました（笑
解説動画とかも見たりしましたが、そこでは一番近い部屋をつなげるとかしてました。
６．実行結果
色付きの線はエリア分割を視覚化したものです。
何回か回した感想ですが、部屋の貫通は思ったより少ない感じで部屋の合体は結構頻発してる気がします。
統計取ってるわけではないのであくまでも感想ですけど・・
実際にゲームとして動かすときは拡大してスクロールする感じにしようかと思ってます。
シレンぽいか？と言われるとそうでもない感じですね（笑
７．終わりに
久々にgodotさわってみました。とはいえGemini先生にコード書いてもらって少し手直しする程度ですが・・・
AIが全部やってくれるので記事書く意味がない気もしますが、一応自分の復習用ということで
毎回この辺で止まるのでもう少し頑張りたい所です（汗
ソースはGithubにアップロードしています。
