Prozedurale Dungeon-Generierung in Roblox: BSP-Räume, Delaunay & Chunk-Streaming

Prozedurale Generierung ist das Herzstück moderner Roguelikes und Crawler-RPGs auf Roblox. Schlecht geplante Algorithmen führen zu Speicherüberlastungen und unschönen Geometrie-Kollisionen.

Mithilfe von BSP zur Raumaufteilung, Delaunay-Triangulation für natürliche Rundwege und Roblox StreamingEnabled lassen sich gewaltige, performante Dungeons erschaffen.

1. Raumaufteilung mittels Binary Space Partitioning (BSP)

Rekursive Raumunterteilung für ausgewogene Grundrisse:

• Rekursive Teilung: Die Gesamtfläche wird wiederholt horizontal oder vertikal im Zufallsverhältnis geteilt, bis die Blattknoten die Zielgröße erreichen.
• Seitenverhältnis-Beschränkung: Strikte Begrenzung (1:1 bis 1:2.5) verhindert unpassend schmale Schläuche als Räume.
• Kollisionsfreie Einbettung: Räume werden innerhalb der Grenzen platziert, wodurch Überschneidungen mathematisch ausgeschlossen sind.

2. Natürliche Gänge: Delaunay-Triangulation & Minimaler Spannbaum (MST)

Organische Vernetzung aller Kammern ohne Sackgassen:

• Zentroid-Punktwolken: Raumzentren bilden die Basis für ein planares 2D-Delaunay-Netzwerk möglicher Gänge.
• Prim-Algorithmus (MST): Reduzierung des Netzes auf den kürzesten zusammenhängenden Baum ohne isolierte Räume.
• Zyklische Schleifen (15% Bonus-Kanten): Wiedereinfügen von 15% der Kanten sorgt für spannende Rundwege statt linearer Schläuche.

3. Rasterbasierter Gangbau & Mesh-Instanziierung

Umsetzung der Graphen in physische Roblox-Geometrie:

• Orthogonale L-Verbindungen: Rechtwinklige Korridore verbinden die Räume über saubere Türschwellen.
• 4-Bit-Autotiling: Automatische Auswahl passender Wand-, Eck- und Boden-Meshes je nach Nachbarschaft.
• Mesh-Zusammenführung: Bündelung von Bauteilen verringert die Part-Anzahl um bis zu 90%.

-- BSP-Knoten-Teilungsmodul
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. Speicher-Culling & StreamingEnabled-Architektur

Riesige Welten stabil auf Mobilgeräten ausführen:

• ModelStreamingMode.Atomic: Räume werden als geschlossene Einheiten geladen, um visuelle Löcher zu vermeiden.
• Sektor-Partitionierung: Weit entfernte Dungeon-Bereiche werden physikalisch deaktiviert, bis der Spieler naht.
• Okklusions-Culling: Türen und Nebelportale verhindern das Rendern verdeckter Kammern.

5. Deterministische Seeds & Server-Autorität

Latenzfreie Kartenerstellung bei maximaler Cheatsicherheit:

• Seed-Replikation: Ein einzelner 32-Bit-Zufalls-Seed synchronisiert die Geometrie zwischen Client und Server.
• Server-Autoritative Spawns: Monster, Fallen und Schatztruhen werden ausschließlich serverseitig erzeugt.
• NavMesh-Generierung: PathfindingModifier auf Bodenteilen gewährleisten sauberes NPC-Pathfinding.

Frequently Asked Questions