[Solved]Conciling Procedural generation with ECS

Hello,
this is a bit of a technical question concerning procedural generation and ECS (as stated in the title). Here's the context :

- I have a procedural generation engine
- I use ECS to generate 40+k blocks with different textures (not one texture with multiple block texture similar to an atlas, but full HD textures, one per block type).
- As it is a sandbox game with destructible/constructible terrain, i need to access data on each block per coordinate/index
- ECS gives block list in random order
- I want to be able to move only some blocks to new positions, and keep the other where they are so the terrain can follow the player, and not recreating 40+k blocks each time the system's update is called (pooling the entities essentially)

What would be a recommended way to access a block by coordinates.

I thought of a few solutions :
- Using a loop and check for Position values, but it would be very complicated for a pooling system.
- Using some kind of id to mark entities needing change, and keeping the data in a table outside ECS systems, which would be used by the systems. But then it adds a need for more resources.

Also, i took a look at job interfaces, and it's a bit confusing. If i have to change the MeshInstanceRenderer of a lot of blocks in a single frame, which would be the most appropriate? I thought of using IJobParallelFor, since the other don't seem to fit the criteria, but am i right?

 

There is possibly few ways of doing it.
First I would be looking into minecraft approach, of having chunks.
You can have organised references to entities in arrays.
Alternatively, what I am looking at atm., is partitioning by using octrees. And use ray to scan quickly through.
Also, you can assign for each entity, near entity neighbor reference, storing information, on which side, which neighbor is placed. Then you can simply iterate through them.

Either way, you need some form reference, or collection. But one thing I wouldn't be, is to try of creating one infinite size 3D array.

 

@Antypodish Hmm, i haven't had to look at octrees yet, will do.

However, from your answer, it seems i poorly explained my intentions :
- I understand i can't have an infinite sized collection. I never intended to do so. The plan is to have one chunk per player, at a set size (i will determine the size later on based on performance of the system). The only hickup i'm having is deciding how to store those references for easier reuse.

Let me give you an example or two of the use i might do, depending on the implementation :
- The player moves 20 blocks on the left. The chunk is big enough to not have to move anything before the player moves so much. But now, the 20 right most block columns are outside the chunk's area. I would want to move only the 20 right most columns of blocks on the left and reassign the new block types to them. Without touching the other blocks that are still inside the chunk's area. If i use pure ECS without any other references, i would need to loop once to mark all blocks that need movement (keep in mind we can have multiple players which can cause confusion as to which blocks belong to which player's chunk, also that is for now 40+k blocks per player, and i'm talking about the server side here, obviously the client side will only display what the client can see).
- Another potential problem would be when having 2 players near each other. This means many blocks would be visible by both. That also means that many blocks that were assigned only to each player would have to be shared, and the left over would need to be put in a pool. But how do you know which entities were placed in a pool already and which need to be placed in a pool? Do i need a specific data component that has a reference to the entity and information on the shared block? So each time i need to check if a block is shared i go trough that list? It's pretty innefficient in my opinion.

I just though about something. I saw there is a IJobParallelForFilter which reminded me : Is there a way to filter data
prior to receiving the lists inside the systems? If there is, how efficient is it?

 

I haven't used IJobParallelForFilter yet, so unable to answer to this.

From what you are saying, you mainly want to shift columns of blocks. So that makes a bit easier, since you need only to think about 2D architecture. From my understanding, each column has an array. Presumably fixed array of entities references, (since you have limited height?).

But columns handling itself, is the matter.
I see your logic is bit more complex, since you got few possible players etc. Which my brain a bit lazy right now.
But I would approach it with equivalent of 2D array (like view from top) and build logic based on that. Then you worry only about column indexes in the 2D arrays. If that makes sense? Assuming I understood it right.

 

@Antypodish Thank you for the input, however, i used columns as an example. Rows are to consider too, because the player can move horizontally as well as vertically. Also, although it is a 2D side view game, there are several layers (front, back...) so it's more like a 2.5 side scrolling game.

The reason i have yet to use fixed size arrays is because of this shift that could cause some problems. For example :

