Since the last devlog there were 13 commits between 2019/02/16 and 2019/02/22, totaling 34 commits. I have worked 35 hours during this period, bringing the total to 83 hours.

This one is entirely about messing with AI, iterating and refactoring the approach.

Initial Approach

It started with basic xml Behavior Tree from the last devlog. First thing I did though, was updating Haxe to version 4 Release Candidate, in preparation to using inlined markup.

Truth is the xml in the previous devlog wasn’t really used. It was just a template for how I would want it to look. What it actually looked like in code was:

forest = [
	{ behavior: 'Sequence', child: 1 },
	{ behavior: 'Run', sibling: 2, config: { angle: 0 } },
	{ behavior: 'Run', config: { angle: Math.PI } },
];

Where each behavior name mapped to function(nodeId:Int, entity:Entity). Why a function and not some class instance? Because in the ECS spirit, the state, i.e. all the data, is supposed to be stored inside entity’s components. The behavior tree itself should be completely stateless.

So for example Sequence, which needs a state to remember which child it’s currently executing, would use the passed entity to get the AI component and read/write the state there.

But writing it out like in the code sample above is pretty tedious and very error prone. The hierarchy of the tree is mapped using child and sibling properties, which simply contain an integer index pointing to another behavior. Doing this by hand makes my brain hurt.

Macro Powered

Haxe macros to the rescue!

With a bit of magic, I can achieve the same result from the XML file at compile time. Generating the same code by simply doing forest = AIParser.parseAI('data/ai.xml'); Of course I had to write the code to actually do that.

But the behavior logic is still defined as a function, mapped to the proper behavior by a string. I don’t like strings. Too easy to make typos and they often move errors from compile time to runtime. Solution? More macros!

What I did was I turned the Behavior into a class (I know, I know, I said no state and all, but keep reading). Now every Behavior has a class name and has to extend from the Behavior base class. It also made all the child, sibling properties fully typed.

So instead of array of, essentially string names, there is now array of Behavior instances. What about the state? Well, behaviors still need configuration. The child and sibling are part of that. So having instances makes sense. All those properties are final so I can’t accidentally rewrite them. So instead of { behavior: 'Sequence', child: 1 } there’s now new Sequence(1). If the behavior has more properties, they are all added in the constructor, all fully type checked.

But if there’s an error in the XML, while the macro can report it, it might not be entirely obvious what the error is, as inside XML all we have are strings.

Inlined Behavior Trees

Haxe is awesome, I hope that’s clear by now. I mentioned inlined markup support, what is it? Shortly, it allows me to write the XML right inside the Haxe source, process it via a macro and report back. That means I get syntax coloring, errors reported right there, as I write the code, and bunch of other benefits.

I have skipped a couple of iterations, but end result is basically that the behavior tree is declared directly in the code, fully typed and pretty (prettier than here, as the web highlighter doesn’t handle it correctly), like this:

public static var DoggyRun = 
	<Sequence>
		<Run angle={0} duration={1} />
		<Run angle={Math.PI} duration={1} />
	</Sequence>

And the actual behaviors are declared as classes like this:

class Sequence extends Behavior {
    function init():ChildData {
        return {
            child: this.child
        }
    }
    function execute(data) {
        while(true) {
            var child = forest[data.child];
            var status = runOther(child);
            switch(status) {
                case Success:
                    if(child.sibling.valid()) {
                        data.child = child.sibling;
                    } else {
                        clearData();
                        return Success;
                    }
                case Failure:
                    clearData();
                    return Failure;
                case Running:
                    return Running;
            }
        }
    }
}

The fun part about this is that the init function declares state the Behavior needs, which is stored on the entity’s component during execution. If the Behavior doesn’t need state, the code to handle that is entirely removed. It’s also fully typed, so for the data parameter in execute I get proper code completion and error checking.

Also if you notice the runOther and clearData, they aren’t declared in every Behavior, and they actually aren’t even declared in the base Behavior class. How so? The macro that processes the class will check what needs to be done and only include the code if it’s actually needed, with exact inlined code for the logic, right there where it’s called. That effectively means there’s zero runtime overhead for unused features and when the behavior runs, it’s actually just a single method without any function calls.

Practical Test

First actual use of all this was taking our Doggy for a walk. He keeps running around a log, when he notices the hero, starts circling around him, but will return back to running around the log if he gets too far from it.

