New spatial query filters

Updates Announcements
,
1

Hey folks,
We’re adding a simpler and more flexible set of APIs to supersede FilterDescendantsInstances for raycasts, shapecasts, and other spatial queries:

RaycastParams.ExcludeInstances: {Instance}?
RaycastParams.IncludeInstances: {Instance}?

OverlapParams.ExcludeInstances: {Instance}?
OverlapParams.IncludeInstances: {Instance}?

Documentation

:shuffle_tracks_button: New Filters

Previously, FilterDescendantsInstances forced you to choose either a whitelist or a blacklist. The new APIs allow for flexible filters that weren’t possible before without performing multiple raycasts:

Example: Whitelist with exceptions

params.ExcludeInstances = {Tree}
params.IncludeInstances = {Folder}

Folder (include me)
| House
| Tree (...but exclude me)
| Bench

Example: Blacklist with exceptions

params.ExcludeInstances = {Folder}
params.IncludeInstances = {Tree}

Folder (exclude me)
| House
| Tree (...but include me)
| Bench

Example: Include nothing

params.IncludeInstances = {}

Folder (exclude everything including me)
| House
| Tree
| Bench

Example: Include everything

params.IncludeInstances = nil

Folder (include everything including me)
| House
| Tree
| Bench

Note that IncludeInstances = nil and IncludeInstances = {} are opposites - The former is the most permissive possible filter (includes everything), whereas the latter is the most restrictive possible filter (include nothing).

(Note: If an instance happens to be in both lists, the exclusion takes priority as the tiebreaker).

Algorithmic Details

For those interested, the behavior of the new filters can be emulated like this:

function isIncludedByFilter(inst: Instance, exclude: {Instance}?, include: {Instance}?)
    repeat
        if exclude and table.find(exclude, inst) then
            return false
        end

        if include and table.find(include, inst) then
            return true
        end

        inst = inst.Parent
    until inst == nil

    return include ~= nil
end

:rocket: Performance

The new APIs are much faster than FilterDescendantsInstances. This was enabled by a large internal rewrite[1] of how we handle filters for raycast and overlap queries:

  1. Fast log(n)-time lookups: We figured out a way to do log(n) lookups without making RaycastParams construction slower. The raycasts themselves are much faster when using these when you have a large filter list.
  2. Reduced memory thrashing: We carefully tuned the reflection code so setting these properties repeatedly (e.g., dynamically adding parts to the list) has excellent performance.[2]

[1] Besides being faster, this allows us to iterate more quickly internally on new types of spatial queries and filtering APIs.

[2] We also shipped this specific optimization for FilterDescendantsInstances so that existing games run faster with no changes. However, we won’t be able to ship the first optimization for FilterDescendantsInstances, so there is a strong performance benefit for using the new APIs.

:date: Migration

Of course, FilterDescendantsInstances and FilterType will always exist for backwards compatibility. However, we plan to deprecate them eventually in lockstep with community adoption of the new APIs. For you, this only means that continuing to use the old APIs will eventually produce a script analysis warning, and we will prioritize bug fixes and performance optimizations for the new APIs moving forward.

Known Issues

Due to a release delay, between 1% and 2% of Roblox clients on Windows and Android may not have this API yet as of 4/8. We will provide an update when it has 100% availability.

-The Physics Team

249 Likes
2

This topic was automatically opened after 10 minutes.

3

We make a lot of use of :AddToFilter(), will we be getting new variants for the new properties?

As always, great update from the physics team!

24 Likes
4

Thank you for this update, roblox! Been looking forward to this spatial query update!

2 Likes
5

Are collision groups alone still the fastest option for these queries? That’s what I generally prefer to use, because I don’t need to bookkeep instances, and I assume that the physics engine already is well informed on the collision groups.

4 Likes
6

+1 on this - I use this API method a lot, hope it will have support! Love these changes.

3 Likes
7

AddToFilter actually didn’t have much of a perf benefit prior to this because it thrashed memory - While we were making these changes, we optimized it so it doesn’t do that, but we also did the same thing for the new properties. If you set ExcludeInstances over and over, it just reuses the same memory block without thrashing and gives good performance, just like AddToFilter was supposed to do in the first place.

So there’s not a huge performance argument anymore for it, but if there’s still strong demand we can think about adding something like it as a shortcut.

23 Likes
8

What are the chances of the spatial query APIs having a filter system similar to QueryDescendents?

It could be useful if the C++ side could handle specific property/attribute filtering on parts, without needing to store the list of instances that match the filter on the lua side (i.e. a Raycast that can only hit parts named “HumanoidRootPart” or that are anchored)

1 Like
9

Great work. Always great to see new features that simultaneously bring perf gains.

Also, being able to do this has just become relevant to me over the past few weeks as I’ve started building a world partitioning system, where multiple different partitions can overlap the same physical space! What great timing :grinning_face_with_smiling_eyes:

10

:thinking:
Roblox’s CameraScript is saved :partying_face: I think
 

Now, after reading a bit I asked myself, how do I determine, if I want to include everything?

And I see params.IncludeInstances = nil

Okay, but now what if I want the opposite? :thinking:

Is there a way that is not params.IncludeInstances = {}

 

Does Occlusion Culling use a raycast in secret? Sometimes I see that appear in the MicroProfiler.

2 Likes
11

There are complications - We can’t just reuse the same syntax because the QueryDescendant DSL is designed for descendant queries (e.g., it has an implicit >> which doesn’t make sense for filtering individual Instances). Our plan is to add tag filters in the near future, and then we can see how demand shapes up for more generic filters.

At the very least the specialized tag filter will be faster than any generic DSL we can provide.

11 Likes
13

This is a great iteration of the API!

On this same note of the topic of raycasting and performance, has there been any consideration for introducing the ability to batch raycasts and/or spatial queries to further reduce the overhead of the Luau<->C barrier for what would otherwise be many individual calls?

4 Likes
14

has there been any consideration for introducing the ability to batch raycasts

Yes. Stay tuned.

25 Likes
15

great update
but this is different from what I expected
i wanted a feature that raycasts only against specific instances

the problem with passing an instance table via :GetTagged was that it required a lot of performance to find all the descendants

i think we also need a feature that raycasts only against those BaseParts when passing a table containing only BaseParts for performance reasons

params.TargetBaseParts = {BasePart}

params.TargetBaseParts = { 
  CollectionService:GetTagged("A"), 
  CollectionService:GetTagged("B"), 
  CollectionService:GetTagged("C"), 
  CollectionService:GetTagged("D"),
} -- doesn't include their descendants, so it's much faster!
4 Likes
16

Will specifying multiple tags be allowed? Or is it going to be just one tag similar to how only one collision group can be specified?

1 Like
17

Tables potentially containing multiple tags. The API will look similar to ExcludeInstances and IncludeInstances.

2 Likes
18

Me reading this

IMG_4610

4 Likes
19

The type for ExcludeInstances & IncludeInstances should be {Instance}

image
image1998×550 74.4 KB

3 Likes
20

One of our primary use cases was due to the fact we could not grab the table by accessing FilterDescendantsInstances, thus creating a pattern where we frequently duplicated data.

Is this fixed/possible now?

21

OH HEY THISIS COOL!!! Its so awkward needing to pick one or the other it’s nice we’ll be able to have both options!