1
\$\begingroup\$

I have been writing all the necessary code for procedurally generated items within my game. The database mechanism that I have built supports new items at runtime, such as when a player opens a chest. Everything works fine, but I realized a fatal flaw with the way that I generate the "unique" item identifiers. I generate items using a Prefix, such as Fiery, an item type, such as Claymore, and a suffix, such as of Greater Shadow.

I generate the database Identifier using the format of:

Proc_ + Prefix + Type + Suffix + Iteration

As an actual example, the procedural item "Fiery Claymore of Greater Shadow" would then become:

Proc_FCOGS_01

All seems well right? This looks like it could work quite nicely. However, I then realized that I can easily receive identifier clashes. Or as an example: "Freezing Claymore of Greater Striking" would also be created as:

Proc_FCOGS_01

And that's where the problem arises. Because I went through all my affixes, located here and found that a few more of my chosen affixes could also lead to clashing within the database, despite the generated item not actually being the same as the one that is already entered. The routine that I am using to generate these identifiers is as follows:

        public string CreateIdentifier(string prefix, string itemType, string suffix)
        {
            if (!String.IsNullOrEmpty(prefix) && !String.IsNullOrEmpty(itemType) && !String.IsNullOrEmpty(suffix))
            {
                string input = prefix + " " + itemType + " " + suffix;
                string[] segments = input.Split(' ');
                StringBuilder builder = new StringBuilder(segments.Length + 5);
                builder.Append("Proc_");
                for (int i = 0; i < segments.Length; i++)
                {
                    builder.Append(Char.ToUpper(segments[i][0]));
                }
                return builder.ToString();
            }
            return null;
        }

After all of this, I can really only see two options:

  1. Scrap my current Unique Identifier routine and think of another one.

  2. If a collision exists within the Database, simply iterate the generated identifier ending number by 1, check again, and if necessary, iterate the the ending number by 1 again until an unused identifier is found.

As for number 1, that's why I'm here showing you all this. I need ideas about how I can do this in a way that will result in zero clashes unless the item is actually the same thing as previously generated.

And as for number 2, I would really prefer not doing this. I feel as though having fifteen or more database entries of Proc_FGSOTE plus the unique iteration, to be a little silly. Why have fifteen database entries of the same item? Although, I guess that would indeed be putting the iteration value to use...it's just not what I had intended it to be used for and seems like a terrible waste of resources. I really feel as though a better routine is the way to go.

Does anyone know of a better way that I can be generating unique identifiers?

Edit:

