Game Development Community

dev|Pro Game Development Curriculum

Using OmniGraffle To Design Decision Trees

by Scott Coursey · 01/05/2007 (2:02 pm) · 1 comments

Download Code File

Imagine this: You have a chunk of code that contains a dozen "if" statements, numerous "else" ones and all kinds of loops and nasty code sprinkled about. You finally get everything written and test it. WHAM! The code does what it was designed to do, but the design was bad (blame it on the project manager, unless that's who you are).

To redesign the framework, you draw everything up on a sketch pad in a flowchart style. It looks beautiful. Start coding it and you get lost in the little trees. Or, instead of drawing it, you use a flowchart program. Still, it's beautiful, but getting lost in the trunks, branches, and leaves is simple.

That's where I was last week. I was beginning to write a large decision tree for a strategic AI for my current game. I got stuck with the above problems almost immediately.

I looked into the .graffle, hoping I could parse the data I needed to make something helpful as a script. Very luckily, the Omni Group decided to record all the data as an XML file. Simple parsing. I just needed to figure out the schema.

What I came up with is my "parse" script. To use the script, download it and make sure it's accessible (in your Terminal) and executable. I won't go over those concepts, so let's move on.

Inside the ZIP file is a test graffle, which looks like this:

www.courseytechnologies.com/ogparse/ogtest.png
In the above image, there are several nodes of interest.

The first is the CONFIG node. The text defines the behavior of the parser. Each line is separated by a newline. The possible options are:
TREE - which file will get the TorqueScript code for the decision tree itself.
HELP - the file which will get all of the helper functions supporting the tree.
CLASS - the name of the TorqueScript class.
DEBUG - turns on or off extra console output to track the decision tree's progress. The value for DEBUG is 1 or 0, depending on its boolean value you want (or you can leave the line off to disable the debugging).

So, for the test file, we will have a TorqueScript class of "testC", a script file "testG.cs", another for helper functions "testH.cs" and no extra debugging output.

Next comes the "ROOT NODE". This is the starting point of the parser. Everything under here is included into the scripts. All other functions, trees, nodes, leaves, etc are up to you.

Here's how it all comes together. First off, all of the lines have two parts. They are separated by a single newline which defines the function in the code.

If you have a single node with a single output (ex, "Initialize turn"), then you will have a function executed.

If you have a node with two outputs, label then "Yes" and "No". Those will create an if/then/else clause.

If there is a node with a single output and a last line with the LOOP phrase, it will create a "for" loop in the code.

The format for the "LOOP" phrase is (no spaces in the text; I'm putting them here for legibility):

LOOP : var : start : end

var - defines the variable used to control the loop. For the helper functions, it can be accessed as %this.aiLoop_var. So, if you declare "myOrcs", then the variable will be "%this.aiLoop_myOrcs".

start - the starting number for the loop. This can be either an integer or a function call. In this case, it starts at zero.

end - the ending number for the loop. Again, it can be a function call or an integer. It's a function called "GET_KEEP_COUNT" here.

Knowing all this, you can easily create a very complicated flowchart and have it parsed into TorqueScript. Given the minimal example above, let's see the code that gets generated.

Here is the testG.cs, which is the file for the main decision tree logic.
function testC::ThinkFromGraffle ( %this )
{
	%this.INIT_TURN();
	for ( %x = 0; %x < %this.GET_KEEP_COUNT(); %x ++ )
	{
		%this.aiLoop_x = %x;
		if ( %this.CHECK_KEEP_DEF() )
		{
			%this.ENEMY_IN_RANGE();
		} else {
			%this.DO_CHECK_KEEPS();
		}
	}
	%this.END_TURN();
}

Now, here's the testH.cs which contains all the helper functions.
function testC::CHECK_KEEP_DEF ( %this )
{
}

function testC::DO_CHECK_KEEPS ( %this )
{
}

function testC::END_TURN ( %this )
{
}

function testC::ENEMY_IN_RANGE ( %this )
{
}

function testC::GET_KEEP_COUNT ( %this )
{
}

function testC::INIT_TURN ( %this )
{
}

Making the decision trees this way not only allows you to visually see a logical flow of the execution, but allows the parser to update the two script files as needed.

One other feature of the parser I have not yet mentioned is its non-desctructive nature.

Let's say you parse a graffle into script. You spend hours adding code to the Helper script (never touch the decision tree script file). You can always re-run the parse and it will ultimately do two things:
1. Completely rewrite the decision tree code. You can change the layout, nodes, commands, etc and the parser will create a new tree.
2. Only add function definitions to the Helper script for the functions that it cannot find. The function definitions are appended and no other code will be lost (it will be up to you to adapt your code as necessary if you change a function name or delete one all together).

For me, this script has been an extreme time saver. I change my graffle many times over and simply re-parse it. Right now, I'm at 62 functions in my decision tree and plan on it getting much larger. If you want to see a shrunken version of my tree at the time of writing this, click here.

I hope this script is beneficial for someone.

Enjoy!