Problem with efficiently making ignore lists for raycasts, given my game's rules

[Zomebody]

For a project I am working on, I am working a lot with raycasts. Whenever I cast a ray, I need to ignore specific objects, but the rules for which object to ignore are a little tricky. In essence, there are different ignore lists per team. For each team, the ignore list exists out of:

• Characters of players in that team
• Objects tagged RAY_IGNORE (but there are some team-specific exceptions)

I have the logic working for the second part, which is objects that are tagged RAY_IGNORE. However, I am struggling with figuring out how I can best approach adding player characters to these ignore lists.

Rays will be cast very often (potentially tens of times per second), so recreating the ignore list whenever you cast a ray can become an expensive process real quick, which is why I figured I should have one array per team to which I add objects when needed. When an object tagged RAY_IGNORE gets destroyed, I keep them in the list because these arrays get refreshed at the end of a round anyway, and removing these parts could mean looping through an array of a couple hundred objects to find out which index I have to remove from the array. Keeping these removed parts around in memory temporarily does not significantly impact performance at all.

This approach does not work well for characters however. Before a round ends, characters could have respawned a hundred times. If I were to treat characters the same way as above, that means I could potentially have an array with references of a hundred dead characters (including textures, accessories, and more). These references do not get cleaned up until the end of the round and so I will be taking up a lot of memory towards the end of a round. However, I am not keen on removing characters from these arrays either whenever they die, because that means that in the heat of combat I might be looping through hundreds of objects every second.

My original solution to this problem was to not only have team-specific arrays in which I keep the RAY_IGNORE objects, but to also create a separate array for each team in which I store the character models. Whenever I cast a ray I combine the two arrays into a new array that I use as the final ignore list. However, a raycast’s ignore list does not support nested arrays, so I cannot do e.g.

function ReturnIgnoreList()
    -- IgnoreParts and IgnoreCharacters are team-specific arrays
    local IgnoreList = {IgnoreParts, IgnoreCharacters}
    return IgnoreList
end

So I am now looking for a new approach. These are the approaches I am currently thinking of:

1. I keep a separate team-specific array for the character models and the RAY_IGNORE objects. When character models are removed I remove them from their array as well, which will be fast because the array is short. And whenever I cast a ray I create a new table into which I unpack the RAY_IGNORE array, and then add the character models to the end of this new array afterwards. However, this sounds like it would nullify most of the performance benefits that I was hoping to create in the first place.

2. Combine the player characters into the array with RAY_IGNORE parts, and whenever they die just keep the reference of the character models in those lists. This might take up significant memory though towards the end of a round, but will save computing power.

3. Combine the characters into the array with RAY_IGNORE parts, and whenever they die, loop through the whole table to find out which index holds the dead character and remove that index. This will take up less memory, but it will put a little more stress on the CPU.

I am hoping that there might be a more elegant solution that someone can share with me. If not, I hope that someone with more experience on this subject can help me figure out which of the given approaches I should take by explaining the benefits and downsides of each option.

[woot3 (Woot)]

Chances are, you probably don’t need to worry about the overhead of reconstructing the array each time you need it. However, if you are concerned about overhead then you can do the following:

• Instead of using tags, place all RAY_IGNORE parts into a single folder. You can then just include this folder in your ignore list.
• Keep track of the characters in the game, when they die remove them from the array using table.find.
• Use this ignore list whenever you raycast.

local Players = game:GetService("Players")
local ignoreList = { workspace.IgnoreParts }

Players.PlayerAdded:Connect(function (player)
    player.CharacterAdded:Connect(function (character)
        -- check player meets your condition
        table.insert(ignoreList, character)
        character.AncestryChanged:Connect(function ()
            local index = table.find(ignoreList, character)
            table.remove(ignoreList, index)
        end)
    end)
end)

[EchoReaper]

This is a valid use of weak table values (metatables). If the reference is weak, then it won’t block the instance from being cleaned up. There is an issue with weak instance references that you will need to work around (Anaminus’s suggestion seems extremely straightforward), but it is much more manageable.

[Zomebody]

@woot3

Instead of using tags, place all RAY_IGNORE parts into a single folder.

Unfortunately there are some small problems with this approach. Some objects that are tagged RAY_IGNORE may only be applicable for one team, for example in the case of a team-only door. Should I instead isolate these ‘exceptions’ and treat them similar to characters, where I evaluate them separately whenever they’re added to decide which ignore list they should go in?

