BattleLang – A Domain Specific Language in .NET – Part III

by Call me dave... 23. December 2009 06:45

In this series of blog posts I am exploring the creation of a DSL for a mythical Role Playing Game called “Dragons of Kin” at the Puzzle Guzzler software house.  The language will allow the game designers to interact with the underlying game engine.  All the business logic and heavy lifting is performed by the engine meanwhile the language will be used a conduit into the engine.  Characters, layout and animations will be configured using the language.  In this post I will show the first implementation of the DSL.

In the last post Douglas (the development lead) and Jasmine (the level designer) had created the following example of the first cut of the language they had developed.

 Creature Crocodile {
    Life := random_select [30..40] LP
    Magic := 15 MP
    LifeHealingSpeed   := 3 LP/sec
    MagicHealingSpeed   := 1 MP/min
    Weapons
    {
      Bite:
        Inflicts:= random_select [5..10] LP
      PoisonBite:
        Inflicts:= random_select [5..10] LP + 3 LP/sec
        Costs:= 5 MP
    }
  }

Douglas takes the language fragment to Jimmy a developer on his team.

Jimmy So this is the infamous BattleLang
Douglas Yep.  As we discussed in the Stand Up.  We have three weeks to implement a text mode engine that will allow Christoph to move from the town to the spring.  There he will kill the crocodiles and save the town.
Jimmy Everything hard coded then.  So we will have three Creature types – Jimmy, Crocodile and Boss Crocodile.  Lets not do spawning either.  The Crocodiles will be created as soon as the engine starts.  There really should be an Area type in the language so that Jasmine can assign the Crocs to a location.
Douglas Definitely.  Lets put that up onto the Product backlog.  So can you do the first cut of the parser over the next couple of days?
Jimmy I think so.  I was looking at F# Lex support, ANTLR, Bison but if I only have 2 days I don’t want to learn a new library or toolset.  I’ll just crank out something quickly and we’ll throw it away bit further down the track. It looks pretty easy to parse.
Douglas Lets go to the white board and draw out a transition diagram.

image  

Each line represents a token that the scanner is reading from the input.  We start with “Creature” read in the name of the name Creature then we have an open and close bracket and then we reach the end. In this case we are saying its legal to have a Creature with no attributes defined at all.
Jimmy And what we assume that during each transition all the whitespace is thrown away?  It doesn’t make sense for that to be legal does it?
Douglas For now lets assume that around every token there is whitespace.  When the code is rewritten we can throw that assumption away.  So the code should actually look like this.
  Creature Crocodile {
    Life := random_select [ 30 .. 40 ] LP
    Magic := 15 MP
    LifeHealingSpeed   := 3 LP / sec
    MagicHealingSpeed   := 1 MP / min
    Weapons
    {
      Bite :
        Inflicts := random_select [ 5 .. 10 ] LP
      PoisonBite :
        Inflicts := random_select [ 5 .. 10 ] LP + 3 LP / sec
        Costs := 5 MP
    }
  }

What is I mean by it being legal is that the checking if the Creature is valid is a different step in the process. 
image 
By shifting the complex validation out of the Syntax Analyser it makes the code a lot simpler. 
Jimmy Ok.  Let me see so to do the parsing of the character attributes there is another string literal and then we parse the function itself.
 image  

And the function parser is as follows.
image
Douglas I’ll add in the Weapons
 image

 

Building the Proof of Concept BattleLang DSL

As described above there are a couple of stages to process a language:

  • Lexical Analyser which converts the input stream into into Tokens
  • Syntax Analyser which implements the transition diagram
  • Semantic Analyser validates the business rules

 

Lexical Analyser

By simplifying the language definition so that all Tokens are separated by whitespace the scanner is very simple.

public static TokenAndStringIndex GetNextToken(string text, int currentIndex)
{
    string token;
    if (HaveReachedEndOfInput(currentIndex, text))
        return new TokenAndStringIndex("", text.Length);

    currentIndex = RemoveWhitespace(currentIndex, text);
    currentIndex = GetToken(currentIndex, text, out token);
    return new TokenAndStringIndex(token, currentIndex);
}

