Alternatives to map of strings in regard to performance

Question

I would like to start my first question here with a subjective question. I think it qualifies as constructive.

To introduce the situation: I have a 2D tiled map. I also had different arrays of graphics (one array for tile graphics, one array for GUI graphics, multiple arrays for different kinds of entities that can be placed onto the map).

Because I have not liked these many arrays I wanted to refactor so that I have one data structure to hold all my graphics. The thing is now that a number of graphics belong together

• A map tile has several graphics for different views, i.e. angles you can watch from.
• An animation has multiple frames and is also view-dependant.
• There are entities with have multiple states and therefore different graphics.
  • These states I can also use for GUI elements (button normal, hovered, pressed).

To consolidate all these requirements I thought of

std::unordered_map<std::string, const GraphicSet*>

as the holder of all the graphics

// with ...
class GraphicSet : private std::unordered_map<GraphicSetKey, Animation*, ...>

class Animation : private std::vector<const IGraphic*>

typedef const std::string GraphicSetKeyState;
typedef const std::string GraphicSetKeyView;
typedef std::pair<GraphicSetKeyState, GraphicSetKeyView> GraphicSetKey;

// ...and IGraphic as the very graphic

. I knew that using standard library container is slower than arrays in memory but tried it anyway. And indeed it is too slow. According to callgrind rendering a single frame is nearly 85% slower than before. This is unacceptable.

I do not want to badmouth the standard library because if I would implement my own container it would be as bad. The problem - callgrind reveals this as well - are the strings I am using. For every tile I want to draw the program creates a string uses the whole mechanism hashing and so on just to get me the graphic I desire.

---

Now we are getting to the question:
What data structure / technique would you suggest? (please read on)

My next idea is to partially fall back to my graphics arrays. But instead of several arrays I want to do one big array and map these views and state at compile time to indexes.

One issue I yet have in mind: My goal eventually is to be open for extensions. I want everything to be configurable so for example modifying the entities and the graphics of the game is possible by editing a config file.

With strings this is pretty easy by simply adding a new key to the map. If however I use fixed indexes at compile time this will be a very big problem in the future.

How can I keep it performant but also flexible for the future?

Answer 1

AFAIK standard procedure is to have resources stored in a map-like structure with strings as keys, since it's extensible as you've seen. However, for the core game elements (especially the performance-critical ones), the resources will be explicitly linked instead of involving a key-lookup, thus skipping the lookup overhead.

For example, you might have a Pony that you render by drawing a Sprite. Initially you might lookup the sprite by using the string "pink_pony_sprite" then rendering it, every frame, but to make this more efficient, your pony will hold a reference to the sprite directly. Your pony might look something like this then:

class Pony {
public:
    Pony(const std::string& name, const Sprite& sprite);
    void Render(Renderer& r) { r.render(_sprite); }
private:
    const Sprite& _sprite;
};

// Construction:
Pony p{"Speckles", bigSpriteMap["pink_pony_sprite"]};

This setup has the following advantages:

• Extensible (you can easily add, or change what sprite to use for your ponies)
• Reusable assets (multiple ponies can use the same sprite)
• Efficient (only one map lookup, during construction)