I found more optimized job/ECS examples in this forum that don’t seem to work for my nested loop code example below.
I’m struggling to find a way to write into the outer & inner loop’s components here in a more efficient way (more efficient than just nesting loops and accessing components in the potentially slowest possible way here).
Design idea, an “interaction system”: Allow a system handling components of one type to iterate over potential related/usable components of another type and change both components when they start (and update) an interaction.
I wondered if I can write the loop below such that
the outer loop is parallelized, and
the inner loop can write to the components accessed (here with GetComoponentData/SetComponentData) of the outer and inner loop
Observations: The elements of type “InteractionComponent” in the outer loop should be easily parallelized since that’s just an IJobForEach iteration/parallelization over components that may change (allow read and write access).
The inner loop is more complicated here since we can potentially write twice into the same component of type “InteractableComponent” (if two elements of the outer loop affect the elements of the inner loop) and seems to need a classic mutex/sephamore MT pattern (?) to lock writes or at least make them atomic (in terms of access from different threads).
Any good nested loop improvements or code examples that do something like mine below?
Thanks!
PS: My current naive classic nested loop code:
protected override void OnCreate()
{
var query = new EntityQueryDesc
{
Any = new ComponentType[] {typeof(InteractionComponent) }
};
m_groupInteraction = GetEntityQuery(query);
var query2 = new EntityQueryDesc
{
Any = new ComponentType[] {typeof(InteractableComponent) }
};
m_groupInteractable = GetEntityQuery(query2);
}
protected override JobHandle OnUpdate(JobHandle inputDeps)
{
NativeArray<Entity> interactions = m_groupInteraction.ToEntityArray(Allocator.TempJob);
NativeArray<Entity> interactables = m_groupInteractable.ToEntityArray(Allocator.TempJob);
foreach (var Entity1 in interactions)
{
InteractionComponent Interaction = EntityManager.GetComponentData<InteractionComponent>(Entity1);
if (Interaction.CanInteract())
{
foreach (var Entity2 in interactables)
{
InteractableComponent Interactable = EntityManager.GetComponentData<InteractionComponent>(Entity2);
// Just an example: Affect both components to memorize that they're now in a state of interaction
Interaction.UsingInteractable = Entity2;
Interactable.UsedByInteraction = Entity1;
// ... and change a few other values on "Interaction" & "Interactable" to start their interaction
EntityManager.SetComponentData(Entity1, Interaction);
EntityManager.SetComponentData(Entity2, Interactable);
...
}
You need to create a partitioning scheme to separate things out. Let’s start with a simpler example and then expand.
Lets suppose you needed to check every interactable against every other interactable. One way you could do that is by splitting the interactable array in half, and then schedule a job for each half to use your naive loop on its own half. Then do a final pass where you have the first half loop over the second half.
It works by dividing the world into a grid of cells and placing anything that touches multiple cell regions into a special “cross-bucket” cell. The whole operation can be done in two passes, first a parallel pass on all the individual cells, and then a pass on all the cells against the “cross-bucket” cell.
Actually I noticed your post too late (need to set up my forum settings correctly)…
So I started splitting the loop by using “time slicing”, i.e. only iterating a maximum time over the outer loop (elements in the outer loop in my case are far more than the ones in the inner loop, roughly 3000 to 1).
Right, I see that a broad phase (like in physics systems) would help here, that makes sense.
It would also help solving the issue I didn’t mention in the code above, that strictly speaking two interactions could try to interact with the same interactable.
It seems that in ECS there are only a few options that many sources can change the same target entity at the same update:
add a dynamic buffer element for each individual interaction, and then resolve afterwards in a system/loop what this implies
write into a parallel writable native container for each individual interaction, and then again, resolve in a simple loop what the written elements imply
Anyway, I’ll read through your solution to get some fresh ideas how to spatially optimize this!
Thanks!
PS / Edit: I already wonder how long you are into (physics) programming?
The explanations on your GitHub and your insight into your tech design and physics are fairly advanced.
Here is a very simply trigger based interaction system:
[Serializable]
[GenerateAuthoringComponent]
public struct Interaction : IComponentData
{
[UnityEngine.HideInInspector]
public Entity interactableEntity;
}
[Serializable]
public struct Interactable : IComponentData
{
public bool inUse;
//this is a struct in my project that is part of a custom state system
//public State stateToStart;
public float rangeSq;
}
[UpdateAfter(typeof(EndFramePhysicsSystem))]
public class TriggerInteractionSystem : SystemBase
{
[BurstCompile]
struct TriggerInteractionJob : ITriggerEventsJob
{
[ReadOnly]
public ComponentDataFromEntity<Interactable> interactableLookup;
public ComponentDataFromEntity<Interaction> interactionLookup;
public void Execute(TriggerEvent triggerEvent)
{
var entityA = triggerEvent.Entities.EntityA;
var entityB = triggerEvent.Entities.EntityB;
if (!TryUpdateInteraction(entityA, entityB))
{
TryUpdateInteraction(entityB, entityA);
}
}
private bool TryUpdateInteraction(Entity interactableEntity, Entity interactionEntity)
{
if (interactableLookup.Exists(interactableEntity)
&& interactionLookup.Exists(interactionEntity))
{
var interactable = interactableLookup[interactableEntity];
var interaction = interactionLookup[interactionEntity];
if (!interactable.inUse
&& interaction.interactableEntity != interactableEntity)
{
interaction.interactableEntity = interactableEntity;
interactionLookup[interactionEntity] = interaction;
}
return true;
}
return false;
}
}
BuildPhysicsWorld buildPhysicsWorld;
StepPhysicsWorld stepPhysicsWorld;
protected override void OnCreate()
{
base.OnCreate();
buildPhysicsWorld = World.GetOrCreateSystem<BuildPhysicsWorld>();
stepPhysicsWorld = World.GetOrCreateSystem<StepPhysicsWorld>();
}
protected override void OnUpdate()
{
Dependency = new TriggerInteractionJob
{
interactableLookup = GetComponentDataFromEntity<Interactable>(true),
interactionLookup = GetComponentDataFromEntity<Interaction>()
}.Schedule(stepPhysicsWorld.Simulation, ref buildPhysicsWorld.PhysicsWorld, Dependency);
}
}
This code is thread safe (runs in a single worker thread) and simply sets an interaction component. The interaction component is the current interaction that an entity can use. A separate system(s) is needed for starting the interaction, setting the ownership of the interactable, etc.
On the topic of nested loops:
The most appropriate use of nested loops in a system would be a case where you iterate through the different values of a shared component and schedule jobs on groups of entities based on the value of the shared component attached to them.
Just as a heads up, I have some draft documentation written up that goes into the details of the underlying data structure that I plan to release in a couple of weeks but can send you an early copy of if it helps.
It is just collision detection and spatial queries, which I use to drive nearly all of my game logic for the kinds of games I make. Oddly enough, I’m not that experienced with actual physics simulations. I did a lot spatial query algorithm design in C++ between 2012 and 2016 before I switched to Unity.
I just tried something similar, still I had two small issues, still I may be mistaken with how to use and optimize triggers:
once I add Unity Physics and a body and shape “only” to support triggers my frame rate goes down considerably for my 2000 entities (speaking of magic numbers like “2000”, I could retry and measure this to get some more precise and useful numbers that tell what is getting so slow here)
it seems due to the physical simulation kinetic/dynamic bodies can’t be effectively teleported frame-by-frame by changing the “Translation” component so I’d have to change code running custom movement every frame to code that moves my entities via linear velocity
Yes, I think I see what you mean.
At least in general a spatial query like your example makes complete sense for cases like mine since a naive nested loop just wastes CPU time (not using any spatial information as an advantage here).
I just spent 30 minutes or so to browse your code so far and when I ran out of time I just roughly knew at that point that there’s a Query and its internal counterpart, still didn’t check how the spatial partitioning it is based on worked exactly.
Obviously, similar to what you state in your documentation (and partially implied in what I replied to the comment of user “desertGhost_”)…
I don’t really need to run a whole physics simulation (defining/allocating bodies and running kinetics/dynamics) “only” to run custom spatial queries.
In other words, it seems that your underlying concept of querying multibox overlaps/relationships is more the basic query level of logic I need here.
This is still a draft pre-pemdoc, so apologies if things are missing or aren’t clear. I also included some of the test code of the new algorithm. That test code is not the most up-to-date with what I use in my actual framework, and the test version might have a couple of bugs that I fixed in the actual version, but it is boiled down quite a bit and hopefully easier to understand.
