Top Mud Sites Forum Return to TopMudSites.com
Go Back   Top Mud Sites Forum > Mud Development and Administration > MUD Coding
Click here to Register

Reply
 
Thread Tools
Old 04-02-2003, 11:19 PM   #1
karlan
Member
 
Join Date: Apr 2002
Location: Brisbane Australia
Posts: 74
karlan is on a distinguished road
You may have to bear with me for a bit, as the idea is only a sketchy plan in my head, but it brought up this issue.

If you wanted to maintain a record of "who knows who", so characters wouldn't know by name another character until they had been introduced (maybe a special command, so that you could "point someone out"), most of the solutions I can think of seem either memory, or cpu intensive (often both)

* each character could have an AVL tree listing the chars they know, although on a mud with a lot of players these could get quite big quickly (should still be fairly quick to search), although this also would begin to chew up cpu time.
* could maintain a master list in the form of a file/table that contains nXn entries refering to if the character is known
* hash table ?? (I never got the hang of these   )

The actual method used is not what I am asking here, although I am sure plenty of people besides myself would find it interesting/helpful.

More I am interested in what is better from a usage point of view, particularly if your MU* is being hosted on a shared server.
karlan is offline   Reply With Quote
Old 04-03-2003, 05:00 AM   #2
Kastagaar
Member
 
Join Date: Apr 2002
Location: Hampshire, UK
Posts: 117
Kastagaar is on a distinguished road
Send a message via Yahoo to Kastagaar
My usual MO is: If a function is performed infrequently, use the CPU time instead. If a function is performed frequently, use memory. Of course, I ask my profiler if a function is performed frequently or not

Not a hard and fast rule, but a good one.

Also, consider that you might store the relation "X knows Y" on Y rather than X. Then, if Y deletes themself, all the data that is now obsolete disappears with them.

-----8< quick note on hashtables 8<-----

A hashtable is basically a lookup table where each element has a "key" that is unique, or mostly unique. These keys lead to sets or lists (or other data structures. They are commonly known as "buckets") that contain the actual data. Consider a "name", which can start with one of 26 letters of the alphabet. When asking Bubba if he knows "Henry", it first goes to the bucket whose key is "H", and then iterates them to see if "Henry" is in that list. Hence, given that each bucket is populated evenly, only 1/26th of the effort is needed to search the hashtable than searching an array, in a worst-case scenario. I have a generic hash-table snippet at http://snippets.kastagaar.com if that interests you.

Kas.
Kastagaar is offline   Reply With Quote
Old 04-03-2003, 10:31 AM   #3
enigma@zebedee
Member
 
Join Date: Mar 2003
Posts: 70
enigma@zebedee is on a distinguished road
Your problem is that the data involved will expand exponentially with the number of users.

i.e. 10 users is 100 combinations, 100 users is 10000 combinations.

Some things I can think of to help are:

'Forgetting' if you don't talk to someone for a month they are moved into a forgetting list. Search the other list first each time. If someone is on the forgetting list for 3 months then remove them entirely.

(Obviously the times need working on).

You could possibly optimise things a lot by having groups as well. For example all members of the 'order of the light' could be assumed to know each other. Once you have been introduced to a certain % of a group you could assume you know the whole group (i.e. they have told you enough about the others). That sort of thing.

Whatever you do you are always going to need a lot of storage, and spend a lot of time searching that storage.

I think you really need to look at this idea and see if it is really going to add anything substantial to the game...
enigma@zebedee is offline   Reply With Quote
Old 04-03-2003, 11:08 AM   #4
markizs
Member
 
Join Date: Jan 2003
Location: Riga, Latvia
Posts: 36
markizs is on a distinguished road
Send a message via ICQ to markizs
well there is a simple solution. One mud i once played got such system: u need to be introduced to recognize the other player. if not you just would see him as 'small dwarf with long nose' etc. and to avoid any resources consuming there was limit of people you could 'know'. it did depend on your intelligence or race or level. i dont recall. but thats the way if you want to make it more rpish. like troll fighters couldnt recall many names while elf druids could do lot more.
markizs is offline   Reply With Quote
Old 04-03-2003, 04:01 PM   #5
angelbob
Member
 
