How should I store dynamic game entities for efficient area-based selection?

Question

In my 2d block-based game I'm trying to implement a data structure that would store entities entities in a way that's capable of:

• Direct selection based on coordinate.

• Iteration

• Iteration limited to an area

I thought of these solutions:

For 1,3 I thought that a 2 dimensional array of entities' coordinates would be suitable but I already have a 2 dimensional array of blocks' coordinates and don't want to have another one too. And this solution is not suitable with 2, there will be too many gaps when iterating the array and this is a performance loss.

The next solution I thought was simply using an array and adding new entitys simply by arr[length], this is performance wise for 2 but it is hard to perform 1 and 3 (use a for loop everytime to check if I'm colliding with an entity (duh)).

The last solution is simply adding entity data to my (already exists) blockList 2 dimensional array, this one has nearly the same pros and cons with first solution.

And there is always the alternative of using first and second solutions together by making them refer to the same object.

---

Which one of these solutions should I use, cause all of them have their pros and cons and I have to something uses less space, cause the game map is not fixed.

Answer 1

Another option may be using a quadtree structure or if you have many moving objects a spatial hashing aproach.

Answer 2

In the game I'm making I store the entities (actually their components) in an array (structure of arrays) and then I create a spatial grid containing, in each cell, the array index of the entities that belong to that area; and yes, you have to rebuild it every frame for dynamic objects, but the tutorials I've seen (that I remember) do this, especially for quad/octrees. That's fast for simple iteration and for area selection and in the case of rebuilding the grid is just one 'array.push_back' per entity each frame.

You may consider ordering the entities in the array based on their position, to avoid cache misses when selecting them by area (if you have all the data grouped together you avoid jumping here and there on the RAM). But you don't need to do that each frame, maybe keep a index of the 'chaos of the system', based on how much the entities move, how many die and so on, and perform the sorting when it's too high (try and profile if that is needed)

Creating different arrays for different areas I think is not a good idea, both in terms of maintaining your code and performance, due to the continue swapping of entities betweens one area and the other (and so a lot of moving data). Maybe, I've never tried this approach, you can go this way if you have large different areas which don't communicate too much, but i don't think it's your case.

Answer 3

I have used 2 simple dirty tricks.

1 - Level divided by "chunks". Let's say 10x10 (CHUNK_SIZE = 10) abstract units. So your level near 10x10 chunks. Let's say chunks array - it's a sort of low-detailed map when few enities can be in one cell. Every time when entity move (or every 10 game ticks), I recalculate new chunk chunk position ( like enity.chunk_x = enity.x / CHUNK_SIZE ). After, if chunk-position for entity has been changed (we moved to another chunk), I remove link from previous chunk, and put link on entity.

Now, let's say, your characted can see for 2 chunks around. Much more faster to look at near chunks, than go through hude array of entities.

2 - observation list: each playable character who can observe entities around, may keep and manage observation list. (using 1st dirty trick).

For javascript this techique is more that enough.