Elysium: The Forsaken Dungeons

The backend of a Roblox action RPG: procedural dungeons, a server-owned inventory, and weighted loot drops. Written in Luau.

This is a JavaScript port of the in-game generator, scaled down to 26 rooms. It runs the same steps as the Luau version, so every click builds a new dungeon.

Dungeon generation

Each run places 100 rooms on a grid and turns them into one connected dungeon in six steps, entirely on the server.

The real generator in Studio: rooms are placed, corridors are carved between them, then straight runs merge into larger hallway pieces.
  1. Place rooms on a 36-stud grid

    Rooms land on random grid cells, and overlaps are rejected with GetPartBoundsInBox. Each room opens one of its four doors at random. The first room is the start; the room farthest from it becomes the boss room.

  2. Triangulate the doors

    An incremental Delaunay triangulation (Bowyer–Watson) connects door positions. Points are inserted in x order, so triangles whose circumcircle falls behind the sweep are finished early instead of being re-tested. Coordinates are normalized to a unit square to keep the circle math stable.

  3. Filter, then repair connectivity

    Skinny triangles and edges longer than 12 cells are dropped. Union–find tracks which rooms are still connected and reconnects any that were cut off using the shortest discarded edges. Both limits are Studio attributes, so they can be tuned without touching code.

  4. Build a spanning tree, then add loops

    Prim's algorithm on a binary min-heap picks the shortest set of connections. Edges that lead back to visited rooms get a 1-in-10 chance to stay, up to 11, so players get loops instead of a strict tree.

  5. Carve the corridors

    For each connection, a greedy best-first search walks the grid and spawns hallway blocks. Rooms block the search; touching an existing hallway reuses it, so corridors merge into shared halls.

  6. Merge pieces and furnish rooms

    A depth-first walk over the hallway graph merges straight runs of 2–4 blocks into longer prefab halls and 2×2 clusters into large chambers. A room setter then places the shop and assigns ambush, easy, trap and mini-boss rooms from prefab pools.

Why greedy search instead of A*

The earlier pathfinder was A*, ordering cells by distance travelled plus distance left. Ordering by distance left alone explores far fewer cells per corridor. The trade-off is that corridors aren't always the shortest route, which suits a dungeon. Both versions use the same custom heap, so the switch was one comparison.

Sweep step of the triangulation: finished triangles are retired without a circle test.
for i = #active, 1, -1 do
  local t = active[i]
  local remove = false
  -- X-sorted insertion: completed circles
  -- cannot contain future points.
  if t.right < v.x - 1e-12 then
    finish(t); remove = true
  else
    local dx, dz = v.x-t.x, v.z-t.z
    if dx*dx+dz*dz <= t.radius2+tolerance then
      edge(t[1],t[2]); edge(t[2],t[3]); edge(t[3],t[1])
      remove = true
    end
  end
  if remove then
    active[i] = active[#active]; active[#active] = nil
  end
end
Prim's algorithm keeps a few edges back to visited rooms to create loops.
for _, newEdge in ipairs(graph[to]) do
  local ranNum = math.random(1,10)
  if not visited[newEdge.endnode] then
    pq:Enqueue(newEdge)
  elseif newEdge.endnode ~= from
     and ranNum == 1 and #randomLines < 11 then
    table.insert(randomLines, {From = newEdge.startnode,
      To = newEdge.endnode, Distance = newEdge.distance})
  end
end
The pathfinder's heap orders cells by the Manhattan heuristic only, which makes it greedy.
local function GetHeuristic(posA, posB)
  return math.abs(posA.X - posB.X)
       + math.abs(posA.Z - posB.Z)
end

function PathPQ3:_heapifyUp(index)
  while index > 1 do
    local parent = math.floor(index / 2)
    if self.heap[parent]:GetHcost()
       <= self.heap[index]:GetHcost() then break end
    self.heap[parent], self.heap[index] =
      self.heap[index], self.heap[parent]
    index = parent
  end
end

Inventory

Every player's items live in one server-side table keyed by player. Clients can only ask for a copy, so they never edit their own inventory.

  • Each stack records an item id, a quantity, a stack limit from the item's data, and a stack id.
  • Adding items tops up a matching stack first. Anything over the limit spills into new stacks, and whatever can't fit once the stack cap is reached is reported as lost.
  • Item ids are validated before anything changes: they must be strings in the 0x… format.
  • New players start with four default moves and a starter item. Saving between sessions with DataStores is the next step.
Item typeMax per stack
Consumable10
Moves5
Armor1
Weapon1
Cards1
The overflow path in UpdateInv: fill the current stack, then open new ones while there's room.
local canAdd = math.min(num, itemData.stackable - foundStack.quantity)
foundStack.quantity += canAdd
overflow -= canAdd

while overflow > 0 do
  if playerInventory.LastStackID + 1 < invServer.MaxStack then
    local stackSize = math.min(overflow, itemData.stackable)
    InventoryServer.MakeStack(player, id, stackSize)
    overflow -= stackSize
  else
    print("Inventory Full. You lost: " .. overflow .. " " .. itemData.name)
    break
  end
end

Try the stacking rules

Ten stack slots. Click a stack to delete it. The item names here are examples.

    Loot randomizer

    Chests roll from a weighted loot pool and hand the result straight to the inventory, which applies the stacking rules above.

    • Each chest drops 1–3 items, with 1–3 of each.
    • For each drop, the randomizer rolls 1–10 and walks the pool, adding up weights until the running total reaches the roll. A weight of 5 out of 10 is a 50% chance.
    • Duplicate drops are merged by item id before they're added, so a chest never fills two slots with the same item.

    Example pool with weights adding up to 10, and the roll range each one covers:

    local function chooseItem()
      local randomNum = math.random(1,10)
      local counter = 0
      for rarity, item in pairs(LootPool) do
        counter += item.weight
        if randomNum <= counter then
          return {name = item.name, description = item.description,
                  quantity = math.random(1,3), id = item.id}
        end
      end
    end

    Check the odds

    Roll the example pool 10,000 times and compare each item's share of drops with its weight.

    ItemExpectedRolled