JacksonDunstan.com

As you know, making your game data-driven is good idea. So you make all kinds of configuration files with numbers in them: starting health, damage amount, XP reward, etc. But what do you do when those values aren’t just constants? Today’s article presents a little one-file class that you can use to evaluate simple formulas instead of just constants. What if your data for “XP reward” wasn’t just “100” but instead a formula like “10+MMRDifference*50”? That’s a great tool you can hand to game designers to data-drive your game. Read on to learn how!

The formula evaluator that is the subject of today’s article is really simple. It only evaluates single-line formula strings consisting of a few types of elements:

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

There are no parentheses or precedence. These formulas are simply evaluated from left to right like on a calculator. If you expect precedence like in C#, you’ll get the wrong answer. Again, think of it like a calculator:

// this formula...
2+10*3
// is equivalent to this C#...
(2+10)*3
// so the answer is...
36
// so rewrite it so it works the way you expect...
10*3+2
// equivalent to C#...
(10*3)+2
// so the answer is...
32

The lack of negatives isn’t a big deal. The only time it comes up is when you want to start the formula with a negative. In those cases, you can just subtract from 0:

// instead of...
-10*health
// use this...
0-10*health

That’s all there is to the syntax! Just that much allows you to make some pretty expressive formulas:

// XP gain...
5.5*monster_level
 
// monster health...
PlayerLevel*100+100
 
// max MMR difference...
NumSecondsWaitingInQueue*3+50
 
// score...
NumTargetsHit*100-NumTargetsMissed

It’s not a real programming language, but it’s a lot better than just a single number for a lot of cases.

Now let’s look at how this is implemented. There are two phases: compile and evaluate. The Formula class has a Compile function that takes your formula string and returns a CompileError struct. So here’s how you start using it:

// Make a formula. Used to compile and evaluate formulas. Optional capacity shown.
Formula formula = new Formula(16);
 
// Compile a formula.
// In practice you'll pass in a string you load from a config file, server, etc.
Formula.CompileError error = formula.Compile("100+level*50");
 
// Check the compile error. It's NoError if successful. Otherwise print the error.
if (error.Reason != Formula.CompileErrorReason.NoError)
{
	Debug.LogErrorFormat("Error {0} at {1}", error.Reason, error.CharIndex);
}
else
{
	// TODO
}

So far so good. Now for that “TODO”. The next steps are to set the values of all the variables in the formula. This one requires level to be set. Then we can call Evaulate to get the result of the formula:

// Set all the variables
// Important note: this is guaranteed to not create any garbage!
formula.SetVariable("level", 60);
 
// Evaluate the formula
// Important note: this is guaranteed to not create any garbage if successful!
double result = formula.Evaluate();
 
// Print the result
Debug.LogFormat("Result: {0}", result);

Alternatively, we might not know all the variables that the formula has in it. In that case we can call GetVariableNames to get them all:

// Gather all the variable names into a HashSet
HashSet<string> variableNames = new HashSet<string>();
formula.GetVariableNames(variableNames);
 
// Set all the variable names
foreach (string variableName in variableNames)
{
	switch (variableName)
	{
		// Set known variable names
		case "monster_level":
			formula.SetVariable(variableName, monster.Level);
			break;
		case "player_level"
			formula.SetVariable(variableName, player.Level);
			break;
		// Unknown variables are a problem. Don't evaluate this formula!
		default:
			Debug.LogErrorFormat("Unknown variable: {0}", variableName);
			return;
	}
}
 
// Evaluate the formula
double result = formula.Evaluate();
 
// Print the result
Debug.LogFormat("Result: {0}", result);

To clean up the Formula, we have three options:

// Forget the old formula and variables completely. It's like we just constructed.
// Useful when putting this formula back into an object pool.
// Guaranteed not to create any garbage.
formula.Reset();
 
// Forget the old formula and variables completely. Replace it with a new formula.
// Useful to reuse the Formula object for another formula, e.g when reused from an object pool.
formula.Compile("PlayerLevel*100+100");
 
// Un-set all the variables.
// Useful to make sure no variables are reused between Evaluate() calls.
// Guaranteed not to create any garbage.
formula.ClearVariables();

