Everything at its Time

I had an interesting bug with eventos that I think is worth sharing. When I first noticed it, without thinking about it too much, I thought the cause was one thing--which had a simple solution. Turns out I was wrong about that.

Recall from a previous post about eventos that I implemented a toy response for the say evento for nipics. That is, when they hear someone say something, they respond in indignation. In the linked post, it looks quite sane. Compare that to what I discovered it somehow regressed to:

<type commands for a list> say wat

a man says, 'What do you mean, "wat"???'
You say, 'wat'

Clearly the order of responses has changed somehow. I assumed this was because the code that delivers the evento does so in an arbitrary order. In the following snippet, the Mob, when it wants to say something, has the room have everyone in it hear the evento.

self.room.receiveEvento(SayEvento.new(self, text))

It turns out that the room is allowed to deliver the evento to its listeners (the mobs standing in the room) in whatever order it wants. Consider the following, obvious implementation of EventoSpeaker::receiveEvento, which is behind the previous piece of code.

def receiveEvento(evento)
    results = Hash.new()

    self.eventoListeners.each() { |listener|
        result = listener.receiveEvento(evento)
        results[listener] = result
    }
    ...

If eventoListeners here is a Set (which it often is) then its elements are ordered arbitrarily, so iteration may go in no relevant order. I took this to be the main cause of the failure, so I changed the implementation here so that the source of the evento is always first in the iteration. This did not fix it; now the source is guaranteed to see the evento in the correct order, but from a bystander's point of view, the incorrect ordering may still take place.

The actual nature of the bug is the fact that the call to receiveEvento may itself produce an evento in response. For instance, a nipic would respond with its own say evento -- the reply you see in the MUD output above. This happens inline during the delivery of the first evento, and completes its delivery to all present in the room before the first message has been delivered to everyone.

Try 1: add some threads

The way I tried to fix it was by delivering the first evento to everyone at the same time, and having the second evento block until the first completes. Here is the actual implementation, which uses threads.

mutexResults = Monitor.new()
listenerThreads = []

self.mutexEventoSpeaker.synchronize() {
    self.eventoListeners.each() { |listener|
        listenerThreads << Thread.new() {
            result = listener.receiveEvento(evento)

            mutexResults.synchronize() {
                results[listener] = result
            }
        }
    }
}

listenerThreads.each() { |t|
    t.join()
}

Now the first command will be delivered to everyone in parallel. Those who produce reply eventos that would go to the same room will have to acquire the room's mutex (mutexEventoSpeaker) first, and will therefore block until the original deilvery has completed.

Doh, that's not quite good enough

Unfortunately, this isn't enough to prevent all kinds of problems. While this method is, I think, correct for the situation I just described, it doesn't work if the reply evento goes to a different target than the same room. Consider if the nipic instead broadcasted its reply to the entire MUD. Since the whole MUD has a different evento speaker, that lock will be free and the reply will be delievered before the original evento.

There are a few ways by which I could fix that. One way I could do it is with more locking. I could make every evento listener have its own mutex. Then, whenever anyone wants to deliver an evento to someone, he first acquires the target's lock before delivering. If you've done any thread programming you know that this isn't the whole story. Actually, I would have to impose a total ordering on all the evento listener mutexes, to prevent a deadlock. Since I would like to leave the design open to pretty much anything being an evento listener (even dealies), this means I could have hundreds or thousands of mutexes, and acquiring one would mean acquiring all of the previous ones in the total ordering. I don't believe in premature optimization, but I get the feeling this solution is doomed from the start.

The simplest way I see this working is to force replies to take place on the next pulse. Eventos are delivered in the first pulse, and all replies are delivered in the next pulse. This means that there would need to be a queued and non-queued type of delivery. Actually, let me just go implement this right now while it's fresh in my mind, since it seems like a decent idea.

Try 2: Ahh, that's much better

OK, back. Man, I feel better now. Now I set a flag at the start of receiveEvento that says that this listener is in the process of receiving an event. If someone tries to sendEvento during this time, they will end up calling queueSendEvento rather than delivering immediately.

At first, this kind of flag-setting seems at risk from multiple callers in parallel, but it turns out the MUD is only multithreaded in certain ways and at certain times. I can guarantee that receiveEvento above will never be called in parallel, because this part of the MUD is driven by a single thread that "pulses" every subscribed object on the mud serially.

For the queueing, I decided to go back to the MainInteractionMode well, which has this queue pretty well implemented already, and also does a set of actions every pulse. I just added a new invocation type that sends an evento as specified.

<type commands for a list> say wat
You say, 'wat'

