Most efficient way to merge two buffers on two entities

I'm not very familiar with the terminology so please accept this drawing.


Assume Entities represent bottles. They have a buffer representing their contents. Bottle A on the left has two elements. Bottle B on the right has three elements, with an extra element that adds both volume and a different kind of element.

I want, in the most efficient way possible, to take Entity A and B, compare their contents, and then resolve them such that Entity A and B have different buffers representing interaction (i.e. they're mixed and evened, so that Entity A has an added C:2 and Entity B has C:2 instead of C:4).

It has to be blazing efficient. There are thousands of these in the environment.

 

Are the elements sorted in their buffers?

 

No. I don't think sorting is possible (there can be a huge number of elements and duplicates of the same element with different properties). Can I hear what your suggestion would be if they could be sorted? There might be a halfway point.

 

If they were sorted in each buffer, you could zipper merge them into a scratch buffer, divide the content values by two, and then memcpy the scratch buffer to each DynamicBuffer.

 

I am not sure if I got what OP means, but if buffer'w slices are not suitable, maybe try using Native Hash Set or Map? There is also Multiple Hash Map. Then later you can easily get unique values and sort if needed.

 

It's not an issue of "how do I take two sets of data and make them identical halves equal to the sum of their parts".
It's an issue of "how do I, in ECS, interact with the buffer of a second entity?"

I can make sure that the other entities are not a part of the parallel job's set of entities.

 

Store a reference to the required entity, then just use BufferFromEntity for that entity?

If you need to have unique non-repeating contents from both buffer in a single one - simplest solution as mentioned is by using NativeHashMap.

For other operations, it probably would be a lot tricker if non-bruteforce methods are applied.

 

Let me try to better illustrate what I hope to accomplish.

I am attempting a very rudimentary physics simulation in pure ECS. Below is a Rubick's cube which is a very close representation of how a 3x3 room looks in my simulation. Each cube is a meter, and the simulation makes a Z-level 3 meters tall. So, a 3x3 room has 9 cubes representing a cubic meter of air.



They alternate black and white like a chessboard because this is how I believe I can cleanly simulate exchange.

Lets suppose that the black cube in 0,0,0 (bottom, closest to the camera) suddenly has three times as much air as the rest of the room.

First, the simulation runs the black cubes. It has three times as much pressure as its adjacent cubes, which are white. So it imparts on them some of its gas to equalize (the exchange rate will depend on local factors).

Then, the simulation runs the whites. Now those three cubes adjacent to the first black one have a pressure higher than their black counterparts, except the first, so now they will exchange with their black adjacent cubes.

This repeats. Eventually, after a small amount of time, the room will achieve homogeneity.


The contents of the cube are important. It might be three times as much air or it might be a bunch of chlorine gas. It might be hot steam or very cold nitrogen gas. I can't really assume anything about their contents.


For implementing this with ECS, it's much harder to explain. When I tried this in the past with Unity and a bunch of GameObjects I had success but of course that's all single threaded.

In my head, it looks something like this.



However, I don't know if it's possible to do this. Can a parallel job store data outside of its anonymous function to be actioned in a meaningful way in a different job that has to await its completion?

 

Yes, just write required data to the native container (any that fits use-case).


As for job dependency, its possible to combine dependencies directly (to create a job chain):
1. Create required systems;
2. In second system that has to wait -> fetch "Dependency" from the first system in OnUpdate;
3. Do:

Code (CSharp):

1. Dependency = JobHandle.CombineDependencies(*firstSystem*, Dependency);

4. Start parallel job as usual. Second job would run after first one completes + other system job dependencies are completed;

 

If I understand correctly, because each cell is related to other cell, it may be challanging to run it in parallel.

But I would use NativeMultiHashmap, or nativeList both parallel.

So you iterate through all cubes, and only consider higher pressure to lower pressure tra sition. You calculate how much of pressure should be moved and add value to list, or native multi hashmap. Hashmap would hold key as entity and value, how much of preasure need be added.
Similar with list, but you store strict inside, with entity and value of preasure.

In case of hashmap, you can have job for each of cubes, which looks for keys in hashmap, and grabs values. Acummulate pressure difference and add to the cube. Or whatever meed be done.

In case of list, you probably want run it single threaded. You grab values and entities and apply accordingly to your cubes.

The difference between approaches is, hash map requires all entities cubes to be iterated, for run checks. But is parallel and blazing fast anyway.

For list, you iterate only number of elements in the list, but is single threaded. You may have multiple elements, applying preasure changes to same cube.

All/most can be done in parallel. But you will need two jobs.

 

I'm having a very difficult time overcoming DynamicBuffers. As I described in OP, the contents of the cubes (which is called a 'jar' for storing elements) is a DynamicBuffer.

Even when completely ReadOnly, I can't create an IJobForEach because I cannot pass a DynamicBuffer as a constructor type. I cannot try and pass a DynamicBuffer of values to a NativeHashMap in the ParallelWriter because DynamicBuffers are not blittable.

My ForEach constructor looks like this:

Code (csharp):

1.  
2.             EntityQuery query = GetEntityQuery(
3.                 ComponentType.ReadOnly<ChemicalComp>(),
4.                 ComponentType.ReadOnly<Pressure>(),
5.                 ComponentType.ReadOnly<Jar.Adjacent>()
6.             );
7.             var hashMap = new NativeHashMap<Entity, DynamicBuffer <ChemicalComp>>(query.CalculateEntityCount(), Allocator.Temp);
8.  
9.             // find all jars that have been made inhomogenous by content changes
10.             Entities.WithBurst()
11.                 .WithAll<ChemicalComp, Pressure, Jar.Adjacent>()
12.                 .ForEach((ref DynamicBuffer <ChemicalComp> comps, in Pressure pressure, in DynamicBuffer<Jar.Adjacent> adjacents) => {

It's driving me crazy. What I want to do should be the simplest thing in the world.

Container A has 1 part Air.
Container B has 3 parts Air.

The 1 part of Oxygen at room temperature is a ChemicalComp. The contents are described as DynamicBuffer<ChemicalComp>.

Container B has way more pressure than Container A. If they are exposed to one another, they will eventually completely homogenize, but for the sake of this I just want them to even out their pressure difference.

Container A has nothing to give to Container B. Container B has a difference of 2 parts of Air.

In the first job, this difference is detected. I would like that at this point a HashMap, or some other ledger, notes that Container B needs to remove 1 part of Air and donate it to Container A.

The second job should write these differences from the HashMap.

Is there an example of this documented anywhere?

 

You don't pass whole buffer into hashmap. You iterate elements, check for changes and pass only entity as key and pressure change as value. You don't need pass values, if they for example don't change.

I do not expect any official docs. But there is quite a bit talk and forum threads about hash maps. Worth check them. Bit simply experiment with it.

Also look into Unity DOTS git samples. Search for relevant keywords. It is reach source of information and examples.

 

Hello,

What I understand from your post is that you are trying to make involves concepts similar to voxel world and flood simulation. It makes me think of a weather simulation.

The voxel world concept has been discussed many times in this forum and the concensus is is that an entity per voxel is a bad idea.
Your buffer of elements seem to take that approach so I would probably try to rethink that part.
Also the fact that you buffer can contain different type of element makes you miss on parallelisation option.
If you were to have the element type as component you could run systems that operate on different kind of elements at the same time.

I would try to go with one entity that has a buffer for each type of element. Each buffer would contain 9 values (taking your cube exemple) to form a chunk.
You can then have a system/job for each type of element to do the pressure equalization among the cells of the same chunk.
You could also have systems to mix element together. For exemple if your cell has hydrogen and oxygen element and the right pressure/temperature property you can consume those element to produce water.

Your accessing adjacent cells would be simpler except for bordering chunk cells.

Also about buffers you can't read from adjacent cells while also writing to the same type of buffer because another thread may be reading from that same buffer you are writing to pr the other way around. You have to use a double buffering strategy. Copy the data to read to a new container as read only data and write to the "original" buffer.

 

1) I don't think a global hashmap will never make any sense. I think any hashmap proposal here was aimed towards any individual cell vs cell interaction to match up the elements.

2) This type of entity interaction is non-trivial to parallelize, and the safety system is going to be up in your face about it. If you want to make peace with it, you will need to double-buffer your dynamic buffers. That means adding a second DynamicBuffer type that receives the output of the operation, such that the two input buffers (one from each entity) are read-only. This is a "gather" approach to the problem.

3) The ECS data structure isn't really well-suited for spatially aligned data, and so consequently your buffer accesses are all going to be random. Using a different data structure will likely offer you much better performance, but may take a fair bit of work to get running.

 