Join Date: Feb 2003
Location: Bay Area, CA, USA
Posts: 39
angelbob is on a distinguished road
Actually, few MUDs are going to have more than, say, 300 players most days. Since storage expands quadratically (not exponentially) in the number of players, say that's 900000 bits for whether you know somebody. That's less than 900kB.

You could make it *much* smaller by runlength-encoding your string of bits. That means that people who knew almost everybody and people who knew almost nobody would both have really small representations for who they knew.

If you do it right it's quite fast. That's how the original Quake did its visible surface lookup, roughly.
angelbob is offline   Reply With Quote
Old 04-03-2003, 04:06 PM   #6
angelbob
Member
 
Join Date: Feb 2003
Location: Bay Area, CA, USA
Posts: 39
angelbob is on a distinguished road
I'm silly. Over 900,000 bits would be just over 100kB. I knew what I meant :-)

If you need to store more than a bit it gets to be a lot more significant. You also may not be able to usefully run-length encode.

[Edited: still no good at math]
angelbob is offline   Reply With Quote
Old 04-04-2003, 04:24 AM   #7
karlan
Member
 
Join Date: Apr 2002
Location: Brisbane Australia
Posts: 74
karlan is on a distinguished road
Almost need to split discussion into 2 threads, one for ideas, one for usage discussion. *ponder*

