[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

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.:wink:
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.

One method: You can use EntityManager.GetComponentOrderVersion() to see if the order for particular component type has changed. If you need to maintain a lookaside index into your data (e.g. table from grid indices to component index), you can then update that lookaside table which you can store in your system, whenever the order version is bumped.

If you take the minimum order version of all the required components in your block type, that will be the version number that tells you if any block type component has been potentially moved.

For instance. Say you have block type which has components A and B. But you also have a different archetype which uses component A and C.

0123 4567
AAA AAAA
BBB CCCC

And you delete 6.

0123 457
AAA AAA
BBB CCC

The component order version for A and C will have been bumped, since the structure of those two components has changed. But the component order of B will not have changed. So the minimum value of (A,B) tells you that nothing in the (A,B) group has been structurally changed.

@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.

1 Like

@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 :
Normal Method

private void CreateBlocks(ChunkData data)
        {
            float3 chunkOrigin = new float3(data.CurrentPosition.x - (data.Size.x / 2.0f), data.CurrentPosition.y - (data.Size.y / 2.0f), data.CurrentPosition.z + 1);

            //Get reference to the chunk so we can iterate only on the concerned blocks
            var refs = BootStrap.GameData.Players.First(p => p.Id == data.PlayerId);
            //Get the array with the blocks
            refs.Blocks = new NativeArray<Entity>(data.Length, Allocator.Persistent, NativeArrayOptions.UninitializedMemory);
            //Instantiate the entities
            EntityManager.CreateEntity(BootStrap.BlockArchetype, refs.Blocks);
            var scale = new Scale { Value = BootStrap.Settings.Map.BlockSize };

            //Iterate over all positions and generate the blocks
            for (int y = 0, idx = 0; y < data.Size.y; y++)
            {
                for (int x = 0; x < data.Size.x; x++, idx++)
                {
                    //Get entity
                    var block = refs.Blocks[idx];
                    //Set block view owner
                    var id = new BlockIdentityData { Id = data.PlayerId };
                    //Set position
                    var bPosition = new Position { Value = new float3(chunkOrigin.x + x, chunkOrigin.y + y, chunkOrigin.z) };
                    //Generate block type
                    var bData = new BlockData { Code = GenerateCode(bPosition.Value, 0, 0, ResourceManager.Textures.Length) };

                    //Apply changes
                    Buffer.SetComponent(block, bData);
                    Buffer.SetComponent(block, scale);
                    Buffer.SetComponent(block, bPosition);
                    Buffer.SetComponent(block, data);
                    Buffer.SetComponent(block, id);

                    //Add marker so we can update mesh instance renderer
                    Buffer.AddComponent(block, new BlockViewUpdate());
                }
            }
        }

Jobified method (after many tries and corrections)

 private void CreateBlocksAsync(ChunkData data)
        {
            float3 chunkOrigin = new float3(data.CurrentPosition.x - (data.Size.x / 2.0f), data.CurrentPosition.y - (data.Size.y / 2.0f), data.CurrentPosition.z + 1);

            //Get reference to the chunk so we can iterate only on the concerned blocks
            var refs = BootStrap.GameData.Players.First(p => p.Id == data.PlayerId);
            //Get the array with the blocks
            refs.Blocks = new NativeArray<Entity>(data.Length, Allocator.Persistent, NativeArrayOptions.UninitializedMemory);
            //Instantiate the entities
            EntityManager.CreateEntity(BootStrap.BlockArchetype, refs.Blocks);
            var scale = new Scale { Value = BootStrap.Settings.Map.BlockSize };

            new CreateBlockJob
            {
                Blocks = refs.Blocks,
                Buffer = Buffer,
                Id = data.PlayerId,
                Origin = chunkOrigin,
                Scale = scale,
                Width = data.Size.x
            }.Schedule(refs.Blocks.Length, 1).Complete();
        }

The job

    //Of course can't burst compile an ECB
    //[BurstCompile]
    public struct CreateBlockJob : IJobParallelFor
    { 
        public NativeArray<Entity> Blocks;
        [ReadOnly] public EntityCommandBuffer Buffer;
        public int Id;
        public float3 Origin;
        public Scale Scale;
        public int Width;

        public void Execute(int index)
        {
            var block = Blocks[index];
            var id = new BlockIdentityData { Id = Id };
            var y = index / Width;
            var x = index - y * Width;
            var bPosition = new Position { Value = new float3(Origin.x + x, Origin.y + y, Origin.z) };

            var bData = new BlockData { Code = BootStrap.GenerationRule.GetValue((int)bPosition.Value.x, (int)bPosition.Value.y, (int)bPosition.Value.z) };

            Buffer.SetComponent(block, bData);
            Buffer.SetComponent(block, Scale);
            Buffer.SetComponent(block, bPosition);
            Buffer.SetComponent(block, bData);
            Buffer.SetComponent(block, id);

            //Add marker so we can update mesh instance renderer
            Buffer.AddComponent(block, new BlockViewUpdate());
        }
    }

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.