You're right, it is very close. I haven't thought of that before.

Can you link me to suggestions if entity per voxel is a bad idea? It won't be in the range of millions of entities but there will be thousands of them.

Edit: I've found this thread, but unfortunately there doesn't seem to be an actual suggestion.
https://forum.unity.com/threads/designing-a-voxel-structure-around-ecs.883537/

Edit 2: I'm pretty sure I have to use an entity per voxel. I'm looking at a map of like 1024x1024x3 tops and there's a lot more going on than just 'sand cube' and 'dirt cube'.

If I'm not using entities or gameobjects for those I cannot even conceptualize what else I would be using. My folly here is that there is a lot of information I'm going to have to attach to each meter in space.

 

I have not played with this kind of implementation myself and my view on the subject as evolved quite a bit as you can see from my post on the thread you mentioned.
I would use the search function of the forum to look at all post/thread that mention voxel. I'm sure you will have lots of interesting reads.

 

I actually thought that @DreamingImLatios had a long time posted something around kernels for neighbors but I might be wrong, this was long ago and maybe someone else (since he is responding here).

Completely different problem (some belt logic) but relevant for double buffer and parallelism…can’t find thread but it’s in dots forum and I think @tertle posted a great solution (also some year back)

 

You know that is over 3mln voxels? Assuming filling up whole space.

