How exactly are Spatial Queries checking parts?

[placomi (plac)]

I tested the speed that workspace:GetPartBoundsInBox() takes to run depending on a couple of factors and got some strange results.

I want to make sure I can reduce the amount of checks ROBLOX needs to do by restricting it with OverlapParams.

With only one part in workspace, the benchmarker recorded this:

This makes sense, since both are checking one part.

With 1000 parts in workspace, it resulted in this:

Shouldn’t the spatial query that is only checking one take a similar or equal amount of time as the queries where there was only one part in the workspace?

When I move the 1000 parts outside of the spatial query location, it resulted in this:

What is going on? Is this supposed to be how it functions?

[7z99 (cody)]

Can you show your overlap params

[placomi (plac)]

local op = OverlapParams.new()
op.FilterDescendantsInstances = {workspace.Parts.part}
op.FilterType = Enum.RaycastFilterType.Include

Simply filtering for a single part.

[7z99 (cody)]

Ok yeah, getting the same results. I was thinking that there could have been a logic error with how you defined your overlap params, but it seems spatial queries still scale up regardless of specifying a whitelist, and regardless of specifying a collision group, which is extremely disappointing. I’m at a bit of a loss here, sorry.

[RoBoPoJu]

Based on your results, it seems like Roblox will do the search in the same way (using some kind of an acceleration structure) regardless of OverlapParams and the OverlapParams are only used as a filter for which of the parts that were found to be in the region are added to the list that is returned to the user. If that’s true then the time taken will always depend on the number of parts in the region.

I believe it is designed this way because when there are a lot of parts in the whitelist and few parts in the region, going through every part in the whitelist and checking whether the part is in the region would be less efficient than doing the normal spatial search and checking which of the results are in the whitelist. Binary search can be used to efficiently check whether a part is in the whitelist. Edit. Idk what I was thinking when writing this sentence. Binary search obviously only works if the query function orders the whitelist based on some numerical property of the parts. If they aren’t ordered in any way, binary search can’t be used.

I’m not sure why they don’t change the behavior depending on whitelist length to optimize cases where the whitelist is very short. Perhaps searching with a short whitelist is so uncommon that the engineers don’t consider this whitelist length check worth adding.

[placomi (plac)]

That’s unfortunate. I find it much more reasonable to use smaller checks if only checking a small number of BaseParts.