Efficiency of the Find Entities Function

[skittles sour]

Is it true that the TheSim:FindEntities function is actually very inefficient and cycles through the entirety of the Ents table?

[IronHunter]

It must be pretty efficient considering the game runs it dozens of times a second for sanityaura checks.

I think the frequency of your function calls is the important decision here. While it is not as optimal as a specialized ent loop that only contains a list of your chosen ents. Its flexible and useful to handle a lot of cases especially when there is lots of unknowns that could change when a ent is valid or not for your checks.

E.g. if you wear the beefalo hat you get the beefalo tag. This makes the hostile beefalo in heat for their findtarget checks ignore you.

[CarlZalph]

The game already runs on tiles, so it'd come to a shock to me if there isn't any partitioning up of the lookups by having each tile itself know what entities are on it for example.

Assuming memory isn't too much of an issue for the redundancy for faster lookups, then doing it like this would see a huge increase if the number of entities to check increased.  The dark blue tiles wouldn't need to be checked, the green tiles would, and the light green are the permitted entities.

For example, let's say that the world is a typical 450x450 and that there is exactly 1 entity per tile.  Thus there are 202500 entities in this world.  Using the infographic as a basis, it would reduce the checks from 202500 to 24 (number of green tiles), and could create an array of 43 (blue + green) maximum entities and 19 (blue) minimum entities.

Even in this trivial case it should be apparent at how much more efficient it would be to spatialize up the world.

The granularity of the spatialization (the region size for each square) would have an ideal size based on probability distributions.  You can see this by looking to the extremes:  With a region the exact same size as the map you gain no benefits as the entire map is one region and thus all entities are checked.  With a region size extremely small you now have a lot more zones to iterate over creating "artificial" entities to look at instead (imagine 202500 zones to look over being equal to 202500 entities).  Some point in between the extremes would trade off memory use for performance at an acceptable ratio, and I would assume that it's the same size as the turf tiles the game uses by default.

[skittles sour]

Thank for the explanation! So does this mean that, if what's in question is a handful of entities that can be easily tracked, it'd remain more efficient to use the TheSim:FindEntities function to determine their presence, rather than to write a custom function?

Edited May 25, 2021 by Bad Willow

[CarlZalph]

7 hours ago, Bad Willow said:

Thank for the explanation! So does this mean that, if what's in question is a handful of entities that can be easily tracked, it'd remain more efficient to use the TheSim:FindEntities function to determine their presence, rather than to write a custom function?

If you're able to track them as they're important to each other, then it would be more efficient to do so.

The post I put there is what most games do when having an underlying grid to work from to speed up radius-based checks and I assume is what Klei's doing for theirs when you use TheSim:FindEntities.  (If they're not, well rip that optimization pass.)