Evenly distributed random points

Help and Feedback Scripting Support
1

I essentially need to regularly generate a random x and z within the bounds of a SpawnPart, Previously I was doing this purely randomly, however this presents the problems typical with a pure random distribution (oversampling in some areas, undersampling in others.

To address this, I’ve implemented a version of Mitchell’s Best Candidate Algorithm. Essentially, you’re supposed to generate x points and discard all but the furthest away from all existing points to achieve a more even distribution. For some reason however my implementation seems to have the opposite effect more densely clustering points the higher the Sampled Points is. I’ve tried breaking it down multiple times however I can’t figure out where I went wrong. The code is essentially as follows:

function ZoneControl:FindClosest(p)
	local closestmatch
	local closestdistance
	
	for index, v in ipairs(self.CurrentPoints) do
		if closestmatch == nil then
			closestmatch = v
			closestdistance = (p - v).Magnitude
		else
			local dis = (p - v).Magnitude
			
			if dis < closestdistance then
				closestmatch = v 
			end
		end
	end
	
	return closestmatch
end

function ZoneControl:Tick()
	local Chosen = self.SpawnPlan:GetRandomLoot()
	local Choice = self.SpawnSet:FindFirstChild(Chosen)
			
	local Pos = self:Sample()
			
	if Pos ~= nil then
		local Safe = SafeClass.new(Choice, Vector3.new(Pos.X, (self.SpawnPart.Position.Y + self.SpawnPart.Size.Y/2) , Pos.Y), self.SpawnConfig:FindFirstChild(Chosen))
				
		table.insert(self.CurrentPoints, Pos)
				
		Safe.Destroyed:Connect(function()
			self.CurrentCount -= 1
					
			local match = table.find(self.CurrentPoints, Pos)
					
			if match then
				table.remove(self.CurrentPoints, match)
			end
		end)

		self.CurrentCount += 1
	end
end

function ZoneControl:Sample()
	local BestCandidate
	local BestDistance = 0

	for i=1, self.SampledPoints do
		local SpawnX = math.random(self.SpawnPart.Position.X - self.SpawnPart.Size.X / 2, self.SpawnPart.Position.X + self.SpawnPart.Size.X / 2)
		local SpawnZ = math.random(self.SpawnPart.Position.Z - self.SpawnPart.Size.Z / 2, self.SpawnPart.Position.Z + self.SpawnPart.Size.Z / 2)

		if BestCandidate == nil then
			BestCandidate = Vector2.new(SpawnX, SpawnZ)
			
			local Closest = self:FindClosest(BestCandidate)
			
			if Closest ~= nil then
				BestDistance = (BestCandidate - Closest).Magnitude
			end
		else
			local OwnVec = Vector2.new(SpawnX, SpawnZ)
			
			local Closest = self:FindClosest(OwnVec)

			if Closest ~= nil then
				local Dis = (OwnVec - Closest).Magnitude
				print(Dis)
				
				if Dis > BestDistance then
					BestCandidate = OwnVec
					BestDistance = Dis
				end
			end
		end
	end

	return BestCandidate
end

Putting the SampledPoints to 1000 and letting it run gives the following result showing that it’s infact clustering as close as possible rather than the opposite desired effect. Any ideas on why this might be?

Clustered
Clustered1046×538 435 KB

Edit: It took me a few days primarily because this wasn’t the biggest issue I was working on, however I finally decided I had the time to fix it and the solution is quite comical. It boils down to me simply forgetting to update closestdistance within the FindClosest function.

1 Like
2

Nope, no idea. I tried it myself and it works perfectly:

image
image792×586 16.1 KB

Here are my nearestPoint and bestCandidate functions:

function nearestPoint(p)
    if #points == 0 then return nil end

    local nearest, nearestDist = points[1], pointDist2(p, points[1])
    for i = 2, #points do
        local dist = pointDist2(p, points[i])
        if dist < nearestDist then
            nearest = points[i]
            nearestDist = dist
        end
    end

    return nearest
end

function bestCandidate()
    if #candidates == 0 then return nil end
    
    local best, bestDist = candidates[1], pointDist2(candidates[1], nearestPoint(candidates[1]))
    for i = 2, #candidates do
        local c = candidates[i]
        local dist = pointDist2(c, nearestPoint(c))
        if dist > bestDist then
            best = c
            bestDist = dist
        end
    end
    return best
end

I recommend setting a breakpoint and stepping through the code line-by-line to see where it’s wrong