# best structure to handle entities in an entity component based game engine

I am trying to develop a 2D entity component based game with multiple layers as tilemaps (front or back from the scene).

I currently handle the tilemap layers in a 3 dimension array[z][y][x]. Each tile from the map is an entity and have a positionComponent which define x, y and z. The array structure is very convenient to update and render only visibles entities (in the viewport).

I have also added an 1 dimension array to handle the ennemies and items. The problem is that I want to fusion the tilemap and ennemy array in one single structure (I want to update and render entities within a single strcture).

As the entities already have a positionComponent defining x, y and z, is there a good way to get rid of the 3 dimensions array without loosing performance?

Ideal will be to be able to do something like entities.get(z, y, x).

• Can your enemies and items overlap multiple tiles? (For example, do they move across 8x8 tiles a pixel at a time?) Or is the granularity of placement/movement 1 tile? – leander May 4 '13 at 18:37
• Instead of finding a solution to the problem, circumvent it by not combining the tiles, enemies, and items in the first place. If anything, you would want to use more, not fewer, data structures sorting your objects/tiles/whatever depending on how many search methods you want to implement. Your priority should not be on saving some trivial amount of memory, but on functionality first, then readability and ease of debugging code. – Attackfarm May 4 '13 at 19:12

What you describe is certainly a strange approach to a grid based game. Anyway, there's no way to optimally reference a particular range of your xyz cube of entities without a relational structure containing them such as a 3 dimensional grid array, or something like an octree. Otherwise you're stuck looping through all of them comparing their positions which is unacceptable with large lists of tiles / entities.

It is strange for you to want to combine tiles with entities in a single structure because they would have completely different operations performed on them. Entities would be changing position and state whereas tiles are often static and need to be accessed very quickly for their information. Also if your entities' sizes can span multiple tiles, then there is certainly no reason to try to combine their structures together.

A multi-dimensional array offers very fast lookup at the cost of some memory, and is always the way to go when storing something like grid-based tile data. Entities like moving characters are better stored in lists that you iterate through for small amounts of entities, and structures like quadtrees/octrees for large amounts.

• I can not only think of many, many reasons why separating tiles from entities would be beneficial, I can't think of a single reason why the OP would want to combine them. – Attackfarm May 4 '13 at 19:08
• +1. Tiles should not be shoehorned into an ECS. – jmegaffin May 4 '13 at 20:09
• I bet your right, I am thinking about a layers system based on 3 dimension array. One layer for the tile, one for the ennemies, one for the items. Each positionComponent have then to maintain theire coordinates in the layer they belong to. Does it sounds good? – Alexandre GUIDET May 5 '13 at 6:18
• Why do you need it to be a "third" dimension? You can store tiles, enemies, and items in their own optimal structures, then when it comes to rendering you simply render everything in whatever priority you choose so that for example: tiles are rendered first, then items, then enemies. – Fizzik May 5 '13 at 19:07

Assuming your tiles / enemies / items all share a common base class, I don't see why this wouldn't work with a 1 dimensional array. You simply call each element as normal, except now you lose the ability to reference a tile by it's position easily. However, you can still do this pretty easily with the xyz components you mentioned.

If they do not have a common base class, then I'm not sure you could do this all in one array.

• all entities share the same class, they are all Entity instances with components. What I need is a structure that allow me to retreive all entities in a range like in a relationnal database. EG: entities.get().where(x > n1 and x < n2), same thing with y and z. As the map may be really huge, I want to focus on the performances. Iterating through a list and comparing x y and z from the positionComponent may be a poor solution if the entity list is hudge. – Alexandre GUIDET May 4 '13 at 17:05
• So, why not make a method that takes a x and y range, and returns an array / list with all those elements? Basically: for( int x = xLower; x < xUpper; x++ ) { for( int y = yLower; y < yUpper; y++ ) { add object at y * mapWidth + x; } } – Ben May 4 '13 at 17:22
• I am afraid that for huge arrayList, iterating each entities and testing coord (x,y,z) may be CPU consuming. I'll try and keep you inform. – Alexandre GUIDET May 4 '13 at 17:30
• Sure, but you would only do this as you need to. Like when a new map is loaded, or when the camera moves a substantial amount. If it means anything, I did something similar with a 1000 * 1000 map in XNA and there was no lag at all. Unless you're drawing the entire map every frame, you won't see a huge performance drop. Anyways, try it out. – Ben May 4 '13 at 17:36
• I have tried the arrayList solution to handle each entities and when the amount of tiles increases, the performance drawn significantly. This is ok for a level based game, but not for the type of game I want to do (one big level as the whole world). – Alexandre GUIDET May 5 '13 at 6:21