The only parts left are a couple of exceptions that can be thrown by Evaluate:

try
{
	Debug.LogFormat("Result: {0}", formula.Evaluate());
}
catch (Formula.NoFormulaException ex)
{
	Debug.LogErrorFormat("Whoops, we forgot to successfully Compile() a formula");
}
catch (Formula.VariableNotSetException ex)
{
	Debug.LogErrorFormat("Whoops, we forgot to set a variable's value with SetVariable()");
}

Finally for today is the actual source code for Formula. It’s a single class in a single file with no dependencies on anything, so you should be able to easily drop it into any project. I hope you find it useful! Let me know in the comments if you use it or anything similar!

using System;
using System.Collections.Generic;
 
/// <summary>
/// Compiler and evaluator of simple formulas. A single line string is compiled and evaluated from
/// left to right. It may consist of constants (numbers and decimal dots), variables (upper- and
/// lower-case letters plus underscore), and arithmetic operators (+, -, *, /). For example:
/// 
///   100*level+50
/// 
/// Before evaluating the formula, variables may be set to specific values. Variables may be reset,
/// the entire formula maybe cleared to save memory, or new formulas may be compiled.
/// 
/// Example usage:
/// 
///   Formula formula = new Formula();
///   Formula.CompileError error = formula.Compile("100+level*50");
///   if (error.Reason != Formula.CompileErrorReason.NoError)
///   {
///     Debug.LogErrorFormat("Couldn't compile formula: {0} at {1}", error.Reason, error.CharIndex);
///   }
///   else
///   {
///     formula.SetVariable("level", 60);
///     double result = formula.Evaluate();
///     Debug.LogFormat("Result: {0}", result);
///   }
/// 
/// </summary>
/// <author>Jackson Dunstan, http://JacksonDunstan.com</author>
/// <license>MIT</license>
public class Formula
{
	/// <summary>
	/// Types of nodes in a formula
	/// </summary>
	private enum NodeType
	{
		/// <summary>
		/// An unset node
		/// </summary>
		Default,
 
		/// <summary>
		/// A constant (e.g. 123.45)
		/// </summary>
		Constant,
 
		/// <summary>
		/// A variable (e.g. health)
		/// </summary>
		Variable,
 
		/// <summary>
		/// Addition operator (i.e. +)
		/// </summary>
		Add,
 
		/// <summary>
		/// Subtraction operator (i.e. -)
		/// </summary>
		Subtract,
 
		/// <summary>
		/// Multiplication operator (i.e. *)
		/// </summary>
		Multiply,
 
		/// <summary>
		/// Division operator (i.e. /)
		/// </summary>
		Divide,
 
		/// <summary>
		/// Modulus operator (i.e. %)
		/// </summary>
		Modulus
	}
 
	/// <summary>
	/// A node in the formula
	/// </summary>
	private struct Node
	{
		/// <summary>
		/// Type of the node
		/// </summary>
		public NodeType Type;
 
		/// <summary>
		/// Name of the variable (if Type == Variable)
		/// </summary>
		public string Name;
 
		/// <summary>
		/// Value of the variable or constant (if Type == Variable or Constant)
		/// </summary>
		public double Value;
 
		/// <summary>
		/// If the variable has its value set
		/// </summary>
		public bool HasValue;
	}
 
	/// <summary>
	/// Reasons why Compile() might fail
	/// </summary>
	public enum CompileErrorReason
	{
		/// <summary>
		/// No error
		/// </summary>
		NoError,
 
		/// <summary>
		/// The source string was null
		/// </summary>
		SourceNull,
 
		/// <summary>
		/// The source string was empty
		/// </summary>
		SourceEmpty,
 
		/// <summary>
		/// A constant or variable was expected
		/// </summary>
		ExpectedConstantOrVariable,
 
		/// <summary>
		/// The formula must end with a constant or a variable (i.e. not an operator)
		/// </summary>
		MustEndWithConstantOrVariable,
 
		/// <summary>
		/// A variable can't directly follow a constant. It must be separated by an operator.
		/// </summary>
		VariableCanNotFollowConstant,
 
		/// <summary>
		/// A constant can't directly follow a variable. It must be separated by an operator.
		/// </summary>
		ConstantCanNotFollowVariable,
 
