Real-Time Strategy (RTS) games on the Roblox platform often face challenges when it comes to unit targeting, especially when there are a large number of units involved.
Imagine a situation below where you have your N=1 unit (blue) and there are M=13 enemy units (red) all around the map.
Figure 1
To calculate which is the closest enemy unit in range you would need to perform 13 distance calculations because you don’t know until you perform the distance calculation that the units outside of the target range are actually outside of the target range.
This can quickly become CPU-intensive as the number of distance calculations would grow proportionally to the number of friendly and enemy units leading to N * M distance calculations resulting in performance issues.
In this article, we will discuss how to create and implement a Swarm module in Roblox Lua to optimize compute-intensive tasks for an incremental amount of memory usage.
Efficient Unit Targeting Using a Swarm Module
A Swarm module is designed to coarsely track units based on their position, allowing for more efficient target selection by reducing the number of distance calculations required.
Instead of performing a distance calculation from every friendly unit to every enemy unit on the map, we can coarsely place every unit into a cell (Fig 2) and track units as they move between cells:
Figure 2
From there, when we are trying to find the nearest enemy unit, we run a search starting from the same cell as the friendly unit (Fig 3), and then expanding out in a concentric grid (Fig 4)
Fig 3: Search the friendly unit cell first
Fig 4: Search outwardly in an expanding concentric cube
In the example above, we’re able to reduce the number of distance calculations from 13 to 3, a 77% improvement!
Implementing a Swarm Module in Lua
Here’s an example implementation of the Swarm module in Roblox Lua:
module = {}
local cellSize = nil
module.cells = {}
module.unitToCell = {}
module.CELL_X = 1
module.CELL_Y = 2
module.CELL_Z = 3
-- Set the size of your swarm module
function module.setCellSize(cellSize)
if cellSize == nil then
warn("Cell size has already been set and will not set again")
return
end
module.cellSize = cellSize
end
function module.calculateCell(unit)
if module.cellSize == nil then
error("You haven't called setCellSize() yet")
return
end
local pivot = unit:GetPivot()
local x = math.floor(pivot.Position.X / module.cellSize)
local y = math.floor(pivot.Position.Y / module.cellSize)
local z = math.floor(pivot.Position.Z / module.cellSize)
return {x, y, z}
end
-- Convert a cell array to a key
function cellToKey(cell)
return tostring(cell[module.CELL_X]) .. "," .. tostring(cell[module.CELL_Y]) .. "," .. tostring(cell[module.CELL_Z])
end
function module.deleteUnitFromCell(unit, cell)
local key = cellToKey(cell)
for index, value in ipairs(module.cells[key]) do
if value == unit then
indexToDelete = index
break
end
end
if indexToDelete then
table.remove(module.cells[key], indexToDelete)
end
end
function module.deleteUnit(unit)
local cell = module.unitToCell[unit]
if cell == nil then
return
end
module.deleteUnitFromCell(unit, cell)
module.unitToCell[unit] = nil
end
function module.updateUnitCell(unit)
local previousCell = module.unitToCell[unit]
local currentCell = module.calculateCell(unit)
if previousCell then
if previousCell[1] == currentCell[1] and
previousCell[2] == currentCell[2] and
previousCell[3] == currentCell[3] then
return
end
module.deleteUnitFromCell(unit, previousCell)
end
local key = cellToKey(currentCell)
if module.cells[key] == nil then
module.cells[key] = {}
end
table.insert(module.cells[key], unit)
module.unitToCell[unit] = currentCell
end
-- Function to find the closest unit that takes in an originUnit, the distance of cells to search, a comparsion function and a filter function you don't want to find friendly unit
function module.findClosestUnit(originUnit, searchRange, compareFunc, filterFunc)
if module.cellSize == nil then
error("Cell size not set. Call setCellSize() first.")
return nil
end
local originCell = module.calculateCell(originUnit)
local closestUnit = nil
local closestDistance = nil
-- Function to check and update the closest unit
local function checkAndUpdateClosestUnit(unit)
if not filterFunc(unit) then
local distance = compareFunc(originUnit, unit)
if closestDistance == nil or closestDistance > distance then
closestDistance = distance
closestUnit = unit
end
end
end
-- Loop through an outwardly expanding concentric cube
for range = 0, searchRange do
local foundInThisLayer = false
-- Iterate over the cube's outer layer
for x = originCell[module.CELL_X] - range, originCell[module.CELL_X] + range do
for y = originCell[module.CELL_Y] - range, originCell[module.CELL_Y] + range do
for z = originCell[module.CELL_Z] - range, originCell[module.CELL_Z] + range do
-- Only process cells on the outer layer, because we would have already search the inner cube
if x == originCell[module.CELL_X] - range or x == originCell[module.CELL_X] + range or
y == originCell[module.CELL_Y] - range or y == originCell[module.CELL_Y] + range or
z == originCell[module.CELL_Z] - range or z == originCell[module.CELL_Z] + range then
local key = cellToKey({x, y, z})
local cellUnits = module.cells[key]
if cellUnits then
for _, unit in ipairs(cellUnits) do
checkAndUpdateClosestUnit(unit)
foundInThisLayer = true
end
end
end
end
end
end
-- If a closer unit was found in this layer, we can exit early since the only closer unit
-- would've been in the inner cube
if foundInThisLayer and closestUnit then
break
end
end
return closestUnit
end
return module
And how to use the SwarmModule:
SwarmModule = require(workspace.SwarmModule)
-- 1. INITIALIZATION
--Before using the swarm module you have to set the cell size in studs
--This is specific to your Experience and you would need to
SwarmModule.setCellSize(5)
-- 2. TRACKING UNITS IN THE SWARM
-- a. When a unit is spawned you must set the position in the swarm
SwarmModule.updateUnitCell(unit)
--b. When a unit is moving you should set its new position in the swarm
-- For compute efficiency, you can reduce how often this runs at th
local RunService = game:GetService("RunService")
local UPDATE_FREQUENCY_IN_SECONDS = 1
local cellUpdateTime = 0
local function updateUnitPositions()
local currentTime = tick()
if cellUpdateTime < currentTime then
cellUpdateTime = currentTime + UPDATE_FREQUENCY_IN_SECONDS
for unit in workspace.Units:GetChildren() do
SwarmModule.updateUnitCell(unit)
end
end
end
RunService.RenderStepped:Connect(updateUnitPositions)
-- c. When a unit dies you need to delete that unit from the swarm
SwarmModule.deleteUnit(unit)
-- 3. NEAREST UNIT TARGETING
local function filterFunc(unit)
local result = false
if unit:GetAttribute("Team") == "RED" then
result = true
end
return result
end
local function getPivotDistance(unit1, unit2)
local pivot1 = unit1:GetPivot()
local pivot2 = unit2:GetPivot()
-- Get the position vectors of the pivots
local pos1 = pivot1.Position
local pos2 = pivot2.Position
-- Calculate the distance between the two positions
local distance = (pos1 - pos2).Magnitude
return distance
end
-- Knowing the size of your cell and the range of your target you can calculate how many cells away from the unit you will have to check
-- the range of cells is -cellsInRange to +cellsInRange in all dimensions of (x, y, z)
local cellRadiusInRange = math.ceil(unit:GetAttribute("Range") / SwarmModule.cellSize)
SwarmModule.findClosestUnit(unit, cellRadiusInRange, getPivotDistance, filterFunc)
Final Thoughts
RTS games on Roblox can be complex and require an efficient use of computational resources to keep performance high.
By implementing Swarm modules for tracking units, we can optimize compute-intensive tasks like target selection for increased memory usage.
Through cell-based tracking, we reduce the number of distance calculations required, thereby improving overall game performance and providing a better gaming experience for players.
For a more advanced solution, you can look at using a Dynamic Octree System.
