I would have thought you would want the mobile to continue hating the player and attack him when he logs back in.

But it's a pointer. I would think the pointer changes when a player logs in and out.

I'm not sure that was the right word, I guess. I was merely trying to point out that using BSTs when your tree sizes would be 2-3 is somewhat like calling an electrician to change a light bulb. Both will get the job done, and do it properly, but it's usually best to use the simplest structure for the job. Also, while having two concurrent trees would prevent you from having to iterate the entire tree from start to finish on average, you still have to find the specified character, which may or may not be at the beginning or end of the tree, so your best- and worst-case scenarios stay the same.



You'd probably want to use a static character ID if you want hate to save like this.

Unless the simplest is, say, O(n) and the not-simplest-but-still-simple is O(log n) and the data set is big enough which it is since it's a global tree… :smile:


I don't understand why this is. Worst-case for finding a character is log(n). Best-case is, well, better. The tree doesn't really have a "beginning" and an "end" to look at – that's the point of BSTs, isn't it?

You just got done talking about internal BSTs… not global… make up your mind! :P A global BST (such as the one he's using) is a different story. Of course it makes sense to use a BST instead of a list for this purpose. I was pointing out that using internal (within the chardata structures) BSTs is not a good idea, because it makes something more complicated than it needs to be, at no additional increase in efficiency due to the domain.



Again, you went back to the global reference while I was referring to internal. A 2-3 leaf BST's find function is going to make the same amount of comparisons on average as a linked list of the same size, simply because of the size of the data set.

And yes, BSTs do have a beginning (root) and end (actually multiple ends, being any leaf on the bottom level).

Edit: Oh, and by the way, I am not some anti-BST nazi as it probably appears. I actually use them all the time in various programs (including my MUD), as the need arises. I'm just a minimalist, and like to use the simplest algorithm/data structure/etc. that gets the job done without sacrificing (noticeable) efficiency.

I think that by now we have agreed several times that a list makes more sense for storing in every character. :wink:

As for beginning and end, I beg to differ because the beginning could just as easily be the smallest node and the end the largest one. Under your definition, where the root is the beginning, there still is no proper end because you have many of them. The point was that saying that you traverse a BST from start to end is a little odd because that is not how you are supposed to use BSTs when you are looking up known keys.

Here again, I think we're only disagreeing on the basis of personal definitions. When I think of the "beginning" of a list, it's always the node you start checking on, and the "end" is the farthest possible node from the beginning (with the node you're looking for being the "destination"). Similarly, with a BST, I consider the "beginning" to be the root because you always start there, and I consider the "end" to be any node which is the farthest from the root (highest depth).

Also, a problem that I should bring up concerning BSTs made up of pointers, is that pointers (being memory addresses) are not guaranteed to be sporadic, and in fact, memory is usually pretty sequential when assigned. Given that fact, your global BST runs the serious risk of being completely unbalanced, potentially doubling (worst-case scenario; linear) the amount of comparisons that a similar-sized list would require. Balancing the tree on insertion is a possibility, but with tens of thousands of nodes, you're looking at serious overhead for that. Of course, this can be solved fairly easily by giving characters randomly generated ID #s and comparing those instead of the pointers, which sounds like what he'll be doing anyways if he needs to save hate over reboots and such.

Self-balancing trees such as red-black trees were designed exactly for this purpose and are quite good at it. I'm not sure how much overhead is "serious overhead" for you.

Admittedly, RB trees are no longer simple and you'd be better off using an existing implementation.


Not sure why a pathologically unbalanced BST would be worse than a list: both have the same worst-case scenario of a linear number of comparisons.

Incidentally, although memory is probably sequential when assigned, chances are that not all mobs and players are actually assigned sequentially. Perhaps the first batch of mobs will be sequential, but as those mobs are killed and more are assigned, and players log on and off, the tree is likely to look better. An easily verified empirical question either way, in any case.

Then clearly you shouldn't be using a pointer. :biggrin:

It's usually a mistake to allow gameplay to be influenced by your choice of algorithm: you should change the way you code to produce the behaviour you want, not vice versa.

So: should a player be able to stop a mob from hating him by logging off and immediately logging back on again, or would it be better for the mob's hatred to survive that? If the latter, then clearly using a pointer to the player object is the wrong approach; you need to reference some kind of identifier which persists between sessions. On the other hand, if you actively wanthatred to cease at log-off then the best method is probably for the player to have his own list of "haters" just as the mob has a list of "hatees" so that all mobs' lists can be updated as necessary when logging off.

While I agree with that statement, it doesn't seem to hold true in the real world.

Examples: Xbox Live has a max amount of friends a user can have, and many users have hit that limit.
World of Warcraft has a max gold limit, and people are starting to hit that limit.
Megaman for the PSP has a number of slowdown/lag issues. Coded correctly, this shouldn't have happened.

Agreed. AVL trees also address this, albeit they're slightly worse at insertion overhead (but better average case lookup).



If you're checking the left branch first in your algorithm, and your tree is completely unbalanced with all nodes in order from smallest to largest (i.e. they only have right branches), you're going to be doing 2 comparisons per node, or double that of a list. Similarly, if you check right branches first and the tree is in order from largest to smallest, you'll have the same problem. In the case of pointer comparisons and sequential memory addresses, it would be best to check your right branch first, obviously (assuming you're not going to balance the tree - if you do, it doesn't matter).



New mobs won't be getting new memory in that case, they'll just be getting recycled memory (unless you have a resource leak). Of course, even this is "easily" dealt with if you balance the tree during boot time, since mobs will make up 95+% of your structure.

Anyway, I was just offering up a caveat.

I'm not sure why you speak of which branch you check "first": that is determined by the node comparison, not by how you wrote your algorithm. You just need to do one value comparison, get the signum, and then act according to the signum. Anyhow, I misread your original point; as I said in the bit you replied to I thought you were talking about asymptotic performance, not constant-time differences.


This is a rather odd distinction, but fine, yes, they'll be getting blocks of memory you might have seen in the past. :tongue:

How do you propose you traverse a BST with one comparison (maximum) per node? If you can figure that out, you'll be quite famous!



It's not odd… recycled memory maintains the same address(es), and thus wouldn't change the structure of your tree, regardless of how many mobs died and respawned.

Perhaps we are not talking about the same thing. You compare the value just once to the value of the node and obtain the signum, as I said. You then, naturally, need to do the appropriate thing based on the signum, which involves figuring out what the signum is, which naturally involves comparing it to -1, 0 or 1. I'm not sure what is being debated as I think I just said that I misread your post and thought we were talking not about constant time differences but about asymptotic performance. :smile:


There's no guarantee that you'll recycle exactly those blocks you had in the first place for mobs. Memory is being allocated and freed all over the place so recycled memory will not necessarily be used for the exact same mobs. Besides, as you recycle memory, it's help balance the tree because you'll be able to add it in smarter locations than a straight line.

Yeah, so I've come to the conclusion that you and I obviously have some kind of epic communication problem.

Hey, we all have our faults, ours is just not being able to talk to each other without confusing things. :tongue:

Thanks for the help. I released the BST code I did for now.
http://www.mudbytes.net/index.php?a=file...

Not sure if I will be using it for the hate system, but since I don't know if there is a large interest in a hate system snippet I'm gonna put it on hold for now. Always have a ton on my todo list for my MUD.