#Design effective Grid system

1 messages · Page 1 of 1 (latest)

meager loom
#

I want to implement endless generated grid where:

  • Cells grouped by a chunks which can be rather an entity or some other grouping data structure
  • Each cell is an entity which linked by grid chunk

all mentions of chunk refers to grid chunk and not to ArchetypeChunk

Cell count in grid chunk is known at compile time, so I can transform global grid coordinates (x,y) to coordinates of chunk then obtain that chunk and access cell entity by it's local to chunk coordinates.
This lets me access to cell in chunk with O(1).
But how effectively store grid chunks is an open question for me. I guess chunks also can be inside other chunks and so on, and if I know current top level of chunk nesting I can recursively access chunks until reach needed cell. How would you implement such data hierarchy? Though with growing nesting lvl grows number of ComponentLookup accesses.

However chunks can store fixed cells count and I'm looking for solution to do this. I see planty of ways:

  • Using just DynamicBuffer<CellLink> where CellLink : IBufferElementData { public Entity Entity; } but I don't need dynamic size collection for this
  • Using FixedListX<Entity> but again I don't need list functionality
  • Using c# fixed-arrays but they only allow us to use primitive blittable types in unsafe context while I need to store entity link and today unity ECS have no lightweight entity version with just single int or a way to convert single int to existing entity (or just use 2 fixed arrays of ints to store entities like separately)
  • Store nested collections somewhere on system side but not "on entities". This can be done with managed collection in a simple way or with native collections in complex way of implementing needed collection structure using all this unfamiliar to me unsafe native arrays, etc.

Well. Maybe one of dots senseis can give me clever advice. I hope so 🙂

brave crown
meager loom
meager loom
#

@brave crown can you help me a bit to understand internals of FixedListX?

last lynx
#

here you go, threw together a FixedArray of any size you want

# 
public unsafe struct FixedArray<T, TS>
        where T : unmanaged
        where TS : unmanaged
    {
        private TS data;

        internal readonly T* buffer
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            get
            {
                fixed (void* ptr = &this.data)
                {
                    return (T*)ptr;
                }
            }
        }

        public int Length => sizeof(T) / sizeof(TS);

        public T this[int index]
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            readonly get
            {
                CollectionHelper.CheckIndexInRange(index, Length);
                return UnsafeUtility.ReadArrayElement<T>(this.buffer, CollectionHelper.AssumePositive(index));
            }

            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            set
            {
                CollectionHelper.CheckIndexInRange(index, Length);
                UnsafeUtility.WriteArrayElement(this.buffer, CollectionHelper.AssumePositive(index), value);
            }
        }
    }```
#

use like this

        public static void TestMethod()
        {
            var fixedArray = new FixedArray<int, Bytes256>();
        }
        
        [StructLayout(LayoutKind.Explicit, Size = 256)]
        public struct Bytes256
        {
        }```
#

completely untested, implemented in 2min

#

but i think it should explain the concept reasonably well

#

alternatively you can make fixedlist variations that have a fixed size instead of allowing any size to be passed in

meager loom
#

wow! Thank you! What is T stands for? I understand part with TS it just a empty struct which layouted to 256 bytes, so we will have fixed 256 bytes array, but why we need to specify int as T ?

last lynx
#

T the type of the array

#

array<T>

#

array<int>
array<entity>

meager loom
#

I'm sorry, yeah, this is obvious

last lynx
#

basicalyl remove TS, and just put a fixed sized 32 struct in and call it FixedArray32Bytes

#

and you've got what FixedList is except without a length

meager loom
#

so I can use all N bytes without any padding

#

Well, I'm still wondering what is going on inside fixed list since I already have started to look inside

there is byte* buffer property which points to &data and then make offset by size of ushort which is reserved by length

internal readonly unsafe byte* buffer
{
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    get
    {
        unsafe
        {
            fixed (void* ptr = &data)
                return ((byte*)ptr) + UnsafeUtility.SizeOf<ushort>();
        }
    }
}

but then it has byte* Buffer property which uses buffer property + some FixedList.PaddingBytes<T>(), can't understand what padding bytes is since we already do offset for length

internal readonly unsafe byte* Buffer
{
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    get
    {
        return buffer + FixedList.PaddingBytes<T>();
    }
}
#

Buffer supposed to point to 1st element in collection

last lynx
#

i think it's just ensuring it aligns because of the length offset

#

you aren't going to have alignment issues without the length offset

#

because otherwise you have

|2 bytes| |List starts here 2 bytes offset this unaligned|

#

it's probably going to end up something like
|2 bytes| |2 bytes padding| |list starts here|

meager loom
#

thanks for clarificartion!

#

@last lynx @brave crown how would you store such chunks? FixedArray is good to let chunk contains cell entity links! But chunk count is dynamic, so I now need to figure out how to effectively obtain chunk by cell coordinate. I think to have somewhere HashTable but getting hash from int2 I guess not so performant

last lynx
#

personally i would just make 1 chunk per entity

#