I also quickly added support for “barks” for this test. They are a way for an NPC to convey emotions and such.

All that is powered by this behavior tree:

<Sequence>
	<MarkPosition mark={'spawn'} />
	<UntilFail>
		<Selector>
			<Sequence>//either find interest and circle it until too far away
				<FindInterest radius={70} interestingEntities={interestingEntities}/>
				<BarkAction engine={engine} type={BarkType.Icon(ExclamationRed)}/>//bark when found
				<Parallel>
					<Sequence>
						<UntilFail><DistanceSmaller value={200} from={'spawn'} /></UntilFail>
						<AlwaysFail><BarkAction engine={engine} type={BarkType.Icon(Question)} fast={true}/></AlwaysFail>
					</Sequence>
					<CircleAround />
				</Parallel>
			</Sequence>
			<Parallel>//or follow path, if close enough
				<DistanceSmaller value={150} from={'spawn'} />
				<AlwaysSucceed><FollowPath path={paths.get('tree_log_walk')} /></AlwaysSucceed>
			</Parallel>
			<Sequence>//otherwise we are lost, run home!
				<Parallel>
					<AlwaysSucceed><FollowPath path={paths.get('tree_log_walk')} /></AlwaysSucceed>
					<UntilSuccess><DistanceSmaller value={50} from={'spawn'} /></UntilSuccess>
				</Parallel>
				<BarkAction engine={engine} type={BarkType.Icon(HeartFull)}/>
			</Sequence>
		</Selector>
	</UntilFail>
</Sequence>

And this is how it looks compiled:

var forest = [];
forest.push(new ai_behaviors_Sequence(forest,0,-1,1));
forest.push(new ai_behaviors_Run(forest,1,2,-1,0,1));
forest.push(new ai_behaviors_Run(forest,2,3,-1,Math.PI,1));
forest.push(new ai_behaviors_FollowPath(forest,3,-1,-1,paths["tree_log_walk"]));
forest.push(new ai_behaviors_Sequence(forest,4,-1,5));
forest.push(new ai_behaviors_MarkPosition(forest,5,6,-1,"spawn"));
forest.push(new ai_behaviors_UntilFail(forest,6,-1,7));
forest.push(new ai_behaviors_Selector(forest,7,-1,8));
forest.push(new ai_behaviors_Sequence(forest,8,18,9));
forest.push(new ai_behaviors_FindInterest(forest,9,10,-1,interestingEntities,70));
forest.push(new ai_behaviors_BarkAction(forest,10,11,-1,engine,gui_BarkType.Icon(8)));
forest.push(new ai_behaviors_Parallel(forest,11,-1,12));
forest.push(new ai_behaviors_Sequence(forest,12,17,13));
forest.push(new ai_behaviors_UntilFail(forest,13,15,14));
forest.push(new ai_behaviors_DistanceSmaller(forest,14,-1,-1,"spawn",200));
forest.push(new ai_behaviors_AlwaysFail(forest,15,-1,16));
forest.push(new ai_behaviors_BarkAction(forest,16,-1,-1,engine,gui_BarkType.Icon(9),true));
forest.push(new ai_behaviors_CircleAround(forest,17,-1,-1));
forest.push(new ai_behaviors_Parallel(forest,18,22,19));
forest.push(new ai_behaviors_DistanceSmaller(forest,19,20,-1,"spawn",150));
forest.push(new ai_behaviors_AlwaysSucceed(forest,20,-1,21));
forest.push(new ai_behaviors_FollowPath(forest,21,-1,-1,paths["tree_log_walk"]));
forest.push(new ai_behaviors_Sequence(forest,22,-1,23));
forest.push(new ai_behaviors_Parallel(forest,23,28,24));
forest.push(new ai_behaviors_AlwaysSucceed(forest,24,26,25));
forest.push(new ai_behaviors_FollowPath(forest,25,-1,-1,paths["tree_log_walk"]));
forest.push(new ai_behaviors_UntilSuccess(forest,26,-1,27));
forest.push(new ai_behaviors_DistanceSmaller(forest,27,-1,-1,"spawn",50));
forest.push(new ai_behaviors_BarkAction(forest,28,-1,-1,engine,gui_BarkType.Icon(5)));

Bonus video – testing performance – so far so good.