7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I feel like you might be getting the term entity system confused. Am I right in saying you're asking for a way to efficiently store object positions for spatial queries? \$\endgroup\$ – Anko Aug 20 '15 at 16:33
  • \$\begingroup\$ Oops, sorry you're right. \$\endgroup\$ – MindlessRanger Aug 20 '15 at 16:35
  • \$\begingroup\$ No worries, it happens. :) I found some similar questions on improving collision detection performance and implementing a spatial hash and differences between spatial hashes and quadtrees. \$\endgroup\$ – Anko Aug 20 '15 at 16:40
  • \$\begingroup\$ Have you tested that your current method is really too slow? In my experience, iterating through up to maybe a hundred or so objects is fast enough to do at interactive rates in JS on most devices. \$\endgroup\$ – Anko Aug 20 '15 at 16:48
  • \$\begingroup\$ @Anko Currently, I don't have any methods to store entities', (just finished the Entity constructor) but it is not a problem with speed, I've already limited updater and renderer functions to user's viewport. My problem is: I already have a grid to store blocks and don't want to use a grid to store entities, because gaps between entities are big and because of this there would be too many empty array keys if I use a grid, I was just looking at a different solution but after seeing the other techniques for spatial storage systems, I think that using a grid is the best option. \$\endgroup\$ – MindlessRanger Aug 20 '15 at 17:03
1
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ But wouldn't I have to rebuild the tree in every update? \$\endgroup\$ – MindlessRanger Aug 20 '15 at 8:27
  • \$\begingroup\$ Haven't seen spatial hashing, looking at it. \$\endgroup\$ – MindlessRanger Aug 20 '15 at 8:29
  • 1
    \$\begingroup\$ What about grids, bounding area hierarchies, binary space partitioning, kd-trees, ...? \$\endgroup\$ – Exilyth Feb 19 '16 at 14:23
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.