Procedural Dungeon Generation in Roblox: BSP Rooms, Delaunay Corridors & Chunk Streaming

Procedural generation is the core engine powering roguelikes, crawler RPGs, and survival games on Roblox. Without careful algorithmic design, generated maps quickly exceed Roblox's memory budget, causing lag spikes, memory crashes, and awkward geometry intersections.

By integrating Binary Space Partitioning (BSP) for recursive room subdivision, Delaunay Triangulation with Prim's MST algorithm for natural corridor loops, and Roblox's native `StreamingEnabled` chunk boundaries, developers can build infinite, lightweight dungeons that load instantaneously.

1. Room Generation via Binary Space Partitioning (BSP)

Recursive space subdivision for balanced room distribution:

• Recursive Subtree Splitting: Start with a bounding box and split horizontally or vertically at randomized ratios (0.4 to 0.6) until leaf nodes reach the target room dimensions.
• Padding & Aspect Ratio Clamping: Enforce strict minimum width-to-height aspect ratios (1:1 to 1:2.5) and edge padding to prevent claustrophobic pencil-thin rooms.
• Leaf Node Room Inscription: Inscribe a randomized rectangular room within each partition boundary, guaranteeing non-overlapping room placement without expensive collision testing.

2. Natural Corridors: Delaunay Triangulation & Minimum Spanning Trees (MST)

Connecting rooms with organic flow while eliminating dead-ends:

• Centroid Point Clouds: Extract the center coordinates of all rooms to construct a planar 2D Delaunay Triangulation graph of possible corridor pathways.
• Prim's Minimum Spanning Tree: Prune the Delaunay graph down to an MST that guarantees every single room is reachable with the shortest total corridor length.
• Loop Re-Injection (15% Extra Edges): Add back 12–18% of pruned Delaunay edges into the graph to create cyclical loops, preventing monotonous backtracking in gameplay.

3. Grid-Based Corridor Carving & Tile Instancing

Translating graph edges into physical Roblox geometry:

• L-Shaped & S-Shaped Corridor Routing: Connect room pairs with orthogonal right-angle bends, placing doorway thresholds at room wall boundaries.
• Tilemap Bitmasking: Use 4-bit autotiling rules (North, East, South, West adjacency) to select the correct floor, straight wall, corner, or intersection mesh.
• Collision-Free Geometry Instancing: Pre-fabricate corridor segments as welded models or use EditableMesh to merge floor tiles into continuous low-part meshes.

-- Binary Space Partitioning (BSP) Room Tree Splitter
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. Memory Culling & StreamingEnabled Chunk Architecture

Scaling massive dungeons without exceeding mobile memory limits:

• ModelStreamingMode.Atomic: Wrap individual rooms and connected corridors into atomic models so Roblox streams them into memory as complete units without popping walls.
• Spatial Sector Partitioning: Organize dungeon geometry into 64x64 stud chunk containers, unparenting or disabling physics on distant sectors until players approach.
• Dynamic Occlusion Culling: Close doorways and place fog portals between rooms to allow Roblox's occlusion engine to skip rendering off-screen dungeon chambers.

5. Seed Replication & Authoritative Gameplay Spawns

Preventing client-side desync while securing loot and enemy encounters:

• Deterministic Seed Replication: The server broadcasts a single 32-bit pseudo-random seed integer to all clients; both client and server generate identical geometry locally.
• Server-Authoritative Entity Spawns: While cosmetic floor tiles render locally, enemy NPCs, treasure chests, and trap triggers spawn strictly from the server.
• NavMesh Generation & Pathfinding: Bake PathfindingModifiers into floor tiles to guide NPC pathfinding seamlessly around procedural obstacles and chasms.

Frequently Asked Questions