How to efficiently filter by a component with a specific value in an entity component system (all entities in grid position [x,y,z], for example)?

Question

I'm working on a 3d grid based game, and I am trying to implement it using an ECS.

I have a position component which indicates the entity's position on the grid. It is comprised of 3 integers (for example [1,3,2]). Now lets imagine the user clicked on position [1,3,2]. I now want to efficiently retrieve all entities in position [1,3,2].

I can see only one way to achieve that using an ECS. I need to filter for all components that have a position component (this can be done in O(1)), then filter through all the position components to find only those positions that equal [1,3,2]. This is extremely inefficient, since I have a hundred thousand entities with a position component to loop through, but I only need a minuscule fraction of them.

It's important to note that I never need to loop through all the hundred thousand position components in a single frame in any other case. For all other systems, I filter entities that have both a position component as well as other components, so I end up only looping through a small fraction of positions in each frame. This means I cant just retrieve all the relevant entities as part of the loop that goes through all the positions, since I dont have such a loop.

Traditionally using OOP, I would have a dictionary from a position to a container that contains all the objects in that position, which would allow me to accomplish the above in O(1). This isn't correct design for an ECS though, from what I understand.

Am I misunderstanding something about Entity Systems? If anyone has any advice I would be glad to hear it.

Thank you.

Answer 1

Basically you miss use a ecs system. Such a system isn't about collision detection, it is about organization. It's a system on how to plan and structure your game parts.

So now that you accept this fact it is easy to find more infos on how to retrieve entities that are needed to apply actions on them like clicking and selecting.

For this is mostly used tequniques like the commenter mentioned space oriented structures which are mostly binary trees like a octree with n, s, e, w,... From each point.