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 06-02-2004, 09:51 PM   #1
erdos
 
Posts: n/a
Hey, in case there's anyone besides pathetic advertisers that still uses these forums, let's try and generate some actual discussion and try and make some ground against the nonstop ads.

So I was thinking about mob progs; now it seems to me these fall way on the unefficient end of the compiled vs. scripted spectrum.

Obviously the idea of actually compiling mob progs is absurd; the effort would be of superhuman difficulty.  But compromise could be made.

First, each command structure would be augmented with a string specifying its usual arguments: for example the kill command might have a string like "%r" indicating the command will usually be used with one argument, which will be run through "get_char_room" (hence the 'r').  A more complicated example would be give, which might have a string like "%i %r"-- the %i, of course, indicating an argument which will be run through a "get_item_inventory" type function, and the %r of course being another "get_char_room" argument.  Of course, many commands are too flexible with their input, and a generic "%x" string would be used as a kind of string wildcard.  Thus a command like mpforce might have a string like: "%ar %x"  Here the %ar is a special modified version of %r which means "name of person to pass to get_char_room, *OR* the word 'all'".

Now when a builder writes a prog, it would be "pseudocompiled":  lines would be transformed from raw text into a structure somewhat like this:

[code] struct prog_line
{
 struct prog_line *next;
 command_ptr *cmd;    /* possibly NULL */
 void *arguments
};[/quote]
For example, if the prog has the line "kill dog", this would be "compiled" into a structure like {n,c,"dog"} where n is just a next * link, c is the pointer to the structure for the kill command, and "dog" is just a string to pass to get_char_room.
Now, when the prog runs, rather than just pass the string "kill dog" through the interpreter, the mud would automatically have the command structure (from the *cmd pointer); examining which, it would see "aha, this is going to take one argument which I'll pass to get_char_room.  Therefor the void pointer *arguments must just be a char pointer."

But "kill dog" is a weak example.  Let us consider instead "mptransfer $n dragon".  The mptranfer command string might look something like this: "%ar/w %v/w"  Here ar/w specifies the command will expect one argument which is either "all", or a name to be passed through get_char_room, or *IF get_char_room fails*, passed through get_char_world instead;  likewise %v/w would indicate an argument which is either a room vnum, *or* (failing that) a string to be passed to get_char_world.  Now the prog handler would use a devious "trick":  when it sees the first argument is $n, it will take a nice shortcut by saying "hey, I already know who $n is, so there is no reason to waste time expanding $n into the victim's name, then run that through get_char_room!".  This trick would be one of the main optimizing factors of this whole idea.  In the final structure, the void pointer would point not to a char *, but to a char **, since multiple arguments are expected.  Thus it might look like {next,ptr,{"$n","dragon"}}  (where ptr is of course a pointer to the mptransfer command structure)

So what if the builder does something weird like "kill" with no argument, or "kill blah blah", ie, more arguments than expected?  Or what if the builder enters a command which doesn't even exist?  Then the structure would look like {next,NULL,"kill blah blah"}-- ie, the "command" pointer would be null and the entire line would be stored in the void *arguments pointer.  How this would be handled at runtime is obvious.

For socials, the setup would be similar, although the ability to optimize would be even greater, since socials are so rigorously predictable as far as their arguments go.

Ifchecks would be retooled so as to be structures themselves, similar to command structures.  When a prog contained an ifcheck, the "compiled" version would squish everything from the if to the endif into one single "line", whose structure might look like this:
{next,I,{ptr1,args,ptr2,ptr3}}  where I is just a utility pointer that specifies "this is an ifcheck, not a command", ptr1 would be a pointer to the appropriate ifcheck structure, args would be a pointer to an appropriate structure which contains the ifcheck arguments, and (here is the subtle part) ptr2 and ptr3 would each be pointers to other prog_line structures.
For a specific example, consider the ifcheck:
[code] if class($n) == mage
flee
else
kick
wield sword
endif[/quote]

This would all be "compiled" as a single prog_line, which would look something like this:
{next,I,{class,{"$n","==","mage"},ptr2,ptr3}}
I indicating an ifcheck, class a pointer to the class ifcheck, and ptr2 and ptr3 pointers to the following prog_line structs:

