Sam MacPherson

Flash, Haxe, Game Dev and more…

Compiling Formulas at Runtime

During development of my newest game I ran into a bit of a barrier with the recently implemented lighting system. I wanted to give my level designer a large degree of control over the lighting in the game. My first thought was to associate predefined values with each of the lights. For example if you wanted a flickering light you could attach a “light-type” property with a value set to “flickering” or something similar. At first this seemed like a good idea, but we quickly found out that there is just too much variation to have to rely on the programmer to implement a new light everytime one is needed. The solution? Allow the level designer to specify time-evolution formulas for each of the properties of the light.

I decided to generalize this approach to arbitrary formulas of n input variables. Given a valid formula string this class will compile it and allow you to pass input variables. The answer will be returned as if the programmer had wrote it in the language. Here is an example equation that one might use:

(x0 + x1) / 5 – sin(r)

What this will do is add input variable 0 to variable 1 then divide that by 5 and subtract sin of a random value. As you can see I have included some common functions that you may want to use. Valid functions include:

sin()
cos()
tan()
sqrt()
hs()

Most of these functions are self-explanatory except for perhaps the hs() one. hs() is just the Heaviside step function (http://en.wikipedia.org/wiki/Heaviside_step_function) which is useful for converting continuous functions into discrete ON/OFF style functions.

Also included are a couple of useful identifiers. The constant PI which can be written as “pi” anywhere in the formula. Also you can specify a random value by writing “r” as seen in the above formula. The random value is always 0 <= r < 1).

So what can you do with this? Make cool lights!

Given that the variable x0 will always contain a value from 0 to 1 which will increment by a delta time value every frame we can basically do anything. Want to make a random flickering light that is on 95% of the time? Easy.

on = r – 0.05

Just a side note, "on" is a predefined light value which is either on (>= 0) or not (< 0).

Want to create the tv light from the video in the last post?

red = hs(sin(x0*11*pi)) + 0.5
blue = hs(sin(x0*5*pi)) + 0.5
green = 0
period = 50seconds

What the above formulas do is cycle through 4 distinct possibilities (RED off, BLUE off), (RED on, BLUE off), (RED off, BLUE on) and (RED on, BLUE on). We put the sin function through the Heaviside step function to make these shifts abrupt. If we left the hs() function out we would have more of a gradual color change (which doesn't look very good for a tv).

The compiler is fairly straight forward. First the string is lexed into tokens and stored in an array. After that calls to compute() will return the appropriate value.

public inline function compute (input:Array):Float {
	_index = 0;
	return _expr(input);
}

private inline function _err (token:Token):Void {
	throw new Error("Syntax error at token '" + token.str + "'.");
}

private inline function _eoi ():Bool {
	return _index >= _tokens.length;
}

private function _expr (input:Array):Float {
	var token:Token = _tokens[_index];
	if (Std.is(token, ValueTerminalToken) || Std.is(token, FunctionToken)) {
		return _term(input);
	} else {
		_err(token);
		return Mathematics.NaN;
	}
}

private function _term (input:Array):Float {
	var token:Token = _tokens[_index];
	if (Std.is(token, ValueTerminalToken) || Std.is(token, FunctionToken)) {
		return _moreTerm(_factor(input), input);
	} else {
		_err(token);
		return Mathematics.NaN;
	}
}

private function _moreTerm (left:Float, input:Array):Float {
	var token:Token = _tokens[_index];
	if (Std.is(token, AddToken)) {
		_index++;
		return left + _term(input);
	} else if (Std.is(token, SubtractToken)) {
		_index++;
		return left - _term(input);
	} else if (Std.is(token, RightParenToken) || _eoi()) {
		return left;
	} else {
		_err(token);
		return Mathematics.NaN;
	}
}

private function _factor (input:Array):Float {
	var token:Token = _tokens[_index];
	if (Std.is(token, ValueTerminalToken)) {
		return _moreFactor(_val(input), input);
	} else if (Std.is(token, LeftParenToken)) {
		_index++;
		var v:Float = _expr(input);
		if (!Std.is(_tokens[_index++], RightParenToken)) {
			_err(token);
			return Mathematics.NaN;
		}
		return _moreFactor(v, input);
	} else if (Std.is(token, SinToken)) {
		_index++;
		var v:Float = Math.sin(_expr(input));
		if (!Std.is(_tokens[_index++], RightParenToken)) {
			_err(token);
			return Mathematics.NaN;
		}
		return _moreFactor(v, input);
	} else if (Std.is(token, CosToken)) {
		_index++;
		var v:Float = Math.cos(_expr(input));
		if (!Std.is(_tokens[_index++], RightParenToken)) {
			_err(token);
			return Mathematics.NaN;
		}
		return _moreFactor(v, input);
	} else if (Std.is(token, TanToken)) {
		_index++;
		var v:Float = Math.tan(_expr(input));
		if (!Std.is(_tokens[_index++], RightParenToken)) {
			_err(token);
			return Mathematics.NaN;
		}
		return _moreFactor(v, input);
	} else if (Std.is(token, SqrtToken)) {
		_index++;
		var v:Float = Math.sqrt(_expr(input));
		if (!Std.is(_tokens[_index++], RightParenToken)) {
			_err(token);
			return Mathematics.NaN;
		}
		return _moreFactor(v, input);
	} else if (Std.is(token, HeavisideToken)) {
		_index++;
		var v:Float = if (_expr(input) >= 0) 1 else 0;
		if (!Std.is(_tokens[_index++], RightParenToken)) {
			_err(token);
			return Mathematics.NaN;
		}
		return _moreFactor(v, input);
	} else {
		_err(token);
		return Mathematics.NaN;
	}
}

private function _moreFactor (left:Float, input:Array):Float {
	var token:Token = _tokens[_index];
	if (Std.is(token, MultiplyToken)) {
		_index++;
		return left * _factor(input);
	} else if (Std.is(token, DivideToken)) {
		_index++;
		return left / _factor(input);
	} else if (Std.is(token, AddToken) || Std.is(token, SubtractToken) || Std.is(token, RightParenToken) || _eoi()) {
		return left;
	} else {
		_err(token);
		return Mathematics.NaN;
	}
}

private function _val (input:Array):Float {
	var token:Token = _tokens[_index];
	if (Std.is(token, VariableToken)) {
		_index++;
		return input[Std.int(cast(token, VariableToken).val)];
	} else if (Std.is(token, NumberToken)) {
		_index++;
		return cast(token, NumberToken).val;
	} else if (Std.is(token, RandomToken)) {
		_index++;
		return Math.random();
	} else {
		_err(token);
		return Mathematics.NaN;
	}
}

I want to note that this is not the most efficient way to do this since you have to essentially recompile every time you want to compute a value. A better solution is to compile the formula into actionscript bytecode (ABC). I will likely switch over to that method soon.

This class can be used like this:

var eqn:Equation = Equation.compile("x0 + 5");
trace(eqn.compute([2]));

The above piece of code should print 7.

Advertisements

One response to “Compiling Formulas at Runtime

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: