I think you're taking too narrow a view of databases. It's not just MySQL, Oracle etc. (Although even those can be stored in-memory!) Just take it literally: a place where you store data…


I'm afraid that I don't understand how this replies to my comment. Would you mind explaining that?

Yes, I know they can. I was just assuming you were talking about these types of databases, since your comment didn't make sense to me applied to anything else. Of course all object information is stored in an object itself. That's the entire point of the concept of an object - self-containing data. You would be correct if we were no longer talking about OOP, but then, referring to objects is kind of confusing in that context.



I was talking about an indexed array (OK, not really a map, but…), using character ID as the index. I know that using an actual map requires comparisons, but why on Earth would you want to do that? Maps have their uses, but I see no way that using one for this would be beneficial in any way.

Re: database. A database is a collection of data about various entities i.e. objects. A database does not necessarily store data about every object i.e. entity by creating a structure representing that object listing all of its relations.

Re: arrays/maps. An array indexed by character ID is a map. It'll be a rather sparse array, incidentally, but it's still conceptually a map. BTW, comparisons over IDs and pointers are not of linear cost.

I know full well what the definition of a database is, and what they can and can't do - I've been working with them for 14 years. You're making no sense regarding your use of the term, was my point.

And there are no comparisons in an array indexed by IDs. That's the whole point in indexing it that way.

hate_value = hate_map[ch->getID ()]; // no comparison
hate_value = hate_map[ch->getID ()][victim->getID ()]; // also no comparison
ch = hate_map[victim->getID ()]; // still no comparison

Regardless of how you choose to implement it, indexing by ID is the only way to make sure there is no comparison. I still stand by the fact that keeping lists within the objects is the more sensible approach, though.

Sorry, don't really know what to say. Databases are just data stores. Look up 'deductive database' for an example.


I didn't say there were… :rolleyes:

That said, indexing by character ID is likely to be quite inefficient memory-wise depending on how sparse the character IDs are.

The deductive database concept has nothing to do with what you referenced - not sure where you're going with that.

And character IDs don't have to be static. In fact, it would be terribly inefficient if they were, as you pointed out. The most sensible approach would be to recycle them. After all, the only purpose they serve is to uniquely identify a character with a slot in the array.

Are you sure that's possible? Do I need to do anything special? I finished my BST, but it seems to have issues on checking if the player exists in the hate data.

You should probably post a bit of the relevant code; and yes, it's possible, but I hope you don't have too many mobs.

Note any bug() are simply debug msgs for me.

tree_position tree_find( CHAR_DATA *target, search_tree tree )
{
    if ( tree == NULL )
        return NULL;
bug("tree_find: found %s", tree->hatedata->target_char->name );
    if ( target < tree->hatedata->target_char )
        return tree_find( target, tree->left );
    else if ( target > tree->hatedata->target_char )
        return tree_find( target, tree->right );
    else
        return tree;
}

HATE_DATA *tree_retrieve( tree_position pos )
{
   return pos->hatedata;
}

if( ( P = tree_find( ch, victim->hatedata )) == NULL || tree_retrieve( P )->target_char != ch )

If false, then the ch is not found in the tree.

Now the code mostly works. If "Xio" gets hate, then "Admin" gets hate everything works fine. But if "Admin" gets hate first, then "Xio" tries to get hate, the ifcheck will always be false…

You don't need the tree_retrieve function at all. Your tree_find function already returns a pointer to the tree node, so to reference its hatedata structure you can replace this:

if( ( P = tree_find( ch, victim->hatedata )) == NULL || tree_retrieve( P )->target_char != ch )

with this…

if ( ( P = tree_find ( ch, victim->hatedata ) ) == NULL || P->hatedata->target_char != ch )

Outside of that, everything you've shown is fine, which means your bug is elsewhere (most likely wherever you're adding the hate).

Yeah, I added retrieve just to see if find was having issues.

I don't think the adding hate code is the problem, but here it is:

/* Hate System test  -Zeno */
   if ( IS_NPC(victim) )
   {
        HATE_DATA *hatedata;
        tree_position P;

bug( "list of hate…");
tree_find( NULL, victim->hatedata );
bug( "————–");
        if( ( P = tree_find( ch, victim->hatedata )) == NULL || tree_retrieve( P )->target_char != ch )
        {
          int test;
          hatedata = (HATE_DATA * ) malloc( sizeof( HATE_DATA ) );
          //victim->hatedata = tree_make_empty( NULL );
          hatedata->target_char = ch;
          test = number_range( 1, 50 );
          hatedata->hate_amount = test;
          victim->hatedata = tree_insert( hatedata, victim->hatedata );
          ch_printf( ch, "It should now hate you for %d.\n\r", test );
        }
        else
        {
          hatedata = tree_retrieve(tree_find( ch, victim->hatedata ));
          ch_printf(ch, "You are already hated for %d!\n\r", hatedata->hate_amount );
        }

   }

What does the insert function look like?

search_tree tree_insert( HATE_DATA *hatedata, search_tree tree )
{
    if ( tree == NULL )
    {
        tree = (HATE_NODE * ) malloc( sizeof( HATE_NODE ) );

        if ( tree == NULL )
           bug( "tree_insert: out of space!" );
        else
        {
           tree->hatedata = hatedata;
           tree->left = tree->right = NULL;
bug( "tree_insert: inserted" );
        }
    }
    else if ( hatedata->target_char < tree->hatedata->target_char )
        tree->left = tree_insert( hatedata, tree->left );
    else if ( hatedata->target_char > tree->hatedata->target_char )
         tree->left = tree_insert( hatedata, tree->right );

bug( "tree_insert: already exists.");
    return tree;
}

else if ( hatedata->target_char < tree->hatedata->target_char )
         tree->left = tree_insert( hatedata, tree->left );
     else if ( hatedata->target_char > tree->hatedata->target_char )
         tree->left = tree_insert( hatedata, tree->right );

That part looks suspicious to me. Looks like it only sets the left side of the tree.

Typos are fun, aren't they? I'll fix that and see how it goes.

[EDIT] Appears to be working.

Here's a question… what do I do when a player quits? Obviously I can loop through all mobs to check their hate data, but that isn't smart to do.

Also, if victim->hatedata happens to be NULL, you're allocating two hatedata structs to contain the same information - one in the add function and one in the insert function. That's gonna be a leak…

Easy answer? Use the internal linked list structure I suggested, instead of the BST.

Practical answer? Add checks to any functions that use the hate concept to make sure ch != NULL, and if it does, remove it from the tree. It's better to progressively remove a character than to open yourself up to spam/abuse by making it traverse the whole tree every time a character quits.

You're mixing up choice of data stored vs. choice of data structure. :tongue: You could do the mirroring just as easily with any container implementation.

That said, Zeno, if you really are putting this into each mob and not using a global structure, a linked list does make more sense, depending on how many entities you foresee in each mob's hate list.

He's using a global structure and asking how to deal with when a player quits (meaning he'll have to traverse the entire structure and remove references to that chardata from any/all mobs). I didn't mix up anything… I was just going by what he's been referencing in his posts.

I know it's possible to do the containing with separate, internal BSTs, but let's be honest here - choosing such an obfuscated data structure when your maximum nodes are only going to be 2-3 around 99% of the time, is not a wise choice.

I don't know why you think the BSTs are obfuscated. I think it's a subjective measure; to me they seem exceedingly simple… That said, I already agreed that if you're putting it into the individual mobs it makes sense to have lists.

And incidentally, you could set up global structures to avoid having to iterate over the whole list, I believe I referred to indexing the global map already by "hater" and "hatee".