10

Usually, entities and components or other parts of the game code in data-driven design will have names that get checked if you want to find out which object you're dealing with exactly.

void Player::Interact(Entity *myEntity)
{
    if(myEntity->isNearEnough(this) && myEntity->GetFamilyName() == "guard")
    {
       static_cast<Guard*>(myEntity)->Say("No mention of arrows and knees here");
    }
}

If you ignore the possibility that this might be premature optimization, it's pretty clear that looking up entities would be a lot faster if their "name" was a simple 32 bit value instead of an actual string.

Computing hashes out of the string names is one possible option. I haven't actually tried it, but with a range of 32bit and a good hashing function the risk of collision should be minimal.

The question is this: Obviously we need some way to convert in-code (or in some kind of external file) string-names to those integers, since the person working on these named objects will still want to refer to the object as "guard" instead of "0x2315f21a".

Assuming we're using C++ and want to replace all strings that appear in the code, can this even be achieved with language-built in features or do we have to build an external tool that manually looks through all files and exchanges the values?

2
  • 1
    +LOL for the guard's message :D
    – Petruza
    Jan 4, 2012 at 18:50
  • I'd say that you really would want dynamic_cast<Guard*> here. RTTI may have a bad name in game development, but this is bound to be far slower than that, not to mention harder to maintain.
    – MSalters
    Jan 4, 2012 at 20:51

4 Answers 4

13

Jason Gregory wrote this on his book :

At Naughty Dog, we used a variant of the CRC-32 algorithm to hash our strings, and we didn't encounter a single collision in over two years of development on Uncharted: Drake's Fortune.

So you may want to look into that.

And about the build step you mentioned, he also talked about it. They basically encapsulate the strings that need to be hashed in something like:

_ID("string literal")

And use an external tool at build time to hash all the occurrences. This way you avoid any runtime costs.

6
  • 4
    In C++11, you should be able to use a constexpr function to do the hashing at compile time, removing the need for an external tool. Jan 4, 2012 at 17:59
  • @MikeSeymour That's really cool, had no idea. Haven't really looked much into C++11 yet. Disappointed at VS's lack of support.. Jan 4, 2012 at 18:11
  • That's pretty awesome Mike, totally forgot about constexpr. Add it as an answer and I'll accept it.
    – TravisG
    Jan 4, 2012 at 19:50
  • Second hand knowledge here (never worked at Blizzard) but they use(d) CRC32 as well in a dual or triple hash look up (one key generates 3 hash values) to really reduce the chances of a collision.
    – James
    Jan 5, 2012 at 0:47
  • 1
    This is one of the reasons that Naughty Dog used LISP to program its games in the Jak days: we could write compile-time macros to generate unique IDs of strings, and replace any mentions of the strings in the code with that integer, without any risk of collision. The macros would also update a shared database with these string mappings, so that offline tools could use them as well; that allowed us to refer to content and asset names by "string" in Maya, but have it cook to an integer in export.
    – Crashworks
    Apr 23, 2012 at 1:22
1

This is what enums are for. I wouldn't dare to decide which resource is best for the topic, but there are plenty to choose from: https://www.google.com/search?q=c%2B%2B+enum

4
  • 1
    The problem with enums is that they're "fixed" and don't tango well with an extensible scripted system or data-driven design. Jan 4, 2012 at 16:51
  • You can do it the old-fashioned way with macros, that way you have got complete control of the process. Jan 4, 2012 at 17:06
  • 1
    Could you expand on that thought a little? Maybe we're not thinking of similar scenarios. As an example, let's say you create an entity named "level1_garden_door" in your level editor. Then you'd like to reference that entity in a script file to add some interactivity. For ease of use, you should still be able to reference your entity by name. But string lookups are slow, so hashing these ids into ints at build time provides a decent middle ground between usability and speed. An enum needs to know all of the values it can represent, but here those values are used-defined. What's the solution? Jan 4, 2012 at 18:23
  • Now you actually describe an example with two scripting environments, the level file and the script should share an environment, so when the level file says: entity=loadEntity("filename") entity will be a variable directly accessible to the script. But I think we might be moving into an area that is hard to discuss on an abstract level. The exact implementation depend on the exact circumstances. Jan 4, 2012 at 19:04
0

I'd say go with enums!

But if you already have a lot of code already using strings, well, either just keep it that way (simple and usually enough fast on a PC anyway) or hash it using some kind of CRC or MD5 into an integer.

0

This is basically solved by adding an indirection on top of a hash map.

Say you want to convert strings to integers:

  • Write a class wraps both an array and a hashmap. I call these classes dictionaries.
  • The array contains the strings.
  • The hash map's key is the string (shared pointers or stable arrays where raw pointers are safe work as well)
  • The hash map's value is the index into the array the string is located, which is also the opaque handle it returns to calling code.
  • When adding a new string to the system, it is searched for already existing in the hashmap, returns the handle if present.
  • If the handle is not present, add the string to the array, the index is the handle.
  • Set the string and the handle in the map, and return the handle.

Notes/Caveats:

  • This strategy makes getting the string back from the handle run in constant time (it is merely an array deference).
  • handle identifiers are first come first serve, but if you serialize the strings instead of the values it won't matter.
  • Operator[] overloads for both the key and the value are fairly simple (registering new strings, or getting the string back), but wrapping the handle with a user-defined class (wrapping an integer) adds a lot of much needed type safety, and also avoids ambiguity if you want the key and the values to be the same types (overloaded[]'s wont compile and etc)
  • You have to store the strings in RAM, which can be a problem.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.