# Optimizing Unit Targeting in Roblox with a Swarm Module

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)
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)

``````

## 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.

67 Likes

Awesome tutorial. I would like to see A*-pathfinding tutorial from ROBLOX staff someday. since mine runs very slow at 50+ stud distances

3 Likes

Octree by Quenty is the solution. Even DOORS uses it for something, I think.

Case is very specific.

The tutorial that I want is anything that is related to _“showing what makes a game lag” and then “how to solve it”.

e.g. Part and Physics and Replication and Network Delay

Octree by Quenty is the solution. Even DOORS uses it for something, I think.

Octrees dont make much sense for RTS’es which usually only have movement on two axis.

What does the term RTS mean in this context?

RTS = Real-time Strategy

There are many other problems that could be solved with Memory vs CPU tradeoffs using similar techniques.

Hello, it’s nice to see Roblox admins finally looking into the performance issues of rts games (next tutorial should be about unit movement systems that use velocity optimizations). However, I’m pretty sure RenderStepped cannot be used in server scripts, why are you trying to over-complicate a loop that runs every second?