What you can do. is to have entities as chunks. Then store all data of voxels in that chunk in buffers for example.

Problem with double buffer is, that it still has limit, how much can be written in parallel, when voxels interact with each other. If having two or more voxels writing to same voxel data, you are stuffed. This is where I would prefer use storing changes in native List, or multi hashmap, and run second job, to finalize calculations.

Depending how often data is calculated and how many, you may need to weight, which solutions are more suitable.

 

One additional tought maybe you can use shared component data to segregate white and black cells/chunks. That way you can use that to treat black chunks on even frame and white ones on odd frames. That could avoid double buffering (saving lots of memory) by accessing one set in read only while you access the other in write only.
Either way you will have to adapt the logic for the bordering cells of the chunks.

 

@WAYN_Games I think white and black vixels were just to represent differences of air pressure. I suspect, they can be of any value and changing often. Hence shared component won't be suitable.

 

That's what I was planning, yes. I have them tagged White and Black so they can alternate without constantly writing over themselves.

I'm looking into blob assets to move adjacency data over to that and I have an approach I'd like to try.

Question: What is the appropriate way to use NativeList<T>.ParallelWriter? I can't .Dispose it, it creates memory leak issues, and if I don't use ParallelWriter it doesn't work with .ScheduleParallel() jobs.

 

The aim of the shared component would no be to have data in itself it would just be to segregate adjacent cells in an alternating patter to ensure that a white cell is always serounded by black cells. That way you only have to write to the your color and read from the other.

Blob are for static read only data. There is no control for write yet after creation but once they put that in place you'll be screwed. Or you would have to do like the physics package does and rebuild everything every frame.

One tip when it comes to understanding how a container is used is to look at the tests of the collection package .

 

I wouldn't store the pressure / gas data in Entities either. It does not seem like a good data structure.

I'd just create a system that would own and update the simulation of gas transfer. It would use whatever container would be most suitable (maybe flattened 3d array or something like that).

Any other system would be able to get access to the owning system and access the data. This means other systems could 'read' the gas data. When something releases or consumes the gas, it would simply attach component to some entity. Then entities with such component would be picked up by another system which would write into 'gas data'.

Maybe the simulation could even write some 'command buffer', which would contain information that some room is for example toxic or no longer toxic. This command buffer would then attach components to entities so you can build logic on top of that using entities.

Now for the container itself and the way it updates:
- you probably want to have two copies of data, read A, write to B, then swap
- to parallelize well, you want one worker per write location
- each worker reads surrounding area in A, calculates output for his cell and writes it to B
- ^^ this can be parallelized very well (concurrent read access is fine)
- it has to take into account both received and transferred amount
- it shouldn't be hard to calculated that ^^ based on pressure gradients

I don't know how your logic around different gasses work and how many of them are there.
- if it's just small number of different gasses maybe have small fixed array for each of them directly in each location?
- and maybe one extra slot as sum for total pressure so you can calculate the gradients quickly?
- I'm really guessing here

 

Thanks for all the input. The BlobArray is definitely something that should be promoted more in the documentation. And thanks @WAYN_Games for the tip about the unit testing, I was able to figure out what I was missing that was preventing me from using native collections like I wanted.

I moved the adjacency information from the tiles to a BlobArray and it felt like a eureka moment. Definitely a way forward. A lot of this data never is totally static and just needs to be kept in a read-only, ultra-performant format.

