Parse for Thought

Yes, the puns are bad, and I expect will continue…

Anyway, as I posted before, ExoMud has reached some kind of significant milestone – i.e. I have the core server mechanics done solidly (as of today, XML serialisation of all the description code), and can now start to, you know, build a game.

When coding, I’m a great believer in a bottom-up approach, creating a solid foundation for everything you intend to construct on top.  Unfortunately, I’m also lazy and ad-hoc, so this doesn’t alway work the way it should.  In this case, however, once I tamed SVN and figured on a sane project structure, I think it’s worked quite well.  So I figured I’d fill up a few posts with random bits of code I like.  So this will get a wee bit technical.

Now, to preface, I’m an immense fan of Scala; a functional, object-orientated language that is interoperable with Java (and, in fact, compiles to the same bytecode), and that’s what I’ve used to write ExoMud.  Hopefully the code sample should still make sense to the programmers amongst you…

class TreeLexer[T](val c: Char, val p: Option[TreeLexer[T]])  {
    private var value: Option[T] = None
    private var children = new HashMap[Char,TreeLexer[T]]
    private var count = 0
 
    def this() = this(' ',None)
 
    def size = count
 
    def string: String = {
        p match {
            case Some(x) => x.string + c
            case None => c + ""
        }
    }
 
    def += (value: (String,T)) = add(value._1,value._2)
 
    def -= (value: String) = remove(value)
 
    def add(s: String, v: T)    {
        add(s.toList,v)
        count += 1
    }
 
    private def add(c: List[Char], v: T)    {
        if(c.length == 0) value = Some(v)
        else {
            var t = new TreeLexer[T](c.head,Some(this))
            if(children.contains(c.head))    {
                t = children(c.head)
            } else {
                children += ((c.head,t))
            }
 
            t.add(c.tail, v)
        }
    }
 
    def remove(s: String)    {
        remove(s.toList)
    }
 
    def remove(c: List[Char]): Boolean = {
        var canRemove = false
        if(c.length > 0 && children.contains(c.head))     {
            canRemove = children(c.head).remove(c.tail)
            if(canRemove) children -= c.head
        }
        value match {
            case Some(x) if c.length == 0 && children.size == 0  => true
            case Some(x) if c.length == 0 => 
                value = None
                false
            case None if(c.length == 0) => canRemove
            case _ => false
        }
    }    
 
    def parse(s: String): List[T] =    {
        parse(s.toList)
    }
 
    private def parse(c: List[Char]): List[T] = {
        if(c.length == 0) {
            value match {
                case Some(x) => List(x)
                case None => childValues
            }
        }
        else    {
            if(children.contains(c.head))    {
                children(c.head) parse c.tail
            } else {
                Nil
            }
        }
    }
 
    private def childValues: List[T] = {        
        childMap.toList.sortWith({(a,b) => a._1.length < b._1.length}).map{a => a._2}
    }    
 
    private def childMap: HashMap[String,T] = {
        val map = new HashMap[String,T]
        value match {
            case Some(x) => map += ((string,x))
            case None => 
        }
        children foreach { x => map ++= x._2.childMap}
        return map
    }        
}

Okay, so my (rather messy) code is there, but it’s probably not particuarly apparent what it actually does.  That, fortunately, is a bit easier to explain.  Basically, these things form a tree, and each one holds a single character – in this case a letter or number.  Words can be added to the structure, along with a value that you want to associate with the word.  When you then supply the lexer with a string, it searches through the tree, finding the nearest match – in this case either an exact match, or a list of matches, in order of the length of the words with which they’re associated.

Imagine that this particular lexer holds the following words;

sword, pie, orc, saber, pi

Now the tree structure this creates looks like this;

     root
    / | \
   p  o  s
   |  |  | \
   i* r  w  a
   |  |  |  |
   e* c* o  b
         |  |
         r  e
         |  |
         d* r*

The actual values (in this case things in the game) are held at the letters marked with an asterisk (*). Root is just the first node in the tree – this doesn’t hold a value.  Now, suppose we compare the string ‘orc’ to the tree?  First it finds the node ‘o’, then ‘r’, then ‘c’, giving us the value at c*.  However, if we give it the value ‘or’, it can only search to ‘o’, then ‘r’, but still gives us the same result, as there’s only one possible match.  If we pass it ‘pi’ we get the value under i* as it’s an exact match, but if we pass it ‘s’, we’ll get both ‘sword’ and ‘saber’ back.  Now, in a MUD, this kind of mechanism is at the root of the parsing algorithms.  With a bit of extra work, it lets us turn something like;

k big

into

kill the big orc

And the beauty is, it can be used for anything, either noun or verb from the point of view of the game engine.

Stuck in the Mud

Well, inaugeration post here for the new incarnation of, well, my ‘blog.  I do have a tech-blog, which I intend to fill with all sorts of work-sanitized stuff whenever I have the time over at iGlossolalia, but that’s linked to work’s main blog and I don’t want to fill it with decidedly-non-work-related stuff.

And the reason for this blog then?  Well, firstly I’ve decided I hate LJ, and it’s quite the hassle managing two blogs on two seperate sites.  Also, my Current Project – in coding terms at least – is reaching some kind of tangible existance, and I figured a new blog was just the thing to mark this occasion – notable due to my inability to stick at most of these personal projects, Broken excepted.

Anyway, I’ve decided to write a MUD; a classic, text-based MMO, essentially.  This is because I like coding, I like the idea of writing a game, but I suck at art and, for the moment at least, have a few (I think) interesting ideas to play around with, which will be much easier to implement in a MUD form.  Plus you’ve got the advantage of a kind of ‘open-ended’ play; rulesets can be re-worked, and the range of options available to a player can increase massively with comparatively little impact on the rest of the code.

For the moment, the server will be running (very very sporadically) on exoverse.webhop.org on port 4444 – a standed MUD client such as MUSHClient will connect quite happily to a dumb login prompt.  And this is all it does; accepts a ‘connect’ command, with a username and password (passed together, or one at a time), and returns a ‘login successful’ response.  But this is still a milestone, incorporating as it does;

1. Java NIO for client-server interaction, which was a bugger to get my head round.  Currently this runs in one thread, but it’s got scope for more.
2. The notion of a stateful Player – when you first connect, you’re in the LoginState, which handles all the applicable rules in this state, likewise for character creation, then gameplay, then document reading, each of which happens at a higher level of the stack.
3. Binding between the connection from the client, and the appropriate player.
4. Some authentication stuff.
5. A DB connection, using H2.
6. And, pride of place, my TreeLexer, that takes a string, compares it to a set of strings and returns all matches, starting with the shortest.  Doesn’t seem much, but can be used to match ‘sw’ to ‘sword’ or ‘n’ to ‘north’ depending on the context, so it forms the key building block of the natural language parser I’m going to need.
7. A message/library/helpfile system that controls how text is formatted based on pseudo-xml.  This means I can pass a standard message object that can be turned into information sent to the player based on season, languages the character speaks, or whatever else affects the character’s perceptions at that time.

Anyway, will be putting up code snippets/ideas/whatnot over the next while, I suspect.