Err… I don't think you said anything different than me. :rolleyes: In the end of the day, the distribution of the space mapped into by the hash function is what matters – that is the only way in which a hash function is "good" (except perhaps for efficiency of computation).

I wasn't saying that a hash table is a bad idea. But since we're talking about what we think is funny, I think it's equally funny when people assume that hash tables will solve all of their problems and be super-efficient. Clearly, you have thought about how to choose a good hash function for x,y coordinate rooms. Unfortunately, most people don't even realize that's a decision they need to make very carefully if they want their data structure to be efficient.

I would say that a good hash function is often much harder to implement than a binary tree, because a binary tree can be "implemented" by typing in std::set or std::map. :smile: (It's worth noting that, in practice, there are very few times you'd actually choose a non-balanced tree over a balanced tree.)

The reason someone would want a balanced tree is for good search times.
The reason you might want a non-balanced tree could possibly be you aren't as interested in search times as you are with insertions and deletions.

The reason you might want a hash table is if you're working in C is if the problem just happens to lend itself to working out easily for a hash solution. Luckily in muds specifically rooms tend to.

Not quite. A non-balanced tree doesn't guarantee good insertion and deletion performance. Neither here nor there at the moment (and I'm in a hurry) so I won't get further into it at the moment.


Err, again, not quite. You want a hash table if you have a good hash function, meaning that lookup will be more or less constant-time, and/or it is difficult to meaningfully (or efficiently) compare elements.

Hash tables should not be thought of as merely the "easy version" of binary search trees.

Just so everyone knows.
David is the smartest guy in the room.
Just ask him, he'll tell you so.


Nobody said that hash tables are the easy version of a binary search tree. You can come write my balanced binary tree code for me in C. I'll stick to using an easy to implement and nearly evenly distributed hash table like most people would while you continue to tell it to the mountain that assuredly they aren't smart enough to understand what they are actually implementing.

I am not entirely sure why you feel the need to get personally offensive. Leaving that aside for now, you had said:

I don't think it's entirely unreasonable to infer from this that you were saying that you should go with a hash table when it's "easi[er]" to do so, even when a binary tree might be better. If you didn't mean that, it would have been very easy to just say so instead of what you chose to do.

Yes, you can infer from that, that I will decide when to use a hash table and when to use a binary tree. And yes, you can infer from that, that I will weigh how easy it is to implement up vs the efficiency loss. (Which, btw, is often inconsequential.)

I stand by what I said.

See, that wasn't so hard – there was no need to get personal about it. :rolleyes:

Now that this mini-battle is over, remember we don't HAVE to write everything from scratch. This is 2008, and there are plenty of non-commercial, non-GPL'd versions of generic data structure implementations out there in Googleville. I know sometimes it's easier to just write it yourself, but I also know it's easy to get fixated on doing it from scratch and spending days or weeks doing something that's already available out there for an hour or two of searching.

As usual, I blame lawyers… in this case, for the aura of FEAR they generate, which drives many a developer to slave away reinventing the wheel for fear they might have misread one of the sub-chapters in the licensing agreement, stating that you can only use said software if you guarantee that no future user of YOUR software will ever implement a blue button, but red or green buttons are fine.

I guess I didn't mention that I already am done with the code?

I was more thinking of the AVL trees, but…. good! :)

Well, yeah, I certainly would find a library before reinventing that wheel, but for generic purpose lists I'm pretty much done–Particularly I find it interesting that our system will use iterators.

On a side note, I'll be happy when we actually have the C++ standard libraries at our disposal.

The problem (from all the bits said) is probably from the victim dieing in the multi_hit() and being extracted, then going on with the new weapon code without checking if victim is still good. Adding either a call to char_died() (not sure if ROM has that or not) or checking if the ch still has a valid fighting target with something like:
if((victim = ch->fighting) != NULL)
before the new code should take care of the problem.

rom doesn't have a char_died function. Also, calling ch->fighting is going to crash you if the pointer ch is no longer valid. E.g. it was freed or deleted.

By default on a lot of these rom muds it uses some strange recycling system that doesn't actually free the pointer. In that case you could use the variable they use for that which is ch->valid. It's true when the data is in use. When it's been freed and waiting to be given out it's false. Of course, that could potentially mess you up if ever for some reason that data was freed and handed out to a different character all of a sudden.

Heh, yeah… recycling is another dinosaur technique from the days when malloc/free was actually expensive…. understandable when you were running on RLL disk drives that had seek times of 500ms, and your MUD was probably using all 4 Megs of physical RAM plus another 2 megs of virtual memory (residing on said 500ms seek time disks).

Nowadays, I think ripping all that nonsense out is almost the next thing on my list. The OS will already handle that for you (via the brk/sbrk system calls behind malloc), so it's just extra CPU cycles and opportunities for bugs IMHO.

I'm not sure it was just about disk performance.

Memory pools are a common technique to address memory fragmentation. If you have software that periodically allocates/deallocates memory of variable size and let it run for a while, it will consume more total memory over time as the heap gets more and more fragmented.

Memory, storage, and CPU cycles are all much cheaper these days, so optimizations like this are far less critical but can still be beneficial.

True, but the tradeoff is in code maintenance costs. Maintaining a seperate linked list for every "free" struture, and then having to check that every time you want a "new" one adds more complexity, and more CPU overhead, and possibly more page faults as your free list has to be swapped in to be checked.

I'm not saying you won't see some benefits from doing it, just that it's not worth the effort when we're talking about games that only use 10-20Megs of RAM, and typically reboot frequently anyways.

Micro-level optimizations like those should really only be made with solid numbers to back them up, and with fairly clear use cases for where this actually hurts us. Sure, they can be beneficial, maybe even quite beneficial in some circumstances, but they also introduce considerable complexity w.r.t. code maintenance. So I'm agreeing with Quix here: it would probably be simplest to just drop them and move on, and be happy. :smile:

i just want to thank runter and davidhaley for the momentary thread derailment there and then i want to thank sharmair for getting it back on topic, however i think there's a vital piece of info that must be shared, i am not trained at C nor have i read any books on it so some of these posts don't make any sense to me. i taught myself how to code (poorly) by reading the source for muds and just trial and error. that said, it looks like what sandi mentioned may help me but i'm unsure as to where to place that bit of code. is that supposed to go before the mention to can_see in the previously posted code? is it supposed to be in a completely different function than the update_violence? someone mentioned that the snippet shouldn't even be in update_violence but should be in multi_hit and after i reviewed the snippet it said something about that but it also said to replace some part with that but the only place the code i'm supposed to replace is, is in violence_update. hmm that might have been a run-on sentence but i hope everybody understands what i meant there. i'm slightly hung-over right now so i'm having trouble making sense of anything so i'll just stop this here and hope there isn't any further thread derailment.

This:

for (vch = ch->in_room->people; vch != NULL; vch = vch->next_in_room)

should be this:

for (vch = ch->in_room->people; vch != NULL; vch = vch_next)
vch_next = vch->next_in_room;

Drop by Tir na nOg and see what I've done in 5 years. I don't know any C, either. ;)

Before we try to explain why the above is needed, do you understand how a for() loop works?