2009-06-19-more on muds and the smc
MUDs are composed of several interconnected rooms that overall create a complete world on which a virtual avatar develop it's adventures andinteract with objects and other players. One of the hardest(funnest also?) part of playing this kind of games is that the user needs to navigate this maze of rooms with little or no help at all. Players have to memorize paths and landmarks and a well seasoned player might have almost every room mapped on his head, but this is a long and treacherous process since MUDs change constantly; they are text based the creator can do in text everything he wants, so it's fairly mutable and unpredictable.
Writing aiding tools for these games can be as hard as the MUD creator wants, after all he can write in natural language and he can change the game without affecting the human understanding or the game mechanics but force the player to rewrite the tools he might be using. Because of this, separating the parsing from the logic process for the tools is a mayor priority that needs to be adresses to create a powerful tool that can be shaped accordingly as the MUD changes over time.
Most of the time the players have to use simple pattern matching or trivial parsers to aid in their exploring, some MUD clients give the user a bit more expressive tools to create their tools but overall it's really primitive when one compares these tools to the complexity of the problems a MUD player must solve when he wants to create non-trivial tools.
The whole system is best modelled as a collection of concurrent FSM that represent the state of the world in the MUD, that includes the avatar in that world and it's belongings.
While I was deciding on which programming language I should implementthe client and tools I was planning to create(the SMC), I considered and tested implementations on erlang and lisp. While writing this kind of thing on these languages is probably the best idea; the user interface APIs that these two languages provide are very clumsy and proven to be a very unpleasant and grunting task, more than I was going to accept for the UI part of the code. So far I haven't dropped the idea of using erlang or lisp due since on these languages one can hotpatch the code. This is a valuable asset when you consider the mutable nature of the MUD.
I hit several annoyances while using erlang, the main one was the sub-par string support and tools for MUDs begin as heavy string manipulators, even when you do proper separation of the parser and FSM implementations. Yet writing concurrent FSM on erlang is a very pleasant task.
On the Lisp side, while writing concurrent FSM is not as easy as it's on erlang it has a serious string manipulation library.
In the end I came up with an stackless python implementation under a very pleasant environment to develop. Stackless python provides a solution to the problem that prevented me from considering python at all for this task, until I had first tried erlang and lisp first, that is the concurrent FSMs and a proper programming model for that. But now, as I said earlier, I'm needing the hotpatch characteristic of erlang and lisp and a way that single Bots (as I call a single FSM that interacts with the MUD) can die and I can patch them without killing the whole state for all the other things that happen on the rest of the client.
Now I have this implementation of the previous ideas on the SMC and probably I have enjoyed more writing and testing all this than actually playing the game, you say for every hour I have spent in the game I have spent several more hours thinking and designing the client.
Writing real bots as in programs that automate the playing of the game rather than aiding the user to play the game should be easy with the client as it's, but now I'm most interested on a larger and more complex problem.
Navigating in a MUD is a hard task, not exploring which is fun and rewarding, but going from room X to room Z and back can be repetitive and boring when you have to move from several landmarks while you're on your character's daily routine. Remembering landmarks and maybe making comments about certain rooms on your notebook is a good practice but the information isn't really attached to the world. When your character wants to be involved in a major quest it requires moving through several steps on a number of rooms and interact with the denizens in a certain order, taking notes about this and retrieving them when needed along with context involved could be handy.
The problem I describe here is more complex than the ideas I'm going to write next, since I'm just going to relate how I'm planning to model the room map for a certain MUD.
Overall all the rooms in a mud are connected to each other in a pretty digraph like for me, So that's what I'm going to use to model the whole map.
Given room A, which has exits on several directions, say: North,south,east,west; to rooms: B, C, D, E accordingly; we on our minds picture something like this:
E - A - D
I chose the directions arbitrary, there could be any number of directions to exit the given room. But this representation is fairly incorrect given that there are a number of cases that can happen in a MUD that this graphic doesn't describe, to model correctly the situation the graph hould be something like this
E <- (A,w) <- A ->(A,e)-> D
As you see this model tells you that if you want to move south of A and land in to C you have to pass trough (A,s). That would mean moving SOUTH in the game, but if you notice it doesn't tell you how to go back from C to A and it shouldn't. It's not uncommon in MUDs to find situations and rooms that are one way, that only let you move from A to C but not C to A using the reverse move, there are also movement commands that haven't a reverse movement command.
If we graph how A and C would look on the model when there's a reverse movement step it would look like this.
|------------ (C,w) <---------------|
|-----------> (A,e) ----------------|
At this moment I'm thinking on a hyper-graph on which the Room is the hyper edge and the nodes are the (Room,Direction) tuples. I feel it's pretty much the same. The only real difference might be the efficiency of the algorithms we use on the graph but I haven't tested either.
There's a problem that I have yet to solve or handle, is that usually MUDs makes it hard(it's impossible) to identify exactly which room you're and it's certain that you might find that your bot identifies several rooms as the same one.
Now that we know what's impossible let's try to design a proper mechanism that help us to assign unique names to these repeated rooms.
The first approach that comes to my mind, is that since for us the room isn't unique we need to find something unique about that room for us; that might be the room, the exits it has and it's Nth level neighbours. We start at zero level neighbours(just the room) and increase the depth when we find a collision, until no collision is detected. That leaves us with two problems: first, the adventurer in the MUD would be obliged to walk in a funny and really annoying pattern when the discovery is needed and that may put the adventurer in danger when the area has traps or aggressive denizens. Second, if we don't do the discovery pattern, we need a way to handle incomplete discovery's and a node disconnect/attach algorithm capable of altering the graph as needed, this can be really cpu intensive if not done well.
The simplest solution I have come so far and will be the end of this writing is that on collision a single room is described by itself and the previous N rooms visited by the player, that brings other problems but would let me write a first attempt of the mapper.
The graphical representation of such a graph might not match at all the idea of the map the player might have in his mind since it would identify the a single room as different rooms depending the path the player used to arrive to such room and on two other situations.
First situation, for N = 3 and all rooms marked with x are identified with the samename in the mud:
[A] -> [x] -> [x] -> [x*]
The room x* while it's the same room it would be identified as a different room if you arrive from the path that starts on room A or room B. This shouldn't be a problem but there should be a way to merge paths manually.
The second problem probably isn't a good way to solve it in the program without human intervention that is cyclic paths like this simple one.
[A] -> [x] --|
But there are MUDs on which they count how many times you have recurred the loop and you have to go back the same amount, while the mapper simply could grab that as the expanded loop, the player should be able to edit the path and create the proper digraph structure himself.
I leave this post like that. Well the "graphs" get mangled I'll fix them later in a edit.comments powered by Disqus