In the normal version of Unity, i use one dimensional arrays, and convert coordinates to indexes to acces the block data. However if i begin shifting the data, the coordinates and indexes will all change, thus needing a new array with shifted data. Which would be pretty inefficient. I think it would be a lot faster juste moving all the entities and assigning them types based on new positions.

This might be premature optimisation, but considering i have to use coordinates for adding physics later on, i think i should do this properly rather than changing the whole one i hit the really gritty part of the game. Let me give you a few examples of physics i need to implement later on :
- The usual moving objects with gravity and collisions
- Wall/ceiling walking units
- Fluids (water, oil, lava...)
- Jet packs

This all will need to have collisions with other blocks, so i will need to efficiently access blocks to simulate the physics since physics are not currently implemented in the game. Also, i can't be iterating over all the blocks and checking if they are affected by a collision or some physics effect each frame. Your idea about having neighbours is ok as long as only blocks interact with each other, but once you add moving objects, it becomes very hard without being able to access blocks on specific coordinates almost instantly. That is why i considered a fixed size array, but because of the shifting part, i have yet to implement it. The other option i considered, iterating over all positions...well because of the sheer amount of objects, i don't think i would attain the 60fps i want to have.

 

Ok, I will attack question from different angle.

Why in first place you want to move this blocks? Are there vehicles? Or you try to tackle floating origin? Or something else?

 

@Antypodish yes well, i was trying to not do the chunking of the map since it add some overhead and more calculations. But with all the complications of trying to move the blocks and such, it might be the best solution. Though, i still will be needing the access of blocks per coordinate for physics. But with the chunking, i could have each chunk hold an array to all the blocks they oversee. That said, i'm wondering if i could have an ordered array of entities, or block data directly rather than having to order it each time the system is called. If i add a separate struct/class containing block data, that will simply add overhead and use more resources. But i haven't seen a way to order the arrays we get with the system.

 

I think I have seen recently topic regarding ECS collection request. So there may be a chance, they will appear at some point. Including sorted list etc. By what you saying, you definitely need some grouping mechanism. Group 10x10x10, that already 1k blocks. Then iterating by 40 groups of blocks, ( which is equivalent of 40k blocks), is almost 0 overhead in comparison.

So far, you can try to look at sorting algorithms.
I.e.
Data Structure - Bubble Sort Algorithm
https://www.tutorialspoint.com/data_structures_algorithms/bubble_sort_algorithm.htm

Not the cleanest way, but this is what we got atm.
And keep sorted, every time, anything changed.
That is what happens normally anyway.

 

@Antypodish Yes, i was afraid i would have to do that. The problem i'm seeing is not on the sorting side, but on the ramifications of such implementation. This is basically the collision detection system of many 2D games :
-First we split the scene in big chunks, then each to smaller chunks, then each of those can be split to even smaller chunks, so forth so on...
- When we want to check for collision, we first get the biggest chunk containing the collision points, then we drill down till we find the objects concerned by the collision.
- Then we apply whatever the collision is for.

If i recall correctly, one of the famous games implementing this is R-Type. In any case, i was hoping to avoid this multi layered thing because it adds complexity. Complexity i wanted to avoid. But it seems i have no choice on this matter. In any case, thanks for the helpful replies. With this, i think i know which way to go from here on.

 

I don't think even in current OOP, there is any specific effiecent way, of storing and searching 3D arrays / list, by position.
You can try Linq, but has a bit overhead, when requesting queries.
Also, I am not sure if Linq is suitable for ECS. Simply I don't know.

This is, where octrees come useful as an example.
You grab group, or groups, in required group only. Which is fast.
Only that, octrees don't like to be moved. You can of course, but that implies expanding and contracting octrees leafs/branches. Depends, how often you want to do checks, this may be not a problem at all.

 

@Antypodish Actually there is, a simple way :
- This works for 2D as well as 3D
- First decide which way to look up (top to bottom? left to right?)
- Then decide the size of chunks, they all have to be the same size
- Then make 1D arrays per chunk
- Use coord to index conversion to access block data

The math is simple in 2D (usually we use bottom to top and left to right) :
- chunk origin = chunk coordinates - (chunk size / 2)
- local coordinates = world coordinates - chunk origin
- Index = local x + (local y * chunk width)

It's similar in 3D except you factor in depth. But in the same way as octree, it doesn't like moving, since you would need to move everything to keep the coordinates consistent.

 