		/// <summary>
		/// An illegal character was found
		/// </summary>
		IllegalCharacter,
 
		/// <summary>
		/// An invalid constant (i.e one that couldn't be parsed) was found
		/// </summary>
		InvalidConstant
	}
 
	/// <summary>
	/// An error compiling a formula's source
	/// </summary>
	public struct CompileError
	{
		/// <summary>
		/// Reason for the compilation failure. Set to NoError on success.
		/// </summary>
		public CompileErrorReason Reason;
 
		/// <summary>
		/// Index of the relevant character or -1 if no character is relevant
		/// </summary>
		public int CharIndex;
	}
 
	/// <summary>
	/// Exception that is thrown when evaluating a formula with a variable whose value wasn't
	/// set by <see cref="SetVariable"/>.
	/// </summary>
	public class VariableNotSetException : Exception
	{
		/// <summary>
		/// Name of the variable that isn't set
		/// </summary>
		/// <value>The name of the variable that isn't set</value>
		public string Name { get; private set; }
 
		/// <summary>
		/// Create the exception
		/// </summary>
		/// <param name="name">Name of the variable that isn't set</param>
		public VariableNotSetException(string name)
		{
			Name = name;
		}
	}
 
	/// <summary>
	/// Exception that is thrown when evaluating a formula and there is no formula to evaluate
	/// </summary>
	public class NoFormulaException : Exception
	{
	}
 
	/// <summary>
	/// Nodes of the formula. May be empty.
	/// </summary>
	private List<Node> nodes;
 
	/// <summary>
	/// Create a formula with capacity for a certain number of nodes
	/// </summary>
	/// <param name="initialCapacity">
	/// Initial capacity to hold nodes of the formula. If exceeded, the nodes list will resize.
	/// </param>
	public Formula(int initialCapacity = 16)
	{
		if (initialCapacity < 2)
		{
			initialCapacity = 2;
		}
		nodes = new List<Node>(initialCapacity);
	}
 
