How to find an `Entity`, from a set of 1M, with particular `int2` grid position, fast?

Questions & Answers
, ,
1

Currently, I’m using Unity ECS to simulate a simple world. The world is a grid of about 1000 x 1000 cells. Each cell is treated as a separate unit, totaling 1 million units. Additionally, I’m simulating the movement and growth of plants and animals on this terrain. Each cell can only have one plant, indicated by an occupied component on each cell entity.

Currently, when I need to spawn a new plant, I go through all 1 million cell entities to find the one corresponding to the plant’s position in the world. This process involves the following code:

static public Entity GetCellEntity(int2 position, EntityManager em)
{
    EntityQuery query = new EntityQueryBuilder(Allocator.Temp).WithAll<Position>().Build(em);

    var entityes = query.ToEntityArray(Allocator.Temp);

    foreach(Entity entity in entityes)
    {
        Position pos = em.GetComponentData<Position>(entity);
        if(pos.gridPosition.x == position.x && pos.gridPosition.y == position.y)
        {
            return entity;
        }
    }

    entityes.Dispose();
    query.Dispose();

    return Entity.Null;
}

However, this method is highly inefficient and time-consuming. Do you have any suggestions for improving this function or restructuring the code, such as possibly having all cells under a single large entity or grouping entities as chunks of cells?

2

Linear search was ok as a quick first iteration. But 1 million of anything is where linear search always stops being practical.
What you need is some kind of method to map int2 values to specific Entity, instantly.

This is where spatial hashing comes in

which does exactly that. The requisite is that you create and maintain a NativeArray<Entity> for that to work.

Alternatively, you can be lazy like me, and just use a native HashMap<int2,Entity> and be done with it (my old example I’ve given earlier to somebody: Example of a grid system built with with ISystemStateComponentData · GitHub )

3

Thanks so much! @andrew-lukasik

Here is my new code (will the static nativearray cause any future bottlenecks ?):

public static NativeArray<Entity> gridLookup;
public static int gridsize;

public static int2 IndexToPosition(int pos)
{
    return new int2(pos / gridsize, pos % gridsize);
}

public static int PositionToIndex(int2 pos)
{
    return pos.x * gridsize + pos.y;
}

static public Entity GetCellEntity(int2 position, EntityManager em)
{
    int index = PositionToIndex(position);
    return gridLookup[index];
}