A couple years ago, I wrote an article showing how to empower game designers with the ability to write simple formulas like PlayerLevel*100+100. These are much more useful than just constants and don’t require any of the complexity of a real programming language. Today we’ll bring it into the Burst-compatible world and also improve its ability to handle more complex formulas.

Problems

We left off with a formula evaluator that had these features:

  • Constants like 123.45. Values are double: 64-bit float.
  • Variables like health. Uppercase, lowercase, and underscores allowed.
  • Arithmetic operators: + - * / %

That was back in the Unity 2017.1 days. From today’s 2019.2 perspective, we now notice that we’re lacking the ability to evaluate expressions within Burst-compiled jobs. That’s because the code uses strings, exceptions, and classes like List<T> and HashMap<T>.

More fundamentally, formulas were executed from left to right in a simplistic way without any operator precedence at all. This meant that we could write a formula like this:

x*3+1

And it would be evaluated, as expected, like this:

(x*3)+1

But we couldn’t write a formula like this:

x+1*3

The reason is that it would be evaluated like this:

(x+1)*3

It also lacked support for parentheses, so we couldn’t write formulas like this:

(x+1)*(y-2)

There’s no way to even rearrange this formula so that it would work without parentheses.

We also couldn’t add any spaces to make the formula more clear, like this:

x*x + y*y + z*z

We’ll fix all of these issues today.

Burst Compatibility

First, let’s add Burst support. The key here is to recognize that there are two main operations: compiling and evaluating. Compiling requires the formula string and so it’ll never be supported in Burst. Evaluating, however, doesn’t need the formula string so it should be possible to execute in Burst.

To get the strings out of the Formula struct, we need to look at its only field:

private List<Node> nodes;

Node looks like this:

private struct Node
{
    public NodeType Type;
    public string Name;
    public double Value;
    public bool HasValue;
}

So we need to get rid of the List<Node> and get rid of the string Name field of Node in order to store a Formula in a Burst-compiled job.

Getting rid of List<T> is easy: just swap in NativeArray<T> and handle dynamically growing it manually like so:

// Double the length to avoid growing for every single new element
NativeArray<Node> newNodes = new NativeArray<Node>(nodes.Length * 2, allocator);
for (int i = 0; i < nodes.Length; ++i)
{
    newNodes[i] = nodes[i];
}
nodes.Dispose();
nodes = newNodes;

To get rid of the string, we can build an array of variable names during compilation and only store the index into that array. This means setting variable values changes a little:

// Old
formula.SetVariable("level", 10);
 
// New
formula.SetVariable(Array.IndexOf(compileResult.Variables, "level"), 10);

Next, we need to get rid of the exceptions. Instead, we’ll return a struct to tell the caller about the result of the compilation:

public struct CompileResult
{
    public bool Success;
    public Formula Formula;
    public string[] Variables;
}
Precedence and Parentheses

To support operator precedence and parentheses, we need to split compilation into two parts:

  1. Parse the source string into nodes
  2. Reorder the nodes into “postfix order” (a.k.a. Reverse Polish Notation)

The reason for the second step is because we want to be able to write in so-called “infix order” as math generally appears:

x + 1

Evaluating infix expressions is very difficult though, so we’ll reorder them so they’re into postfix order:

x 1 +

In this order, evaluation is simple! When we encounter a constant or variable, we push it onto a stack. When we encounter an operator, we pop two values off the stack, apply the operator to them, and push the result onto the stack. The output is whatever’s left on the stack.

So for the above example of x 1 + when x has the value 10:

Node Action Stack
x Evaluate x 10
Push 10 10
1 Push 1 10 1
+ Pop 1 10
Pop 10
Add 1 and 10
Push 11 11

The result is the 11 left on the stack.

To do the reordering, we employ the Shunting Yard Algorithm. It uses a queue and a stack which we can easily allocate with NativeArray<Node> using Allocator.Temp without fearing creating any garbage.

This algorithm support parentheses, so we can add them to our parsing step. We'll also add support for spaces, which we simply skip.

Usage

Now that we've made these changes, let's try out the system starting with a Burst-compiled job that evaluates formulas:

[BurstCompile]
struct FormulaJob : IJob
{
    public Formula Formula;
    public NativeArray<double> Result;
 
    public void Execute()
    {
        Result[0] = Formula.Evaluate();
    }
}

In order to feed in a Formula, let's compile one outside of the Burst job:

Formula.CompileResult result = Formula.Compile(
    "(NumTargetsHit*100) - (NumTargetsMissed*50)",
    Allocator.TempJob);