Yep this 1D array good one. I completely overlooked it.
I think even was even discussed somewhere recently here.

Providing you have group, which stores 1D array of its blocks local position, you don't really need move blocks in array. You just shift group (chunk) itself, in parent 1D array of groups (chunks). Or chunks of chunks, etc.
1D array is definitely much more friendly for ECS.

 

@Antypodish yes, but the math is complicated. I'm already calculating chunk size based on max view size so i have chunks big enough to cover the view but not too big so unnecessary blocks are instantiated, then i would have to calculate which chunks at which position i have to make too. I already did the math with the normal Unity version, and it's not pretty. Lots of positional math. The good side being i can simply reuse said math.

 

@mike_acton i understand the general usage of the version you are talking about. However i fail to see the application in my case. I haven't looked at GetComponentOrderVersion yet. Is there any documentation i could read up on that? I don't remember seeing that in the github ECS documentation.

 

@Antypodish, @mike_acton : I finally arrived at something i'm ok with. In the boostrap, I'm creating a list of objects contaning information on the chunk it concerns, and having a 1D table containg a few informations pertininet to block manipulation

The blocks are sorted in a way that i can use world coordinates to access the block under said coordinates.
I'm even using that to move chunks around. So far, other than a few spikes to 40ms (that i will look into), the rest stays well under the 14ms (i think the average is around 7ms). I'm sure there can be optimization work done on what i wrote. But for now i need to hool up the system with the map generation.

 

@Antypodish So, i tried to play around with the solution i got, and once i begin moving around, diagonal moves give big spikes : from 7-14ms, up to 74ms. The slowest being the creation system. It takes around 50 ms to execute when i'm callin upon the generation system. And currently it's only a simple one that returns a value from system.random

This is still an improvement from the 8 seconds for the previous version (yes, unplayable, i know). So i want to jobify the creation part. The problem i'm facing is how to jobify that part. No matter what i try, i'm getting the erro saying i'm writing on entities i shouldn't.

Here is the code :

Spoiler: Normal Method

Code (CSharp):

1. private void CreateBlocks(ChunkData data)
2.         {
3.             float3 chunkOrigin = new float3(data.CurrentPosition.x - (data.Size.x / 2.0f), data.CurrentPosition.y - (data.Size.y / 2.0f), data.CurrentPosition.z + 1);
4.  
5.             //Get reference to the chunk so we can iterate only on the concerned blocks
6.             var refs = BootStrap.GameData.Players.First(p => p.Id == data.PlayerId);
7.             //Get the array with the blocks
8.             refs.Blocks = new NativeArray<Entity>(data.Length, Allocator.Persistent, NativeArrayOptions.UninitializedMemory);
9.             //Instantiate the entities
10.             EntityManager.CreateEntity(BootStrap.BlockArchetype, refs.Blocks);
11.             var scale = new Scale { Value = BootStrap.Settings.Map.BlockSize };
12.  
13.             //Iterate over all positions and generate the blocks
14.             for (int y = 0, idx = 0; y < data.Size.y; y++)
15.             {
16.                 for (int x = 0; x < data.Size.x; x++, idx++)
17.                 {
18.                     //Get entity
19.                     var block = refs.Blocks[idx];
20.                     //Set block view owner
21.                     var id = new BlockIdentityData { Id = data.PlayerId };
22.                     //Set position
23.                     var bPosition = new Position { Value = new float3(chunkOrigin.x + x, chunkOrigin.y + y, chunkOrigin.z) };
24.                     //Generate block type
25.                     var bData = new BlockData { Code = GenerateCode(bPosition.Value, 0, 0, ResourceManager.Textures.Length) };
26.  
27.                     //Apply changes
28.                     Buffer.SetComponent(block, bData);
29.                     Buffer.SetComponent(block, scale);
30.                     Buffer.SetComponent(block, bPosition);
31.                     Buffer.SetComponent(block, data);
32.                     Buffer.SetComponent(block, id);
33.  
34.                     //Add marker so we can update mesh instance renderer
35.                     Buffer.AddComponent(block, new BlockViewUpdate());
36.                 }
37.             }
38.         }

Spoiler: Jobified method (after many tries and corrections)

Code (CSharp):