and store chuk data in a dynamicbuffer

meager loom
#

how then you would search chunk by int2 position?

last lynx
#

if you already have the chunk?

#

or just int2 in the world anywhere

meager loom
#

just int2 in the world

last lynx
#

probably just have a map

#

that points chunk -> entity

#

it kind of depends if you want to do work on chunks

#

because if so the entity per chunk is much cleaner for execute work on it each frame

#

if you don't need to do work then i often just do the whole thing outside of entities

#

hashmap of arrays

meager loom
#

Do I understand you correctely. Map chunk -> entity is something like NativeHashMap<int, Entity>?

last lynx
#

yes

#

this is if i wanted to store chunk as entities

#

it depends on requirements if i'd do this or not

meager loom
#

I've read somewhere that default GetHashCode for structs isn't performant, because it combines hashcode field by field or something instead of managed objects which just uses it's ptr or something like that. Would it be nice to use int2 as a key to NativeHashMap

last lynx
#

just override the gethashcode to use the int2

#

isn't it a requirement to implement it anyway

brave crown
#

or maybe do it like archetype chunk

#

Where hashmap stores pointers

last lynx
#

don't know what you mean

brave crown
#

Chunks are probably massive size

last lynx
#

what do you mean by chunk specifically

brave crown
#

Copying left and right not a good idea

last lynx
#

are you talking like, chunk in voxel/tile sense or entity sense

brave crown
#

Tile

last lynx
#

and i don't really see why i'm copying anything

brave crown
#

You pass int2, you get a copy of 1kb or smth fixedarray

last lynx
#

(also this whole ref/copy/micro optimization stuff is so overrated on here. everyone so obsessed with it and then write terrible architecture at the macro level which is magnitudes more important)

brave crown
#

You write copy back

last lynx
#

that isn't a requirement at all?

#

if i can i have ref extensions if i cared

        public static ref TValue GetOrAddRef<TKey, TValue>(this NativeHashMap<TKey, TValue> hashMap, TKey key)
            where TKey : unmanaged, IEquatable<TKey>
            where TValue : unmanaged```
#

but i barely use it because it really doesn't matter if i'm not iterating some loop on this

brave crown
last lynx
#

? an array is a pointer

brave crown
#

Oh, it is?

last lynx
# 
  public struct NativeArray<T> : IDisposable, IEnumerable<T>, IEnumerable, IEquatable<NativeArray<T>>
    where T : struct
  {
    [NativeDisableUnsafePtrRestriction]
    internal unsafe void* m_Buffer;```
#

i don't know what you're smoking ^_^'

brave crown
#

but you can't use them

#

Nested collections

last lynx
#

Oh I'm sorry

#

you use the unsafe versions or just alloc yourself

#

You're smarter than this Issue, i don't get what you're having trouble with

#

If you weren't using entities, or collections or even unity, and just writing unmanaged code

#

How would you be handling this?

brave crown
#

I'm talking about using fixed arrays

#

Literally giant sized structs

#

So hashmap does need ref extension for this case

last lynx
#

yes but that was not what i was talking about from what you quoted me on

#

i gave him the fixed array solution

#

and then told him how i'd do it personally

brave crown
meager loom
#

yeah copying something that contains huge data isn't good enough you right @brave crown , this is why DynamicBuffer solution to store cells references looks better here. I wonder why we haven't ref return from native collections built-in. We have ref return when constructing blob assets, so shouldn't be something very dangerous.

meager loom
#

Where to store NativeHashMap of grid chunks? First I thought about managed singleton component to allow many systems access it, but it breaks burst compilation of this systems

# 
// can't be burst compiled
public void OnUpdate(ref SystemState state)
{
    if (!SystemAPI.ManagedAPI.TryGetSingleton<WorldGridChunkStorage>(out var chunkStorage))
        throw SystemUtils.GetNoSingletonExc(this, typeof(WorldGridChunkStorage));
}
last lynx
#

why does it need to be managed

meager loom
#

because I can't store NativeHashMap inside unmanaged IComponentData struct

last lynx
#

yes you can (as of 1.0)

meager loom
#

wtf

#

and NativeHashMap can exist on entity?

last lynx
#

yes

#

you can't bake it

#

but you can add it at runtime

meager loom
#

0_0

#

same with other native collections?

last lynx
#

yes

meager loom
#

seems like a big thing. How I missed this in changelogs

#

since I spawn grid chunks in runtime I just can have NativeArray inside of chunk's component

last lynx
#

just remember you have to be able to deallocate this

#

also you can't read this data in a job

meager loom
#

yeah, just a few destroy-only systems for that

last lynx
#

so i recommend native containers as singletons

meager loom
#

or cleanup components

last lynx
#

so you can query in system and pass container into job

last lynx
#

if you leave play mode you'll leak every time

meager loom
#

same with OnDestroy method?

last lynx
#

ondestroy is fine

#

and the general way

#

create singleton containers in oncreate, attach to entity (or system)

#

destroy singleton container in ondestroy