ptr2 -> {null,flee,null}
ptr3 -> {ptr4,kick,null}   where
ptr4 -> {null,wield,"sword"}

Uncompiled, running the ifcheck does the following wasteful things:
* search for "class" in the list of ifchecks
* search for "flee" in the command table
* search for "wield" in the command table

All of these searches are superfluous, and that's the point of this whole idea.  If the example ifcheck included a line like "laugh $n", then we could add
* search for "laugh" in the list of commands
* failing that, search for "laugh" in the list of skills
* failing THAT, search for "laugh" in the list of socials
* expand "$n" into "erdos" (or whoever the victim is)
* search for "erdos" among the room occupants (!)

Note the last 2.  The prog handler already *knows* which character $n is referring to.  It uses this knowledge to obtain $n's actual name, which it then uses--- to search for the very pointer it started with!

Finally, the astute reader will already have noticed how inefficient our "command strings" idea at the top of the message was.  To wit, it takes precious time to interpret a line like "%ar/w %r/w";  I spoke of these to make the concept intuitively clearer, but of course a far more efficient method would be to simpy pass the void pointer in the prog_line to a function which is linked to by the command structure (in other words, object oriented programming. yes, this can be done in regular C without great difficulty)

So what's the point, you ask.  I mean, with modern processors, the beggar's little 100 coin give prog is completely negligible, right?  Right.  But imagine the power of incorporating progs into EVERYTHING:  builders could create custom spells online, specifying their behavior by using progs.  admin could create custom commands online, again using progs.  objects and mobs could have "cansee" progs where builders would completely customize who can and cannot see them (kind of a super customizable invisibility).  Quests could be set up by having "questprogs" continuously run on the questers, allowing the questmaster to make a hardcode-quality quest completely online.
But these examples are examples of super-intensive usage of progs.  Where they currently lie, far on the inefficient side of the spectrum, such features would very rapidly cause the mud to choke and die.  But with a system of "semi-compiled" progs, the envelope could be pushed considerably further.

This would not be easy at all to pull off.  A coder would have to be at least as skilled as myself, and few these days are.  And the time it would take would be quite large, more than I have to burn these days.
  Reply With Quote
Old 06-02-2004, 11:50 PM   #2
the_logos
Moderator
 
the_logos's Avatar
 
Join Date: Sep 2002
Location: Mill Valley, California
Posts: 2,299
the_logos will become famous soon enough
I can't comment on the level of coder skill required to compile mobprogs, but it's definitely doable. Our mobprogs are all compiled into basically a stack and a set of instructions. Of course, it's running under our Rapture engine and so isn't compiled into C, but Rapture can run the compiled versions very quickly. We use them for all sorts of things, and haven't had to hardcode a quest in a long time. We use them now for, ####, everything from custom effects for eating food to a whorehouse where players can go to be entertained by ladies of the evening, as it were.

As you say, not compiling them does tend to limit, performance-wise, what you can do with them. We only switched to compiling them maybe a year or a year and a half ago, precisely for that reason. I'd definitely encourage larger muds who may start to run into limits on what they can do in a single server setup to work on compiled progs. It drastically increases the breadth of things you're willing to spend processor cycles on, since you'll get way more out of each cycle.

--matt
the_logos is offline   Reply With Quote
Old 06-03-2004, 10:18 AM   #3
Gakusei
New Member
 
Join Date: Nov 2003
Posts: 7
Gakusei is on a distinguished road
This sounds like a parse tree. You would not need to be a super coder to pull this off. If you use flex/bison and a basic tree library, you can probably knock up a language in about 10 minutes. You can run through a parse tree - you do not need to generate I-code. I think this is how ruby works.

I have not really looked at stock mob-prog implementation, but IIRC they seemed to have made it hard on themselves.

I guess this is not used more often because flex and bison can look a little intimidating at first, and I guess not many hobbyists have the requisite knowledge.
Gakusei is offline   Reply With Quote
Old 06-26-2004, 06:19 AM   #4
scandum
Senior Member
 
scandum's Avatar
 
Join Date: Jun 2004
Posts: 308
scandum will become famous soon enough
It's mostly refered to as tokenized scripts. The mob prog engine my merc mud uses works pretty much as you described, in short:

unsigned char: type - social, command, if, else, endif, switch, break, etc.

