I've been a fan of MUDs (multi-user dungeons) since I was introduced to the internet back in 1993. Back then I just played them, but after a while I started programming on them. Since 2000 I've tinkered with various forms of them on my own, often using them as a platform for learning or for practicing coding techniques.
Recently I decided to take an existing code-base that was written in ANSI C and port the entire project to C# (for those who might be interested, the project is called
SmaugCS). Yes, that is pretty crazy I know, but its been a very fun challenge. Even more of a challenge I think than creating a MUD from the ground up.
This past fall I found the need to evaluate expressions that are commonly used in games such as D&D. These are often represented in short-hand form and appear as "2d4+2" or "12d10-6" where the "d" is short-hand for "die". So 2d4 would tell the system to roll two 4-sided dice twice and add the results together. In the Smaug MUD code this formula often incorporates statistics or values from within the game and appear as "2d4+L+4" where the L represents the level of a character or monster. Parsing expressions can be challenging, but the addition of a variety of values made it even more so.
While working on a solution I came across a third-party library called
NCalc - Mathematical Expressions Evaluator for .NET. This appeared to have what I needed so I began working on integrating it, but I ran into a problem with the "L". How to turn that into a custom function that NCalc could understand?
The solution it turns out was a mixture of regular expressions and the almight Func<>. To begin with I download the NCalc package using Nuget. This was the easiest way and ensures you have the latest version. Then I created an ExpressionParser class with an Execute function that took the expression I want to parse as a string parameter.
Code Snippet
- public int Execute(string expr)
- {
- Validation.IsNotNullOrEmpty(expr, "expr");
-
- string newExpr = ReplaceExpressionMatches(expr);
-
- Expression exp = new Expression(newExpr);
- exp.EvaluateFunction += delegate(string name, FunctionArgs args)
- {
- if (_expressionTable == null)
- return;
-
- CustomExpression customExpr = _expressionTable.Get(name);
- if (customExpr != null && customExpr.ExpressionFunction != null)
- args.Result = customExpr.ExpressionFunction.Invoke(args);
- };
-
- object result = exp.Evaluate();
-
- Int32 outResult;
- Int32.TryParse(result.ToString(), out outResult);
- return outResult;
- }
This may look a bit odd, but follow my logic here. The important part is that the function must convert my syntax (in this case the "L" in the expression) to a function that the NCalc library can parse and that function must have logic associated with it. So, in the case of the "L" we first want to transform it into something such as "Level()". The expression started as "2d4+L+4" and becomes "2d4+Level()+4". This is done using a custom ExpressionTable that we pass into the ExpressionParser during construction. I'll get to the table and to the ReplaceExpressionMatches() function in a moment.
To continue with the logic of the Execute function, after we replace "L" with "Level()" we create a NCalc Expression object and then a delegate that will be called when that expression is evaluated. This delegate will invoke each custom function defined within the expression tree and replace it with the result. So, if the character's level statistic was 16 at the time the expression was evaluated then the debugged expression might look like "2d4+16+4".
Finally, we tell the expression to evaluate itself and then try to parse the result. That's it! Pretty clean and straight-forward. What about the regular expressions and your custom functions you ask? Well, let's go back to that.
Within the Execute() function we made a call to another function in the class called ReplaceExpressionMatches() that looks like this:
Code Snippet
- private string ReplaceExpressionMatches(string expr)
- {
- if (_expressionTable == null || _expressionTable.Keys.IsEmpty())
- return expr;
-
- string newStr = expr;
- foreach (CustomExpression customExpr in _expressionTable.Values)
- {
- Regex regex = customExpr.Regex;
- int originalLength = newStr.Length;
- int lengthOffset = 0;
-
- foreach (Match match in regex.Matches(newStr))
- {
- string firstPart = newStr.Substring(0, match.Index
- + lengthOffset);
- string secondPart = newStr.Substring(match.Index
- + lengthOffset + match.Length,
- newStr.Length - (match.Index + lengthOffset + match.Length));
- newStr = firstPart + customExpr.ReplacementFunction.Invoke(match)
- + secondPart;
- lengthOffset = newStr.Length - originalLength;
- }
- }
-
- return newStr;
- }
What does this do? Well, we loop through the CustomExpression objects within the ExpressionTable and do a regex match and replace on every match found (since there could potentially be more than one "L" in our expression). And then we return the newly updated expression which turned "2d4+L+4" into "2d4+Level()+4".
The last piece is our expression table itself. Here's what an entry looks like. The ExpressionFunction is what is called when NCalc does the actual evaluation of the expression (e.g. getting the value of Level()) while the ReplacementFunction tells the ExpressionParser what to replace the regex match with.
Code Snippet
- ExpressionTable table = new ExpressionTable();
- table.Add(new CustomExpression
- {
- Name = "Level",
- RegexPattern = @"^?\b\w*[l|L]\w*\b$?",
- ExpressionFunction = LevelFunction,
- ReplacementFunction = ReplaceLevelCall
- });
The final two pieces, the contents of the ExpressionFunction and the ReplacementFunctions.
Code Snippet
- private static int LevelFunction(FunctionArgs args)
- {
- return GameManager.CurrentCharacter.Level;
- }
- private static string ReplaceLevelCall(Match regexMatch)
- {
- return "Level()";
- }
Both functions could probably be handled more elegant, perhaps in a static dictionary, but my primary goal was to make the system flexible. So the CustomExpression object maintains a reference to each of these functions, one which tells the Replace method what to replace the match with (the word "Level()" in this case) and another which tells NCalc what to do when it encounters the Level() function in an expression (in this case, call the GameManager and get the CurrentCharacter's level).
That about covers it. There are also unit tests covering the ExpressionTable and the ExpressionParser (giving it 96% coverage in fact). All of this was packaged into two self-contained libraries for each portability and reference.
I welcome any feedback, suggestions, comments on the code and if you want to see more (including the unit tests) please let me know.