if (!result.Success)
{
    Debug.LogError("Compile error");
}

Then we set the variables' values:

Formula formula = result.Formula;
string[] variables = result.Variables;
 
formula.SetVariable(Array.IndexOf(variables, "NumTargetsHit"), 5);
formula.SetVariable(Array.IndexOf(variables, "NumTargetsMissed"), 1);

Now we can run the job:

var evalResults = new NativeArray<double>(1, Allocator.TempJob);
new FormulaJob { Formula = formula, Result = evalResults }.Run();
double evalResult = evalResults[0];
evalResults.Dispose();

We have the result back from the job, so let's print it:

Debug.Log("Result: " + evalResult);

We see the expected result: 450!

Source Code

Here's the full source code for the formula compiler and evaluator. It weighs at just 452 SLOC:

using System;
using Unity.Collections;
 
/// <summary>
/// Compiler and evaluator of simple formulas. A single line string is compiled
/// and evaluated to produce a number result. It may consist of constants,
/// variables, arithmetic operators (+, -, *, /, %), and parentheses.
/// For example: <code>100*level+50</code>
/// </summary>
///
/// <example>
/// Formula.CompileResult compileResult = Formula.Compile("level*50+100");
/// if (!compileResult.Success)
/// {
///     Debug.LogError("Compile error");
/// }
/// else
/// {
///     Formula formula = compileResult.Formula;
///     formula.SetVariable(Array.IndexOf(compileResult.Variables, "level"), 5);
///     Debug.LogFormat("Result: {0}", formula.Evaluate());
/// }
/// </example>
/// 
/// <author>
/// Jackson Dunstan, https://JacksonDunstan.com/articles/5385
/// </author>
/// 
/// <license>
/// MIT
/// </license>
public struct Formula : IDisposable
{
    /// <summary>
    /// The result of calling <see cref="Compile"/>
    /// </summary>
    public struct CompileResult
    {
        public bool Success;
        public Formula Formula;
        public string[] Variables;
    }
 
    /// <summary>
    /// Compile a formula string
    /// </summary>
    /// 
    /// <param name="source">
    /// Source to compile
    /// </param>
    ///
    /// <param name="allocator">
    /// Allocator to allocate the formula with
    /// </param>
    ///
    /// <returns>
    /// The result of compilation
    /// </returns>
    public static CompileResult Compile(string source, Allocator allocator)
    {
        CompileResult result = ParseInfixFormula(source, allocator);
        if (!result.Success)
        {
            return default;
        }
 
        if (!ConvertInfixToPostfix(ref result.Formula))
        {
            result.Formula.Dispose();
            return default;
        }
 
        result.Formula.AllocateStack(allocator);
 
        return result;
    }
 
    /// <summary>
    /// Set a variable's value
    /// </summary>
    /// 
    /// <param name="index">
    /// Index of the variable in <see cref="CompileResult.Variables"/>
    /// </param>
    ///
    /// <param name="value">
    /// Value of the variable
    /// </param>
    public void SetVariable(int index, double value)
    {
        for (int i = 0, count = m_NumNodes; i < count; ++i)
        {
            Node node = m_Nodes[i];
            if (node.Type == NodeType.Variable && node.VarIndex == index)
            {
                node.Value = value;
                m_Nodes[i] = node;
            }
        }
    }
 
    /// <summary>
    /// Evaluate the formula
    /// </summary>
    /// 
    /// <returns>
    /// The result of evaluating the formula
    /// </returns>
    public double Evaluate()
    {
        int top = 0;
        for (int i = 0; i < m_NumNodes; ++i)
        {
            Node curNode = m_Nodes[i];
            switch (curNode.Type)
            {
                case NodeType.Constant:
                    m_Stack[top] = curNode.Value;
                    top++;
                    break;
                case NodeType.Variable:
                    m_Stack[top] = curNode.Value;
                    top++;
                    break;
                case NodeType.Add:
                    m_Stack[top - 2] = m_Stack[top - 2] + m_Stack[top - 1];
                    top--;
                    break;
                case NodeType.Subtract:
                    m_Stack[top - 2] = m_Stack[top - 2] - m_Stack[top - 1];
                    top--;
                    break;
                case NodeType.Multiply:
                    m_Stack[top - 2] = m_Stack[top - 2] * m_Stack[top - 1];
                    top--;
                    break;
                case NodeType.Divide:
                    m_Stack[top - 2] = m_Stack[top - 2] / m_Stack[top - 1];
                    top--;
                    break;
                case NodeType.Modulus:
                    m_Stack[top - 2] = m_Stack[top - 2] % m_Stack[top - 1];
                    top--;
                    break;
            }
        }
 
        return m_Stack[0];
    }
 
    /// <summary>
    /// Dispose of any memory the formula holds
    /// </summary>
    public void Dispose()
    {
        if (m_Nodes.IsCreated)
        {
            m_Nodes.Dispose();
        }
        if (m_Stack.IsCreated)
        {
            m_Stack.Dispose();
        }
    }
 
    private enum NodeType
    {
        Constant,
        Variable,
        Add,
        Subtract,
        Multiply,
        Divide,
        Modulus,
        LeftParen,
        RightParen,
    }
 
    private struct Node
    {
        public NodeType Type;
        public int VarIndex;
        public double Value;
    }
 
    private NativeArray<Node> m_Nodes;
    private int m_NumNodes;
    private NativeArray<double> m_Stack;
 
    private void AddNode(Allocator allocator, in Node node)
    {
        if (!m_Nodes.IsCreated)
        {
            m_Nodes = new NativeArray<Node>(8, allocator);
        }
        else if (m_NumNodes >= m_Nodes.Length)
        {
            NativeArray<Node> newNodes = new NativeArray<Node>(
                m_Nodes.Length * 2,
                allocator);
            for (int i = 0; i < m_Nodes.Length; ++i)
            {
                newNodes[i] = m_Nodes[i];
            }
            m_Nodes.Dispose();
            m_Nodes = newNodes;
        }
        m_Nodes[m_NumNodes] = node;
        m_NumNodes++;
    }
 
    private void AllocateStack(Allocator allocator)
    {
        m_Stack = new NativeArray<double>(m_NumNodes, allocator);
    }
 
    private static int GetPrecedence(NodeType type)
    {
        switch (type)
        {
            case NodeType.Add: return 2;
            case NodeType.Subtract: return 2;
            case NodeType.Multiply: return 3;
            case NodeType.Divide: return 3;
            case NodeType.Modulus: return 3;
            default: return -1;
        }
    }
 
    private static bool AreSubstringsEqual(
        string str,
        (int startIndex, int length) subA,
        (int startIndex, int length) subB)
    {
        if (subA.length != subB.length)
        {
            return false;
        }
        for (int i = 0; i < subA.length; ++i)
        {
            if (str[subA.startIndex + i] != str[subB.startIndex + i])
            {
                return false;
            }
        }
        return true;
    }
 
