Partial Command Matching

 
Post new topic   Reply to topic    mudlab.org Forum Index -> Coding
View previous topic :: View next topic  
Author Message
Kelson



Joined: 18 May 2005
Posts: 71
Location: SC

PostPosted: Thu Nov 10, 2005 3:46 am    Post subject: Partial Command Matching Reply with quote

First my goals, I have a multi-level set of command tables (much like a stack) which needs to be used at different levels at different times, but which should be fairly consistent between those times. One level handles asynchronous commands (immediate, exact-match only administrative commands executed outside the main game loop), one level handles non-game related commands (like quit or score - not interacting with the world), and the lowest level (right now) are the in-game commands (interacting with the world, executed in the main game loop).

The idea here is a clear delineation between game access levels. Administrators hit all three levels when they enter a command (earliest located match is executed). Players have access to commands like score and quit as well as movement, but their input is never even checked for a match with the administrative commands. Game objects only interact with the game world interactive commands (like movement). This prevents bugs like one player causing another player's character to execute out of game commands (like delete, quit, and password changing).

Naturally I wouldn't post this if I didn't have a problem though (as much as I do enjoy bragging...this isn't really braggable). The problem comes from the second and third levels, since I would optimally like command completion for both levels at the same time for parsing at level 2, without copying the command table for level 3 into level 2. Currently, I'm do simple string comparisons until the command ends (the ROM way), but I'm open to other options.

- Kelson
Back to top
View user's profile Send private message Send e-mail AIM Address
Author Message
KaVir



Joined: 11 May 2005
Posts: 565
Location: Munich

PostPosted: Thu Nov 10, 2005 10:04 am    Post subject: Reply with quote

Just to make sure I understand you correctly, you have:

1) Admin commands (must be typed in full)
2) Non-game commands such as score/quit (can be abbreviated)
3) Game commands such as north/kill (can also be abbreviated)

And you want to have it so that you don't have to check all non-game commands before checking the game commands? Eg so 's' counts as 'south' (a game command) and not 'score' (a non-game command) - but equally 'sc' counts as 'score' and not 'scan' (a game command)?

Personally I'd be tempted just to combine 2 and 3, and just add an 'in-game' flag to the command table. You could then use that flag when parsing (eg if you 'order' a mob to do something, call the parser but tell it to only use commands with a game flag).

If you really want to separate them, though, you could try having two sets of game commands - high priority and low priority. You'd then check like this:

1) Admin commands
2) High-priority game commands (eg 'south')
3) Non-game commands (eg 'score')
4) Low-priority game commands (eg 'scan')

Then whenever you run into ordering issues with a command, you could just move it to the high-priority table.

If you don't like breaking the commands up into two separate tables, you could also just add a priority flag, then check the game table twice (or first half/non-game/second half if you keep all the high priority commands at the top of the table).
Back to top
View user's profile Send private message Visit poster's website
Author Message
Tyche



Joined: 13 May 2005
Posts: 176
Location: Ohio, USA

PostPosted: Thu Nov 10, 2005 11:24 am    Post subject: Reply with quote

Obviously to do command completion one must have assembled a set of candidate commands from the partial command entered. I use a ternary search trie to store commands. One property is that it's fast and another is that can handle and return wildcard matches efficiently. I return the possible commands in an array and then go to process the next command trie adding to that array. I don't have to rescan the command tries because the array of possible commands includes everything needed to process any of the commands. That is it contains references to them.

I'm not sure what you are really asking though.
Back to top
View user's profile Send private message Visit poster's website
Author Message
Sandi



Joined: 13 May 2005
Posts: 94
Location: Boston

PostPosted: Thu Nov 10, 2005 11:31 am    Post subject: Reply with quote

I think I agree with KaVir - merge the tables.

The only idea I have is a bad one. Number the tables, using about twice the number of numbers as you have commands so there will be "holes" in the second level where you can position third level commands you want to take precedence. . Scan both tables for a match, compare the numbers, and run the command that wins.

The Diku command table works just fine, though, it checks for level and position among other things and I don't recall any bugs with players using commands at the wrong level. I think Kavir's flag suggestion is a good one. I appreciate what you're doing is conceptually more secure, but I'm not sure it's better in practice.
Back to top
View user's profile Send private message Visit poster's website
Author Message
Gromble



Joined: 08 Oct 2005
Posts: 23

PostPosted: Thu Nov 10, 2005 12:09 pm    Post subject: Reply with quote

Another approach worth considering involves permissions.

Every command in the system belongs to one or more permission groups, as does each user.

The largest permission group consists of common commands, but you have the flexibility to restrict commands based on any number of factors such as race, class, skills, administrative responsibilities, etc.

In the context of your question, you could rank the permission groups and then look for the first command match as you progressively searched from group to group.

There's also the benefit of only showing available commands to a user when they enter "help".
Back to top
View user's profile Send private message
Author Message
Kelson



Joined: 18 May 2005
Posts: 71
Location: SC

PostPosted: Fri Nov 11, 2005 12:57 am    Post subject: Reply with quote

KaVir wrote:
1) Admin commands
2) High-priority game commands (eg 'south')
3) Non-game commands (eg 'score')
4) Low-priority game commands (eg 'scan')


I actually had conceptualized a similar system, though instead of calling the first table high-priority game commands they were merely completion aliases.

Regarding merging the tables, I want to avoid that as the command parsing stacks may not always include all command sets (there may be numerous game command tables and they may change). A 'master' command table could be added to the top of the stack consisting of all commands below it, but that requires repeatedly re-copying the data (although it is possible to make players share the created tables and thus rarely make new ones or use up much memory). On the whole, I wanted to avoid this solution.

Perhaps my end solution will consist of an alias set for each player respective to each command table such that only the 'in-use' command tables are possible final commands for the aliases.

