6
\$\begingroup\$

In my game I'm generating a character seed from a bunch of traits that the player chooses. The traits are all part of a Enum. In unity I've attached a script to a bunch of toggles. When the player selects a toggle I do this : charGen.testCharHash += trait.ToString().GetHashCode(); Does this guarantee that I will have a unique number generated based on the players choice ?

\$\endgroup\$
27
\$\begingroup\$

Hash codes are never guaranteed to be unique. Also, you do not get a guarantee that adding hash-codes gets you an unique value which does not collide with a different combination of hash-codes.

The usual solution to identify a combination of on/off flags is to use a bitfield.

Assign manual integer values to your enum which are all powers of two:

[Flags] // optional attribute which tells the compiler that this is a bitfield
enum CharacterTraits {
    TRAIT_ONE = 1,
    TRAIT_TWO = 2,
    TRAIT_RED = 4,
    TRAIT_BLUE = 8,
    TRAIT_BLACK = 16,
    TRAIT_OLD = 32,
    TRAIT_NEW = 64,
    ...   
}

When you look at these values in binary, you will notice that they all just have a single bit set. When you simply add a combination of these values together, you will always get an unique integer. Bitfields also have other useful properties when used with bitwise operators. For example:

 if (character.traits.HasFlag(CharacterTraits.TRAIT_TWO)) { ... }

will trigger when the trait combination of the character has the bit for TRAIT_TWO set.

To set traits:

character.traits = CharacterTraits.TRAIT_ONE | CharacterTraits.TRAIT_BLACK;

To add a trait:

character.traits |= CharacterTraits.TRAIT_BLUE;

To remove traits:

character.traits &= ~CharacterTraits.TRAIT_BLUE;

An enum is backed by an int by default, so you get up to 31 traits that way (one bit is lost because of negative values). You can increase that to up to 64 by declaring it as enum CharacterTraits : ulong {. Should you need more than 64 traits, you need to look for a different solution, like an array of bool.

\$\endgroup\$
  • 6
    \$\begingroup\$ Bitfields are massively underrated IMHO. \$\endgroup\$ – user5665 May 25 '16 at 8:03
  • 1
    \$\begingroup\$ No, you just perform the bitwise (binary) operations on them. The & operator returns a true value if the bit mask you query is present. \$\endgroup\$ – user5665 May 25 '16 at 8:17
  • 17
    \$\begingroup\$ @Philipp Using + almost always opens it up to small non-obvious bugs, when dealing with bitfields |= foo, &= ~bar are always going to yield expected results. \$\endgroup\$ – user5665 May 25 '16 at 8:25
  • 2
    \$\begingroup\$ And of course remember that you can abstract the bitfield behind a struct/class to make it easier to use, refactor and potentially expand and less error prone though this will be slightly slower. \$\endgroup\$ – Maurycy May 25 '16 at 9:00
  • 5
    \$\begingroup\$ If you're going to have a lot of these flags, I'd recommend writing the values as 1<<0, 1<<1, 1<<2, 1<<3, etc., or maybe 0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80, etc. instead of writing out the powers of 2 by hand. It makes it more obvious what your intent is, and is less error prone than making sure you type out 2147483648 etc. correctly. \$\endgroup\$ – Darrel Hoffman May 25 '16 at 15:34
4
\$\begingroup\$

As Phillipp said, HashCodes do not guarantee uniqueness. In fact they pretty much don't guarantee anything.

What you seem to want to do is to generate a unique number from a unique string. How to do that generically is answered in this question: How can I generate a GUID for a string?

If you just want a unique identifier which is allowed to differ even for the same input, you can use Guid.NewGuid().

\$\endgroup\$
  • 1
    \$\begingroup\$ Except that it doesn't need to be a GUID... \$\endgroup\$ – immibis May 25 '16 at 10:13
  • \$\begingroup\$ @immibis The linked answer suggests various algorithms (MD5, sha). The result can be stored in a GUID, but doesn't have to be. Keep in mind that storing it in a GUID makes it obvious to everyone who's reading the code what is going on. \$\endgroup\$ – Peter May 25 '16 at 10:54
  • \$\begingroup\$ Well, they guarantee that if two of them are different then the objects they're calculated from must not compare equal. You mean, anything apart from that I assume ... \$\endgroup\$ – davidbak May 25 '16 at 22:56
2
\$\begingroup\$

It might be useful to note that while it is not guaranteed to be unique, your original approach is still going to work in practice with small amounts of traits, and a collision would not even have disastrous consequences if it happened.

The chance that some combination of hashes will match the hash some other trait is n!/2^32 (for a 32-bit hash), which is almost 0 for n=10, but becomes significant at 15-20 traits.

\$\endgroup\$
  • \$\begingroup\$ given the fact that I would have at most 15 traits my approach would have worked just fine but Philipp's answer is better and more elegant. \$\endgroup\$ – Uri Popov May 25 '16 at 14:12
  • 1
    \$\begingroup\$ @Peteris That probability is explicitly NOT guaranteed by GetHashCode(). The requirements for GetHashCode are very weak, so small changes of input are allowed to produce similar or identical results. If you need a stronger hash function where any change of input has a near 50% chance of flipping every output, you must use a hash function that guarantees such behavior, like MD5 or sha. Using a defined hash function also means the value also won't suddenly change when switching the .NET version. \$\endgroup\$ – Peter May 25 '16 at 16:07
0
\$\begingroup\$

To generate unique seed from non-boolean traits (small integers in some range), for purposes of random generation or other equivalent, you can treat all the possible player choices as dimensions, giving you a multi-dimensional coordinate when you consider them together (in the state space of all possible trait combinations a player may choose)

So if you have 3 choices, treat that as a 3D point.

Second step, you linearize this multidimensional coordinate into a single dimensional. Similar to how a 3D array would be mapped in RAM.

Given integer traits (ranged 0-n) x,y,z with max values sx,sy,sz:

int uniqueSeed = x*sy*sz + y*sz + z;

It should be easy to see how this would generalize to a higher number of traits/dimensions (just throw the traits and their sizes in an array and use some loops)

Assuming your range for each trait is minimal, this will give the smallest integer presentation possible for selected traits (assuming you dont want to compress/favor some possibilities over others).

You can use this seed directly for random generation, assuming the PRNG is good enough.

If thats not what you need it for, you can hash it with a good hash function to generate a random-looking / scrambled seed.

While a (decent) hash can potentially collide with another hash, the probability is practically 0 if it has enough bits. (lets assume 64 bits, which has 9 223 372 036 854 775 807 possible values, youd probably win the lottery thousand times over before you experience a collision, even if hash functions cant perfectly utilize the available values)

Also note that if you use this to seed a random generator, potential collisions in generating the seed are irrelevant because you will ALSO get 'collisions' from the random generator itself, if you only generate a finite amount of random numbers (there is a probability that two different seeds will get you the same initial random numbers).

Stuffing your choices in a bit field will work if they are simple binary choices. As will simply concatenating their bit representations if theres few enough that they fit in an integer (or if they happen to all have a range that is power-of-2).

My suggestion is use the hash, because stuffing them in a limited-size integer is both annoying the extend (what if you add a trait with type float?), and will not scale beyond a few traits (which will limit your game design, for no real benefit). Just use a decent hash (not something made out of 1 multiplication, shift, and a xor operation!). If by some miracle there was a collision, salt the hash (throw in some extra number with the other data) and problem solved.

\$\endgroup\$

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.