# Data structure to store map layers in each Tile while keeping the order of terrain, items and monsters intact

My game represents its map as a 2D array of tiles, each of which stores a stack of layers. I'm looking for a data structure to efficiently represent this .

I want to be able to add layers dynamically, so fixed arrays won't do.

Additionally, the layers are applied in zones, to make sure that terrain is always drawn before items and monsters, and that items/monsters are drawn before the player. This is the order:

terrainlayer
terraineffectlayers
itemlayers
monsterlayers
playerlayers
specialeffectslayers


I want to store all those zones in the same data structure, so I can traverse it from end to end in either direction. I also need to be able to add a monster layer that would automatically go at the end of monsterlayers data structure while still having a global object that would let me traverse from the all the layers. I also need the ability to access the data structure with index, so I can get the 3rd monster in the tile easily or remove the 3rd monster. Add will always be sequential, but remove are at random indexes.

Does a data structure like this already exist or do I need to make some sort of vector/doubly linked list/deque hybrid?

I have already seen this question but it doesn't help me.

• By "zones" do you just mean "order"? I think you're overthinking this: A doubly-linked list (maybe nested such) sounds almost optimal. Have you tested your current approach and found it to be too slow before optimising like this? – Anko Oct 15 '14 at 1:09
• Anko, the brute force approach I tried would be to have one huge double-linked list then figure the correct place to put it in everytime, but that will probably be slower than having an hybrid. If I insert something in the middle of monster for example I'd have to traverse half of my linked list. While if I had a better data structure I could just traverse half of my monster data structure. I'm leaning toward doing a data structure similar to how memory caching work at the moment by keeping index reference to where each zones starts and ends. – Mystra007 Oct 15 '14 at 1:19
• TL,DR: I'm trying to sort a set and keep elements of the same type sorted together. I'm trying to figure out how to do this with a divide and conquer approach, by having each type in their own set then concatenating the set into a bigger one so I can traverse it from either end. I still want to be able to access the nth element of a smaller set. – Mystra007 Oct 15 '14 at 1:28
• Attempting to condense: Both your layer-datastructure and game-object-datastructure should have the same properties of (a) being faster than linear-time to modify at any point, and (b) stay ordered. (Is that right?) – Anko Oct 15 '14 at 1:36
• (a) I'm trying to have a complexity like O(a bit less than n) instead of O(n). I know that the complexity class is the same. It just seems logical that if I have 100 layers on a tile, of which 2 are monsters, that to add a monster over existing ones I only need to traverse 2 elements, not 100. And to only traverse 2 elements when I want to get the 2nd monster in the tile. (b) yes – Mystra007 Oct 15 '14 at 1:43