One issue I see looming with multiple command tables, some of which may not always be present, and at least some using command completion is unintentional commands. For example, I enter 'm' which completes to 'mstat' when I normally have the out-of-game command table. Suppose one time that table is not present and I enter 'm', but now it executes 'murder' - that could be very non-obvious and problematic (that is actually why the admin commands are non-completing)

- Kelson
Back to top
View user's profile Send private message Send e-mail AIM Address
Author Message
Alister



Joined: 13 May 2005
Posts: 62
Location: Alberta, Canada

PostPosted: Fri Nov 11, 2005 2:12 am    Post subject: Reply with quote

Kelson wrote:

One issue I see looming with multiple command tables, some of which may not always be present, and at least some using command completion is unintentional commands. For example, I enter 'm' which completes to 'mstat' when I normally have the out-of-game command table. Suppose one time that table is not present and I enter 'm', but now it executes 'murder' - that could be very non-obvious and problematic (that is actually why the admin commands are non-completing)


Perhaps here's an option that addresses this problem as well as your original one. Do away with command completion. Now, observe that there is regularity between the abbreviations that players use for commands that are abbreviated. For instance, look, north, east, and kill are invariably abbreviated to l, n, e, and k, respectively.

What you could do is have command expansions that are tried before a command is even looked up in one of the command tables. l would expand to look, k to kill, i and inv to inventory, etc...
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Author Message
Lared



Joined: 07 Oct 2005
Posts: 26

PostPosted: Fri Dec 02, 2005 11:30 am    Post subject: Reply with quote

Alister wrote:
Perhaps here's an option that addresses this problem as well as your original one. Do away with command completion. Now, observe that there is regularity between the abbreviations that players use for commands that are abbreviated. For instance, look, north, east, and kill are invariably abbreviated to l, n, e, and k, respectively.

What you could do is have command expansions that are tried before a command is even looked up in one of the command tables. l would expand to look, k to kill, i and inv to inventory, etc...


Okay...and for people like me who type inv this system breaks.

What you're suggesting is a giant leap back more than ten years and I'm trying to see the value for this idea. Coming up empty. Enlighten me?
Back to top
View user's profile Send private message
Author Message
KaVir



Joined: 11 May 2005
Posts: 565
Location: Munich

PostPosted: Fri Dec 02, 2005 12:49 pm    Post subject: Reply with quote

Lared wrote:
Alister wrote:
What you could do is have command expansions that are tried before a command is even looked up in one of the command tables. l would expand to look, k to kill, i and inv to inventory, etc...


Okay...and for people like me who type inv this system breaks.


How would it break? He's specifically said that he would support "inv"...
Back to top
View user's profile Send private message Visit poster's website
Author Message
Alister



Joined: 13 May 2005
Posts: 62
Location: Alberta, Canada

PostPosted: Fri Dec 02, 2005 5:58 pm    Post subject: Reply with quote

Lared wrote:
What you're suggesting is a giant leap back more than ten years and I'm trying to see the value for this idea.


Well, it addresses these problems:

Quote:

Suppose one time that table is not present and I enter 'm', but now it executes 'murder' - that could be very non-obvious and problematic


Quote:

The problem comes from the second and third levels, since I would optimally like command completion for both levels at the same time for parsing at level 2, without copying the command table for level 3 into level 2


Which appear to be his main concerns. What would you suggest be done instead?
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Author Message
BobTHJ



Joined: 19 Nov 2005
Posts: 31

PostPosted: Sat Dec 03, 2005 3:22 pm    Post subject: Reply with quote

The command parser I use for my custom MUD Engine works very similar to Alister's suggestion. I store all possible command matches in a hashtable for quick lookup. For example, for the LOOK command I store the values "LOOK", "L", "EXAMINE", and "EX". Then, it's a simple matter of finding an exact match in the command hashtable. If an exact match doesn't exist, then you know it's not a game-wide command.

Of course, there is a bit more complexity. If the match is not found in the command list, the mud creates a Message object (the same type of object I use to send a message to a room or player) and sends it to the player's location. This allows any objects in the room to handle the command input. For example, you wouldn't want a "LIGHT" command ad the mud-wide level, because it would be useless most of the time. However, if there is a Torch object in your room and you enter a "LIGHT" command, the Torch object can handle it and change it's state so it is lit. Also at this level you will find room exits (in my mud these are first-class objects that respond to messages like any other object). This allows me to have named exits like "Small Green Door". The room exits can handle the player's command if it matches (or partially matches) the exit name and move the player through that exit.

Finally, if there is no match at the mud-wide command level, or from an object nearby the player, the command is passed to the socials list, which is again a hashtable lookup.

One thing I have considered implementing is a adaptive learning command system. It would log all the failed commands (ones which no match could be found for), along with the next command the player entered. Once a pattern had been established between a failed command and a valid command, that failed command could be added to the mud-wide command list pointing to the valid command. For example: If players enter "LO" for "LOOK" they will get an invalid command error because "LO" is not in the mud-wide command table. However, since most people will try "LOOK" after receiving that message, a correlation could be established between "LO" and "LOOK". Once a sufficient number of people went through this process the "LO" could be added to the command table pointing to the "LOOK" command. This way anyone who enters "LO" in the future will be able to Look.

You wouldn't even have to automate the above proces. All you would need to do is store a list of all invalid commands which you could review from time to time to see if there are frequently entered strings which are not being found and processed by your command parser.
Back to top
View user's profile Send private message Send e-mail
Display posts from previous:   
Post new topic   Reply to topic    mudlab.org Forum Index -> Coding All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Powered by phpBB © 2001, 2002 phpBB Group
BBTech Template by © 2003-04 MDesign