Hi. In my game I have 100 different creatures (all named like "creature_1", "creature_2" etc..) and 100 different objects that a creature can interact with. again all named like :"gun", "knife", "watch", "cup". These are rep as strings. Not all creatures can interact with all objects. Some of creatures can only interact with 2 objects other with 10 object etc.. Now. What I am trying to do is in my game menu when I select for example "gun" object I would like to display all creature names that interact with "gun" object. Say the output would be : Object Selected: "gun" ->> is used by the following creatures: "creature_2", "creature_34", "creature_89". Now. I am wonderring what would be the most efficient way to store all creature and object names (strings) and how to link objects with creatures so it would be fast to query and economic in terms of data storage? I havent done much database programming but I can imagine I could use some kind of key mapping (maybe using pointers) rather than storing same data in each object or creature. Note: there could be up to 4000 creatures and 4000 objects invloved at a time. What are you views? Thank you. [edited by - papa on May 27, 2004 5:28:01 PM]

hmmm.. DarkHamster this is the easiest way but unfortunately the longest way to search for all creatures that eg, can interact with "gun" object.
Say you have 4000 creatures each has roughly about 50 object to interact with. Using your method if I select an object "gun" as a query and scan all creatures and its interactive object. I mean :

string QueryObject = "long_name_gun";nCreatures = 4000;// loop through creaturesfor( int i=0; i<nCreatures; i++){    // loop through creature's all interactive object to see if it matches the query     for( int j=0; j<creature[i].numInteractiveObjects; j++)    {        if( creature[i].interObjectName[j] == QueryObject )        {            // ok object used by this creature, display creature name here.        }    }}

I think this is too lengthy to search 4000 creatures assuming each creature has 50 interactive objects. Every query will cost you 4000*50 = 200.000 searches in worst case (string comparison very expensive). Very naive. Unless you mean something else.
Anybody else has ideas? Some tricky ways of using hash tables or indexing?

The way I thought is the opposite to DarkMaster (faster but uses more storage). I would load all (eg. 50) objects first. while loading each object I would check each creature is it uses this object if so then I would store a pointer to this creature (4 bytes) in current objects pointer array. see below :

struct Object{   string Name;   Creature **UsedBy;}

so in the end I would end up with 50 objects and each object would hold pointers to creatures that use this object. I know it would be 4000*50=200.000 comparisons but only once when loading. Later in runtime on each query I would just select eh object m,atching query and print out its list of creatures (pointer list) that are using this object. It would be no comparisons at all. Immediate response! But I am wonderring whther somebody else has even better way of doing this?
Anyone?

[edited by - papa on May 27, 2004 6:21:38 PM]

You could create a map data structure (or a tree) that takes an object name (in your case a string) and keeps a list of creature references. Using references to the creature objects at least keeps some of the space cost down of the datastructure.

So in the case you were explaining the map would search for the key "gun" and retrieve a creature list containing all the creatures that can use it.

So in pseudo C++ you could try something like:

map&ltstring, creaturelist> objectMapkey = "gun"creaturelist c = objectMap.find(key)if(!c.empty()){  iterate the list and output all the creature names}  

[edited by - Zorbfish on May 27, 2004 6:14:07 PM]

Haha.. Zorbfish this is exactly what I thought. See my edited above post. But your structure is much cleaner. Thank you. Cool stuff! Can anybody else think of even more efficient and cleverer way of doing it? Could I use hash table for it? I dont know much about it..

[edited by - papa on May 27, 2004 6:30:00 PM]

Yes I''m sure a hash map could be used as well (although I''m not familiar with any of the STL implementations). You''d just have to hash the key string instead of looking for it, then use chaining to store the creature objects.

Does the list have to maintain a certain order according to some other value? If it doesn''t, keep each object and creature name sorted alphabetically. Then you can track certain positions in the list with similar spelled names.
For Example:: The first set all start with ''a'', next set start with "bc", etc...

1. std::map IS the "hash" / "dictionary" / "associative array" from other languagues.

2. Never forget that you can have MULTIPLE views / lists to give you efficient lookup whichever way you want, such as this:

typedef std::vector<std::string> StringList;typedef std::map<std::string, StringList> StringListMap;StringList creatures; // this might be the complete list of creaturesStringList objects; // this might be the complete list of objectsStringListMap creatureInteractions; // a map where the key is a creature, and the value is the list of objects it can interact with// could also be named:  interactionsByCreature, creatureToObjectListMapStringListMap objectInteractions; // a map where the key is an object, and the value is the list of creatures that can interact with it// could also be named:  interactionsByObject, objectToCreatureListMapobviously, if you had actual Creature and Object classes, it would look more like this:   typedef std::deque<Creature*> CreatureList;typedef std::deque<Object*> ObjectList;CreatureList creatures;ObjectList objects;typdef std::map<Creature*,ObjectList> CreatureToObjectMap;typdef std::map<Object*,CreatureList> ObjectToCreatureMap;// ORtypdef std::map<std::string,ObjectList> CreatureNameToObjectMap;typdef std::map<std::string,CreatureList> ObjectNameToCreatureMap;

[edited by - Xai on May 27, 2004 6:47:48 PM]

Ok. thank you all.

Last question. I have two clases Creature and ObjectList.

so as Xai mentioned I would be storing objects in a map not just strings but how can I search the map if I dont have a direct access to a string. I mean the map is not just simply but its std::mapCreatureToObjectMap;

the only way to access creature name is by using Creature->GetName; but how the find algo in map will access it as Zorbfish indicated above?. I guess I must read more on maps Thanks all.

[/source]