Decision Graphs (or whatever they're called)

The recent discussion on OO and architecture (hear me out, I'm not
trolling, I swear! :) ) got me thinking about a technique I've been
toying with for a while (well, it's been put to *some* productive use,
but only in a primitive incarnation). That primitive incarnation
turned out good enough that, much to my surprise, it's probably going
to ship soon, and I get the feeling it'd be worth putting in the time
to refine it some for future use.

Apologies in advance if this is something really obvious that
everybody but me's been doing for ages, I only recently came out of my
tools and graphics hole where life is simple...

Anyway, the basic problem I'm solving is implementing absurd designy
high-level logic. For instance, a designer hands you a document that
boils down to a dozen levels of if and switch statements. It's a mess,
but you code it up, and all is well. And then they decide that on
level four they want an entire branch of that logic to be something
else completely, and you've got to go back to your design and add a
virtual call at that branch point (because it was completely
non-obvious that anyone would ever want to screw with the logic
*there*) and override it in level four. Ten levels later and you can't
tell what anything does anymore because code branches off to strange
places all over the place, iteration time goes up and up, and you
start wishing the designers would just hurry up and die (but instead
they change the base design and now half of your override points no
longer make any sense and...).

So what I did to deal with this, is I basically transcribed their
document directly into the game not as code but rather *as data*. The
end result was something like a graph of associative maps, each taking
as a key the result of one level of if/switch statement and returning
either another map for the next level or a leaf node which is either a
function or a list of parameters to some other update function. All
that's then left is to evaluate all of the branch values ahead of
time, stick them in a list, and use that list to traverse the graph in
some sane manner.

My initial experience has been ridiculously promising (given how
ridiculously ad-hoc the implementation is). All of the updates happen
at the leaves, meaning I have a bunch of very simple little
objects/functions to maintain. Fixing "game breaks in condition X, Y,
Z" bugs has been obscenely easy since all I have to do is trace those
conditions through the graph and there's everything that happens. None
of the nightmares of tracing updates through "oh this is virtual and
the level four object is eight levels of inheritance away" or even
just through stuff like:

if( X )
{
  if( Y )
  {
    //pages of code
  }
  else
  {
    //pages of code
  }

  //some good code
  statement_which_offends_when_Y_and_Z();
  //some more good code
}

ever happened. Crazy "hey, let's make level nine be different"
requests also never really added much complexity since simply patching
the base logic graph at level load ended up being *far* more
maintainable than going back and adding hooks specifically for level
nine overrides. Hell, the final scripts are nearly simple enough for a
designer (who couldn't code hello world to save his life) to read. And
it's pretty obvious that the whole thing could be boiled down into a
mess of ugly branchy code, if that were ever needed for performance
(or whatever) reasons, though it also seems that it's awfully close to
something that could be bent to a more stream-processing type
approach... (beyond the obvious compute_traverse_keys( entity[] );
traverse_logic_graphs( traverse_key_list[] ) split).

So, what's that called? "Decision graph" brings up hits on Google, but
that which isn't simply "how we draw flow charts" seems to be mostly
academic, and I'm more interested in getting a good grounding in the
related practical issues (at least at this stage). I assume I've badly
reinvented Lisp or somesuch, and there must be a body of practices
surrounding this already...

Have any of you done serious work with such an architecture? Any "oh
look out for this" type thoughts you can share?

Cheers!
Phill
_______________________________________________
Sweng-Gamedev mailing list
[email protected]
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com