<type commands for a list>
a man says, 'What do you mean, "wat"???'

a guy says, 'What do you mean, "wat"???'

Ta-daaa. Oh look, it looks like our friend, "a man", has a new buddy.

Digression: blogging finds bugs

Part of the reason I write these entries is for documentation about choices I made, since it's not necessarily appropriate to go into some of the details in comments in the code or in changelist descriptions. The other reason is that this kind of narrative builds an internal dialogue that makes me think of potential problems in the design or potential solutions.

It's like--have you ever been stuck on a problem, but as you start to explain the problem to someone else, you find the solution? This happens at work all the time, but since I don't really have a human being here that I can talk to about this, I talk to myself in writing.

Of course, the reason I even bring this up is that I found the nicer solution to this post's problem in the course of writing it. That's also why the writing here is a little bit rambling. At times it's almost a stream of consciousness. After I've finished and published the post, I give it a once-over and try to smooth out some of the rough edges and clarify things that I found might only be obvious to me.

Even More Controlling

The post name is a reference to an older post on a similar topic. In that post, I describe the design of snooping and controlling, two interesting things I believe a MUD ought to support, even if it's not used much in practice or only restricted to imms. In this post, I take the feature in another direction and implement "ordering", which is universally used, mainly with pets.

Briefly, for background info: the "order" command on a MUD allows you to issue an arbitrary command to another player or NPC. The commands you can issue are typically formatted exactly the same as the ones you might type in yourself. The ability to use this power, not surprisingly, is generally highly restricted. Imms can use order to command mobs during scripted quests. Mages can usually enchant lower level mobs and command them to fight or act. Players who have pets can command their pets.

There are a few potentially distinct problems here. Firstly, we need to be able to convey the command to the target in a way he will understand. Secondly, we have to decide on how the target will interpret it. Thirdly, we have to ensure that the target cannot execute commands that they aren't "supposed" to. Fourthly, the target needs to able to handle the delays associated with executing different commands. Finally, we need to ensure that the target cannot escape from an order in some unintended way.

Communicating orders - OrderEvento

Making use of the "evento" system I put in before, to convey an order to a target, the caller creates an OrderEvento object and sends it to the target. Actually, he broadcasts it to the room, because I feel that bystanders should be able to observe this. The evento contains a field with the exact text tat the caller typed in for the order. Here's what it looks like.

<type commands for a list> order man say what's up
You bend a man to your will

<type commands for a list>
a man says, 'what's up'

Interpreting orders

Once the target has received it, he needs to process it. This starts in receiveEvento, which is called for each recipient of each evento. The code detects what type of evento it is and invokes a handler. In this case, the handler takes the full text of the command and has it executed.

The question of how this execution should take place weighed on me for quite a while. One way I might do it is to have the sender (not the recipient) transate the command into an actual Invocation object that contains the command being invoked and the arguments to it. But this could allow the target to receive and execute a command that they normally wouldn't be capable of executing. The target would then queue it up to be interleaved with whatever commands his player is typing in. There's already queueing functionality in the InteractionMode; why would I want to duplicate it for the mob as well?

Well, I wouldn't. Instead I just reused the interaction mode for both local and remote commands. Recall that the interaction mode presents the player with a view of the world, mainly including commands he can type and what he can see. When you enter the MUD you start off in the MainInteractionMode, which presents the usual flow of play and all the usual commands. But the player can enter, say, a text editor mode for editing their description, which shows totally different information to the user and has totally different commands. Which mode should interpret an ordered command?

