Decision Tree Rewrite and Requirements Code Cleanup

First off, a status update: we will not be releasing Alpha 44 this week. We will do an Alpha 43C at some point, and will aim to do Alpha 44 next week. This is due to a number of non-work factors, and we apologize for being a little out of sync. Alpha 44 will be better for it.

Business as usual.

Business as usual.

Last time I wrote a blogpost, I noted that we were redoing the barracks to use a new user interface. Well, the interface code was written, but disabled, because we needed to set the AI to use all the new goodies (and, also, to make sure that we fix some of the long-standing military bugs that make our soldier friends less than effective.) The issue here is that we have a big block of decision tree code which should drive military decisions, as well as your hierarchy of Maslowian needs. Right now, this code doesn’t really have a unified mechanism; there is a big block of code that is hard coded for colonists which evaluates their military tree, and that’s sort of a big ugly mess. There needed to be a mechanism to evaluate a decision tree – a series of requirements and “do I succeed at this requirement or do I fail at this requirement?” decisions, which we can run through consistently and without touching the scripting system. I planned on doing this – and even blogged about it! – a few months ago, but kept putting the rewrite off because I knew it was going to be terrible, and because there we always other things that needed to be done first. Anyhow, I finally ran out of things I could meaningfully do before doing this horrible rewrite, so I finally said “ugh” and started in on it.

The actual code to execute the decision tree was very straightforward. It took me about a day of writing to get into a “rough shape” where it would work, and there will probably be a day or two of debugging before it was done. The problem is that the decision trees internally use the same structure as the jobs XML, except that a decision tree “job” has a “yes” and “no” node branch, and no utility block (since it doesn’t go into the normal job utility evaluation hopper.) In short, the decision tree block basically cannot be edited in a text editor; it is too complex.

"AI programming" by Pieter Breugel

“AI programming” by Pieter Bruegel

At this point, I decided the correct thing to do was to basically write a node graph editor. You might recognize these from Unreal Engine’s Blueprint editor, or the Maya scene graph. Writing one of these is not really the actions of a sane person. Anyhow, I wrote a bezier curve drawing function (it turns out that you actually need to use bezier curves for graph node connections to make them look right; I first used Hermite curves because they’re easy to code. Nope. I then used Catmull-Rom curves, because I had the code for them… nope. So I gave up and wrote bezier curve code, and that let me do what I wanted to do. So now you know, folks) and code to hook windows up to graph nodes. This produces something that looks kind of like this:

shot030Choices in the same level of the decision tree (i.e. “if I am already doing something in the decision tree with a level of priority equal to my thing, I just carry on doing it”) drop out of the bottom of the current graph node. Choices in different levels of the decision tree shoot out to the right/left. Obviously I’m still furiously plumbing in the interface here.

The new problem, of course, is that each of those requirements needs to be editable, and to know how to load and save itself. Currently, we have something like a hundred different sorts of things that our job system can use as a “requirement”, from “I require a game object” (with a complicated set of logic) to “I require that this colonist has this desire, or owns this piece of property” to “I require that this session variable is set.” It’s a very powerful system, but the core loader is implemented as a giant XML-loading case statement.

To break down the XML loading case statement, I set up functions which add loading, saving, and a limited form of reflection to a requirement. Each of those can then have a property on the requirement (here a property is “what tag am I looking for, what tags aren’t allowed, do I lock the thing, do I unlock the thing, etc., etc.”) The new code provides a common hook which walks every attribute, and either loads it from XML, saves it to XML, or creates UI widgets that edit it. (It may also eventually be extended to spit out automatic documentation a la Doxygen, which is something I have wanted to do for years and which would be Pretty Slick(TM)) It does this by checking the context in which it is running, and what information is passed to it:

