Custom spatial query test

ClosestPickup.lua

--!native
--!optimize 2

--[[
	ClosestPickup
	
	- LocalScript inside StarterCharacterScripts
	- MAX_RADIUS is not really a radius, but rather the zone cube size
	- It searches for BaseParts in the workspace with the 'Pickup' tag
		- It assumes BasePart; non BaseParts with the same tag will break this test
	- This tries to reduce calls outside of Lua boundary to maintain good perf
]]

local CollectionService = game:GetService("CollectionService")
local RunService = game:GetService("RunService")

local TAG = "Pickup"
local MAX_RADIUS = 64

local root = script.Parent:WaitForChild("HumanoidRootPart")

local lastClosest = nil

local pickupSpatialArray = {}

local function RoundVector3(v3: Vector3, multiple: number): Vector3
	return Vector3.new(
		math.round(v3.X / multiple) * multiple,
		math.round(v3.Y / multiple) * multiple,
		math.round(v3.Z / multiple) * multiple
	)
end

local function PickupAdded(pickup)
	if not pickup:IsDescendantOf(workspace) then return end
	
	local spatialKey = RoundVector3(pickup.Position, MAX_RADIUS)
	
	-- Get/create zone based on spatial key
	local zone = pickupSpatialArray[spatialKey]
	if not zone then
		zone = {}
		pickupSpatialArray[spatialKey] = zone
	end
	
	-- Gross, but allows us to prevent calling 'pickup.Position' inside the scanning code:
	table.insert(zone, {pickup.Position, pickup})
end

local function PickupRemoved(pickup)
	local spatialKey = RoundVector3(pickup.Position, MAX_RADIUS)
	
	local zone = pickupSpatialArray[spatialKey]
	if not zone then return end
	
	local idx = nil
	for i, v in zone do
		if v[2] == pickup then
			idx = i
			break
		end
	end
	if idx then
		table.remove(zone, idx)
		if #zone == 0 then
			pickupSpatialArray[spatialKey] = nil
		end
	end
end

local function FindClosest()
	debug.profilebegin("FindClosest")
	
	local start = os.clock()
	
	local closestDistance = math.huge
	local closestPickup = nil
	
	local rootPos = root.Position
	
	-- Scan through all adjacent zones:
	debug.profilebegin("Scan")
	for x = -1, 1 do
		for y = -1, 1 do
			for z = -1, 1 do
				local pos = rootPos + Vector3.new(x * MAX_RADIUS, y * MAX_RADIUS, z * MAX_RADIUS)
				local spatialKey = RoundVector3(pos, MAX_RADIUS)
				
				local zone = pickupSpatialArray[spatialKey]
				
				if zone then
					-- Find the closest part within the zone:
					for _, pickup in zone do
						local distance = (pickup[1] - rootPos).Magnitude
						if distance < closestDistance and distance < MAX_RADIUS then
							closestDistance = distance
							closestPickup = pickup[2]
						end
					end
				end
			end
		end
	end
	debug.profileend()
	
	-- Highlight the closest part green:
	if closestPickup ~= lastClosest then
		-- This ends up being the slowest code due to having to write to .Color property:
		debug.profilebegin("Colorize")
		if lastClosest then
			lastClosest.Color = Color3.new(1, 0, 0)
		end
		if closestPickup then
			closestPickup.Color = Color3.new(0, 1, 0)
		end
		debug.profileend()
	end
	
	lastClosest = closestPickup
	
	local duration = os.clock() - start
	
	debug.profileend()
	
	print(("FindClosest: %.2fms"):format(duration * 1000))
end

CollectionService:GetInstanceAddedSignal(TAG):Connect(PickupAdded)
CollectionService:GetInstanceRemovedSignal(TAG):Connect(PickupRemoved)
for _, pickup in CollectionService:GetTagged(TAG) do
	task.spawn(PickupAdded, pickup)
end

--RunService.Heartbeat:Connect(FindClosest)
while true do
	task.wait(0.2)
	FindClosest()
end