WHY A BOOL SOLVER
There are often situations, where it makes sense to just have a simple expression language, that
allows to describe certain things which just some simple boolean states.
It could help in defining conditions for keyboard shortcuts, sensors/states for video game agents,
procedarual generation systems and a lot more.
INSPIRATION
A post by
Wortex17 on mastodon finally
gave me the inspiration to implement it.
The implementation should be able to compute a value, to cache paths of the expression
and also to only evaluate if needed.
Examples:
( a && b ) || a // Should never need to eval "b"
a || b || a // Should execute "a" only once
IMPLEMENTATION
The implementation that I created, uses a abstract expression class with a reference to its parent expression.
Specialized implementations like Or/And/Group will also reference their child expressions.
Expressions have a method to compute their values, which needs to be specialized and a getValue-Method,
which is used to compute and cache the value.
This way the tree allows to compute the value by calling the method "getValue" of the root expression.
Since the implementation uses the C# boolean logic to AND/OR
expressions, they will also be automatically only executed on demand ("short circut eval"). Also, all nodes
will flag themselves as computed once the computed a value.
The only exception are the references to variables. Here the referenced variables themselves cache the value.
RECOMPUTATION
The tree structure with its parent has a reason. Whenever a variable is changed, it can bubble up its
changes to the references, which will bubble their changes to their parents. The generated paths are the parts of the
expression tree that are affected by the change.
Below you can see where I setup the expressions and test what happens when I change variables.
The console outputs document which structures are computed or return cached values.
This is pretty far in fullfilling most requirements. The only thing that is missing is an optimizer, that is
running through all paths on the initial structure and also when values changes and transforms the tree to more
efficient structures (like in the first example, the expression could be simplified to "a").
And of course there are more things to optimize, if the computation of the expressions needs to be boosted.
TESTING IN UNITY
using UnityEngine;
namespace ROKOJORI.Bools
{
[ExecuteAlways]
public class UnityBools:MonoBehaviour
{
public void Test()
{
var a = new Variable<int>( "a", true );
var b = new Variable<int>( "b", false );
var and = new And<int>( a.GetReference(), b.GetReference() );
var group = new Group<int>( and );
var or = new Or<int>( group, a.GetReference() );
Logger.Log( ">> Initial => ( a && b ) || a; a = True; b = False " );
var result = or.GetValue();
Logger.Log( "----" );
Logger.Log( ">> Changed a = False" );
a.SetValue( false );
var result2 = or.GetValue();
Logger.Log( "----" );
Logger.Log( ">> Changed b = True" );
b.SetValue( true );
var result3 = or.GetValue();
Logger.Log( "----" );
Logger.Log( ">> Initial => c || d || c; c = True, d = False" );
var c = new Variable<int>( "c", true );
var d = new Variable<int>( "d", false );
var or1 = new Or<int>( c.GetReference() , d.GetReference() );
var or2 = new Or<int>( or1 , c.GetReference() );
var result4 = or2.GetValue();
Logger.Log( "----" );
Logger.Log( ">> Changed c = False" );
c.SetValue( false );
var result5 = or2.GetValue();
Logger.Log( "----" );
}
public bool updateFlag;
public void Update()
{
if ( ! updateFlag )
{
return;
}
updateFlag = false;
Test();
}
}
}
CONSOLE OUTPUTS
>> Initial => ( a && b ) || a; a = True; b = False
Variable(a)@15 Computed value. Result = True
Variable(b)@16 Computed value. Result = False
And@19 Computed value. Result = False
Group@20 Computed value. Result = False
Variable(a)@15 Returning cached value. Result = True
Or@22 Computed value. Result = True
----
>> Changed a = False
Variable(a)@15 Computed value. Result = False
And@19 Computed value. Result = False
Group@20 Computed value. Result = False
Variable(a)@15 Returning cached value. Result = False
Or@22 Computed value. Result = False
----
>> Changed b = True
Variable(a)@15 Returning cached value. Result = False
And@19 Computed value. Result = False
Group@20 Computed value. Result = False
Variable(a)@15 Returning cached value. Result = False
Or@22 Computed value. Result = False
----
>> Initial => c || d || c; c = True, d = False
Variable(c)@23 Computed value. Result = True
Or@27 Computed value. Result = True
Or@29 Computed value. Result = True
----
>> Changed c = False
Variable(c)@23 Computed value. Result = False
Variable(d)@24 Computed value. Result = False
Or@27 Computed value. Result = False
Variable(c)@23 Returning cached value. Result = False
Or@29 Computed value. Result = False
----
SOURCE CODE
using UnityEngine;
using System.Collections.Generic;
namespace ROKOJORI.Bools
{
public class Logger
{
public static void Log( string value )
{
Debug.Log( value );
}
}
public class IDGenerator
{
static int idCounter = 0;
public static string Create()
{
var id = idCounter +"";
idCounter ++;
return id;
}
}
public abstract class Expression<T>
{
public T data;
protected bool computedValue = false;
protected bool hasValueComputed = false;
protected abstract bool ComputeValue();
protected Expression<T> parent;
protected string id;
public virtual string ID => this.GetType().Name + "@" + id;
public Expression()
{
id = IDGenerator.Create();
}
public void SetParent( Expression<T> parent )
{
this.parent = parent;
}
public virtual bool GetValue()
{
if ( hasValueComputed )
{
Logger.Log( ID + " Returning cached value. Result = " + computedValue );
return computedValue;
}
computedValue = ComputeValue();
hasValueComputed = true;
Logger.Log( ID + " Computed value. Result = " + computedValue );
return computedValue;
}
public void TriggerChange()
{
this.hasValueComputed = false;
if ( this.parent == null )
{
return;
}
this.parent.TriggerChange();
}
}
public class And<T>:Expression<T>
{
public Expression<T> left;
public Expression<T> right;
protected override bool ComputeValue()
{
return left.GetValue() && right.GetValue();
}
public And( Expression<T> left, Expression<T> right )
{
this.left = left;
this.right = right;
this.left.SetParent( this );
this.right.SetParent( this );
}
}
public class Constant<T>:Expression<T>
{
public readonly bool value;
protected override bool ComputeValue()
{
return value;
}
public Constant( bool value )
{
this.value = value;
}
}
public class Group<T>:Expression<T>
{
public Expression<T> expression;
protected override bool ComputeValue()
{
return expression.GetValue();
}
public Group( Expression<T> expression )
{
this.expression = expression;
this.expression.SetParent( this );
}
}
public class Not<T>:Expression<T>
{
public Expression<T> expression;
protected override bool ComputeValue()
{
return ! expression.GetValue();
}
public Not( Expression<T> expression )
{
this.expression = expression;
this.expression.SetParent( this );
}
}
public class Or<T>:Expression<T>
{
public Expression<T> left;
public Expression<T> right;
protected override bool ComputeValue()
{
return left.GetValue() || right.GetValue();
}
public Or( Expression<T> left, Expression<T> right )
{
this.left = left;
this.right = right;
this.left.SetParent( this );
this.right.SetParent( this );
}
}
public class Variable<T>
{
protected bool computedValue = false;
protected bool hasValueComputed = false;
protected bool value;
protected string _name;
public string name => _name;
protected List references = new List();
protected string id;
public string ID => this.GetType().Name + "(" + name + ")@" + id;
public Variable( string name, bool value )
{
this._name = name;
this.value = value;
id = IDGenerator.Create();
}
public VariableReference<T> GetReference()
{
var v = new VariableReference<T>( this );
references.Add( v );
return v;
}
public bool ComputeValue()
{
return value;
}
public bool GetValue()
{
if ( hasValueComputed )
{
Logger.Log( ID + " Returning cached value. Result = " + computedValue );
return computedValue;
}
computedValue = ComputeValue();
hasValueComputed = true;
Logger.Log( ID + " Computed value. Result = " + computedValue );
return computedValue;
}
public void SetValue( bool value )
{
if ( this.value == value )
{
return;
}
this.value = value;
this.hasValueComputed = false;
references.ForEach( e => e.TriggerChange() );
}
}
public class VariableReference<T>:Expression<T>
{
protected Variable<T> variable;
protected override bool ComputeValue()
{
return variable.GetValue();
}
public override string ID => this.GetType().Name + "(" + variable.name + ")@" + id;
public VariableReference( Variable<T> variable )
{
this.variable = variable;
}
public override bool GetValue()
{
return this.variable.GetValue();
}
}
}
All social media brands are registrated trademarks and belong to their respective owners.
NEWS
STORE
LABS
NEWSLETTER
