Movimentum - Walking over the canyon

Did you see this guy walking over the canyon in China two days ago? I mean - he must be totally crazy: No safety net, no way to succeed except ... to succeed.

Like Movimentum. If the constraint solver does not work, everything up to now is moot. Well - it doesn't kill me, but only the project (which is a small hobby project, to be precise). Still, walking up to this point was like the advance to the rim of the canyon.

Now, we'll start to cross the canyon.

We'll see whether we'll cross it alive.

Movimentum - Better rigid body constraints; and ToString()

Rigid body constraints rewritten

Ok - I botched it. Not really that obviously, but still, the code for the rigid body constraints was not thought out enough. The issue there is the lifetime of things: When do things start to appear in the animation?

My implicit assumption was that the first time a thing (i.e., a thing's anchor) is mentioned, it will be rendered into the animation. But then, I cannot hook all rigid body constraints to the first step - because then, all things will try to appear in the first step. However, at this point the constraints explicitly written in the script are still missing! - so the constraint solver will not be able to compute a location for the things, and hence it will complain.

I therefore rewrote the rigid body constraint code so that it now creates these constraints at the first step where a thing's anchor appears on the left side of a constraint. In the course of this, I also added code to create the 2d constraints (and I found out that the MovimentumParser.ConstAdd() method did not behave well with 2d anchors - it needed another if. The code looks now a little "over-if-ed", but for this helper method, so be it.)

Altogether, the code for these constraints is about 110 lines.

 

Debugging Output = ToString()

Moreover, I now added (hopefully) sensible code for ToString() of constraints and expressions so that they are more or less easily readable in the debugger. I will not explain that code too deeply - it is only for debugging -, but only give a short overview. If you are interested, please look into the github repository.

The main parts of the ToString() code are:

• Each expression gets a ToString method with an additional parameter for controlling the parentheses. The code of this methods is one of the following if the expresion is a binary or a unary expression:

    protected internal override string ToString(AbstractOperator parentOp) {
        return parentOp.Wrap(_lhs, _operator, _rhs);
    }

    protected internal override string ToString(AbstractOperator parentOp) {
        return parentOp.Wrap(_operator, _inner);
    }

• This code is used in a ToString() method for all expressions: I wasted the precious resource "base class" for this feature - both ScalarExpr and VectorExpr now derive from a class Expr which has the ToString() method in it:

public abstract class Expr {
    public override string ToString() {
        return ToString(AbstractOperator.IGNORE_OP);
    }

    protected internal abstract string ToString(AbstractOperator parentOp);
}

• Finally, the following code inside AbstractOperator handles the parenthesizing by a mutually recursive call to the ToString(AbstractOperator parentOp) method from the first item above:

        public string Wrap(Expr lhs, AbstractOperator op, Expr rhs) {
            string s = lhs.ToString(op) + op + rhs.ToString(op);
            return op.Precedence < Precedence ? "(" + s + ")" : s;
        }

        public string Wrap(AbstractOperator op, Expr e) {
            string s = e.ToString(op) + op;
            return op.Precedence < Precedence ? "(" + s + ")" : s;
        }

So that the precedence check and output works, operators need to be defined with the correct precedence and output string. Here is an example for the binay scalar operators - the precedences are copied over from the grammar (if the operator occurs in simpleexpr2, precedence is 2; if it occurs in simpleexpr3, then 3, etc.):

    public class BinaryScalarOperator : AbstractOperator {
        private BinaryScalarOperator(int precedence, string asString) : base(precedence, asString) { }
        public static BinaryScalarOperator PLUS = new BinaryScalarOperator(1, " + ");
        public static BinaryScalarOperator MINUS = new BinaryScalarOperator(1, " - ");
        public static BinaryScalarOperator TIMES = new BinaryScalarOperator(2, " * ");
        public static BinaryScalarOperator DIVIDE = new BinaryScalarOperator(2, " / ");
    }

For the moment, this works as expected. And as it is only debugging output, I confess that I skipped the unit tests for this.

Movimentum - Implementation of rigid body constraints, constraint lifetime, and 3-d troubles

Implementation of rigid body constraints

I have now implemented the creation of the rigid body constraints. This required a change to the grammar and the model: I could not express the squares succinctly, so I added a "squared" (and a "cubed"; and a "square root") expression. Here is the code for the new constraints - it's longer than I would have expected:

    public partial class Script {
        public void AddRigidBodyConstraints() {
            if (Steps.Any()) {
                foreach (var th in _things) {
                    string[] anchorNames = th.Anchors.Keys.ToArray();
                    for (int i = 0; i < anchorNames.Length; i++) {
                        for (int j = i + 1; j < anchorNames.Length; j++) {
                            string anchorName1 = anchorNames[i];
                            string anchorName2 = anchorNames[j];
                            AddRigidBodyConstraint(th.Name,
                                anchorName1, anchorName2,
                                th.Anchors[anchorName1], th.Anchors[anchorName2]);
                        }
                    }
                }
            }
        }

        private void AddRigidBodyConstraint(string thing,
                string anchorName1, string anchorName2,
                ConstVector cv1, ConstVector cv2) {
            string auxVar = thing + "_" + anchorName1 + "_" + anchorName2;
            ScalarEqualityConstraint constraint1, constraint2;
            {
                var anchor1 = new Anchor(thing, anchorName1);
                var anchor2 = new Anchor(thing, anchorName2);
                UnaryScalarExpr xSquared = SquareCoord(UnaryScalarVectorOperator.X, anchor1, anchor2);
                UnaryScalarExpr ySquared = SquareCoord(UnaryScalarVectorOperator.Y, anchor1, anchor2);
                UnaryScalarExpr zSquared = SquareCoord(UnaryScalarVectorOperator.Z, anchor1, anchor2);
                BinaryScalarExpr squaredSum =
                    new BinaryScalarExpr(xSquared,
                        BinaryScalarOperator.PLUS,
                        new BinaryScalarExpr(ySquared,
                            BinaryScalarOperator.PLUS,
                            zSquared
                        )
                    );
                constraint1 = new ScalarEqualityConstraint(auxVar, squaredSum);
            }
            {
                double squaredDistance = Square(cv1.X - cv2.X)
                                       + Square(cv1.Y - cv2.Y)
                                       + Square(cv1.Z - cv2.Z);
                constraint2 = new ScalarEqualityConstraint(auxVar, new Constant(squaredDistance));
            }
            // AddRigidBodyConstraint is only called when Steps.Any() is true - therefore Steps.First() is safe.
            Steps.First().AddConstraint(constraint1);
            Steps.First().AddConstraint(constraint2);
        }

        private double Square(double v) {
            return v * v;
        }

        private static UnaryScalarExpr SquareCoord(UnaryScalarVectorOperator coordOp,
                                                   Anchor anchor1, Anchor anchor2) {
            return new UnaryScalarExpr(UnaryScalarOperator.SQUARED,
                new BinaryScalarExpr(
                    new UnaryScalarVectorExpr(anchor1, coordOp),
                    BinaryScalarOperator.MINUS,
                    new UnaryScalarVectorExpr(anchor2, coordOp))
                );
        }
    }

But - don't I add too many operators ad hoc and just so, like the SQUARED above?

Maybe I should stress the following at this point: At some point, all these mathematical operators will go into that magic constraint solver, and then "all hell will break loose," i.e., I will find out that constraint solving is hard, hard, hard. Therefore, I'll then revise the grammar by excluding operators - so all expression types now in the grammar are more a sort of suggestions. We will see which of them remain - and which are definitely necessary - in the end.

Still, I could not formulate the rigid body constraints directly as in the previous posting. The reason is that the left side of a constraint can only be a variable (which is also used as a key for the lifetime management of the constraint). So I had to formulate each constraints as a constraint pair like that:

   auxVar = (P.x - Q.x)² + (P.z - Q.z)² + (P.z - Q.z)²
   auxVar = constant
  
where the constant is the square of the length. This creates two more issues:

Constraint lifetime

The first issue is that we can have more than one constraint with the same key at the same time (here, "auxVar" is the key of two constraints which should hold simultaneously). Thus, the lifetime management of contraints will probably have to be: If, in a step, new constraints (plural!) are defined for some key, all current constraints with that key are removed; and then the new constraints are enacted.

3-d swiveling

The other issue is that the z coordinate I have added so happily in my 3d posting creates a big headache: Things can now "swing into the third dimension" - and there is no constraint preventing them to do this! What to do? Again, there are at least the following possibilities:

• Explicitly adding constraints to fix all anchor z-s at zero.
• Some implicit mechanism. As I allow a two-dimensional vector notation [a,b], the following might help: If an anchor is created with only two coordinates specified, a constraint fixing the z coordinate at 0 is created automatically.

I'll implement the code for the latter.

Still, an item with only two anchors could swivel around the axis defined by them. It seems that placing the images in 3-d will require additional rules - but right now, I separate the constraint solving from the final image creation: The former should create unique solutions also in 3-d, the latter is right now only defined for 2-d machines. This conforms to the item

• "2D only. Maybe we have 3D ideas later - not now (however, I think I'll give them vectors 3 coordinates from the start)."

in my item list.

Movimentum is on github!

My colleague Thomas (thoemmi) has helped me to put Movimentum on github! It is now available at https://github.com/hmmueller/Movimentum. The support for builds is still rudimentary - e.g., one must run ANTLR manually by calling a Windows BAT file runantlr.bat. I'll leave it at that for the moment ... my focus is on design and continuing the implementation.

Thanks, thoemmi!

Movimentum - Rigid body constraints

We are quickly closing in on the central algorithm of Movimentum: The constraint solver. But before I try to fathom the depths of that topic, there is still something missing: Constraints that capture the rigidity of our things. To see why we need them explicitly, let's write a script for a simple horizontal bar:

    .config(1);

    Bar : 'bar.gif' P = [10,10] Q = [50,10];

    // We place the bar somewhere

    @0.0  Bar.P = [10,10]; Bar.Q = Bar.P + [_,0];

This step can be rewritten into the following scalar equations:

   barPx = 10; barPy = 10; barQx = barPx + d; barQy = barPy;

barQy can readily be computed, but not barQx! Some constraint is obviously missing. This also follows from the fact that we have four equations, but five variables: The four bar.. variables and the "slack variable" d.

Let's now rotate the bar by 45°:

    @1.0 Bar.Q = [e,e];

According to the "key convention", the constraint Bar.P = [10,10] remains in force, but the Bar.Q constraint from @0.0 is replaced. Therefore, we end up with the following four equations:

   barPx = 10; barPy = 10; barQx = e; barQy = e;

Again, we cannot compute some values - in this case, both for barQx and barQy. Again, we have five variables - the bar..s, and e -, but only four equations.

Let's now add a "length constraint":

   // implicit length constraint

   (Bar.P.x - Bar.Q.x)² + (Bar.P.y - Bar.Q.y)² = 40²

Using this constraint, we get a fifth equation. For the initial placement in step @0.0, we can now solve the equations:
 
   barPx = 10; barPy = 10; barQx = barPx + d; barQy = barPy; 
   (barPx - barQx)² + (barPy - barQy)² = 40²

We substitute barPx and barPy (as they are equal to constants) and barQy and get:

    barQx = 10 + d; (10 - barQx)² + (10 - 10)² = 40²

Dropping  (10-10)² = 0 and substituting barQx gives us

    (10 - 10 - d)² = 40²

and we arrive at the two solutions d = +40 and d = -40. Backsubstitution will give us the variables for the initial placement of the bar.

But ... there are two possible solutions! What do we do about this? Possibilities:

• We require an additional explicit constraint, e.g. Bar.Q.x > Bar.P.x.
• We assume additional implicit constraints - my suggestion: If for two anchors A and B of a thing T, we have A.x > B.x, then we also require T.A.x > T.B.x for the solution.

However, I'm afraid that implicit inequality constraints will either

• hold too short (i.e., they are also necessary for some movements); or 
• too long (i.e., they will prevent a single solution at some time); or
• are not sufficient (e.g., when two solution have equal x, or when multiple quadratic equations yield four or more solutions).

So I will, for the moment, require explicit inequality constraints for unique solutions.

But also for explicit inequality constraints, the lifetime seems to be tricky - the three problems above might also occur with them. So we need a lifetime regime for inequality constraints!

Here is my suggestion: Inequality constraints are marked with the variable on the left side and the inequality operator (maybe <= is unified with <, and >= with >). Using the following "vacuous" constraint, an inequality constraint can be "killed:"

    x > _

(Another possibility would be to have infinite lifetime for inequality constraints, but invoke them only if there are two or more solutions ... but I am afraid that then, it gets even harder to get unique solutions).


Let's also try the solution for the @1.0 step: We have the five equations

   barPx = 10; barPy = 10; barQx = e; barQy = e; 
   (barPx - barQx)² + (barPy - barQy)² = 40²

We substitute all four bar.. variables and get:

   (10 - e)² + (10 - e)² = 40²

This can be solved and yields 10 - e ≈ ±28.28, or e ≈ +38.28 or e ≈ -18.28. From this, we can find the values of the bar.. variables. Again, > constraints are needed to select a unique solution.

The rigid body (length) constraints must of course remain in force for the full script. Therefore, I give them a key that can never be given to another constraint - some internal Guid or the like.

Movimentum - Reminder

Before I forget it (I wouldn't, but it should be in the blog): I'll also need non-rigid things. Springs are certainly important in mechanical machinery, but there are others - look at www.animatedengines.com for ideas.

Movimentum - 3-d or not 3-d

Before I think a little bit about the 3d topic, I confess I have played with the grammar somewhat. I want to introduce vector variables and also use the special variable _ for vectors - but when I added this to vectorexpr5, the grammar got ambiguous. So I simplified (or "simplified"?) the vector constraints in the same way as the scalar ones:

    constraint returns [Constraint result]
      : a=anchor // <----- was v1=vectorexpr up to now!
        '='
        v=vectorexpr
        ';'              { result = ...; }
      | i=IDENT
        '='
        s=scalarexpr
        ';'              { result = ...; }
      ...

This disallows "very implicit constraints" - I'll see when I need them. On the other hand, it introduces a clear key also for each vector constraint, which is necessary for the Idea introduced at the end of this posting.

But now onwards to the 3d question. In the "what I want list" over there, there was also an item

• 2D only. Maybe we have 3D ideas later - not now (however, I think I'll give them vectors 3 coordinates from the start).

I have dodged this up to now. But among my ideas on what I want to animate, there are at least a few mechanisms that are three-dimensional:

• The valve gear for the center cylinder of UP's 4-12-2 engines, 
• or the lever train from the route lever to the locking bar in a German "Einheitsstellwerk".

How would one explain these? My idea would be about as follows: Start with 2d explanations - e.g. the standard Walschaerts gear -, but then "zoom out" to present a view on the 3d mechanism. But .... ahhhh ... that means that not only the mechanism has to be 3d, but also the camera's movement!

And this leads to a solution to a problem that has sat in the back of my mind for all that time: A useful animated explanation at times also needs to zoom into some part of the moving mechanism - and I could not see how I could integrate this zooming with the moving mechanism in the script: How can I "scale part of the mechanism"?? But of course: This scaling is not part of the moving mechanism, but of the camera's moving around - which is a completely separate script, probably even with special operations like "zoom center part (of 'diameter' 15 degrees)" or the like, which do not make sense for the mechanism per se. I'll not delve into this "camera script (language)" for the moment, but it will have to be done ...

Another 3d question: Where do the objects ("things") come from? For 2d things, there are standard formats even I know of (GIF with transparency, for example). But are there standard 3d formats which can readily be loaded and rendered by .Net? I do not know, and for the moment, I'll ignore this topic (I'll ask Dennis when I see him next time :) ). The examples above, at least, can be readily explained with "paper-thick 2d objects," which are projected onto a camera moving in 3d.

And as I do now have a somewhat clear understanding of the very limited 3d capabilities Movimentum should have, I'll upgrade my vectors to 3 coordinates!

Here are the changes to ConstVector - for enhanced usability, I continue to allow two-coordinate vectors:

    constvector returns [ConstVector result]
      :       {{ double x = double.NaN, y = double.NaN, z = 0; }}
        '['
        ('-' c=constscalar  { x = -c; }
        |    c=constscalar  { x = c; }
        )
        ','
        ('-' c=constscalar  { y = -c; }
        |    c=constscalar  { y = c; }
        )
        ( ','
          ('-' c=constscalar  { z = -c; }
          |    c=constscalar  { z = c; }
          )
        )? 
        ']'                 { result = new ConstVector(x,y,z); }
      ;

    constscalar returns [double result]
      : n=number            { result = n; }
      | c=constvector      
        ( X                 { result = c.X; }
        | Y                 { result = c.Y; }
        | Z                 { result = c.Z; }
        )
      ;

with a simple lexer addition:

    Z :  '.z';

And here is the change to Vector:

    vector returns [Vector result]
      : '['
        s1=scalarexpr
        ','
        s2=scalarexpr
        ( ','
          s3=scalarexpr
        )?
        ']' { result = new Vector(s1, s2, s3 ?? new Constant(0)); }
      ;

Both changes, of course, require corresponding changes in the constructors as well as the Equals() and GetHashcode() methods of the mentioned model classes. After I implemented these changes and upgraded a few test cases (I do not allow default parameters - the model is not an API!), all the tests ran without a hitch!

Movimentum - Unit testing the parser

The parser (and model builder) is not that complicated - but there is a minimal number of tests that we should provide. First of all, each path in the actions should be tested once - a copy paste error could e.g. produce a wrong operator, or drop a part of an expression. Moreover, a few features warrant special testing. They are:

1. The hard-wired anchor definition computations.
2. Image loading.
3. The time computation for the steps (the two variants of the @ feature).
4. Producing different variables when using the underscore _.
5. Correct disambiguation in the rule with backtrack=true.

This takes some work. However, when the grammar is extended (and it will be extended - there are already a few features I'd like to have), these unit tests are necessary as a safety net.

A first test for numbers might look like this:

    [Test]
    public void Test_number() {
        Assert.AreEqual(1.0, GetParser("1").number(), 1e-10);
        Assert.AreEqual(1.0, GetParser("1.").number(), 1e-10);
        Assert.AreEqual(10.0, GetParser("1.E1").number(), 1e-10);
        Assert.AreEqual(0.01, GetParser("1.E-2").number(), 1e-10);
        Assert.AreEqual(10.1, GetParser("1.01E1").number(), 1e-10);
        Assert.AreEqual(0.010001, GetParser("1.0001E-2").number(), 1e-10);
    }

Then, a test might just parse all sorts of scalar expressions:

        [Test]
        public void TestJustParse_scalarexpr() {
            GetParser("a+b").scalarexpr();
            GetParser("a+b*c").scalarexpr();

            ...
        }

However, this test will not work - it throws an exception about an "unexpected EOF". Why? Well, the grammar knows that scalar expressions can never be at the very end of an input file. So, it treats an EOF right after a scalar expression as an error. We can repair this by providing enough following symbols for the LL parser so that it remains happy. In our case, a semicolon suffices, as each constraint - which might have a scalar expressions at the end - is terminated by that symbol. So, the following actually tests parsing of scalar expressions:

        [Test]
        public void TestJustParse_scalarexpr() {
            GetParser("a+b ;").scalarexpr();
            GetParser("a+b*c ;").scalarexpr();
            GetParser("(a-b)*c ;").scalarexpr();
            GetParser("a+b*-c*d ;").scalarexpr();
            GetParser("(a-b*c)/-(-d) ;").scalarexpr();
            GetParser(".i(a+2*b) ;").scalarexpr();
            GetParser("(3+.d(-a-b*2))-d ;").scalarexpr();
            GetParser("-.a([0,1],[1,1]) ;").scalarexpr();
            GetParser("_+_ ;").scalarexpr();
            GetParser("3*.t ;").scalarexpr();
            GetParser("(.iv-.t)/2 ;").scalarexpr();
        }

Next, we have to check that the correct model is returned - and here we get a problem: How do we compare two models? There are two possibilities: We can either compare each property, or we implement an Equals method in each class. As we might want to compare model parts also later (e.g. to find out that a constraint is superfluous; or for constant folding), I opt for the Equals methods. So each expression (at least) now gets three methods - here is an example for class BinaryScalarExpr:

        public bool Equals(BinaryScalarExpr obj) {
            return Equals((object)obj);
        }
        public override bool Equals(object obj) {
            BinaryScalarExpr o = obj as BinaryScalarExpr;
            return o != null
                && o._lhs.Equals(_lhs)
                && o._operator.Equals(_operator)
                && o._rhs.Equals(_rhs);
        }
        public override int GetHashCode() {
            return _lhs.GetHashCode() + (int)_operator + _rhs.GetHashCode();
        }

The tests I write look like this. They are a sort of mixture between single-purpose tests (where you would put only exactly one operator or the like into an expression) and integrating tests - and are quite boring to write ...

    ScalarExpr x = CreateParserForSyntacticTests("a+b*-c/d ;").scalarexpr();
    Assert.AreEqual(
        new BinaryScalarExpr(new ScalarVariable("a"),
            BinaryScalarOperator.PLUS,
            new BinaryScalarExpr(
                new BinaryScalarExpr(new ScalarVariable("b"),
                    BinaryScalarOperator.TIMES,
                    new UnaryScalarExpr(UnaryScalarOperator.MINUS,
                        new ScalarVariable("c")
                    )
                ),
                BinaryScalarOperator.DIVIDE,
                new ScalarVariable("d")
            )
        ), x);

I wrote about 20 of them up to now - that should suffice for my enterprise. If I find errors, I'll add more. Tests for the five specific items mentioned at the beginning are still missing, I confess.

Remark: During testing I found -  I think - some quite serious restrictions in my grammar. For example, I cannot write 2*[0,1] for a multiplication of a scalar and a vector, much less a*[b,c]. I'll leave it at that right now:

• Either one can work around the restrictions - this is an animation program, not a generic mathematical equation solver;
• or I introduce the {...} braces for vector expressions (if that helps);
• or I find some other clever way ...

UPDATE: I have now written some more test cases, especially for 4 of the 5 special issues mentioned at the beginning. Still missing are tests for correct (and failing) image loading - I'll push them to later times.

Movimentum - Building the model cont'd

After the things and their anchors, we build the steps. For the time tracking, we keep a global variable in the parser that is set or incremented, depending on the format of the @ directive:

    time
      : '@' n=number         { _currentTime = n; }
      | '@' '+' n=number     { _currentTime += n; }
      ;
   
I therefore changed the creation of a Step in the script rule to

          ...

          )*        { sts.Add(new Step(_currentTime, cs)); }

          ...

The constraint rule creates on of the three constraint types:

    constraint returns [Constraint result]
      : v1=vectorexpr
        '='
        v2=vectorexpr
        ';'     { result = new VectorEqualityConstraint(v1, v2); }
      | i=IDENT
        '='
        v=scalarexpr
        ';'     { result = new ScalarEqualityConstraint(
                                   $i.Text, v); }
      | i=IDENT {{ ScalarInequalityOperator op = 0; }}
        ( '<'   { op = ScalarInequalityOperator.LE; }
        | '>'   { op = ScalarInequalityOperator.GE; }
        | '<='  { op = ScalarInequalityOperator.LT; }
        | '>='  { op = ScalarInequalityOperator.GT; }
        )
        s=scalarexpr
        ';'     { result = new ScalarInequalityConstraint(
                                   $i.Text, op, s); }
      ;
In a similar way, we build vector expression. Here is the top rule for a vector expression:

    vectorexpr returns [VectorExpr result]
      : v=vectorexpr2        { result = v; }
        (                    {{ BinaryVectorOperator op = 0; }}
          ( '+'              {{ op = BinaryVectorOperator.PLUS; }}
          | '-'              {{ op = BinaryVectorOperator.MINUS; }}
          )
          v=vectorexpr2      { result = new BinaryVectorExpr(
                                                 result, op, v); }
        )*
      ;

All the rest is similar and, overall, simple. The only change I made is to Anchor: Originally, I wanted to pass in a ready-made Thing. But this would require to move the Thing collection somewhere where we can access it - I defer this to some later semantic phase of the interpreter.

The complete grammar file with actions is here.

Movimentum - Building the model

Now that we have model classes and a grammar, we must direct our parser to create the model while parsing. In ANTLR, one writes the corresponding statements into the grammar. Here is the original rule for script, below the "code-enhanced" rule:

    script
      : config
        thingdefinition*
        ( time
          constraint*
        )*
        EOF
      ;

    script returns [Script script]
      :                      {{ var ths = new List();
                                var sts = new List();
                             }}
        cfg=config
        ( th=thingdefinition { ths.Add(th); }
        )*
        ( t=time             {{ var cs = new List(); }}
          ( c=constraint     { cs.Add(c); }
          )*                 { sts.Add(new Step(t, cs)); }
        )*                   { script = new Script(cfg,ths,sts); }
        EOF
      ;

Some bits and pieces:

• Each call to a subrule now assigns its result to a local variable (which ANTLR declares for us).
• These variables can then be used as variables in the actions.
• I prefer the "constructor style" of object creation: First, create all sub-objects, at last call the result constructor (new Script(...) in this case). The other possibility is to create the object at the beginning and then provide construction methods (e.g. AddStep(...) etc.). But the second method requires modification methods on the objects, and as I said, I like to keep immutability as intact as possible.
• Actions are usually put by ANTLR inside if (!backtracking) { ... } guards. However, for some declarations, this leads to code that is not compilable. For these cases, ANTLR provides the {{...}} blocks - however, one must take care that these do not contain actions with side effects. As seen above, I use these blocks for the declarations and emtpy initializations of local collections. This will never do any harm (and for this rule, I even know that no backtracking will ever happen).

In the next production rule, we need the actual value of a number. Therefore, I replace NUMBER everywhere with a new rule number, which is defined as follows:

   number returns [double value]
     : NUMBER            { value = double.Parse($NUMBER.Text,
                                   CultureInfo.InvariantCulture); }
     ;

(This requires an additional "using" in the @parser::header section). With this, I can now complete the config rule:

    config returns [Config result]
      : CONFIG '('
              fptu=number  // frames per time unit
        ')'                  { result = new Config(fptu); }
        ';'
      ;

The rule for a thingdefinition works a little bit different from the rest, because it does that small computation for relative anchor definitions:

    thingdefinition returns [Thing result]
      : IDENT
        ':'
        s=source    {{ var defs = new Dictionary<string,
                                         ConstVector>();
                    }}
        (anchordefinition[defs]
        )+
        ';'         { result = new Thing($IDENT.Text, s, defs); }
      ;
  
    anchordefinition [Dictionary<string, ConstVector> defs]
      : n=IDENT
        '='    {{ ConstVector v = null; }}
        ( c=constvector 
               { v = c; }
        | i=IDENT '+' c=constvector 
               { v = ConstAdd($i.Line, defs, $i.Text, c, true); }
        | i=IDENT '-' c=constvector 
               { v = ConstAdd($i.Line, defs, $i.Text, c, false); }
        )      { defs[$n.Text] = v; }
      ;

ConstAdd is a helper function which we define in the non-generated partial class of MovimentumParser:

        private ConstVector ConstAdd(
                int lineNo,
                Dictionary<string, ConstVector> defs,
                string lhsName,
                ConstVector rhs,
                bool plus) {
            ConstVector lhs;
            if (!defs.TryGetValue(lhsName, out lhs)) {
                throw new Exception(string.Format(
                    "Line {0}: Anchor {1} not yet defined",
                    lineNo, lhsName));
            }
            return plus
                ? new ConstVector(lhs.X + rhs.X, lhs.Y + rhs.Y)
                : new ConstVector(lhs.X - rhs.X, lhs.Y - rhs.Y);
        }

The ConstVector itself is created by the rules constvector and constscalar:

    constvector returns [ConstVector result]
      :                      {{ double x = double.NaN, 
                                       y = double.NaN; }}
        '['
        ('-' c=constscalar   { x = -c; }
        |    c=constscalar   { x = c; }
        )
        ','
        ('-' c=constscalar   { y = -c; }
        |    c=constscalar   { y = c; }
        )
        ']'                  { result = new ConstVector(x,y); }
      ;

    constscalar returns [double result]
      : n=number             { result = n; }
      | c=constvector
        ( X                  { result = c.X; }
        | Y                  { result = c.Y; }
        )
      ;

We also need to read in an image. A straightfoward implementation would be:

    source returns [Image result]
      : FILENAME     { result = Image.FromFile($FILENAME.Text); }
      ;

However, when you try this (or think about it), it kills testability: Suddenly, we must really have all those image files at the correct place in the file system! So, we replace this with a call to a virtual method ImageFromFile in our Parser, and then use an overloaded (or mocked) version in the unit tests.

What about the constraints? Well, currently the rule for a constraint simply declares a result - ANTLR will initialize it with default(Constraint), which is null - and this is what we get right now for each constraint:

    constraint returns [Constraint result]
      : vectorexpr
        '='
        vectorexpr
        ';'
      | ...

      ;

I'll of course add more code here.

Here is the grammar file in its current state, here is the partial MovimentumParser class with the methods mentioned above, and here are a few of the current test cases.