[woot3 (Woot)]

You can place those in sub-folders of the ignore parts container, then selectively decide which folders to include in your ignore list.

[HaxHelper (ken)]

I think I would maintain two tables:

local external = {}
local internal = {}

Note that external is a dictionary-like table, while internal is an array-like table. To add an item to the collection, it is appended to the end of internal, and is associated with its position via external:

function insert(item)
    local newIndex = #internal + 1
    internal[newIndex] = item
    external[item] = newIndex
end

Now removing an item from internal is just a pop and a swap:

function remove(item)
    internal[external[item]] = table.remove(internal)
    external[item] = nil
end

Integrating with CollectionService is simple:

local CollectionService = game:GetService("CollectionService")

CollectionService:GetInstanceAddedSignal("foo"):Connect(insert)
CollectionService:GetInstanceRemovedSignal("foo"):Connect(remove)

-- at game start populate the collection...
for _, instance in pairs(CollectionService:GetTagged("foo")) do
    insert(instance)
end
-- or whenever it is appropriate

I did not for the sake of simplicity, but this can be made faster by keeping an additional variable to track the number of items currently in the collection, as insert would not need to calculate the length of internal, and remove could index directly into internal to pop the last element off instead of using table.remove. However, it’s probably fast enough for most uses already.

(Whoops - there’s a bug in remove! Can anyone spot it? )

The correct remove function

remove must also update the value of the swapped item in external:

function remove(item)
    local swapped = table.remove(internal)
    internal[external[item]] = swapped
    external[swapped] = external[item]
    external[item] = nil
end

But wait! The behavior of remove is still incorrect removing from the end of internal - in this case, external[item] will be set to nil, but internal[external[item]] will still exist! We need to check that we are not at the end of internal before swapping:

function remove(item)
    local swapped = table.remove(internal)
    local index = external[item]
    -- internal[index + 1] will be equal to nil if we are at the end of the array 
    local notLast = internal[index + 1]

    if notLast then
        internal[index] = swapped
        external[swapped] = index
    end

    external[item] = nil
end

[BanTech]

I find this (effectively woot’s solution) to be the best solution for my own raycasting applications that raycast sometimes several casts per frame.

The folder structure would be like:
Workspace
‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‎‎└ IgnoreFolders
‏‏‎ ‎‏‏‎‏‏‎ ‎‏‏‎ ‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎├ allTeamFolder
‏‏‎ ‎‏‏‎ ‏‏‎ ‎‏‏‎ ‎‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎├ specificTeamFolder1
‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎‏‏‎ ‎└ specificTeamFolder2

local ignoreTable = {
    Workspace.IgnoreFolders.allTeamFolder,
    Workspace.IgnoreFolders.specificTeamFolder,
}

for _, p in ipairs( Players:GetChildren() ) do
    if p.Team == Teams.TeamToFilter and p.Character then
        table.insert( ignoreTable, p.Character )
    end
end

local part, intersect, normal = Workspace:FindPartOnRayWithIgnoreList( ray, ignoreTable )

You can maintain tables and worry about what is and isn’t in them and whether it’s weak or strong etc. But creating the array as above has never caused me any problems when performed every frame at 60fps.

[blobbyblob]

I think you can have “junk” in the blacklist, so if you’re willing to just leave dead characters/destroyed objects/etc. in your blacklist for a little while, you can avoid the problem of having to search a long list to find the index you have to remove whenever a player dies or debris is removed.

You could just do an occasional (once a minute or so) complete reconstruction of the list to clean it up.

This falls apart if things leave the blacklist for other reasons, such as a character being swapped to another team, or some object “materializing” so you can now shoot it, but these situations may not be realistic for you – not entirely sure.

[VegetationBush (FartedAtLightspeed)]

Can you think on the flip side and see what objects are not ignored? For example, if there is so many things to be ignored, so why not just use a whitelist?

You can use each tag to tag different objects that whitelist to each individual team, for example:

Team A → Can destroy object 1
Beam B → Can destroy object 2
Team C → Can destroy object 1 and 2

You would tag object one as “TeamA” and “TeamC” and object 2 as “TeamB” and “TeamC”

Whenever you want specific teams to acces specific things, use a whitelist table instead.