For a project of mine, I recently wrote a function that allows me to specify a CFrame, Size, NumPoints, and Minimum Distance(for distribution). It’s supposed to create NumPoints points evenly distributed within that volume.
It “works” , but my main two issue of concern are:
I’m worried its performance is almost entirely based on the RNG
Having to specify a minimum distance manually that works with the target size is really tedious and I feel like it could be done automatically
Everything feels arbitrary
Here’s the function
function SharedUtils:GetRandomDistributedPointsWithinVolume(cframe,size,numPoints,distanceThreshold)
local position = cframe.p;
--[[
This is just a simple grid based chunk thingy I made,
it's comparable to using an octree here and is just made to speed up iteration
by only checking things around the candidate point. 3,5 is 3 dimensions, 5x5x5 studs
also really ugly and arbitrary in this case
--]]
local chunkSystem = ChunkSystem.new(3,5);
--
local Points = {};
local attempts = 0;
local maxAttempts = 50; -- lol
while #Points<numPoints do
if attempts > maxAttempts then
warn("Max attempts reached! Try setting a smaller threshold!");
break;
end
local rx = RNG:NextNumber(position.x-size.x/2,position.x+size.x/2);
local ry = RNG:NextNumber(position.y-size.y/2,position.y+size.y/2);
local rz = RNG:NextNumber(position.z-size.z/2,position.z+size.z/2);
local randomPoint = Vector3.new(rx,ry,rz);
local candidateChunk = chunkSystem:GetChunk(randomPoint,true);
local objectsFound = candidateChunk:GetObjects("Surrounding");
local tooClose;
for i,objectFound in ipairs(objectsFound) do
local dist = (objectFound.Position - randomPoint).magnitude;
if dist <= distanceThreshold then
tooClose=true;
break;
end
end
if not tooClose then -- If the candidate is not too close to another previously placed point, add it to the chunk insert and repeat
candidateChunk:AddObject({Position=randomPoint});
local relative = CFrame.new(randomPoint) * (CFrame.new(position)):Inverse();
randomPoint = (cf * relative).p; -- Moves the point to conform to the cframe/orientation
table.insert(Points,randomPoint);
attempts=0;
else
attempts = attempts + 1;
end
end
return Points;
end
Preferably I’d like something that is more reliable and consistent in performance, and preferably doesn’t need a “minimum distance” variable to be manually found for the target size. It should still be fast and work for just about any size I can throw at it.
I’m a bit stumped on this.
Thanks for your time, interested in seeing what ideas you guys have
To make it less “Ugly”, I used the Minifier plugin by Stravant which allows me to make a script shorter or better
function SharedUtils:GetRandomDistributedPointsWithinVolume(cframe, size, numPoints, distanceThreshold)
local position = cframe.p;
local chunkSystem = ChunkSystem.new(3, 5);
local Points = {};
local attempts = 0;
local maxAttempts = 5000000000000000000000000000000; -- lol to you too
while #Points < numPoints do
if attempts > maxAttempts then
warn("Max attempts reached! Try setting a smaller threshold!");
break;
end
local rx = RNG:NextNumber(position.x - size.x / 2, position.x + size.x / 2);
local ry = RNG:NextNumber(position.y - size.y / 2, position.y + size.y / 2);
local rz = RNG:NextNumber(position.z - size.z / 2, position.z + size.z / 2);
local randomPoint = Vector3.new(rx, ry, rz);
local candidateChunk = chunkSystem:GetChunk(randomPoint, true);
local objectsFound = candidateChunk:GetObjects("Surrounding");
local tooClose;
for i, objectFound in ipairs(objectsFound) do
local dist = (objectFound.Position - randomPoint).magnitude;
if dist <= distanceThreshold then
tooClose = true;
break;
end
end
if not tooClose then -- If the candidate is not too close to another previously placed point, add it to the chunk insert and repeat
candidateChunk:AddObject({
Position = randomPoint
});
local relative = CFrame.new(randomPoint) * (CFrame.new(position)):Inverse();
randomPoint = (cf * relative).p; -- Moves the point to conform to the cframe/orientation
table.insert(Points, randomPoint);
attempts = 0;
else
attempts = attempts + 1;
end
end
return Points;
end
The main thing that the above beautified code does better is have consistent spacing. For instance, in your code when you write a = b right now you sometimes put spaces around the equals and other times just write it all as one blob with no spaces. Same problem with some other operators like + and commas in argument lists.
Adopting a consistent style for this across all of your code for those cases will help you out in the long run.
Here’s an alternative algorithm you could apply which doesn’t take a potentially arbitrarily large number of iterations to get a good result:
Randomly generate the points, evenly distributed over the space
Calculate the Delaunay triangulation (or slightly less efficiently use your chunk system) to find each pair of nearby points
For each pair of points which is closer than the threshold, add a “pusher” (a spring but it can only push the points further apart) between them
For some number of iterations, “push” each pair of points which were too close further apart along the axis separating them such that they’re no longer too close (The reason you need more than one iteration is that if you have a big clump of points the central ones will get pushed back and forth a bit while the outer ones “spread out” over the course of a few iterations)
To avoid having to choose the threshold manually, you can use a formula like this to figure out what the value “should be” for the number of points passed and the size of the area.