char *: string - the argument to the command, if check, etc. If checks are spaced out upon bootup, this way they can get hashed (got roughly 100K lines of mprog total, so that saves quite some memory), and read with sscanf easily.

short: index - index of the command/social table (saves 2 bytes compared to a pointer) usage:

(*cmd_table[token->value].do_fun) (mob, token->string);

unsigned char: level - the functional if level, goes up after an if, goes down after an endif, etc. It's the corner stone for a solid and efficient parser. Each prog is parsed on boot, setting the level of each line.

The main issue when it comes to performance are the progs that trigger at (random) time intervals. 60% of my muds cpu usage was spend on that before I had a look at it, 20% currently.

I got it down mainly by adding a command to add a mob to the time interval trigger list when it should start doing stuff at random, and removing it from that list when it's finished. Sort of looks like:

token -> seconds per trigger -> pointer to the script

Another advantage is that it spreads cpu usage, instead of all random progs being executed every 4 seconds, the progs are triggered in time slices of 0.5 seconds.

In a very bad scenario that would mean that instead of 1 second to execute all progs every 4 seconds during which players are lagged, there are only 0.125 seconds of additional lag every 0.5 seconds.
scandum is offline   Reply With Quote
Old 06-27-2004, 08:29 AM   #5
erdos
 
Posts: n/a
Quote:
Originally Posted by (scandum @ June 26 2004,06:19)
It's mostly refered to as tokenized scripts. The mob prog engine my merc mud uses works pretty much as you described, in short:

unsigned char: type - social, command, if, else, endif, switch, break, etc.

char *: string - the argument to the command, if check, etc. If checks are spaced out upon bootup, this way they can get hashed (got roughly 100K lines of mprog total, so that saves quite some memory), and read with sscanf easily.

short: index - index of the command/social table (saves 2 bytes compared to a pointer) usage:

(*cmd_table[token->value].do_fun) (mob, token->string);

unsigned char: level - the functional if level, goes up after an if, goes down after an endif, etc. It's the corner stone for a solid and efficient parser. Each prog is parsed on boot, setting the level of each line.

The main issue when it comes to performance are the progs that trigger at (random) time intervals. 60% of my muds cpu usage was spend on that before I had a look at it, 20% currently.

I got it down mainly by adding a command to add a mob to the time interval trigger list when it should start doing stuff at random, and removing it from that list when it's finished. Sort of looks like:

token -> seconds per trigger -> pointer to the script

Another advantage is that it spreads cpu usage, instead of all random progs being executed every 4 seconds, the progs are triggered in time slices of 0.5 seconds.

In a very bad scenario that would mean that instead of 1 second to execute all progs every 4 seconds during which players are lagged, there are only 0.125 seconds of additional lag every 0.5 seconds.
Interesting, this still however has the problem of looking up characters when they're already known-- in the following sense: you have a prog which, say, has the blacksmith give an item to the person who says a phrase. Unless your merc has a fundamentally different setup, the phrasesayer should already have a pointer pointing to them in the prog-running function. But the prog-running function would only pass the phrase-sayer's name to the give command, which would use that name to look for the phrase-sayer in the room from scratch.
  Reply With Quote
Old 06-28-2004, 09:15 AM   #6
scandum
Senior Member
 
scandum's Avatar
 
Join Date: Jun 2004
Posts: 308
scandum will become famous soon enough
Yup, but consider the following:

If I'd keep track of the various triggers, and which are executed most, I'd likely end up with 99% of the triggered progs being time/interval based, and not referencing a player.

Beside, most commands used by mobs (says and echos) do not have a target. A couple of commands would be slightly faster (20% or something) but I'm not convinced it would be worth the trouble unless you have a smooth way to go about.

So not ending up with 2 seperate commands for everything, or additional if checks, which only slow things down if they're only valid in 5% of the cases, to see if a pointer is used or not.
scandum is offline   Reply With Quote
Reply


Thread Tools


Some notes on mob progs {codeheavy} - Similar Threads
Thread Thread Starter Forum Replies Last Post
Command trigger for progs Jaegar MUD Coding 1 04-03-2003 06:41 PM
Buggy Notes Verboden Faction MUD Coding 1 03-24-2003 12:57 AM

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 11:30 PM.


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