I'm definitely going to try and de-entity the voxels. I forgot the tiles also had entities, so on a 1024^2 grid you're looking at ~1m for the tiles, 3m for the voxels, and then more entities for things to put in each.


I do not have a plan for storing chemical contents without entities. @OndrejP outlined his ideas for this and I would probably need to see sample code to fully understand his suggestion. It's a complicated task, because when I think of in terms of numbers, it's 3,145,728 cubes containing a variable number of elements from a table of elements which would be defined by scripts and not through hardcoding. A BlobArray seems like the wrong tool for this because it's not easily determined what the bounds of the the array would be, or how I would serialize the data so I can easily determine what belongs to which area.

Just tacking this information as a 3-dimensional array of arrays onto a system seems like cheating, or a divergence back into OOP and defeating the purpose of ECS. I can't guess how it'd actually perform, that's just my intuition on it.

To help, here's what data is contained by a ChemicalComp structure.

Code (csharp):

1.  
2. public struct ChemicalComp : IBufferElementData {
3.     public Chemical Chemical;
4.     public Matter Matter;
5.     public Temp Temp;
6. }

Chemical is a regular struct but with a lot of data that I will move to a BlobArray.
Matter and Temp are simple Value = float structs which have useful math functions on them.

So a compressed ChemicalComp will look like [int,float,float]. I need to store something like ten million of these, read and write.

Edit: I just realized that a 3 byte struct multiplied by ten million is actually a lot of memory. I guess this is why chunking is done. If you can reduce 96 bits to something smaller by making it relative to a chunk, that's more ideal.

 

That sounds like something I would post. The terminology is a bit trickier to apply here because this is a 3D grid with a variable number of elements per cell. But the underlying concept (double-buffered gather) is what I was suggesting here as well.

I highly recommend you use NativeQueue or NativeStream instead. Note that the ParallelWriter and other nested types are just views into the parent container with different read-write capabilities that make it thread-safe for its particular "mode". But Disposal should always be done on the top-level container.

 

Over the last few days, I've painstakingly decoupled the spatial structs from entities. Now, only the actual grid has a component/entity and through that any specific information about the three-dimensional structure can be determined.

I'm now going to start approaching my original issue with this new perspective.

One of the things I am doing is moving all the chemicals from simple structs to entity components. I'm a bit torn over this. If I make chemicals into structs, then other components wanting to reference those chemicals must either reference the Entity (and thereby require an entity lookup to ever actually utilize that information), or store copies of that struct locally.

The chemical structs are by far the most complicated struct in my code and is at least 12 4-byte fields, so if I understand how it works, any struct with a Chemical field is actually at least 48 bytes in size because it makes an entire copy of the struct.

However, If I decided to make this a class, then it can't be used in ECS.

It makes me wonder if I should just succumb and use a public static on the Chemical struct. I could serialize it into a BlobArray, but I don't know who would own it.

I feel like I am now overusing BlobArrays, however. Basically everything I used entities for is now in a BlobArray and I'm looking at the Chemicals (which, granted, will be built once at the start of the game and are totally immutable) and thinking how I can BlobArray them too.

Can you please give me an example a system that has an implementation like this where it "owns" the set of data? I've only seen systems working with entities. Do I just query a bunch of entities in the OnCreate() and then set up everything I need for the read/write jobs?

I suppose my confusion stems from how systems are "set up". I know how entities are set up. I have a spawner GameObject that creates everything. Systems just sort of exist and I don't know how to work with them like I might need to.

 

"System owning a data": There are two easy ways I know of, each has some pros and cons.

The first is system simply having some data container (as field) and sharing it to whatever other system wants it.
Other system would call in OnCreate something like "GetOrCreateSystem<DataOwningSystem>" and then in OnUpdate get the data container m_dataOwningSystem.GetGasDataContainer() and use it.
...this was two disadvantages, first is that data lives outside entities, second is that there's no thread safety regarding the container (if you would modify container data only in DataOwningSystem, it's not a big problem).

The other option is to use a singleton entity and store the data there (as bunch of normal and BufferComponents). ECS will handle thread safety regarding parallel read/write in this case and you'll have all data on the entities which is good. The disadvantage is that you have limited data structure to simple structs (components) and simple arrays (buffer component).

You can take a look here, where I use this system for Pathfinding and Ground information:
https://github.com/OndrejPetrzilka/...sEcs/Assets/Scripts/Simulation/Pathfinding.cs

For prototyping the first system is really easier to setup and play with.