Wednesday, November 26, 2008

Recursive Descent and grander ideas

I've spent the past week or so of spare time in between working on shipping projects refining my adventure game idea, and I've come to a decision. I'm not going to make an adventure game; instead, I'm going to reinvent MUDs. I have some experience with MUDs, and while I enjoy the concept greatly (especially allowing users to create the environment), I have never enjoyed the command interface. Too many non-intuitive commands to do things (especially allowing users to create the environment).

Part of my reinvention is to fix what I find to be this most annoying of issues - the lack of a natural-language-esque command system. To that end, I've been studying parsing, compiler-compilers, EBNF rules, all sorts of fun things. My initial path through this landscape took me to compiler-compilers like YACC, ANTLR, etc., but I grew frustrated by my lack of understanding into the problem domain.

So yesterday I decided to take a different route. I figured I'd retrace the steps it takes to create a compiler-compiler; that is, I must first understand compilers. To this end, I wrote a very simple expression parser, using recursive descent over an LL(1) grammar. Here's the grammar:

    1 //assignment:    ID EQU expression EOF

    2 //expression:    term (PLUSMINUS term)*

    3 //term:            factor (MULDIV factor)*

    4 //factor:        MINUS? (NUMBER | ID | LPAREN expression RPAREN)


    6 //ID:            [a..z A..Z]+

    7 //NUMBER:        [0..9]+

    8 //PLUSMINUS:    '+' | '-'

    9 //MULDIV:        '*' | '/'

   10 //EQU:            '='

   11 //LPAREN:        '('

   12 //RPAREN:        ')'

   13 //EOF:            [EOF]

The purpose is to parse expressions such as 'vara = 1 + 2 / (3 * varb)' and then evaluate the resulting tree. I'm not really sure if what I'm building is an Abstract Syntax Tree or not, but it suits my purposes. Anyway this is just my first attempt.

I wrote a scanner, which takes an input stream and returns tokens from it sequentially (a token being one valid element in the grammar), a parser which uses the scanner and returns a tree by consuming the tokens, and an evaluator which performs the work of turning the tree structure into run-time instructions. I added some state to the evaluator, such that it will store the expressions as assigned to variables so that other expressions can make use of them.

One neat feature I added was persistent expression evaluation - instead of storing just the result value of an expression with its label, I store the expression itself. This means that changing the value of one variable will change the value of all other variables that depend on the changed variable, and so on. Say I've got the following:

a = 1
b = a + 1
c = b + 1
d = a + b + c

d's final value here is '6' - but when I change a = 5, b becomes 6, c becomes 7, and d becomes 18. One challenge here of course is circular reference, but thanks to the answers I received to my question on StackOverflow regarding this I was able to detect when this is the case and throw an exception before an (appropriate) StackOverflowException occurs.

So I'll cut to the chase. What I'd like to build is a web-based MUD-like system that allows multiple people to interact in an environment that they can have a hand in building. I'd like the syntax to work something like this:

semantic openable has open and closed.
openable property open is not closed.
openable property closed is not open.
openable hearing open sets open and says "You open the @name." when closed; otherwise says "The @name is already open.".
openable hearing close sets closed and says "You close the @name." when open; otherwise says "The @name is already closed.".
openable hearing slam says "You slam the @name." when open; otherwise says "You must open the @name before you can slam it shut.".

The scenario the above demonstrates is the case when a player wants to define a class of behavior (called a Semantic) that represents something that can be opened and closed. I'll write another post soon about what this means and how I'm going to design this system.

Tuesday, November 18, 2008

Configuration Section Designer

For those of you who come here looking for Configuration Section information, I've found a neat (and free) Visual Studio 2008 add-in that provides a graphical interface for designing Configuration Sections - it's called the Configuration Section Designer. I haven't played with it yet, but it comes highly recommended by some on the list.

Friday, November 14, 2008

Going slow...

Well, the going has been slow. I've been working hard on a shipping provider rewrite for work, and that's sort of sucked the fun out of programming for me lately - especially with the rumors of DHL's demise looming on the horizon. My DHL shipping API integration was my first (and first successful) project with my current job, and to see that 2 months of effort wasted does not help my mood of late.

My plan to write a text adventure game is still brewing. I've been working on story elements - the concept is medieval fantasy, a common staple genre for this sort of game. I'm using the story building as a way to procrastinate, though, and put off building an engine. This sort of thing used to be easy when I was 12 or 13, but every time I start fleshing something out I get mired in objects. Bleh.

Here's the details I've decided upon so far. I will write a text adventure game engine, and the game itself will sit on top of the engine. Where normally I might consider using a database or some sort of configuration DSL, I'm instead going to implement all the rooms, items, npcs, etc., in C# code. This will allow me to implement a great deal of freedom for the player without having to write some sort of scripting language to implement the game in. All the interaction will be handled by the compiled code I write.

So the engine will have things like Room objects, Exit objects, Item objects, NPC objects, etc. The game will implement these things, one for each applicable bit of the game. This sort of thing will allow me, if I so chose, to completely change the rules of the game from room to room. Maybe overkill, but it's the way I want to do it.

So that's what I've been up to. More details later as they develop.