1.  private void CreateBlocksAsync(ChunkData data)
2.         {
3.             float3 chunkOrigin = new float3(data.CurrentPosition.x - (data.Size.x / 2.0f), data.CurrentPosition.y - (data.Size.y / 2.0f), data.CurrentPosition.z + 1);
4.  
5.             //Get reference to the chunk so we can iterate only on the concerned blocks
6.             var refs = BootStrap.GameData.Players.First(p => p.Id == data.PlayerId);
7.             //Get the array with the blocks
8.             refs.Blocks = new NativeArray<Entity>(data.Length, Allocator.Persistent, NativeArrayOptions.UninitializedMemory);
9.             //Instantiate the entities
10.             EntityManager.CreateEntity(BootStrap.BlockArchetype, refs.Blocks);
11.             var scale = new Scale { Value = BootStrap.Settings.Map.BlockSize };
12.  
13.             new CreateBlockJob
14.             {
15.                 Blocks = refs.Blocks,
16.                 Buffer = Buffer,
17.                 Id = data.PlayerId,
18.                 Origin = chunkOrigin,
19.                 Scale = scale,
20.                 Width = data.Size.x
21.             }.Schedule(refs.Blocks.Length, 1).Complete();
22.         }

Spoiler: The job

Code (CSharp):

1.  
2.     //Of course can't burst compile an ECB
3.     //[BurstCompile]
4.     public struct CreateBlockJob : IJobParallelFor
5.     {
6.         public NativeArray<Entity> Blocks;
7.         [ReadOnly] public EntityCommandBuffer Buffer;
8.         public int Id;
9.         public float3 Origin;
10.         public Scale Scale;
11.         public int Width;
12.  
13.         public void Execute(int index)
14.         {
15.             var block = Blocks[index];
16.             var id = new BlockIdentityData { Id = Id };
17.             var y = index / Width;
18.             var x = index - y * Width;
19.             var bPosition = new Position { Value = new float3(Origin.x + x, Origin.y + y, Origin.z) };
20.  
21.             var bData = new BlockData { Code = BootStrap.GenerationRule.GetValue((int)bPosition.Value.x, (int)bPosition.Value.y, (int)bPosition.Value.z) };
22.  
23.             Buffer.SetComponent(block, bData);
24.             Buffer.SetComponent(block, Scale);
25.             Buffer.SetComponent(block, bPosition);
26.             Buffer.SetComponent(block, bData);
27.             Buffer.SetComponent(block, id);
28.  
29.             //Add marker so we can update mesh instance renderer
30.             Buffer.AddComponent(block, new BlockViewUpdate());
31.         }
32.     }

I also have to do a similar thing to the creation with movement. I'm trying to reuse existing blocks rather than destroying the ones outside the view and creating new ones.

I also thought about simply marking for generation the created blocks, and doing the generation in another system, but i would also need to change data, and mark them for update by adding a component.

 