Sorry, I fogot to mention that I don't want to use the entire item name as an identifier, even if it's compressed to trim out all the spaces, mainly because the identifiers are still going to be way too long. This seems like an arbitrary limitation, I know, it's just one that I wanted to enforce so that way the Database could be loaded/parsed faster later down the road.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ I have just now considered to use the GetHashCode() of the item name and affixes...so the result would be 'Proc_93548239_01' or something similar. I could also pre-test this implementation to make sure I don't strangely have a preexisting clash somehow with the HashCodes, which is highly unlikely. It seems like the only draw back to this is that GetHashCode can return negative numbers...which I don't want as an identifier. \$\endgroup\$ – Krythic Nov 3 '17 at 6:40
  • \$\begingroup\$ @UriPopov By hash the name I assume you mean the full generated item name. Make no mistake, I could do that, I just don't want to. I want the identifiers to be as concise as possible. The only reason why "Proc" even exists instead of just "P" is because it makes a better search delimiter. And as for the Database, I'm using my own, which is just a series of generic Dictionaries and some runtime parsing/loading magic I thought of. \$\endgroup\$ – Krythic Nov 3 '17 at 7:21
  • \$\begingroup\$ GetHashCode() will work good for you. I'm guessing you wont have more than 2^32 items in your game. \$\endgroup\$ – Uri Popov Nov 3 '17 at 7:21
  • \$\begingroup\$ @UriPopov I have potentially unlimited hardcoded items in my game, but only a few(I haven't done the math to figure out total permutations of affixes yet, but I'm guessing it's a few hundred at least) procedurally generated items. These are just to add some RNG to my game, and to prep my engine for the Enchanting mechanics later on down the development cycle. \$\endgroup\$ – Krythic Nov 3 '17 at 7:25
  • \$\begingroup\$ Another option would be to get the syllables of the generated item name. This would still cut down the size of the identifier, make it readable(which honestly I don't really care about) and like a poster stated below, decrease or possibly even completely mitigate collisions. Let me do some testing tomorrow with this concept. The GetHashCode route still seems like the best one though. \$\endgroup\$ – Krythic Nov 3 '17 at 8:03
2
\$\begingroup\$

Why don't you just use GUIDs?

  • They can be generated client-side and still be unique.
  • They generate quickly.
  • They're only 16 bytes. That's only a little larger than what you're getting now, but since they're not as constrained as your algorithm, the available range is much, much larger.

They are less human-readable, but you can still always associated a short human-readable "developer name" with an item as well if you need to overcome that. You'd just want to use the actual GUID in any code that cares about being able to uniquely look up an item.


You could also just use auto-incrementing numeric ID keys on the database if you need to store the identifier in fewer than 16 bytes. But while smaller, this has the disadvantage of having the database need to be involved to even generate the ID.

\$\endgroup\$
8
  • \$\begingroup\$ I actually changed my engine, and moved away from string Identifiers, to randomly generated integer hex codes. This means that everything in my game is internally stored under an integer key. So when a new item is generated, a random hex ID between 0 and 2,147,483,647 is generated. This of course means there could be duplicates of an item within the Database, but I also plan on implementing a garbage collector of all procedural items. If there are no active references to it, the engine removes it from the Database. \$\endgroup\$ – Krythic Nov 4 '17 at 4:11
  • \$\begingroup\$ Doing it this way also opens up the possibility of an Enchanting system, too. Essentially, whenever you Enchant an item, a new version of it is created in the database with a uniquely generated hex code. And it is that item you will be given. \$\endgroup\$ – Krythic Nov 4 '17 at 4:15
  • \$\begingroup\$ @Krythic Why randomly generate instead of starting from 0 and incrementing? This avoids the trouble of having to deal with re-rolling the ID if you generate one that already exists (and isn't yet suitable for garbage collection). \$\endgroup\$ – user1430 Nov 4 '17 at 4:53
  • \$\begingroup\$ I wish it were that simple, alas the way the database editor is setup prevents that. All game items are stored in a single Dictionary, but for the editor they're broken up into individual types. imgur.com/LXsotZY If I did it the way you're suggesting, displaying them in an organized fashion would be very difficult. As an example 001 in Items would be Ruby, and in weapons 001 would be longsword. Their IDs would clash. Hope that makes sense. By the way that's an old picture so the hex codes aren't implemented yet. \$\endgroup\$ – Krythic Nov 4 '17 at 5:19
  • \$\begingroup\$ Although, I suppose I could get the length of the internal item dictionary and use that as the new hex id. Then just drop string Identifiers completely and display the item name in the list of. I would need to increment the database for every action that takes place though, so that way the Dictionary of Abilities doesn't clash with hex codes. I need hex codes to be unique across the entire Database for the query mechanism to work. So to get the next free identifier, I would need to take item dictionary length + every other dictionary length. Or just randomly generate hex codes like I was sayin \$\endgroup\$ – Krythic Nov 4 '17 at 5:33
1
\$\begingroup\$

If each keyword (suffix, prefix, etc.) more than a single letter, you would have a lot more unique combinations.

For example:
If you use four letters, then Fiery Claymore of Greater Shadow would become FiryClymrGrtrShdw_1, which is a lot more readable as well as giving you a lot more available keywords. (26^4)

Four letters is pretty readable, but it's up to you how many letters you think you need.

\$\endgroup\$
1
  • \$\begingroup\$ I could do this. I was also considering a custom implemention of GetHashCode, which has a scope large enough to not produce collisions across the few affix combinations that I have. Let's see what other people can come up with, though. +1 for now; I appreciate your input. \$\endgroup\$ – Krythic Nov 3 '17 at 7:07

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.