The TokenAndStringIndex is a tuple that stores the current Index into the array and the Token that was found.  Retrieving a list of all the tokens is a simple matter of looping through the input.  While we could return an IEnumberable<string> in a more complete solution the TokenAndStringIndex would be renamed and extended to to include information such as the line number within the string the token was extract from.  This information is invaluable when it comes to creating useful error messages when problem are found during the Syntax and Semantic Analyser steps.

 

public static IEnumerable<TokenAndStringIndex> GetAllTokens(string text)
{
    int currentIndex = 0;
    while (currentIndex < text.Length)
    {
        var result = GetNextToken(text, currentIndex);
        currentIndex = result.IndexIntoInputString;
        if (!string.IsNullOrEmpty(result.Token))
            yield return result;
    }
}

 

Syntax Analyser

The syntax analyser eats through the streams of tokens moving through the transition diagram.  On nodes such as the Open Bracket it needs to grab the next token and determine which of the three subsequent nodes should be selected (Close Bracket, retrieve Creature attribute or Enter Weapons scope).  There are lots of different ways to model the nodes and transitions.  One very clean way is to have a class per node and implementing the state pattern.  All classes implement an interface INode and member INode ProcessToken(Token t)

However this time I decided to use an even simpler (although far less scalable) approach.

First three enums were created:

  • Keywords – Include nodes for Creature,  Weapons, Inflicts, Costs,  MagicPoints, LifePoints, Seconds, Minutes, RandomSelect and Colon
  • Operators – Includes nodes for Assign, Add, Subtract, Multiply, Divide, Range
  • Scope – Includes nodes for OpenCreateScope, CloseCreateScope, OpenWeaponScope, CloseWeaponScope, OpenRangeScope, CloseRangeScope

I then created the TokenAction class which links the Token string, to the enum and to a delegate that will manage the transition logic and the retrieval of the information about the Creature.

internal class TokenAction<T>
{
    private readonly T _tokenType;
    private readonly string _token;
    private readonly Action _action;

    public TokenAction(T tokenType, string token, Action action)
    {
        _tokenType = tokenType;
        _action = action;
        _token = token;
    }

    public Action Action
    {
        get { return _action; }
    }

    public string Token
    {
        get { return _token; }
    }

    public T TokenType
    {
        get { return _tokenType; }
    }
}

