• Advertisement
Sign in to follow this  

Efficent Tagging

This topic is 768 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am sorry, I am having difficulty articulating the problem I am having, so I hope this doesn't sound like I am rambling.

So I am working on a cascading procedural generation method of sorts... so, assuming I am generating an NPC. First, by looking at the location where the npc is to be generated I choose a race (orc/human/etc) based on the population distribution for the location. Let's say I choose an Orc. The next step is to select the orcs class. So, I would choose from the classes that are tagged with ORC on the white list and not on the black list. Then I can choose a weapon type that is either tagged for ORC or for the Class and not black listed for ORCs or the class.


Another example might be trying to create a gem to add to the loot, first select the race that mined/cut it, then the type of cut they used (different races may prefer different cuts), then the type of material it is made of (Some races or regions are more likely to select particular materials then others) then it's size (Different materials may be more prone to different sizes) then finally based on all that generate a description and value.


The problem I am having is finding an efficient way to tag the records. My only idea currently, is to have two text fields, WTags and BTags and use string finding functions to see if a tag is in the white listed tags (WTags) or the Black Listed Tags (BTags) but a long series of string finding operations seems a bit inefficent.

Share this post


Link to post
Share on other sites
Advertisement

Yeah, avoid "stringly typed" code.

 

If your tags are stored as text, parse them into something more computer friendly (assign each unique string, an integer ID).

 

So now you have integers. Using those might already be good enough for you.

 

 

Since the tags are basically memberships in a set with a fixed number of possible sets, you might be able to compress them into a sequence of bits (to quickly do your checks using bitwise ops). std::bitset works if youre using c++ and can set an upper bound on possible tags at compile time (as the size is needed for the template). Or just use plain old integer if you dont have that many and like things simple.

 

You can also make tags that combine several 'fundamental' tags, to reduce the amount of tags you need per object. For a weapon, instead of tags [orc,human,dwarf,...] you might just use [hasHands]. (this will also make it more structured and maintainable, if you suddenly decide that some race has no hands, and no longer can use half of the 5000 weapon types you laboriously defined... good to have that automatically work)

Edited by Waterlimon

Share this post


Link to post
Share on other sites

You could store each string once, and refer to them from everywhere else. Then equality checking becomes a (string) object identity check, which is just a pointer comparison.

Share this post


Link to post
Share on other sites

You can also hash the strings and just use the hash. Make sure to use a good hashing algorithm (e.g. crc32) to minimize the chance of collisions.

Share this post


Link to post
Share on other sites

Number your classes and your races (I'm assuming here you'll have less than 32 of each).
Include two integers in each item for your white list, and two for your black list.
These are bitsets, where each bit in the integer identifies either a race or a class. So for class 5, the 5th bit is what you're looking for, so (classlist & (1 << 5)) is how you test for the "tag" for that class.

Share this post


Link to post
Share on other sites
Best way I can see to solve this is to store all the data you need in a file, and have an id number for the file. Then you can load the files once upon setting up the game/map. Then simply access the data by grabbing the corresponding ID number's data.

For example:

Have class named Item which holds an ID number. Upon checking for the size for example, you grab the index and the data it hold by simply passing in the ID number.

I would suggest using an std::set for efficiency's sake.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement