Developing a flexible RPG Library in .NET 4.0 – The Expression Parser
[ Blog: Vicente - Jad Engine Blog ]2010:04:23 17:00:00
(disclaimer: this post has some repeated content from a spanish post from last year)
One of my “playtest” projects is developing a small library to implement RPG games, based on the Dungeons and Dragons toolset, most specifically in the d20 System. I’ve been working on it on my free time for the last year, but I have been swamped with lots of things and I haven’t advanced as much as I would like. But nevertheless, I have the core more or less complete from my point of view and the library it’s capable of doing some pretty cool things right now, so my idea is to explain it in detail on the next several posts.
I wanted this library to be data-driven, so I could define most information (weapons, spells, armors,…) in text/xml files and the library would read them at startup to get all the information it would need. That’s great for the future, but in short term it gave me some pretty big headaches, and probably the first one was the parsing of mathematical expressions.
When I was designing how the system would work, I decided that objects would have a list of “modifiers”: expressions that change the value of another object variables. An easy example: a Chain Mail is an item that modifiers the Armor Class of the player that has it equipped. I could claim this idea is mine, but I got it from a spectacular piece of software called PCGen (a character generator for the d20 System).
Let’s imagine an example XML representation for the Chain Mail:
<Armor Name="Chain Mail">
<Modifiers>
<Modifier Attribute="Armor Class" Value="+5"/>
</Modifiers>
</Armor>
The first problem I need to solve was: how I transform that “+5” into a number? In this case, it’s simple, I could just do:
public int Parse(string value)
{
int result;
if (int.TryParse(value, out result))
{
return result;
}
throw new ArgumentException(string.Format("value \"{0}\" is not a valid number", value));
}
That works, but this is a very simple case. Let’s imagine now the spell “Energy Drain”, which gives a creature 2d4 negative levels. The XML could be:
<Spell Name="Energy Drain">
<Modifiers>
<Modifier Attribute="Level" Value="-2d4"/>
</Modifiers>
</Spell>
Now, things have got much harder for two reasons:
- First: I need to be able to parse the expression in several parts, the minus symbol, the 2, the “d” and the 4.
- Second: parsing this expression shouldn’t produce a number, but a method!
There are even harder examples. Let’s think again about another spell, “Cure Light Wounds”, which heals a creature 1d8 hit points plus 1 hit point per caster level. The XML:
<Spell Name="Cure Light Wounds">
<Modifiers>
<Modifier Attribute="Hit Points" Value="1d8 + CasterLevel"/>
</Modifiers>
</Spell>
Nearly no other example gets harder than this in the d20 System: I have to combine (+) two mathematical expressions (1d8, CasterLevel), one which is a weird thing (1d8) and the other one is the value of an object (CasterLevel).
To solve this, I approached the problem in small steps. First, I transformed the expression into a list of tokens. My first simple approach was to rely on string.Split using spaces as separator, but honestly “1 d 8” looks horrible. So I implemented the following grammar (I think it’s in right BNF, but could be it’s not) and wrote a small parser for it.
If you read the grammar and write some examples, you will realize it doesn’t handle parenthesis right, but I do not care about it much as the next step will control that case. The next step is to transform the list of tokens into something I can evaluate. For example, I may have the tokens: Number (5.0), Operator (+), Number (3.3), and I want some way to evaluate that to 8.8. This involves two steps.
First, “5.0 + 3.3” is a mathematical expression in infix notation, which is great for humans to read but a pain to evaluate. It’s far easier for a computer to evaluate mathematical expressions in postfix notation “5.0 3.3 +” (if you have used old HP calculators, you may have seen it there). There are several nice things about this step:
- There is a very simple algorithm that transform infix to postfix expressions: Shunting-Yard (invented by Dijkstra).
- Postfix expressions do not need parenthesis, so if the parenthesis are right the expression will transform using Shunting-Yard and if they aren’t the tranformation will detect it and throw an error.
Now that the expression is in postfix notation, the second step is to evaluate it to produce the expected result: 8.8. The postfix evaluation algorithm is pretty easy too. But while we can evaluate “5.0 3.3 +”, we can’t evaluate “5.0 Character.CasterLevel +”. That’s why our evaluator has to produce a method instead of a number. This may seem hard, but if you read the Shunting-Yard explanation it says:
It can be used to produce output in Reverse Polish notation (RPN) or as an abstract syntax tree (AST).
.NET 3.5 added support to create ASTs! That’s what the Expression Trees feature is all about (it was designed for Linq To SQL, but it helps us here). So, instead of evaluating the expression, what I do is to modify the evaluation algorithm to generate a tree that represents the expression, like this:
private static Expression<Func<CalculationHelper, double>> ToExpressionTree(IEnumerable<Token> tokens)
{
Stack<Expression> operands = new Stack<Expression>();
ParameterExpression parameter = Expression.Parameter(typeof(CalculationHelper), "calculator");
Expression op1, op2;
foreach (Token token in tokens)
{
switch (token.TokenType)
{
case TokenType.Number:
{
operands.Push(Expression.Constant(((NumberToken)token).Value, typeof(double)));
break;
}
case TokenType.Variable:
{
VariableToken variable = (VariableToken)token;
operands.Push(Expression.Call(parameter, "SolveDependency", null, Expression.Constant((variable.Category), typeof(string)), Expression.Constant((variable.Attribute), typeof(string))));
break;
}
case TokenType.Dice:
{
DiceToken dice = (DiceToken)token;
operands.Push(Expression.Call(typeof(Dice), "Roll", null, Expression.Constant(dice.Number, typeof(int)), Expression.Constant(dice.Size, typeof(int))));
break;
}
case TokenType.Operator:
{
OperatorToken operatorToken = token as OperatorToken;
op2 = operands.Pop();
op1 = operands.Pop();
switch (operatorToken.OperatorType)
{
case OperatorType.Add:
{
operands.Push(Expression.Add(op1, op2));
break;
}
case OperatorType.Subtract:
{
operands.Push(Expression.Subtract(op1, op2));
break;
}
case OperatorType.Multiply:
{
operands.Push(Expression.Multiply(op1, op2));
break;
}
case OperatorType.Divide:
{
operands.Push(Expression.Divide(op1, op2));
break;
}
case OperatorType.Power:
{
operands.Push(Expression.Power(op1, op2));
break;
}
}
break;
}
default:
{
throw new ArgumentException(string.Format("An undefined token ({0}) appeared while calculating an expression.", token.Text));
}
}
}
if (operands.Count == 1)
{
return Expression.Lambda<Func<CalculationHelper, double>>(operands.Pop(), parameter);
}
else
{
throw new ArgumentException("Invalid expression");
}
}
If you read the code, you will see it may insert two method calls inside the expression tree, one to Dice.Roll, which simulates a dice roll (1d8), and another to CalculationHelper.SolveDependency, which solves the value of variables from other objects. The tree returned for this method can be later compiled to a delegate Func<CalculationHelper, double> which will be used to calculate the real value of the modifier. For example, the Cure Lights Woulds expression (“1d8 + Character.CasterLevel”) would be transformed and compiled into the following delegate:
Func<CalculationHelper, double> func = (c) => Dice.Roll(1, 8) + c.SolveDependency("Character", "CasterLevel");
(I will explain in another post why CalculationHelper is a parameter of the delegate)
Future improvements (now on hold while I work on other parts of the library) will be:
- Handle parenthesis right in the grammar. Low priority, easy.
- Improve the grammar and the expressions tree generator to handle expressions like xd4 where x is the value of another object. For example, the damage of the spell “Fireball” is 1d6 per caster level, so the expression should be something like “Character.Level d6” or something like that (not sure yet, suggestions accepted). High priority, so-so.
- Improve the grammar and the expression tree generator to support calls to methods from the Math class (Round, Truncate,…). Medium priority, pretty hard.
![mvplogo[1]](http://kartones.net/blogs/jadengine/mvplogo1_thumb_0E5E33BD.jpg)