I had thought of using an array of longs, with bitvectors (as a dodgy hash table'esq setup with the key being [code] (char.id % sizeof(long))[/quote], but still debating with others whether to do it)

I was also asking, since I have never been involved with any of the hosting issues related to muds, whether on shared machines it is better (preferable) to use CPU or memory time/space.
karlan is offline   Reply With Quote
Old 04-04-2003, 10:02 AM   #8
Tamsyn@zebedee.org
New Member
 
Join Date: Mar 2003
Posts: 23
Tamsyn@zebedee.org is on a distinguished road
Hmm. So the smallest amount of memory you could use to remember with 100% granularity (i.e. no groups) is 1 bit per player pair, so for N players this is 1/2N(N-1). For example for 1000 players this is 499500 bits, ~62K. This is not a lot of memory. For 10000 players it takes 6MB, which is much more.

You'd store this list centrally and assign a bit number to each player. To work out whether 2 players have met, you work out where in the list of integers is the correct bit to check.

If a player leaves the game, then you'd make that bit number free, and blank the necessary bits in the list.

This is less complicated than it might sound. Checking whether 2 players have met is very quick. It doesn't use ridiculous amounts of memory (well depending on your point of view).
Tamsyn@zebedee.org is offline   Reply With Quote
Old 04-04-2003, 11:47 AM   #9
KaVir
Legend
 
KaVir's Avatar
 
Join Date: Apr 2002
Name: Richard
Home MUD: God Wars II
Posts: 2,052
KaVir will become famous soon enoughKaVir will become famous soon enough
Quote:
Originally Posted by
Hmm. So the smallest amount of memory you could use to remember with 100% granularity (i.e. no groups) is 1 bit per player pair
I think you mean 2 bits per player pair. Introducing yourself to someone else should not automatically grant you the knowledge of who they are as well.

Quote:
Originally Posted by
For example for 1000 players this is 499500 bits, ~62K. This is not a lot of memory. For 10000 players it takes 6MB, which is much more.
(1000*1000)-1000 = 999000 bits = ~122K for 1000 players.

Quote:
Originally Posted by
You'd store this list centrally and assign a bit number to each player. To work out whether 2 players have met, you work out where in the list of integers is the correct bit to check.
So each player is allocated a "free" slot number when they log on. To see if you know someone, do a lookup based on your slot number at that of the person you're looking at.

Quote:
Originally Posted by
If a player leaves the game, then you'd make that bit number free, and blank the necessary bits in the list.
Instead of blanking the bits upon logging out, I would suggest doing it when you log in. The mud could then use an array of (in this case) 1000 unique 32 bit IDs, which are compared against a (true) unique character ID. When a character connects, the mud could first check the list to see if that character's information is still there - and if so, just assign them that slot number again. To help cut down on slots from being quickly overwritten, the "search for next free slot" should begin at the slot AFTER the last person to have quit, and should try to use the as-yet-unused slots first if possible. This is important, because using your approach, loading is going to be hard work...

The real problem comes when there isn't any valid slot information. First of all you'd have to load up the list of who they know (from a separate file), then you'd have to work your way through every active slot in the list. For each slot, you'd have to (1) check that person's ID against the newly loaded list and update the new slot if necessary, and (2) load up the list of who THAT person knows, check if they know the loading character, and update their slot if necessary.
KaVir is offline   Reply With Quote
Old 04-04-2003, 12:06 PM   #10
enigma@zebedee
Member
 
Join Date: Mar 2003
Posts: 70
enigma@zebedee is on a distinguished road
So you are thinking that each player file would have a list of the names of all the people they know, and then the bitfile would be built dynamically based on the logged on people?


How does this cope with getting introduced to monsters? After all you should not automatically know a monster's name until introduced either....
enigma@zebedee is offline   Reply With Quote
Old 04-04-2003, 12:29 PM   #11
KaVir
Legend
 
KaVir's Avatar
 
Join Date: Apr 2002
Name: Richard
Home MUD: God Wars II
Posts: 2,052
KaVir will become famous soon enoughKaVir will become famous soon enough
Quote:
Originally Posted by
So you are thinking that each player file would have a list of the names of all the people they know, and then the bitfile would be built dynamically based on the logged on people?
No, that information would be stored separately. If you stored it in the same file, then you'd have to regenerate the list every time you typed "save" - by keeping it separate, you never need to re-save it (unless you can forget people), only append to it.

Quote:
Originally Posted by
How does this cope with getting introduced to monsters? After all you should not automatically know a monster's name until introduced either....
It could be handled in exactly the same way.
KaVir is offline   Reply With Quote
Old 04-10-2003, 11:42 PM   #12
karlan
Member
 
Join Date: Apr 2002
Location: Brisbane Australia
Posts: 74
karlan is on a distinguished road
The idea of identifying monsters is interesting. Would it require seperating out their name from their alias list?

it does mean that you can use knowledge based skills for different races ("a tall and powerfully built creature with the head of a Bull, wielding an axe enters from the south" whereas a person with knowledge of hybrid creatures(?) would be able to run away knowing it is a minator(sp?))
karlan is offline   Reply With Quote
Old 04-11-2003, 06:48 AM   #13
KaVir
Legend
 
KaVir's Avatar
 
Join Date: Apr 2002
Name: Richard
Home MUD: God Wars II
Posts: 2,052
KaVir will become famous soon enoughKaVir will become famous soon enough
Ah, well if you're talking about monster types (rather than individually named monsters) you'd probably want to handle it a little differently. You might want to combine it with a system for recognising "types" of other things as well - for example, being able to differentiate between different kinds of fungus, or tree, or whatever.
KaVir is offline   Reply With Quote
Old 04-13-2003, 11:14 PM   #14
karlan
Member
 
Join Date: Apr 2002
Location: Brisbane Australia
Posts: 74
karlan is on a distinguished road
This brings back the original point about mem v cpu use, you could have a relatively fast, but large array for each char containing all of the things they could know, even if for a particularly ignorant char (ie a char who never leaves the city, and has never considered food before it reaches the plate stage, would for rp reasons NEVER learn any of those things) alot of the values would be 0. Or you could have a structure that only stores in memory the things that they acually know, so it ends up with a smaller memory footprint, but would require more processing to check against their knowledge.

I suppose to really decide you should look at the type and setting of the MU and see how often alot of those "recognition" values/checks would be required.

*PONDER*
karlan is offline   Reply With Quote
Reply


Thread Tools


Memory Vs CPU usage - Similar Threads
Thread Thread Starter Forum Replies Last Post
Memory management Sitral MUD Coding 15 01-25-2004 06:04 PM

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off

All times are GMT -4. The time now is 06:15 AM.


Powered by vBulletin® Version 3.6.7
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Style based on a design by Essilor
Copyright Top Mud Sites.com 2014