You got error, supposedly, because your buffer is [ReadOnly].
However, I am not sure (don't remember) if you can have read/write command Buffer in parallel job.
Should work for single threaded job tho.

 

@Antypodish when you say single threaded job, do you mean IJob?

 

Yep.

 

@Antypodish i just tried and i get the same exception. It is thrown when i try to set the component of the entity. I was wondering if maybe the sharedcoponentdata would be the answer, but i'm not sure how to implement that.

 

So i've found a way to jobify the generation. I get mixed results...though it might be my code.
However, if i try to burst compile, i get an error about the static class i'm calling for the generation.
I know that burt compiler doesn't like the statics because of concurency, but then i can't even pass it a reference to the generator since it doesn't like non blittable vars.

The generator is an instance inheriting from an interface, since it allows composition. I'm using it trough the interface API. Is there a way to make calls to the generator with burt compiling?

 

You can try IJob instead IJobParallelFor, to see if that helps in your case.
I am not sure of the result tho.

Also, if you in doubt, you can check sample. They provide range of solutions. Maybe you will dig out something, you need to start of.

Make sure you don't use classes with ECS, if you want to gain most of it. You need use structs.

 

you may need to rewrite parts of it, but here is what I use for abstraction in jobs:

Code (CSharp):

1. public struct Main<T> : IMain where T : struct, ISub {
2.     // optional, holds 'sub' state
3.     public T sub;
4.  
5.     public void DoMain (Foo args) {
6.         // code...
7.         sub.DoSub(args); // sub can have state
8.         // or
9.         default(T).DoSub(args); // no sub may have state
10.         // more code...
11.     }
12. }

the important part is

where T : struct, ISub

, that means you can call interface methods on a generic parameter and the compiler will translate that into a concrete call on the struct method, which Burst will happily compile


so you will end up with

Code (csharp):

1.  
2. struct Generator<T1, T2,T3,etc> : IGenerator where T1 : ... {...}
3.  

where you specify the composition via generic arguments instead of passing interfaces to the constructor.

 

@Antypodish IJob is not useful in this case. Also i switched to IJobProcessComponentData. I looked at the samples but they are a bit outdated i think. Some examples use old preview versions. Also, they are not adapted to what i need to do.

@M_R thanks for that. However, i don't need generics. I have 2 interfaces :
- IGenerationRule : for defining how to generate
- IValueGenerator : for generating a value

The whole system is based around that. I want to be able to pass those to the Burst Compiled job so it can do the call to generate. However, it needs to be an instance since it contains instance specific info, such a seed number. Also, the rule number can be quite high, so i wanted to avoid the whole struct copy situation where it could create a important CPU load. Especially if prepping for job execution.

 

@M_R https://www.codeproject.com/Tips/1023213/Gotcha-When-Csharp-Structures-Implement-Interfaces
this is basically what i'm trying to avoid.

 

that gotcha doesn't apply with burst/jobs, because you cannot possibly have a variable of interface type. you can only have T, and that will be expanded by the compiler to the concrete type. the IL generated is also a

call

instead of

callvirt

, which then it can be inlined etc...

the only thing you cannot have is actual polimorphism, e.g. you have a List<IGenerationRule> where each element is of a different type.

you can avoid copying by passing things by

ref

.

 

@M_R polymorphism IS the goal. I have 3 different value generators, that each answer to a specific need. The same situation can be found with the rules. Unless you have a suggestion on how to replicate that with structs (without case/if inside a single class).
The aim is to allow for a mix and match between custom rules/generators.

 

if the order is not important, i'd go with multiple systems/archetypes/jobs (one for each type of generator) that each do their stuff and then merge the results.

burst don't support reference types, therefore no virtuals and no polymorphism.
(it is optimized for linear memory access, and both dereferencing a class and a virtual call are random memory access.)

also, accessing non-readonly static fields will be prevented by static analysis even without burst.

you can cheat a managed object into a job by using IntPtr/unsafe void* and casting inside Execute(), but it will then your responsibility to avoid race conditions (if multiple threads access to the same memory in the wrong way, Unity will crash or worse). and still no burst

 

@M_R the generator is used only to get a value. It does read values to return it, but it doesn't change anything the jobs are responsible for. So i can assure you it's thread safe. Also, the order is important. The system is made to follow rules of generation, so i can't use UpdateBefore/After to order it.

Also, is there no way to remove/add components inside a job? I mean, why allow for buffers if not to manipulate entities directly in a parallelized job? Or, can anyone give me a use for buffers other than that?

I'm asking because no matter what i try, i can't find a good way to remove a marking component from entities so the job doesn't get called on them again until needed.

 

You may need add something like

Code (CSharp):

1. public EntityCommandBuffer.Concurrent commandBuffer ;

Specifically Concurrent part in IJobParallelFor.

 

@Antypodish nope, i'm still getting the error messages.

 

I don't know them. If I were you, I would get back to Unity samples. Looking for answer.

 

@Antypodish this is exactly why i find this annoying. From the documentation, this should work, but isn't. Also, the samples don't cover all cases. I've already looked over all the classes that have jobs, but found nothing telling me why it doesn't work. Unless we're not talking about the same samples. Are you talking about the unity sample found on github? Because i was talking about those.

 

Yep thats correct.

 

@Antypodish i haven't found any example pertinent to my case. The only time they use the buffer is in a IJob. But that is not what i need. Since i need to simply remove a component, i would need to wait for the buffer so it can be done. But if i do that in IJob, it's the same as doing it in the system. Since both are dependant on the same buffer. What i need is to parallelize the work, but it seems that if i do that, i can't add/remove components. Which is what i find weird.

 

So i moved the work of the job back to the system. I will revisit this later on. With this, the system to be working nicely. I'm getting an average of <5ms with ocassional 20ms for visual update systems (changing MeshInstanceRenderers).
But even with all that, it runs quite smoothly.

I have only 2 problems left. One concerns ECS directly. The other might be related to ECS. So here they are :
1. When i stop the player, and relaunch it tells me an array has not been disposed of so there are leaks. The error is normal since i'm keeping an array of blocks to know which blocks belong to which chunk. However, i haven't found a good way to know when i should dispose of said arrays. Is there a sure way, in ECS, to know when the game is closing so i can dispose of all permament arrays?
2. I tried to build and run the game so i can check the performance without the editor overhead, but i only get the camera background and nothing else. I changed the camera background color to be sure, and it changed in the build too. But i don't see the player character nor the blocks. Is that normal?

 

[Job]ComponentSystem has

OnDestroyManager()

.
with MonoBehaviours, you should use OnEnable()/OnDisable() to allocate/dispose native containers.
custom classes can implement

IDisposable

and be disposed at the appropriate time

you should not use static fields. if you can't avoid it, ECS has an internal hook on domain unload

 

1. For that u use

Code (CSharp):

1. protected override void OnDestroyManager ( )

2. Did you attached scene to build?

 

@M_R is OnDestroyManager called when the scene unloads? Or when there are no elements to process?
Also, as i said, the array is so i don't iterate or change blocks that don't belong to the chunk. I know there is the parent/child now, but with an array i can access the blocks based on coordinates, so when i need only one block, i can get it directly instead of everytime iterating over all the blocks until i find the one i need.

@Antypodish yes, i checked the scene is attached. It's the only one in the build too, so it should launch the scene automatically. I even checked the packages with PackageManager just to be sure there isn't something missing. I also tried to switch between release and developper build, but to no avail.

 

when the World is disposed. it is completely independent form scenes. you can sync world and scene with a MonoBehaviour (create a new World in OnEnable, dispose in OnDisable, add systems manually, inject the world in the player loop).

you can also use

OnStartRunning()

/

OnStopRunning()

if you want to free the memory as soon as you don't have entities (worth only if your system is running very rarely, as you would allocate each time)

 

@M_R, @Antypodish i used OnDestroyManager, following your advice, and now i don't have any more exceptions.

The only problem left is that when i build and run, it doesn't show anything beside the background color.

All current entities use a MeshInstancedRender, which use a shader from Shader Graph. I wonder if that might be the problem.

 

Try standard shader.
Also have you checked GPU instantiating on a material?

 

@Antypodish yes, it is enabled. Also, isn't the standard shader unusable with MeshInstanceRenderers?

 

Why wouldn't be?

That works

 

@Antypodish i tried but i only get the pink color, the same as in your screenshot. Since it is not the texture i want, i'd say it doesn't work.

 

@Antypodish ok, i made a new material with standard shader, put it on my character prefab, and launched the builde and run. Nothing.

The character entity is created in the Bootstrap. When a player is added to the game, so is it's chunk. If the player is not created, there is no need for the chunk. I think the bootstrap might be the problem. But the bootstrap i'm using is the one from the twin stick shooter. I only changed the content of the methods. The methods themselves were left as is.

 

@Antypodish i added a canvas with a simple list of strings. I'm adding a string for each bootstrap method used, and i see they are actually called. I'm adding a player, and a camera entity. The only problem is that they are not visible.

 

Given that my build problem seems to more a shader + rendering pipeline problem than code, i'm considering the subject of this thread closed. Many thanks to @Antypodish, @M_R and @mike_acton for their invaluable help.

 

Hi All
I am trying to simplifying the meshes using DOTS because I work with VR projects and I need to optimize my 3D Assets for VR purposes(similar Mobile developing)
I was looking for any info about this topic but I only found that I would have to create IJob type that reduce the overhead when working with meshes but to be honest with you I have no idea for where I start, for it, Could anybody help or advice me with this topic? Would it be possible?
Hopefully you can understand me
Thanks for your time and sorry for my little English
Best Regards
Alejandro