1
\$\begingroup\$

I'm in the process of developing a game engine and I would like to refer to game objects and assets by an integer id rather than by their string name. This should avoid any string comparisons at runtime. As a result I'm trying to implement the string hashing approach that Jason Gregory describes in Game Engine Architecture.

I've got the actual hashing working, using FNV-1a in my case, but there are some parts of the design from the book that I don't understand.

static StringId sid_foo = internString("foo");
static StringId sid_bar = internString("bar");
...
[stringid.h]

typedef U32 StringId;
extern StringId internString(const char* str);

[stringid.cpp]

static HashTable<StringId, const char*> gStringIdTable;

StringId internString(const char* str)
{
    StringId sid = hashCrc32(str);
    HashTable<StringId, const char*>::iterator it
        = gStringIdTable.find(sid);
    
    if (it == gStringTable.end())
    {
        // This string has not yet been added to the
        // table. Add it, being sure to copy it in case
        // the original was dynamically allocated and
        // might later be freed.
        gStringTable[sid] = strdup(str);
    }
    return sid;
}
  1. Presumably HashTable is a custom hash table implementation as no such class exists in C++? Is there any problem with my current setup of storing the hashed strings in a std::unordered_map<StringID, const char*>?
  2. From my research, making the hash table static means that it is only accessible inside this translation unit. a) Why is it defined this way, and how would you then access the hash table in the rest of the game engine? b) Or do you call internString for every string and store the returned hash in a header #included in every file that needs access?
  3. What is the purpose of making externString extern?

Thanks.

\$\endgroup\$
7
  • 2
    \$\begingroup\$ "I'm trying to implement something similar to the string hashing approach that Jason Gregory describes in Game Engine Architecture." Why? What do you need it for? \$\endgroup\$ – Vaillancourt Dec 14 '20 at 22:07
  • \$\begingroup\$ My C++ is old & rust, but regarding #2: while static can affect linkage, it also means that only a single instance is instantiated & its duration lasts for the entire program. Hard to know w/out see how it's being used, but I suspect that is declared static in order to make it act like a global. \$\endgroup\$ – Pikalek Dec 15 '20 at 0:30
  • \$\begingroup\$ Regarding #1, the author touches on using pre-made container libraries in games in the intro 1.6.4. Third-Party SDKs and Middleware and in greater depth in the Containers chapter 5.3.4.1. To Build or Not to Build. The sort answer is that there's no universal short answer. It's probably fine, but without knowing more about how you intended to use the hashing, you're unlikely to get a definitive answer. \$\endgroup\$ – Pikalek Dec 15 '20 at 0:48
  • \$\begingroup\$ @Vaillancourt Thanks for the reply. I've updated the first paragraph with extra clarification as you advised. \$\endgroup\$ – MasterReDWinD Dec 15 '20 at 10:42
  • \$\begingroup\$ @Pikalek Thanks, I've expanded the first paragraph to clarify things, and added a couple of usage examples from the book. I read those sections and as the Naughy Dog approach is to create custom Containers, I guess that is why this code does that but without explicitly highlighting to it. When you say it's probably fine are you referring to using an unordered_map? \$\endgroup\$ – MasterReDWinD Dec 15 '20 at 10:52
3
\$\begingroup\$

In the book, the subsection 5.4.3 you took the example from is about "ideas". It doesn't seem like the code snippet is meant to be great C++, just good enough to serve as an example that explains the concept.

Yes, you can substitute any hash map.

"how would you then access the hash table in the rest of the game engine?"

From the book, below the example:

When using string ids, the strings themselves are only kept around for human consumption. When you ship your game, you almost certainly won’t need the strings—the game itself should only ever use the ids.

In the book, the topic of that section is unique string identifiers for internal use. You will want to access the map for debugging only, and how you do so is up to you.

The book also mentions looking at FName as a working implementation of a similar concept.*

Strings that are presented to the player need to be handled differently - here you have to look into localization first, because that's where most of the constraints come from.


PS: As a bit of unsolicited advice, this introduces a level of complexity that is unnecessary for a home-built first game engine. Just make a class that looks like FName, only declare the parts you currently need (constructor and comparison), but implement it with std::string and operator== as a first draft. When you later need the additional performance you can then change the implementation to one that uses integer comparisons.

\$\endgroup\$
2
  • \$\begingroup\$ Many thanks for the answer and for the unsolicited advice. I had forgotten that only the int data should be available in the 'retail' version. I'll look into FName via the link you gave. Regarding the level of complexity int ids introduce, is there anything specific I should be aware of? \$\endgroup\$ – MasterReDWinD Dec 16 '20 at 14:25
  • \$\begingroup\$ @MasterReDWinD Int ids don't introduce any complexity. A framework that tries to manage int/string hybrid ids does. There are many alternatives (use short strings, precompiler, etc), and asking about those would certainly justify its own question. \$\endgroup\$ – Peter Dec 16 '20 at 16:54

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.