# Container classes in tile-based games.

I've recently begun working on a tile-based tactical game, and I have questions regarding a couple of key moments.

Is it feasible to organize the tilemap as an array of containers, which can hold the game objects? What are the pros and cons of such an approach? Should I make a single container class for all the game objects, such as characters, walls, and terrain, or try to break it down to separate container types for every single game object class?

Any examples of a container capable of storing objects of several different classes will be greatly appreciated.

Is it feasible to organize the tilemap as an array of containers, which can hold the game objects? What are the pros and cons of such an approach?

I would use std::vector<Tile> or similar. I don't see the need for an array of containers or for multidimensional containers (unless perhaps you have multiple independent layers of tiles). Even a simple plain array of Tile objects would work fine, if you must (although I find the use of vectors far more convenient. You can use a single-dimensional container as a 2D one just fine, you simply make it contain width * height items and to access the tile at (x,y) use indexing math like container[x + (y * width)]. Generally one will encapsulate this indexing math behind a tilemap class or some other kind of abstraction.

The reason for preferring a single-dimensional vector is that a multi-dimensional vector gives you no tangible, significant benefit over a single-dimensional one, but a single-dimensional vector provides the additional benefit of keeping the elements all contiguous in memory, resulting in better locality of reference and cache coherency. A vector-of-vectors-style multi-dimensional array does not have this property, nor does the sane form of a dynamically-allocated multi-dimensional plain array (although one with compile-time bounds will, but that is of limited utility in this scenario when you'll presumably want to read your data from a file eventually).

Of course you could achieve that coherency via pooling allocators as well.

Should I make a single container class for all the game objects, such as characters, walls, and terrain, or try to break it down to separate container types for every single game object class?

If every object in your game can be treated exactly the same, then it may be more efficient to create a common base interface for them, and manage them all as a big list of that base interface. As the complexity of your game objects grows, this may be less true and it may be more beneficial to split them out into different lists based on type or other criteria.

As a rule of thumb, if you keep objects that will be processed similarly with each other organizationally, you'll be able to process them more efficiently. "Processing" here includes not just what they do when they Update() every frame, but also how long they exist in the game world, what their lifetime management policy is, whether or not they must be processed in a certain order, et cetera. Keeping them together may also improve locality of reference and allow you to spread processing out onto multiple threads, which can be a big win for performance.

Any examples of a container capable of storing objects of several different classes will be greatly appreciated.

Almost any container can; it matters more what you store rather than what you store it in. If you take advantage of polymorphism, you can implement a base class or interface

struct Base{
virtual void DoThings() = 0;
};


which everything to be stored together inherits from

struct ChildA : Base {
void DoThings() { /* ... */ }
};

struct ChildB : Base {
void DoThings() { /* ... */ }
};


you can create a std::vector<Base*> (as just one example) and store pointers to ChildA and ChildB in that vector and treat them uniformly by way of their common interface.

You should also consider that its generally good practice to divorce your rendering and game logic code. The effect of storing different classifications of game object in different ways should have no impact on the organization of your rendering queue; you'd still want that to operate on (essentially) a single list of its own type of object (for example, sprites in a 2D game). The most straightforward way to achieve this is to store a pointer or reference to the renderable component (sprite, or some higher level construct if needed) inside the game logic components.

• Much more in-depth answer than mine, thank you Josh :) The only thing I would say about using std::vector is that it uses a contiguous block of memory, so might it not be better to use a linked list, or an std::deque in this case? – Thomas Russell Jul 30 '11 at 23:03
• This is a top-quality answer (+1). I encourage others to upvote this answer so as to generally encourage everyone to provide more detailed answers like this one. – Randolf Richardson Jul 31 '11 at 4:46
• @Shaktal Unless you specifically need the properties of a linked list (constant-time insert/remove at a known position), the non-contiguous nature of a linked list is detrimental to cache coherency during iteration, making a vector preferable unless a custom allocator is used for the list. For many scenarios a linked list's behavior isn't really needed because order doesn't need to be preserved and control over the reallocation of a vector can be maintained under performance-critical scenarios... so a list is often a sub-optimal default. – Josh Jul 31 '11 at 18:56
• It's also notable that you can have auxillary data structures to help with lookup complexity. You could have a quadtree or spatial hash if you need more efficient neighbour queries or culling queries. – Lars Viklund Aug 1 '11 at 7:53
• Fantastic answer! – munificent Aug 2 '11 at 0:57

For your tilemap, I'd recommend either using a C-style multidimensional array wrapped in your own class, or using a multidimensional std::vector for the same purpose. You can then read in this at run-time from your map file (how you do this will depend on how you design your map file).

With regards to storing the entities in a game, it's really up to you, I'd suggest a container (probably a linked list is best in this case because you don't really want a contiguous memory block, and also you will no doubt regularly be adding and removing entities etc. so the amortized constant time may be of some advantage here, or perhaps std::deque, or even std::map depending on how you want to implement it) to store a pointer to each of your entities (which should derive from some base class, probably CBaseEntity or something like that, again depending on how you choose to structure it. Have a base entity to derive from will also help you in terms of your rendering pipeline as well, as you can call some derived Render() function for each entity in the container.

The reason I would use one container rather than several is that it minimizes the number of loops needed in your rendering pipeline. It allows you to perform global entity operations, and if you use an std::map, or std::multimap (or their unordered counterparts) you can still make sure you only choose the entities you are interested in for entity specific proceedures. Moreover, it minimizes overhead (not that is much of an issue with only say, 20 types of entity, but if you move into several hundred types of entity (which could be quite easy depending on how in-depth your game becomes then you could give yourself quite a bit of overhead).

An example of a game engine which keeps all of it's entities in a single container would be the Source engine (used by half-life, half-life 2 etc.)

Hope this helps! :)