How to store grid(or 2d map) of entities

Unity Engine
,
1

Trying to create simple match3 game and stuck on getting neighbours. The question is mostly about ECS ideology, how to store and update that data?

2

lol. I have multiple threads on that subject. For match three I think here is generally a good approach, but watch the response from the Unity dev: Custom 2D/3D indexes for ComponentData access

They really should make an example project for this. Such a common thing, and really hard to figure out when just starting with ECS.

1 Like
3

You can try a Dictionary instead though. If you test different approaches and find the best for you, please let me know here. I have a similar scenario, but working on different things atm.

4

component data is optimized for linear access, so accessing it randomly is slow.

you can (even in jobs):
first pass, loop through your component data and fill a NativeHashMap<Coords, Entity> (job1, can use Concurrent writes)
second pass, do your logic, looping again linearly on your group (or a different group) and fetching neighbours with the hashmap filled in pass 1 (as readonly so you can parallelize this too)

or, you can hard group your stuff in one dimesion with

struct Row : ISharedComponentData {public int value}
struct Column : IComponentData {public int value}

and filter by row in your system

5

Why your Row is ISharedComponentData?

6

to ensure entities with the same row value are packed together, and therefore to enable group.SetFilter(row).

7

Take a look at the following thread:

8

Is random access to ComponentDataArray (say, data struct with 4 arrays of data among 10000 entities) slower than sorting? That would be hard to believe, but IDK, if it isn’t, then I think my approach is preferable since it requires only two extra lines of code and can be reduced to 1. Filtering API seems a bit cumbersome and feels wrong just because we are used to accessing data directly in OOP instead of searching.

The third option is to copy the data into 2D array. I think I can have a generic class that could do that quite easily. Same 1-2 extra lines per system and then free random access to data in a 2D array.

9

If you take a look at the Boids example, they do a neighbor matching as well. They also use hashmaps to get faster access.
(Like @M_R says)

Search in a list is in the worst case O(mn)…
Thats why they use a Hashmap O(mLn(n)) which is significant faster…

Edit:
The filtering approach can be faster. If you don’t change the items.
Keep in mind that, if you change a ISharedComponentData data, the entire entity will be copied to a new chunk.

10

Is random access to ComponentDataArray (say, data struct with 4 arrays of data among 10000 entities) slower than sorting?

Yes, almost certainly slower.

However, that’s a case for copying the ComponentData to a NativeArray (via CopyComponentData) - so you can do random access. Not necessarily a case for sorting.

11

Thanks for answers! Am I need loop througth entities every update? What if the map is really big (2d tile rpg for example)?

12

Split it into chunks then try different offered methods. Depends on the size of the chunks and on how many checks you need. I don’t know the numbers, but maybe if it’s a 128x128 chunk and you need to generate it and check neighbors for every tile that’s 32K-64K checks, in that case, I would guess your best bet is to copy the data to native arrays and query them. For small chunks or fewer checks Group.SetFilter() should work better.

Not sure where to use hashmaps instead of arrays but I’m sure in some cases data copied to hashmaps is the best approach.

13

Here is an idea for big RPG maps. So you are walking around a big map and fighting enemies, and you need to check which enemies are in the range of your attack. The map should be split into chunks. Enemies should be assigned a chunk that they re currently on. Then you can filter enemies by chunk positions to get only the nearby enemies.

Also, you can have only one system doing chunk based filtering and tagging enemies with a “Nearby” tag or something. Then all the rest of the systems can just inject:

{
public ComponentDataArray<Enemy> Enemies;
public ComponentDataArray<Nearby> Nearby; // Just for filtering
}
[Inject] Data data;```

So you don't need to do filtering in the rest of the game, and you can just iterate over nearby enemies for your checks.

You can have multiple ranges for different systems Nearby, Far, VeryFar. If the map is really really big you can of course load and unload chunks of the map along with enemies.
14

@mike_acton I hope it was clear that by sorting I meant filtering. And I hope there will be an option of injection into NativeArray offered in the future instead of ComponentDataArray, optionally into 2D/3D arrays based on a custom index component and array size XY.

15

This may be a dumb question, but is the random access issue (meaning you should copy ComponentData to a native array) only an issue inside of jobs? What if I am randomly accessing data from a ComponentData array on the main thread? I assume it is still beneficial to do a NativeArray copy, but just want to make sure.

16

It doesn’t matter. Random access to a ComponentDataArray will always perform poorly. If you need random access, you should copy into a NativeArray.

1 Like