	/// <summary>
	/// Compile a formula string. After successfully compiling, make sure to call
	/// <see cref="SetVariable"/> for each variable in the formula and then call
	/// <see cref="Evaluate"/>.
	/// </summary>
	/// <param name="source">Source to compile</param>
	/// <returns>
	/// The error resulting from this compilation. Will have the NoError type if successful.
	/// </returns>
	public CompileError Compile(string source)
	{
		// Reset all the nodes
		Reset();
 
		// Source must be non-null and non-empty
		if (source == null)
		{
			return new CompileError {
				Reason = CompileErrorReason.SourceNull,
				CharIndex = -1
			};
		}
		int sourceLen = source.Length;
		if (sourceLen == 0)
		{
			return new CompileError {
				Reason = CompileErrorReason.SourceEmpty,
				CharIndex = -1
			};
		}
 
		// Source must start with either a constant or a variable
		NodeType mode = NodeType.Default;
		int startCharIndex = 0;
		for (int charIndex = 0; charIndex < sourceLen; ++charIndex)
		{
			char curChar = source[charIndex];
 
			// In the Default mode we look for what's next
			if (mode == NodeType.Default)
			{
				// Constant
				if ((curChar >= '0' && curChar <= '9') || curChar == '.')
				{
					mode = NodeType.Constant;
					startCharIndex = charIndex;
					charIndex--;
				}
				// Variable
				else if (
					(curChar >= 'a' && curChar <= 'z')
					|| (curChar >= 'A' && curChar <= 'Z')
					|| curChar == '_')
				{
					mode = NodeType.Variable;
					startCharIndex = charIndex;
					charIndex--;
				}
				// Must start with constant or variable
				else if (charIndex == 0)
				{
					return new CompileError {
						Reason = CompileErrorReason.ExpectedConstantOrVariable,
						CharIndex = 0
					};
				}
				// Add
				else if (curChar == '+')
				{
					nodes.Add(new Node { Type = NodeType.Add });
				}
				// Subtract
				else if (curChar == '-')
				{
					nodes.Add(new Node { Type = NodeType.Subtract });
				}
				// Multiply
				else if (curChar == '*')
				{
					nodes.Add(new Node { Type = NodeType.Multiply });
				}
				// Divide
				else if (curChar == '/')
				{
					nodes.Add(new Node { Type = NodeType.Divide });
				}
				// Modulus
				else if (curChar == '%')
				{
					nodes.Add(new Node { Type = NodeType.Modulus });
				}
				else
				{
					return new CompileError {
						Reason = CompileErrorReason.IllegalCharacter,
						CharIndex = charIndex
					};
				}
			}
			else if (mode == NodeType.Variable)
			{
				// Letters and underscores are OK
				if (
					(curChar >= 'a' && curChar <= 'z')
					|| (curChar >= 'A' && curChar <= 'Z')
					|| curChar == '_')
				{
				}
				// Constants can't immediately follow a variable. They must be separated by an
				// operator.
				else if ((curChar >= '0' && curChar <= '9') || curChar == '.')
				{
					return new CompileError {
						Reason = CompileErrorReason.ConstantCanNotFollowVariable,
						CharIndex = charIndex
					};
				}
				// Operators end the variable
				else if (
					curChar == '+'
					|| curChar == '-'
					|| curChar == '*'
					|| curChar == '/'
					|| curChar == '%')
				{
					nodes.Add(new Node {
						Type = NodeType.Variable,
						Name = source.Substring(startCharIndex, charIndex - startCharIndex)
					});
					charIndex--;
					mode = NodeType.Default;
				}
				// All other characters are illegal
				else
				{
					return new CompileError {
						Reason = CompileErrorReason.IllegalCharacter,
						CharIndex = charIndex
					};
				}
			}
			else if (mode == NodeType.Constant)
			{
				// Numbers and dots are OK
				if ((curChar >= '0' && curChar <= '9') || curChar == '.')
				{
				}
				// Operators end the constant
				else if (
					curChar == '+'
					|| curChar == '-'
					|| curChar == '*'
					|| curChar == '/'
					|| curChar == '%')
				{
					double value;
					if (!double.TryParse(
						source.Substring(startCharIndex, charIndex - startCharIndex), out value))
					{
						return new CompileError {
							Reason = CompileErrorReason.InvalidConstant,
							CharIndex = startCharIndex
						};
					}
					nodes.Add(new Node {
						Type = NodeType.Constant,
						Value = value
					});
					charIndex--;
					mode = NodeType.Default;
				}
				// Variables can't immediately follow a constant. They must be separated by an
				// operator.
				else if (
					(curChar >= 'a' && curChar <= 'z')
					|| (curChar >= 'A' && curChar <= 'Z')
					|| curChar == '_'
				)
				{
					return new CompileError {
						Reason = CompileErrorReason.VariableCanNotFollowConstant,
						CharIndex = charIndex
					};
				}
				// All other characters are illegal
				else
				{
					return new CompileError {
						Reason = CompileErrorReason.IllegalCharacter,
						CharIndex = charIndex
					};
				}
			}
		}
 
		// Set end node to constant
		if (mode == NodeType.Constant)
		{
			double value;
			if (!double.TryParse(
				source.Substring(startCharIndex, sourceLen - startCharIndex), out value))
			{
				return new CompileError {
					Reason = CompileErrorReason.InvalidConstant,
					CharIndex = startCharIndex
				};
			}
			nodes.Add(new Node {
				Type = NodeType.Constant,
				Value = value
			});
		}
		// Set end node to variable
		else if (mode == NodeType.Variable)
		{
			nodes.Add(new Node {
				Type = NodeType.Variable,
				Name = source.Substring(startCharIndex, sourceLen - startCharIndex)
			});
		}
		// Source must end with a constant or variable. Trailing operators are not allowed.
		else
		{
			return new CompileError {
				Reason = CompileErrorReason.MustEndWithConstantOrVariable,
				CharIndex = sourceLen - 1
			};
		}
 
		return new CompileError {
			Reason = CompileErrorReason.NoError,
			CharIndex = -1
		};
	}
 
