I am currently making a boids system, and while it works fine, it’s not very performant. With 1000 boids, it takes a tenth of a second to update. This is the bit of code I’m trying to optimize:
function Boid.__index:CalculateAcceleration(): Vector3?
local AverageHeading = ZERO_VECTOR
local AveragePosition = ZERO_VECTOR
local SeperationHeading = ZERO_VECTOR
local NumBoids = 0
local AvoidBoids = 0
for _, OtherBoid: Boid in ipairs(BoidArray) do
if OtherBoid.Id == self.Id then
continue
end
local Offset = OtherBoid.Position - self.Position
local Distance = Offset.Magnitude
if Distance > self.Range then
continue
end
-- FOV check
if GetAngleBetweenVectors(self.Position, OtherBoid.Position) > self.ViewAngle then
continue
end
AverageHeading += OtherBoid.Velocity
AveragePosition += OtherBoid.Position
if Distance < AVOID_RADIUS then
SeperationHeading -= Offset / Distance
AvoidBoids += 1
end
NumBoids += 1
end
if NumBoids < 1 then
return
end
AverageHeading /= NumBoids
AverageHeading *= ALIGN_WEIGHT
AveragePosition = AveragePosition / NumBoids - self.Position
AveragePosition *= COHESIVE_WEIGHT
-- Dividing by 0 results in nan values, which caused me way too much headache :/
if AvoidBoids > 0 then
SeperationHeading /= AvoidBoids
SeperationHeading *= SEPERATION_WEIGHT
else
return ClampVector(AverageHeading + AveragePosition, self.MaxAcceleration)
end
return ClampVector(AverageHeading + AveragePosition + SeperationHeading, self.MaxAcceleration)
end
After some more benchmarking, I figured out that the main source of lag is the range check, since it checks over every other boid. After some digging, I found out about spacial partitioning. However, I’m not sure which data structure is best, or whether it would even improve performance. Any help on optimizing this code to run faster would be appreciated.