    private static CompileResult ParseInfixFormula(
        string source,
        Allocator allocator)
    {
        // Parse the source into the formula
        // Keep track of the size of the stack when it's evaluated 
        NativeArray<(int startIndex, int length)> variables = default;
        int numVariables = 0;
        Formula formula = new Formula();
        int stackSize = 0;
        for (int i = 0; i < source.Length; )
        {
            char curChar = source[i];
 
            // Constant
            if ((curChar >= '0' && curChar <= '9') || curChar == '.')
            {
                // Find the end
                int startIndex = i;
                do
                {
                    i++;
                    if (i >= source.Length)
                    {
                        break;
                    }
                    curChar = source[i];
                } while ((curChar >= '0' && curChar <= '9') || curChar == '.');
 
                // Parse the value
                double value;
                if (!double.TryParse(
                    source.Substring(startIndex, i - startIndex),
                    out value))
                {
                    formula.Dispose();
                    return default;
                }
 
                // Add the node
                stackSize++;
                formula.AddNode(
                    allocator,
                    new Node
                    {
                        Type = NodeType.Constant,
                        Value = value
                    });
            }
            // Variable
            else if (
                (curChar >= 'a' && curChar <= 'z')
                || (curChar >= 'A' && curChar <= 'Z')
                || curChar == '_')
            {
                stackSize++;
 
                // Find the end
                int startIndex = i;
                do
                {
                    i++;
                    if (i >= source.Length)
                    {
                        break;
                    }
                    curChar = source[i];
                } while (
                    (curChar >= 'a' && curChar <= 'z')
                    || (curChar >= 'A' && curChar <= 'Z')
                    || curChar == '_');
 
                // Find existing variable
                (int, int) variable = (startIndex, i - startIndex);
                bool found = false;
                for (int j = 0; j < numVariables; ++j)
                {
                    if (AreSubstringsEqual(source, variables[j], variable))
                    {
                        formula.AddNode(
                            allocator,
                            new Node
                            {
                                Type = NodeType.Variable,
                                Value = j
                            });
                        found = true;
                        break;
                    }
                }
 
                if (!found)
                {
                    // Initial variables allocation
                    if (!variables.IsCreated)
                    {
                        variables = new NativeArray<(int, int)>(8, Allocator.Temp);
                    }
                    // Grow variables to fit more
                    else if (variables.Length == numVariables)
                    {
                        var newVariables = new NativeArray<(int, int)>(
                            variables.Length * 2,
                            Allocator.Temp);
                        for (int j = 0; j < numVariables; ++j)
                        {
                            newVariables[j] = variables[j];
                        }
                        variables.Dispose();
                        variables = newVariables;
                    }
 
                    formula.AddNode(
                        allocator,
                        new Node
                        {
                            Type = NodeType.Variable,
                            VarIndex = numVariables
                        });
 
                    variables[numVariables] = variable;
                    numVariables++;
                }
            }
            // Add
            else if (curChar == '+')
            {
                stackSize--;
                i++;
                formula.AddNode(
                    allocator,
                    new Node { Type = NodeType.Add });
            }
            // Subtract
            else if (curChar == '-')
            {
                stackSize--;
                i++;
                formula.AddNode(
                    allocator,
                    new Node { Type = NodeType.Subtract });
            }
            // Multiply
            else if (curChar == '*')
            {
                stackSize--;
                i++;
                formula.AddNode(
                    allocator,
                    new Node { Type = NodeType.Multiply });
            }
            // Divide
            else if (curChar == '/')
            {
                stackSize--;
                i++;
                formula.AddNode(
                    allocator,
                    new Node { Type = NodeType.Divide });
            }
            // Modulus
            else if (curChar == '%')
            {
                stackSize--;
                i++;
                formula.AddNode(
                    allocator,
                    new Node { Type = NodeType.Modulus });
            }
            // Left paren
            else if (curChar == '(')
            {
                i++;
                formula.AddNode(
                    allocator,
                    new Node { Type = NodeType.LeftParen });
            }
            // Right paren
            else if (curChar == ')')
            {
                i++;
                formula.AddNode(
                    allocator,
                    new Node { Type = NodeType.RightParen });
            }
            // Space
            else if (curChar == ' ')
            {
                i++;
            }
            // Illegal
            else
            {
                formula.Dispose();
                return default;
            }
        }
 
        // There must be one element left on the stack as a result of evaluating
        if (stackSize != 1)
        {
            formula.Dispose();
            return default;
        }
 
        // Create strings from variable indices
        string[] variableStrings = null;
        if (variables.IsCreated)
        {
            variableStrings = new string[numVariables];
            for (int i = 0; i < numVariables; ++i)
            {
                (int startIndex, int length) variable = variables[i];
                variableStrings[i] = source.Substring(
                    variable.startIndex,
                    variable.length);
            }
            variables.Dispose();
        }
 
        return new CompileResult
        {
            Success = true,
            Formula = formula,
            Variables = variableStrings
        };
    }
 