I made things simple. I look for the shallowest MainInteractionMode, which should always be there for any player or nipic (actually, nipics have a NipicInteractionMode, which is similar but doesn't allow OOC commands), and route the command to it. This clearly makes an assumption about the presence of this specific type of interaction mode, but I feel it's a pretty safe one. The code looks a bit like this.

mainIM = manager().findIntermode() { |im|
    im.instance_of?(MainInteractionMode)
}

DebugOutput.ASSERT(mainIM, "could not find a MainInteractionMode. order shouldn't be allowed at this point. ims: #{@intermodeStack}")

if !mainIM.processRemote(evento.order)
    result = EventoStatus::OrderEvento_F_BadCommand
end

Note that here we call processRemote, not process, which is what is normally called to translate each line of text input from the client and queue it up. This allows us to differentiate between local and remote commands. More on that later.

Restricting what can be ordered

It doesn't make sense to order a nipic to "ooc" something. That is a method of communication reserved for entities that have both an in-character aspect and an out-of-character aspect. Likewise, it doesn't make sense to allow a nipic to quit. In fact, it doesn't make sense to be able to order another player to do either of those things either, since ordering is an in-character concept. This piece of code in processRemote makes it so by checking the kind of invocation it is.

if !invocation.cmd.kind_of?(NullCommand) && invocation.kind_of?(ICInvocation)
    addInvocation(invocation, false)
    return true
end

Command delays

When you type a command in, you incur a delay that is specific to what command you typed. Most of the commands I've implemented so far have a 1-pulse delay, meaning they seem to execute pretty much immediately. In most MUDs the "flee" command has a several second delay, so that it's not too easy to get away from a fight. Right now in my MUD, the toy command "jump" has a 3 or so second delay, purely so that I can test out delays.

When someone else orders your character to do something, your character should delay for as long as the command takes to complete. If both you and another player are sending commands to your character, they should be interleaved in the order in which they were received.

Nicely, the interaction mode's queueing of commands and handling of command delays takes care of this for remote commands too, by inserting both local and remote commands into the same queue, servicing them in order, and applying the appropriate delay after each one.

Haxx to escape

I discovered two ways of circumventing orders that involve exploiting the fact that they are managed by the interaction mode. For the first way, I found this innocuous looking bit of code.

def onEnterDeeper()
    super()
    flushQueue()
    showPrompt()
end # function on enter deeper

Actually, I guess that doesn't really look that innocuous, does it? This function is called when the user types a command that causes a new interaction mode to take the foreground. So if the player started editing his description, which brings the TextDocumentEditorMode to the foreground, it would flush all the commands from the queue. The fix here is simply to remove this flushQueue call; it turns out some other changes I made render it unnecessary.

The other way I found is the FlushCommand, by which a user can type ~ and clear all the commands that he's typed but which have not yet executed. It's useful when you just typed a bunch of commands but made a mistake somewhere in there (like typing "jump" 10 times in a row, which would normally take 30 seconds to finish). Obviously, "order" would be kind of worthless if it were so easy to break free of it. The way I fixed this is by tagging command invocations in process and processRemote as local and remote, respectively. Then ~ can flush only the local commands.

Digression: Ruby-specific features

By the way, in implementing this last part, I broke my internal guideline not to use Ruby-specific language features.

module MIM_InvocationTag
    attr_reader :mimit_isLocal
    attr_writer :mimit_isLocal
end # module MIM_InvocationTag

def addInvocation(invocation, isLocal)
    invocation.extend(MIM_InvocationTag)
    invocation.mimit_isLocal = isLocal
    @invoQueue.addInvocation(invocation)
end # function addInvocation

def flushLocalInvocations(upToInvocation = nil)
    @invoQueue.flush(upToInvocation) { |invo|
        invo.mimit_isLocal
    }
end # function flushLocalInvocations

Ruby has the ability to modify the class of an object instance on the fly. I didn't want to add the local/remote attribute to the Invocation class, and it wasn't convenient to subclass it either. Adding a "tag" like this seems like a really useful thing to do, since it limits the code that "knows about" it. I try not to do this kind of thing too much because deep down I entertain the possibility that I could implement this MUD in another language. If I make use of too many Ruby-specific features, that possibility withers away.

Finally

Finally, as a reward for reading this far, I leave you with what I think is a neat example of how this works.

<type commands for a list> o man o jointface o man say confusing!
You bend a man to your will

<type commands for a list>
a man commands you to do his bidding.
You bend a man to your will

<type commands for a list>
a man says, 'confusing!'

Booting Windows

I originally started writing this MUD on Linux. Slackware, actually, because I had a lot of free time and hated myself. When I moved to Gentoo on MS Virtual PC running on my Vista box (after my actual Linux box died and I got fully brainwashed), I was pleasantly surprised that, aside from some of the Ruby libraries like Facets, I didn't need to change my code at all for it to still work. I suppose that's not terribly surprising; it's a little like writing a program on Windows 2000 and being pleased when it works on Windows XP.

When I installed Ruby on my netbook, I was really surprised when the MUD code basically just worked there too. There were some minor issues with different error codes being thrown from socket functions, but once I caught and handled those the same way as their Linux brethren, I thought I was in the clear.

It would be funny if that were the end of the post, wouldn't it?

Recall the features I implemented around coldboots and hotboots. The coldboot command lets a user basically shut down and start up the mud. The hotboot command did something much more interesting - it let the user restart the mud and pick up any new code changes without kicking off any users. Turns out the latter has issues on Windows.

Hotboot is pretty interesting, and it took me a while to narrow down the problem. This one may actually be a problem in Windows, but I need to get confirmation on that. Here's a very rough outline of what the hotboot code looks like.

First, the portion to save all characters currently connected:

charConnections = Hash.new()
chars.each() { |char|
    charConnections[char] = char.connection.sockConnected.fileno
}

# persist charConnections to a file

# exec() is the magic. it restarts the mud without closing file descriptors
exec("#{Main.getLaunchCommand()}")

Then the portion to restore it:

hashCharFD = Hash.new()
# restore from file

hashCharFD.each_pair() { |charName, fd|
    sockNew = TCPSocket.for_fd(fd)
    # hook up socket to character
}

I've highlighted a few functions there. Those are the functions that do all the heavy lifting, and not surprisingly, the functions that are implemented differently on different platforms.

The first thing I noticed with my simple implementation is that after a hotboot, my character would seem connected, but wouldn't see any output from the MUD, and the MUD wouldn't see any output from it. Somehow the sockets weren't getting hooked up properly.

Compared to when I first wrote this code, I know a little bit more about how OSes work, or at least Windows. I now know that the "magic" I alluded to above is really just allowing inheritable handles. exec seems to be doing it, but it doesn't call into CreateProcess, so just to eliminate variables, I switched the implementation to use spawn instead, and pass :close_others=>false. I wanted to verify that in fact handles were being inherited.

Of course, I used my favorite debugger, windbg, for everything. Here's a bunch of debugger spew.

Breakpoint 1 hit
WS2_32!WSAAccept:
0:000> gu
eax=000003c0 ebx=7ffd9000 ecx=01424a20 edx=0000001e esi=00000000 edi=00000000
eip=76466cc8 esp=0022f118 ebp=0022f118 iopl=0         nv up ei pl zr na pe nc
cs=001b  ss=0023  ds=0023  es=0023  fs=003b  gs=0000             efl=00000246
WS2_32!accept+0x17:
76466cc8 5d              pop     ebp
0:000> !handle 3c0 ff
Handle 3c0
  Type          File

OK, so that handle represents the connected socket. I would expect it to also be there in the child process. Interestingly, at this point Ruby's fileno method that I was using above returns something like 0x54, which is totally different than 0x3c0.

Breakpoint 4 hit
kernel32!CreateProcessA:
0:005> kP1
ChildEBP RetAddr  
0267ee00 100a7a92 kernel32!CreateProcessA(
...
   int bInheritHandles = 1,
...

Confirmed handles should be inherited. Now, in the child process:

0:006> !handle 3c0
Handle 3c0
  Type          File

Well, there it is. Why the heck isn't it being connected properly? I started to suspect something in Ruby's implementation that depended on file descriptors rather than Windows HANDLEs.

I used the very good MSDN Winsock samples to help whip together a quick version of the hotboot code in C++ for comparison. My test app calls accept, then launches another process that writes back to the same handle number from the accept call. And not too surprisingly, it just works as I'd expect. So the Ruby implementation is doing something else weird.

Since I don't have source for Ruby's library, it took putting the for_fd call in an infinite loop and breaking in the debugger and examining the stack to figure out what it's doing to convert between the HANDLE and the file descriptor.

Of course, if I'd known at the start about the existence of _get_osfhandle and _open_osfhandle, I could have spared myself that trouble. It seems that fileno calls _get_osfhandle on the socket returned from accept, and for_fd does the inverse, calling _open_osfhandle on the fd to turn it into a HANDLE.

So I changed my implementation of my C++ app to mimic this, and it still doesn't quite work. I was able to get the child process to write data to the socket, but not read from it. It seems _open_osfhandle on a socket may not work exactly as advertised. This is the part that might be a Windows bug, but I haven't confirmed.

So now what? Well, sadly, I basically give up. Maybe if I find a proper implementation that works on Windows, I could consider contributing to the Ruby source and get this fixed properly. I wonder if anyone else has run into this problem before.

Old Posts are What's Up

Just a quick note that I managed to grab a hold of Caius today. He graciously brought up his old server and let me pillage all my stuff off of it, mainly including all my old blog entries for the original incarnation of Barn Cover. I fixed the formatting for my new system and posted them at their original dates, the last of which is almost a year ago. That's a long break. I was pleasantly surprised how little work it was to import the entries. Most of the work was book-keeping for the svn repository.

slap

this slap chop dance remix thing is pretty much my favorite thing ever as of now. it’s totally stupid, but i can’t help how awesome it is

slappin your troubles away with the slap-slap-slappin your troubles away with the slap chop

New Games are Weird

I was talked into playing Mabinogi the other day. It’s the first MMO I’ve played, but not the first I’ve observed or heard about in some way or another. I had fun playing, but towards the end of my second day I was starting to get a little restless. I found myself thinking back to when I first started playing MUDs years ago.

I don't think I ever started playing one on my own. It was always at someone else's invitation. And of course, in such a situation, they're always far more advanced than you are. There's a fine balance between getting help and leeching. There's a fine balance between them helping you out a bit and too much.

I actually feel kind of wussy, because I don't really feel like I'm learning things on my own. I'm asking a lot of questions and making constant comparisons to other games I know. I do it, and then I realize I'm doing it, and then I feel kind of weird about it. This may be some kind of natural cycle, but I should try to curb it.

The fighting in this game is pretty fun. I heard many times that there was considerable depth here, but now I'm starting to believe it. There are two elements that I like quite a bit: preparing skills and reading enemy attacks.

The combat is in real-time, so you have to think quickly. You can start preparing a skill, and depending on your proficiency in that skill, it takes a shorter amount of time to prepare. Meanwhile, the enemy or enemies you are fighting may also be preparing a skill. Only one skill can be used at a time, so you have to choose wisely.

Furthermore, at least a good part of the time you have to predict what your opponent will do. It seems like enemies fall into certain classes of behavior. For instance, some enemies immediately go on the defensive when you attack them. Others just charge you right back. Right now I find that it's easiest and safest with my limited hitpoints to be quite defensive, but watching others, I see that there are many opportunities to follow up an attack with another different attack. Being low level seems to limit my options considerably.

I constantly make mental comparisons with other games (read: MUDs), and in some ways the combat is more interesting. The choice between fully real-time combat and cyclic combat is always present. I'm leaning more and more towards fully real-time, but the intricacies of making that work well are a bit daunting. I don't want to mooch, but some of the things I'm experiencing here are crystallizing hand-wavy ideas I have floating around.

Now if only I could sort out these foundational problems... More on that later.

Posting with Code

As a general rule, I write these posts in HTML, because I'm a control freak. I kind of have a problem with relinquishing control, at least when it comes to things on a computer. Until relatively recently, I ran Slackware for my Linux box. At work, I write lots of scripts to do things I want. I write far more scripts than I reuse ones that someone else wrote.

I want to be able to post code here, and I want to be able to mark it up a little. For example, I like putting things in bold to point them out. To do this, I use <pre> tags and <code> tags together. Sometimes I want to show snippets of, say, XML. In that case, I need to escape all of the left angle brackets to prevent them from being interpreted.

The solution, of course, is to write a script. I wrote a little something in Ruby that formats the code blocks as it generates the output file. I can probably throw in whatever else I need into the script, too. I'm putting a Makefile in my local directory, so I can easily generate the formatted versions of posts I write in easy-to-read HTML.

To test it out a bit, here's the relevant part of the Makefile. I learned how to define an inference rule.

formatted = \
    20090514-1_posting-code.form  \

.html.form:
	ruby $(FORMATTER) $< $@

$(formatted) :

It only seems proper at this point to mention the post that helped me decide which blogging service to choose. The main part in bold in the middle is what did it: WordPress charges you to edit your CSS; Blogger does not. What else is there, when you plan to write your posts in GVIM offline?

barn cover reborn

This is not the first iteration of this blog. It was formerly hosted on the ill-fated Fallen Earth, where I mainly just wrote about random programming stuff, mainly about Ruby. We’ll see whether the same thing happens again.

If I can get the full set of posts (there were only like 5 or 6) from the old version, I’ll probably back-post them if it’s not too much trouble to edit them for this setting. I’m still trying to track down the admin, who hopefully has a hard drive that still contains them.

I think I’ve edited the theme sufficiently to get decent looking code snippets working, which is really the main feature I needed out of a blogging service. Still, I’m writing some local scripts to transform posts in the form I write them into the form that I can copy and paste in to the site. This involves things like escaping HTML within <pre> tags and removing unwanted line breaks, but ones that make it easy to write. I plan to check in the hand-written files into an svn repository, because I can’t think of a reason not to store pretty much anything under version control. “Why not?” is what I ask myself.

Hm, I’m also kind of trying to get this theme to look at bare as possible. It’s well on its way, but I can do more...

Finally, here’s some random image I had on my computer, to test out how easy it is to upload these things. [Bonus] points if you can name the game (though this is fan art). Oh wait, Windows Live Writer gets access denied when trying to upload an image. Interesting. Oh wait again. Looks like you have to upload once to start from the web with in order to create the Picasa album that stores the images. After that, uploading from WLW seems to work. Could use a better error message there.