If we are at Node “Creature” the next token will be the Creature’s name then the following node should be a “{“.  The “{“ node includes its own transition logic that we can access by calling execute on its Action.  Hence:

new TokenAction<KeyWords> (KeyWords.Creature, "Creature", () =>

  {
    _creature.Name = GetLiteral(); 
    TransitionToScopeToken(new[] { Scope.OpenCreateScope });
  }

)

The following code searches for either “MP” or “LP” and sets the _dimension to the required value:

TransitionToKeywordToken(new[] { KeyWords.MagicPoints, KeyWords.LifePoints });

new TokenAction<KeyWords>(KeyWords.MagicPoints, "MP", () => _dimension = DimensionType.Magic)

new TokenAction<KeyWords>(KeyWords.LifePoints, "LP",  () => _dimension = DimensionType.Life)

As you can see the code “collects” values such as the DimesionType as it parsers the tree.  All of the Tokens and their relevant Actions were placed into three symbol tables using the TokenActions class which manages the moving executing of the Actions.

internal class TokenActions<T> 
{
      private readonly Dictionary<T, TokenAction<T>> _symbolTable = new Dictionary<T, TokenAction<T>>();
      public void Add(TokenAction<T> tokenAction)
      {
          _symbolTable.Add(tokenAction.TokenType,tokenAction);
      }

      private TokenAction<T> GetTokenAction(string token)
      {
          return _symbolTable.Values.First(x => x.Token == token);
      }

      private TokenAction<T> GetTokenAction(T tokenType)
      {
          return _symbolTable[tokenType];
      }

      public void InvokeAction(string token)
      {
          GetTokenAction(token).Action();
      }

      public void InvokeAction(T tokenType)
      {
          GetTokenAction(tokenType).Action();
      }

      public bool IsTokenFor(string s, T tokenType)
      {
          return GetTokenAction(tokenType).Token == s;
      }

      public bool TokenSymbolExists(string token)
      {
          return _symbolTable.Values.Count(x => x.Token == token) > 0;
      }
  }

The parser populates the following objects:

  • Unit which models the following “10 MP / sec”
  • UnitsType a collection of Unit objects and automatically reduces “10 MP / sec + 11 MP / sec” to “21 MP / sec”
  • Weapon which includes the damage that is inflicted and the cost to the user
  • Creature which will be passed to the engine – Currently implemented as a fake shell to demonstrate the parser
using System.Collections.Generic;
using System.Linq;

namespace BattleLangParser
{
    public enum DimensionType
    {
        Magic,
        Life
    }

    public enum TimespanType
    {
        Now,
        Second,
        Minute
    }

    public class Unit
    {
        public float Amount { get; set; }
        public DimensionType Dimension { get; set; }
        public TimespanType Timespan { get; set; }
    }

    public class UnitsType
    {
        private readonly List<Unit> _units = new List<Unit>();
        public IList<Unit> Units { get { return _units; } }
        
        public void Add(Unit u, Operator @operator)
        {
            if(_units.Where(x => x.Dimension == u.Dimension && x.Timespan == u.Timespan).Count()>0)
            {
                var result = _units.First(x => x.Dimension == u.Dimension && x.Timespan == u.Timespan);
                switch(@operator)
                {
                    case Operator.Add:
                        result.Amount += u.Amount;
                        break;
                    case Operator.Subtract:
                        result.Amount -= u.Amount;
                        break;
                }                
            }
            else
            {
                _units.Add(u);
            }
        }
    }

    public class Weapon
    {
        public Weapon()
        {
            Inflicts = new UnitsType();
            Costs = new UnitsType();
        }

        public UnitsType Inflicts { get; private set; }
        public UnitsType Costs { get; private set; }
    }

    public class Creature
    {
        public Creature()
        {
            Stats = new Dictionary<string, UnitsType>();
            Weapons = new Dictionary<string, Weapon>();
        }

        public string Name { get; set; }
        public Dictionary<string, UnitsType> Stats { get; private set; }
        public Dictionary<string, Weapon> Weapons { get; private set; }
    }
}

Semantic Analyser

In this version of the software it does not include a semantic Analyser.

 

 

Unit Tests

An example of one of the Unit tests:

[Test]
public void ParseCreature_MultipleDimensions_EachDifferent()
{
    const string emptyCreature = @"
Creature TestMonster
{
    RingOfhealing := 3 MP / min + 8 LP / min
}";
    var b = new Parser(emptyCreature);
    Creature result = b.Parse();
    Assert.AreEqual("TestMonster", result.Name);

    Assert.IsNotNull(result.Stats["RingOfhealing"]);
    Assert.AreEqual(3.0, result.Stats["RingOfhealing"].Units[0].Amount);
    Assert.AreEqual(DimensionType.Magic, result.Stats["RingOfhealing"].Units[0].Dimension);
    Assert.AreEqual(TimespanType.Minute, result.Stats["RingOfhealing"].Units[0].Timespan);
    Assert.AreEqual(8.0, result.Stats["RingOfhealing"].Units[1].Amount);
    Assert.AreEqual(DimensionType.Life, result.Stats["RingOfhealing"].Units[1].Dimension);
    Assert.AreEqual(TimespanType.Minute, result.Stats["RingOfhealing"].Units[1].Timespan);
}

Verifying the Creature has been created correctly involves:

  • Checking that expected attributes have been loaded
  • Checking that attributes have the correct Units of Measure
  • Providing the user with appropriate error messages

 

Summary

This post has shown how to very easily write a simple DSL (less than 500 lines of code in total) that can be used to populate a relatively complex object. 

There are problems with the approach I’ve taken:

  • The Lexical Analyser was written by hand – There are some great libraries and frameworks that can do the heavy lifting for us on this one
  • Logic for populating the Creature was intermingled with logic for verifying the grammar – An Abstract Syntax Tree and the Visitor pattern is the answer for decoupling those two domains
  • Currently very poor error messages for badly formed user code

 

Source code

BattleLang.SimpleImplementation.7z (91.06 kb)

Tags:

BattleLang – A Domain Specific Language in .NET – Part II

by Call me dave... 20. December 2009 00:24

At Puzzle Guzzler, a small games software company, the development team are starting design work on their new game “Dragons of Kin”.  They are sitting around a table covered with toy dragons, dwarfs and concept drawings. 

The group consists of:

  • Brett the writer – He will be creating the overriding theme for the game, the quests, dialog and boss character personalities
  • Jasmine the environment and level lead – She owns the look of the game and the placement of monsters and items
  • Jen the Animation lead – She owns all CG assets in the game including modelling, lighting and animation
  • Douglas the Engine lead – The programmer geek

 

Brett Just to recap Kin is telling the story of a society falling apart.  Kin was vibrant farming country that stretched from fishing villages in the east, to mines to the north.  There was no King instead each small village was run by a council of elders.  Basically very idyllic with elements of Greek culture but unable to handle a big crisis or invasion. 
Jasmine So no massive cities…  Lots of little towns surrounded by farms fairly clear roads between each area.  The forests will be where all the creatures are then.
Brett Yah that’s right…
Thirty years ago the “Scrolls of Elioch” were discovered and taken to the Mage Guild.  They contained new spells for weather control, a minor fireball and the ability to calm animals.  Its the last one that has caused the trouble.  Relatively quickly the master mages discovered that its a small leap from calming to control.
Now many of the towns folk are slaves to the strongest mage in the area. They use them for their own amusement and live like Gods.  We will get to delve into some pretty dark human vices.  Some will have harems, others will feed off the population to “live forever”.  We will also have a few towns where the local Mage is good but is in constant fear that another stronger Mage will “steal his town”.  So they need to either constantly make potions to give their community immunity or put a minor control spell on everyone.
Jasmine And our hero is?
Brett

Christoph is a member of “Dragons” a resistance movement.  French resistance with fire balls instead of bombs. They go into each town, assassinating the weaker mages, putting potions into the water supply to disrupt the magical control of the towns etc.  The Dragons maybe heroes but since all the militia and armies are controlled by the mages they are public enemy number one.  I’m still working on the back story but his family were refugees fleeing their village. He became separated from the rest of his family and is now trying to find them. 

He has natural immunity to all magic and can’t be controlled but makes his own magical abilities pretty poor.  I think its important that by the end of the game he isn’t walking around with his own slave army.  Kinda defeats the purpose of him being a hero…

Douglas I’m really excited about this game its really going to kick ass.  But we really have to make sure that the coders don’t become a bottleneck like last time.
I want to start working on the AI for fighting.  Do we have an idea yet on what character stats we are going to use?  At least an outline so that I can start creating some of the core classes?
Jen Yah I would like to know as well so that my team can look at mocking up the character setup screens.
Jasmine Steady on.  We aren’t even close to that yet.  Isn’t there a way you can start on the engine without knowing all the details.  It sounds like you want to lock in the design but I think we should delay it as late as possible at least until we have created a completed dungeon and have play tested it for a couple of weeks.
Douglas Umm I’m not sure.  I suppose but I still need a starting point.
Brett How about…  Let me see…
Ok Christoph is with three other members of the resistance.  The town mage is very weak and only just hangs onto power.  But his brother who is now running the town militia has his palace completely locked down.  So the normal dash and stab is out.  The Dragon cleric sends Christoph out of town to find some ingredients for the immunity potion.  Battle, blah, blah hunt/gather blah, blah.   
When he returns to the town there are gallows setup and the Dragon’s have been found guilty of treason.  They will be killed in 2 hours.  Camera zooms in and Christoph’s hands start glowing a large tattoo of a Dragon is seen pulsing on his forearm.  The cleric mouth is moving in the distance but he can hear every word.  “There is a spring above the town go quickly pour the elixir into it.  It runs below the square it might just be enough to save us.”
Later our hero stands looking down on the spring.  There is a large crocodiles chained to an enormous statue. Magical energy vibrates across it.  Of course! This is how the mage controls the town.  Destroy the statue.  Use the elixir and the town will be free.
Douglas Brett you really are full of (*^(*&^
Brett Thanks…  Lets make this interesting. 
There are 10 baby crocs each dealing health damage.  The big one has a poisonous bite.  It drains health away each second after you have been bitten.  By being close to the statue  Christoph is being confounded so he cant move as fast.  He also has a ring on that is slowly healing him ever few seconds.
Douglas Ok so we have a number of effects that are time dependent.  We have effects that are dependent on the distance between objects and of course we have the run of the mill hit points and magic points.
Jen Funny it sounds a lot like a Mel script in Maya.  Some stuff can be done on the timeline and some can be done through triggers.
Douglas Of course, of course that’s all easy to do in Mel as the language is designed around animating.  It knows a lot about polygons, timelines etc.  Maybe we should create a language for “Dragons of Kin”.  At the start it will be very simple and generic just to get us going.  But it will know about spells and damage and weapons. 
Wow that could be great.  If Brett and Jasmine write the story using the language my team can create an Engine that will “play the game”.  Awesome…  And the best bit, my engine and the language and decoupled.  When we start optimising or refactoring it wont break the language as they are completely separate. 
Bring it on…
Jasmine Douglas I don’t want to rain on your parade but I’m not a programmer and sometimes I wonder if Brett can even type.
Douglas Don’t worry about that.  It will be designed for you guys from scratch.  It should be almost identical to how you create the levels in Word now.  But instead of my team having to translate the design into code the document will be the code.

 

BattleLang first draft…

The next day Douglas and Jasmine start on designing the language

Douglas Lets start with the crocodiles setup

  class Crocodile {
    int magicPoints;
    int healthPoints;
    float healthHealingSpeed;
    float magicHealingSpeed;

    Crocodile(…)
  }

Ok so we have this class and stats…
Jasmine Sorry, I thought you said the language would be text like.  Kinda looks like normal code to me.  Why are there int and floats in there.  How do I set the amounts?  What is a class how do I do different types for crocodiles for instance like the boss crocodile?
Douglas Dam your right.  Ok lets start again.  What you need to be able to do is setup the values for the different stats directly in here…  Maybe something closer to Pascal and I’ll kill the semicolon.

  Creature Crocodile {
    Life := 40
    Magic := 50
    LifeHealingSpeed   := 5
    MagicHealingSpeed   := 5
  }
Jasmine That makes more sense.  How fast is the healing speed.  Is it per minute per second.
Douglas Right, maybe we should be using Ada’s and F# Units of Measure. 
Sorry, in a normal programming language everything is a number.  The problem is that it means you can add values that aren’t properly related.  So if you add 3 oranges and 2 apples, instead of getting 5 fruit you get either 5 oranges or 5 apples.  As far as the computer is concerned its just two numbers.  The knowledge about what the number represents in a problem for the programmer.  Units of Measure allows you to stamp each numeric value with the actual item type it represents.  Most examples use gravity, speed, velocity, money that kinda thing.
So…
  Creature Crocodile {
    Life := 40 LP
    Magic := 50 MP
    LifeHealingSpeed   := 1 LP/sec
    MagicHealingSpeed   := 10 MP/min
  }
Jasmine Cool so does that mean we can represent damage this way.
  LizardPoison  := 15 LP + 3 LP/sec
Douglas Wow yes you could.  That is really compact.  Lets extend this to spells
  FireBall :
    Inflicts:= 20 LP
    Costs:= 5 MP
Jasmine I see so the firewall has an amount of damage that inflicts but to use the spell it has a cost of 5.  I suppose all that is really missing is that every crocodile shouldn’t have just 50 LP but it should random from a range of values.
Douglas Ok lets do the Crocodile properly then
  Creature Crocodile {
    Life := random_select [30..40] LP
    Magic := 15 MP
    LifeHealingSpeed   := 3 LP/sec
    MagicHealingSpeed   := 1 MP/min
    Weapons
    {
      Bite:
        Inflicts:= random_select [5..10] LP
      PoisonBite:
        Inflicts:= random_select [5..10] LP + 3 LP/sec
        Costs:= 5 MP
    }
  }

This a good start.  Eventually we will need to extend it to contain all the animation and sounds effects that Jen needs and currently there is no concept of the distance weapons.  Before we go any further I would like to spend a couple of days writing a parser that can load the language into a form an engine can use.

Tags:

BattleLang – A Domain Specific Language in .NET

by Call me dave... 19. December 2009 06:56

Over the next couple of blog posts I will be creating a simple DSL for a Role Playing Game (RPG).   DSLs are often used in the games industry to combat the huge amounts of complex data within AAA titles.  A RPG will often have thousands of different characters spread throughout the environment each having different:

  • Animation cycles and sound effects
  • Characteristics such as hit points and strength
  • Armour and weapons

All of this information eventually gets fed into a C++ engine that actually runs the game.  This means either all of the members of the team need to be professional programmers or the game’s data needs to be managed and manipulated elsewhere.  While a CSV or XML file can provide some assistance eventually the designer will need to be input state based behaviour:

If HiPoints > 20

  Attack closest player

Else

  Run away

This type of logic is extremely difficult to embed into a CSV file.  However it is relatively simple to create a DSL allows the Game Designer to define each creature’s characteristics and the effects of items and spells.

DSL Background - Ubiquitous Language

A core tenet of Domain Driven Design is the Ubiquitous Language where business users and developers, use a shared language and terminology to define each concept, within the domain.  Instead of leaving this information in a document they are embedded into the domain objects within the system that is being built.  By both groups using the same terminology the opportunities for miscommunication are greatly reduced.  Further as the business and developers come to understand and respect the other group’s expertise the language becomes richer and the definition’s gain greater clarity resulting in the the domain objects being updated to replicate the new richer model.

DDD and Acceptance testing are a perfect fit.  By having tests written using terminology from the Ubiquitous Language allows the business to create test cases early in the development process.  These tests can form the basis of the project’s detailed requirements and allows the development team to build the meaty parts of the application extremely quickly and to a very high quality.

Business writing the software

The natural question to ask is “If the business can write the tests can they also write the software”?  The answer is a resounding NO.  Software development is very complex.  Modern generic programming languages are designed to execute an infinite number of different programs.  They do this by having a type system that maps to the architecture of the underlying computer.  We use ints, floats and strings in our programs to represent concepts such as age, weight and names.  Programmers are easily able to do the mental jump between built in types and the abstract concepts that are being simulated by the program and are described in the Ubiquitous Language.  Further developers are able to look at control structures such as for loops and instantly recognise that some action is occurring on each element within an array.  These skills are not universal and without them it is very difficult to understand any non-trivial piece of software.

The problem space that the DSL solves is making a programming language that allows a user to explain a business activity or business data using concepts from the Ubiquitous Language directly.  So instead of having to understand an entire application with five hundred files, tens of thousands of lines of code and concepts such as component layering and patterns.  They can either write or approve a small code fragment that looks surprising close to the Acceptance tests that they may are already actively creating.

Examples of useful DSLs:

DSL Requirements

If we treat our DSL as a tool to allow a business analyst or fairly technical business user to interact with our application we can quickly come up with some high level requirements:

  • The language should use business or problem space terminology – Its pointless creating a DSL that isn’t intermit with the domain
  • The language should include the smallest number of control structures as possible – The more complex the language the more difficult it is to learn and maintain.  If statements and assignment should be adequate for the majority of problems.
  • The DSL user code should be treated as any other development artefact
    • Should be in source control
    • Build server should validate any user generated code on check in – Very important since DSL syntax will change over time hence its vital to know when a script is no longer valid
  • DSL should be very focussed – There is no reason not to have a couple of complementary DSLs on a single project each solving a single problem is a clear and simple manner

Tags: