Re: Decision Graphs (or whatever they're called)

I believe they're called decision trees. They were used by Halo 2.
There's a paper about it somewhere out there. Sorry I can't check
right now, I'm posting from my phone.

Nisarg

On Friday, June 11, 2010, Phill Djonov <[email protected]> wrote:
> The recent discussion on OO and architecture (hear me out, I'm not
> trolling, I swear! :) ) got me thinking about a technique II'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
>
_______________________________________________
Sweng-Gamedev mailing list
[email protected]
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com