	/// <summary>
	/// Get the names of all the variables
	/// </summary>
	/// <param name="variables">HashSet to store the variable names in</param>
	public void GetVariableNames(HashSet<string> variables)
	{
		for (int i = 0, count = nodes.Count; i < count; ++i)
		{
			Node curNode = nodes[i];
			if (curNode.Type == NodeType.Variable)
			{
				variables.Add(curNode.Name);
			}
		}
	}
 
	/// <summary>
	/// Set a variable's value
	/// 
	/// Guaranteed not to allocate any managed memory (a.k.a. "garbage").
	/// </summary>
	/// <param name="name">Name of the variable</param>
	/// <param name="value">Value of the variable</param>
	/// <returns>The number of variables in the formula that were set</returns>
	public int SetVariable(string name, double value)
	{
		int numFound = 0;
		for (int i = 0, count = nodes.Count; i < count; ++i)
		{
			Node curNode = nodes[i];
			if (curNode.Type == NodeType.Variable && curNode.Name == name)
			{
				curNode.Value = value;
				curNode.HasValue = true;
				nodes[i] = curNode;
				numFound++;
			}
		}
		return numFound;
	}
 
	/// <summary>
	/// Clear the values of all variables. They must be re-set with <see cref="SetVariable"/> before
	/// calling <see cref="Evaluate"/> again.
	/// 
	/// Guaranteed not to allocate any managed memory (a.k.a. "garbage").
	/// </summary>
	public void ClearVariables()
	{
		for (int i = 0, count = nodes.Count; i < count; ++i)
		{
			Node curNode = nodes[i];
			if (curNode.Type == NodeType.Variable)
			{
				curNode.HasValue = false;
				nodes[i] = curNode;
			}
		}
	}
 
	/// <summary>
	/// Reset to the default state. The compiled formula and any set variables are lost.
	/// 
	/// Guaranteed not to allocate any managed memory (a.k.a. "garbage").
	/// </summary>
	public void Reset()
	{
		nodes.Clear();
	}
 
	/// <summary>
	/// Evaluate the compiled formula with the set variable values. Make sure to call
	/// <see cref="Compile"/> first then <see cref="SetVariable"/> for each variable in the formula
	/// before you call this.
	/// 
	/// Guaranteed not to allocate any managed memory (a.k.a. "garbage") if successful.
	/// </summary>
	/// <returns>The result of the formula with the set variable values</returns>
	public double Evaluate()
	{
		// Requires at least one node
		int numNodes = nodes.Count;
		if (numNodes == 0)
		{
			throw new NoFormulaException();
		}
 
		// Variables must have been set via SetVariable
		Node firstNode = nodes[0];
		if (firstNode.Type == NodeType.Variable && !firstNode.HasValue)
		{
			throw new VariableNotSetException(firstNode.Name);
		}
 
		// Initial value is the first node
		double result = firstNode.Value;
 
		// Loop over pairs of nodes (operator then value) applying them to a running result
		for (int i = 1; i < numNodes; i+=2)
		{
			Node operatorNode = nodes[i];
			Node valueNode = nodes[i+1];
 
			// Variables must have been set via SetVariable
			if (valueNode.Type == NodeType.Variable && !valueNode.HasValue)
			{
				throw new VariableNotSetException(valueNode.Name);
			}
 
			// Apply the operator
			switch (operatorNode.Type)
			{
				case NodeType.Add:
					result += valueNode.Value;
					break;
				case NodeType.Subtract:
					result -= valueNode.Value;
					break;
				case NodeType.Multiply:
					result *= valueNode.Value;
					break;
				case NodeType.Divide:
					result /= valueNode.Value;
					break;
				case NodeType.Modulus:
					result %= valueNode.Value;
					break;
			}
		}
 
		return result;
	}
}

#1 by Leucaruth on March 13th, 2017 · Reply

Pretty interesting. It opens possibilities to game decisions avoiding code.

Keep up the good work :)

#2 by Ollydbg on March 25th, 2017 · Reply

Wonderful!
I need it.But I need more features.So I modified some of the content to the GitHub, thank you!https://github.com/Ollydbg/FormulaRPN

#3 by jackson on March 26th, 2017 · Reply

Cool! Glad to see you’re finding it useful and extensible. The version in the article is super simple so it’s good to see a little more power being added while keeping to the spirit of the original.

A Simple Formula Evaluator

Comments