    private static bool ConvertInfixToPostfix(ref Formula formula)
    {
        // Convert using the Shunting Yard algorithm
        // This calls for an output queue and an operator stack
        // Use temporary allocation since we only need them for this function
        NativeArray<Node> outputQueue = new NativeArray<Node>(
            formula.m_Nodes.Length,
            Allocator.Temp);
        NativeArray<Node> opStack = new NativeArray<Node>(
            formula.m_Nodes.Length,
            Allocator.Temp);
        int outputQueueIndex = 0;
        int opStackIndex = 0;
 
        for (int i = 0; i < formula.m_NumNodes; ++i)
        {
            Node curNode = formula.m_Nodes[i];
            switch (curNode.Type)
            {
                case NodeType.Constant:
                case NodeType.Variable:
                    outputQueue[outputQueueIndex] = curNode;
                    outputQueueIndex++;
                    break;
                case NodeType.Add:
                case NodeType.Subtract:
                case NodeType.Multiply:
                case NodeType.Divide:
                case NodeType.Modulus:
                    int curPrecedence = GetPrecedence(curNode.Type);
                    while (opStackIndex > 0)
                    {
                        Node opTop = opStack[opStackIndex - 1];
                        if (opTop.Type == NodeType.LeftParen
                            || GetPrecedence(opTop.Type) < curPrecedence)
                        {
                            break;
                        }
 
                        // Pop off operator stack. Push onto output queue.
                        opStackIndex--;
                        outputQueue[outputQueueIndex] = opTop;
                        outputQueueIndex++;
                    }
 
                    opStack[opStackIndex] = curNode;
                    opStackIndex++;
                    break;
                case NodeType.LeftParen:
                    opStack[opStackIndex] = curNode;
                    opStackIndex++;
                    break;
                case NodeType.RightParen:
                    while (true)
                    {
                        if (opStackIndex <= 0)
                        {
                            outputQueue.Dispose();
                            opStack.Dispose();
                            return false;
                        }
 
                        Node opTop = opStack[opStackIndex - 1];
                        if (opTop.Type == NodeType.LeftParen)
                        {
                            break;
                        }
 
                        // Pop off operator stack. Push onto output queue.
                        opStackIndex--;
                        outputQueue[outputQueueIndex] = opTop;
                        outputQueueIndex++;
                    }
 
                    // Pop any left paren off operator stack and discard
                    if (opStackIndex > 0
                        && opStack[opStackIndex - 1].Type == NodeType.LeftParen)
                    {
                        opStackIndex--;
                    }
                    break;
            }
        }
 
        // Copy output to formula then pop operator stack into formula
        int formulaIndex = 0;
        for (int i = 0; i < outputQueueIndex; ++i)
        {
            formula.m_Nodes[formulaIndex] = outputQueue[i];
            formulaIndex++;
        }
        for (int i = opStackIndex - 1; i >= 0; --i)
        {
            Node topNode = opStack[i];
            if (topNode.Type == NodeType.LeftParen)
            {
                outputQueue.Dispose();
                opStack.Dispose();
                return false;
            }
            formula.m_Nodes[formulaIndex] = topNode;
            formulaIndex++;
        }
        formula.m_NumNodes = formulaIndex;
 
        // Free temporaries
        outputQueue.Dispose();
        opStack.Dispose();
 
        return true;
    }
}

Here are some unit tests to go along with this:

using System;
using NUnit.Framework;
using Unity.Collections;
 
public class FormulaTests
{
    [TestCase("")]
    [TestCase("+")]
    [TestCase("+5")]
    [TestCase("5+")]
    [TestCase("(")]
    [TestCase(")")]
    [TestCase("()")]
    [TestCase("((5)")]
    [TestCase("(5))")]
    [TestCase("(5")]
    [TestCase("5)")]
    [TestCase("5++5")]
    [TestCase("5..5")]
    [TestCase("x.5")]
    [TestCase("x5")]
    [TestCase("5.x")]
    public void InvalidFormulaDoesNotCompile(string code)
    {
        Formula.CompileResult result = Formula.Compile(code, Allocator.Temp);
 
        Assert.That(result.Success, Is.False);
    }
 
    [TestCase("5", 5)]
    [TestCase(" 5", 5)]
    [TestCase("5 ", 5)]
    [TestCase(" 5 ", 5)]
    [TestCase("3.1415", 3.1415)]
    [TestCase("4+2", 6)]
    [TestCase("5-1", 4)]
    [TestCase("4*2", 8)]
    [TestCase("6/2", 3)]
    [TestCase("6%4", 2)]
    [TestCase("(4+2)", 6)]
    [TestCase("4+2*3", 10)]
    [TestCase("(4+2)*3", 18)]
    [TestCase("(4+((4+2)*3))*3", 66)]
    [TestCase("4*2+3", 11)]
    [TestCase("ten+2*3", 16)]
    [TestCase("ten+twenty*3", 70)]
    [TestCase("ten+twenty*thirty", 610)]
    [TestCase("ten+ten", 20)]
    public void FormulaEvaluatesToCorrectResult(string code, double expected)
    {
        Formula.CompileResult result = Formula.Compile(code, Allocator.Temp);
 
        Assert.That(result.Success, Is.True);
 
        Formula formula = result.Formula;
        if (result.Variables != null)
        {
            formula.SetVariable(Array.IndexOf(result.Variables, "ten"), 10);
            formula.SetVariable(Array.IndexOf(result.Variables, "twenty"), 20);
            formula.SetVariable(Array.IndexOf(result.Variables, "thirty"), 30);
        }
 
        double actual = formula.Evaluate();
 
        Assert.That(actual, Is.EqualTo(expected));
    }
}
Conclusion

Today we've seen how easy it is to port pre-Burst code so that Burst can compile it, even when that code was using strings, exceptions, and collections. We've also seen how to compile and evaluate more complex infix expressions with operator precedence and parentheses.

The resulting system is a useful tool to give to game designers without the fear of them writing arbitrarily complex and slow code. Now they can express things like damage calculations in a formula that they can iterate on without the need for a programmer to modify C# code. It's much more powerful than giving them simple constants, yet it's still very approachable.