Robloxプロシージャルダンジョン設計: BSP空間分割・ドロネー通路網・チャンク最適化

プロシージャル生成は、RobloxにおけるローグライクやハクスラRPGの根幹です。適切なアルゴリズムなしに生成すると、パーツ過多によるクラッシュや部屋の重なりが発生します。

BSPによる部屋の無衝突分割、ドロネー三角形分割とプリム法による自然なループ通路の形成、そしてRoblox標準の`StreamingEnabled`を連動させた次世代パイプラインを解説します。

1. 空間二分木（BSP）による均等な部屋配置

重なりを数学的に防ぐ再帰的空間分割の手法:

• 再帰的サブツリー分割: 領域を縦横ランダムな比率（0.4〜0.6）で分割し、目標サイズになるまで階層的に分割を繰り返します。
• アスペクト比制限: 細長すぎる不自然な部屋を排除するため、縦横比を1:1〜1:2.5の範囲に抑制します。
• 領域内への内接配置: 分割された末端ノード内に部屋を配置するため、重い当たり判定計算を行わずに部屋の重複を100%回避できます。

2. ドロネー三角形分割 & 最小全域木（MST）による通路形成

孤立や行き止まりのない有機的な回遊ルートの構築:

• 重心点群の抽出: 各部屋の中心座標を結ぶ平面2Dドロネー三角形網を作成し、近接する候補経路を網羅します。
• 最小全域木（MST）による簡略化: すべての部屋が最短距離で接続されるよう、冗長なエッジを刈り取ります。
• ループの再導入（15%）: 刈り取られたエッジの約15%をあえて復元することで、単調な一本道を防ぎ周回性を高めます。

3. グリッド通路の掘削とタイル配置

抽象的なグラフデータをRobloxの実パーツへ変換:

• 直角（L字・S字）配管: 部屋同士を直角に曲がる通路で結び、壁の接点にドアを自動配置します。
• 4ビットオートタイル: 上下左右の隣接状況から、直線壁・角壁・交差路のメッシュを自動選定します。
• パーツ統合: 床や壁をWelded ModelまたはEditableMeshで単一メッシュ化し、パーツ数を90%削減します。

-- BSP空間二分木ノード分割モジュール
local BSPNode = {}
BSPNode.__index = BSPNode

function BSPNode.new(x, z, width, depth)
    local self = setmetatable({}, BSPNode)
    self.X, self.Z = x, z
    self.Width, self.Depth = width, depth
    self.LeftChild = nil
    self.RightChild = nil
    self.Room = nil
    return self
end

function BSPNode:Split(minSize)
    if self.LeftChild or self.RightChild then return false end
    local splitHorizontal = math.random() > 0.5
    if self.Width > self.Depth and (self.Width / self.Depth) >= 1.25 then
        splitHorizontal = false
    elseif self.Depth > self.Width and (self.Depth / self.Width) >= 1.25 then
        splitHorizontal = true
    end
    local maxDimension = (splitHorizontal and self.Depth or self.Width) - minSize
    if maxDimension <= minSize then return false end
    local splitPos = math.random(minSize, maxDimension)
    if splitHorizontal then
        self.LeftChild = BSPNode.new(self.X, self.Z, self.Width, splitPos)
        self.RightChild = BSPNode.new(self.X, self.Z + splitPos, self.Width, self.Depth - splitPos)
    else
        self.LeftChild = BSPNode.new(self.X, self.Z, splitPos, self.Depth)
        self.RightChild = BSPNode.new(self.X + splitPos, self.Z, self.Width - splitPos, self.Depth)
    end
    return true
end

return BSPNode

4. メモリ削減とStreamingEnabledチャンク構造

モバイル端末の2GB RAMでも安定して100部屋以上の迷宮を動かす技術:

• ModelStreamingMode.Atomic: 部屋単位でまとめてストリーミングし、床抜け落下バグを防止します。
• 64x64 studsセクター分割: 遠方のダンジョン領域の物理演算を自動停止させ、CPU負荷を最小化します。
• オクルージョンカリング: 部屋間の扉やフォグを介して、視界外の部屋のレンダリングを完全にスキップさせます。

5. シード値（Seed）同期とサーバー権限のエンティティ生成

チート防止と通信帯域ゼロの完全同期:

• 決定論的シード同期: サーバーから32ビットの整数シードを1つ送るだけで、クライアント側で同一の地形が生成されます。
• サーバー主導の敵・宝箱配置: 見た目の床はローカルで描画しつつ、モンスターや罠の当たり判定はサーバー側でのみ確定します。
• 自動NavMesh構成: 生成された床にPathfindingModifierを自動設定し、敵AIが段差を認識して正確に追尾できるようにします。

Frequently Asked Questions