Download

Does UE4 use any spatial partitioning?

Hey guys,

The title sums it up - is there any built-in partitioning in place? I don’t just mean for collisions (can’t remember if PhysX does that already), but retrieving the other UObjects in the same bucket as another, such as an AI unit getting back the other AI units that are near it, vs getting back all units.

Thanks,
HateDread.

I’m going to qualify my answer by saying I’m not 100% sure and don’t have the code in front of me, but this is my best guess based on what I know:

Unreal Engine does use spatial partitioning (an Octree) but it is owned by the RenderThread (in FScene). But for entity queries in most game engines an entity system maintains it’s own spatial hash of the entities and writes out their positions to the RenderThread in a one-way relationship usually with 1-frame lag. So the GameThread doesn’t read back from the RenderThread’s Octree for queries, no, you’d generally use the entity system’s own method of queries from it’s hash (or list…).

For querying entities withing a radius in Unreal I think you’d attach a sphere component with the radius you wanted then use the components’s GetOverlappingActors method (or the Actor’s method which queries that for all attached components). I think the physics system is maintaining a list of component overlaps. As for what system the physics is using, Physx is said to be using a Sweep and Prune algorithm for acceleration.

So for AI units and such, you’d probably want to have each AI unit write its position to the blackboard (haven’t looked into how the blackboard works in UE4, but if it’s like standard ones, this should be how to use it), instead of using a physics system to query, unless you’re actually doing something like avoidance, in which case where overlap triggers and stuff are good.

But for actually querying, blackboard is the best, and it doesn’t cost too much (shouldn’t anyway) just to set a position onto that each tick. Then your AI can access it.

If you need to make them move together, or do avoidance, a position and knowing a radius for a sphere that covers the unit is pretty dang good, and also quite lightweight.

Theoretically anyway.

If you’re doing something different of course and need like events for overlapping, that’s when it’s nice to use physics volumes for triggers and such.