#define REQ_StringAttrib(name, value) \
if (attrBlock)    \
{                \
    const char **attrs = attrBlock;\
    while (*attrs)\
        const char* pAttributeName = (*attrs); attrs++; const char* pAttributeValue = (*attrs); attrs++;\
else if (fp)\
    fprintf(fp, "%s=\"%s\" ", name,value);     \
else if (vb)\
    illInputBoxWidget *x = new illInputBoxWidget;\

… that sort of a thing. If we can find an attribute block, we load from it; if we can find a file pointer, we save to it, and if we can find a vertical container, we push ourselves into it. The end result is that we can now define the loading/saving/pushing block that handles a requirement like so:

REQ_Start(gameSimRequirePartyBuilding, "require_party_building",true)
    REQ_StringAttrib("name", name);
    REQ_StringAttrib("input", tag);
    REQ_StringAttrib("tag", objectTag);
    REQ_BoolAttrib("must_lock", mustLock);
    REQ_BoolAttrib("must_test_lock", mustTestLock);

REQ_Start(gameSimRequireAssignmentContainer, "require_assignment_container",false)
    REQ_StringAttrib("input", tag);            
    REQ_BoolAttrib("must_lock", mustLock);
    REQ_BoolAttrib("must_test_lock", mustTestLock);

which is much, much cleaner than what we were doing before – if a little macro-flavoured.

For those of you interested in the ins and outs of the requirements system, here is a concrete example: requiring a game object with a certain property is the most common operation that we generally perform in the job system. (This is all data-driven, of course.) The class that requires a game object takes a huge number of parameters:

REQ_Start(gameSimRequireGameObject, "require_gameobject", true)
    REQ_StringAttrib("not_input", notInput);
    REQ_StringAttrib("name", name);
    REQ_StringAttrib("type", type);
    REQ_TagListAttrib("tag", objectTags);
    REQ_TagListAttrib("not_tag", notTags);
    REQ_StringAttrib("member_of_a", memberOfA);
    REQ_BoolAttrib("require_owned", requireOwned);
    REQ_StringAttrib("not_member_of_a", notMemberOfA);
    REQ_StringAttrib("tag_from_string_attrib", objectTagFromStringAttrib);
    REQ_BoolAttrib("tag_from_job", tagFromJob);
    REQ_BoolAttrib("random", random);            
    REQ_BoolAttrib("closest", closest);            
    REQ_BoolAttrib("create_marker", createMarker);
    REQ_BoolAttrib("in_party", inParty);
    REQ_IntAttrib("range", range);
    REQ_BoolAttrib("unique", unique);
    REQ_BoolAttrib("must_lock", mustLock);
    REQ_BoolAttrib("must_unlock", mustUnlock);
    REQ_BoolAttrib("must_test_lock", mustTestLock);
    REQ_BoolAttrib("must_lock_ggp", mustLockGGP);
    REQ_IntAttrib("civ_value_leq", targetCivValueLEQ);
    REQ_IntAttrib("civ_value_geq", targetCivValueGEQ);

I then gave Daniel the job of refactoring all ninety-eight existing requirements to use the new system because I am a bad person(ed. Hooray.), while I keep writing more interface stuff to go on top of that. And now, on with writing more code to use all this! Hooray!

Posted in Clockwork Empires, Programming | Tagged , , , , , , , ,

10 Responses to “Decision Tree Rewrite and Requirements Code Cleanup”

  1. Yeol says:

    “I planned on doing this – and even blogged about it! – a few months ago, but kept putting the rewrite off because I knew it was going to be terrible, and because there we always other things that needed to be done first. Anyhow, I finally ran out of things I could meaningfully do before doing this horrible rewrite, so I finally said “ugh” and started in on it.”

    Ah, the standard decision tree for programmer behavior.

    { reply }
  2. Joel says:

    So, all this certainly sounds like a job for lisp. I know the game uses lua, which makes me wonder why this is in xml?

    With all the macro discussion, I feel like this post is a honeypot for asking about lisp.

    { reply }
  3. Tailes says:

    Updates in this blog is what I am most anxiously wait for all week long 🙂
    I just wish you could implement this in terms of templates instead of macros…

    { reply }
    • Yeol says:

      Implementing a turing complete domain-specific compile-time language using template metaprogramming in order to specify decision trees does seem like it would be an appropriate behavior for programmers above a certain madness threshold.

      { reply }
  4. Stefan says:

    >”At this point, I decided the correct thing to do was to basically write a node graph editor…Writing one of these is not really the actions of a sane person.”

    Love it. In my project, I’m in a similar boat but do not possess the raw manlytude required to stop copy-pasting and get started on a refactor. Then again avoiding refactors is a privilege of mine I suppose as mine is a “project” and not one of those “fun game” things you guys have on your hands.

    Is the intention for this tool to be completely internal? Might be pretty amusing to be able to play around with it as a player.

    { reply }
    • Stefan Bauer says:

      Seconding the request for it to be repackaged as an externally available tool at some point; sounds like it could be really useful for modders.

      { reply }
  5. Insignus says:

    This is likely a tangent, but I’m curious to know if you’ve considered adding a dev tool kit on release that spits out the memory states of your colonists into text files (Basically a log file function) with an associated time stamped decision tree in a .csv format?

    I ask because while you probably how such things would work coding it, I would find it humorous to run a statistical function that asks “Which of these minor factors most directly influences cult behavior over time, controlling for cult exposure?”

    I can then make all my colonists with those factors go live near the swamp.

    Also, if you get anywhere close to what you’re trying to do with the way the colonists behave, and you publish such things (Not open source, but “Hey, you can watch this blow up and poke around on how we did it”), some academic folks might take an interest.

    P.S. if you need to analyze such things for giggles or to IBM SPSS makes a relatively cheap and easy to step into statistics program that you can plug neural net and decision tree extensions. If you tell them what you’re doing, they might let you tinker with it under the free trial.

    If you want to do something crazier you’d need Stata or SAS, which are more expensive, but better.

    { reply }

Leave a Reply

Your email address will not be published. Required fields are marked *