Sign in to follow this  
DF Du Bois

Edict system notes

Recommended Posts

This turned into an epic post that took me (way) longer to write that the code it's based on. I guess you can think of it as a sequel to my AF2012 "save system notes" post.

------

I did a fun little spot of programming today that reminded me of my university days, so I thought I'd share it.

BACKGROUND (longer than I intended! feel free to skip!)

Among other things, today I worked on the Edict system. In Dear Leader, edicts are what our designer JP calls the "verbs" of the player. When the Leader wants to get something done, she selects a form ("Execute somebody") fills out the blank spaces ("Execute the Development Minister"), then sets it in motion with her stamp of approval.

Each blank spot in the form needs to be filled in with what I call a "noun". I was adding the ability for the designers to specify exactly what nouns are valid for each blank spot. In this example, the valid nouns are simple: we want a person, alive, and it probably shouldn't be the Leader herself, or the Minister whose job it is to carry out the order.

Now, this project is blessed with designers who don't mind getting their hands dirty with Lua, but Duncan's been driving a data-driven approach for authoring forms and other game logic, and I wanted to fit smoothly with it. This means having the designer write a little function for each input of each form is right out. The data file is plain old lua, so a non-data-driven approach would look something like this:

tInputs = {

   victim = {

       type=INPUT_Person,

       filter=function(p)

           return (isAlive(p)

                   and not HasRole(p, kROLE.DearLeader)

                   and not HasRole(p, kROLE.Police)

       end

   }

}

That's a lot of boilerplate. And since the game is under rapid and active development, I might later want to give the filter access to the form itself, so we can write filters that are a little more context-sensitive. That would involve changing the signature of every filter to

  function(form, p) ... end

which would be a pain in the butt.

SOLUTION

Here's what this example currently looks like:

tInputs = {

   victim = {

       type=INPUT_Person,

       filter=AND(bIsAlive,

                  NOT(HasRole(kROLE.DearLeader)),

                  NOT(HasRole(kROLE.Police)))

   }

},

Where'd all the boilerplate go? Somehow, are these "variables" like bIsAlive being evaluated at some future time, instead of when the data file is loaded? And how about "functions" like HasRole() -- don't we need to pass it the person that we want to ask about?

The answer comes from a graduate class in programming language theory that I took my last semester in school. I had senioritis and didn't pay as much attention as I should have, but a few concepts from that class stuck with me: currying and combinators.

CURRYING (wiki)

Currying does not refer to the delicious treat enjoyed by the LA-MULANA team, but the process of modifying a function so it needs to be "called multiple times" in order to get a result. That's a bit ambiguous; so a concrete example would be:

HasRole_c = curry(HasRole) -- create the curried function

HasRole  (role, person)    -- this is how you call the original

HasRole_c(role)(person)    -- this is how you call the curried version

The curried HasRole_c still needs two arguments to produce a result, but it doesn't need them all at once. Give it a single argument, and it returns a new function, which we can think of as a "partially evaluated" version of HasRole. Only when the partially-evaluated function is itself called do we get the desired return value (in this case, a bool value used by the filtering step).

Here's a definition of a simple curry() in lua. It's a function that takes a function and returns a function. To fully get how it works requires an understanding of "closures" and "upvalues" in lua, but that's beyond the scope of this already-long post; hopefully you get the gist of what's going on:

function curry(func)

 return function(a)

   return function(b)

     return func(a,b)  -- 'func', and 'a' are 'closure variables', aka 'upvalues'

   end

 end

end

This explains how "HasRole" in the above example works. Calling it doesn't give you a bool; it gives you a function that takes a person and returns a bool. A useful term for "function of one argument that returns a bool" is "predicate" (wiki) and I'll use that term from now on. In particular, I'll note that the original example explicitly assigned a predicate to "filter", which means that the result of all our currying and combinating will hopefully also be a predicate.

As programmers, Duncan and I write predicates that are used for filtering nouns, for setting preconditions on various bits of authored game logic, and so on. We write them in a straightforward style, put them in a central place so the designers only need to look in one place to know what predicates are available to them, then at run time a gameplay system will curry() them before they're used.

So, I've explained "HasRole" (or tried to), but what about AND() and NOT()? And bIsAlive?

Simple one first: "bIsAlive" looks like a boolean variable but it's actually a function -- a predicate, to be precise. For AND and NOT, I come to:

COMBINATORS (wiki)

(Don't click that link because it's not very illuminating)

Combinators, used loosely, are functions that accept only functions, and return functions. In essence, all they do is "combine" functions in some way. Usually they'll return a function of the same type as the functions passed in. In this case, NOT is a combinator that takes a predicate and returns a predicate. AND is similar, but it takes a bunch of predicates.

Why is this fairly esoteric concept useful here? Mostly because I find it to simplify my understanding of how to implement this whole system. In an expression like "AND(bIsAlive, HasRole('Leader))", my thought process goes something like:

- I need a predicate as a final value. AND returns a predicate; check.

- AND requires predicates. bIsAlive is a predicate; check.

- HasRole() also returns a predicate; check

- QED: the system works

You can probably figure out how to write AND by now; here's my version:

function lib.AND(...)

   local aPreds = {...}

   return function(thing)

       for i,pred in ipairs(aPreds) do

           if not pred(thing) then return false end

       end

       return true

   end

end

FINAL THOUGHTS

Lua has its warts, but the fact that it has first-class functions and closures allows for some really powerful programming techniques. Many of these techniques are a little esoteric, but with a bit of familiarity aren't any more difficult to comprehend than recursion. (But, remember how difficult recursion was the first time you learned it!)

There exist programming languages like Haskell (so named for Haskell Curry; guess what he invented) which are built around currying, delayed evaluation, combinators, and other such techniques. Haskell is famously difficult to wrap your head around, especially coming from procedural languages; but that doesn't mean one can't borrow from its bag of tricks. Just do it wisely and with discretion ;-)

Share this post


Link to post
Share on other sites

Not used to lua syntax, but a fun example of closures and currying in production code. My experience with closures in general was that they one of those programming features where I thought "where the heck would I ever need to do that?". Then I ran into a situation where writing a closure turned a huge long spaghetti code mess into an easily maintainable few lines function. They're awesome.

More reading on closures: http://reprog.wordpress.com/2010/02/27/closures-finally-explained/

Share this post


Link to post
Share on other sites

Not used to lua syntax, but a fun example of closures and currying in production code. My experience with closures in general was that they one of those programming features where I thought "where the heck would I ever need to do that?". Then I ran into a situation where writing a closure turned a huge long spaghetti code mess into an easily maintainable few lines function. They're awesome.

More reading on closures: http://reprog.wordpress.com/2010/02/27/closures-finally-explained/

Share this post


Link to post
Share on other sites
This turned into an epic post that took me (way) longer to write that the code it's based on. I guess you can think of it as a sequel to my AF2012 "save system notes" post.

------

I did a fun little spot of programming today that reminded me of my university days, so I thought I'd share it.

Thanks for sharing :). It's awesome for us to get posts like this from Amnesia Fortnight.

Share this post


Link to post
Share on other sites
This turned into an epic post that took me (way) longer to write that the code it's based on. I guess you can think of it as a sequel to my AF2012 "save system notes" post.

------

I did a fun little spot of programming today that reminded me of my university days, so I thought I'd share it.

Thanks for sharing :). It's awesome for us to get posts like this from Amnesia Fortnight.

Share this post


Link to post
Share on other sites

Great post, Paul!

Very interesting to get some glimpses at the nuts and bolts of it all, as it were. :D

Share this post


Link to post
Share on other sites

Great post, Paul!

Very interesting to get some glimpses at the nuts and bolts of it all, as it were. :D

Share this post


Link to post
Share on other sites

Fun fact: my programming classes in college were taught in Haskell and Scala.

Share this post


Link to post
Share on other sites

Fun fact: my programming classes in college were taught in Haskell and Scala.

Share this post


Link to post
Share on other sites

Oh man, today I am my head against a problem I'm kind of scared that the problem really wants to be solved with continuation passing style (wiki). I'm not so much worried about writing the code but writing up the forum post is going to be murder.

The basic problem is that we have a data-driven system that processes "actions over time" -- ie, on turn 3 after this edict is submitted, kill some dude; or tweak someone's loyalty; or unlock a piece of tech after a period of time. Until now they've been simple and linear sequences of "actions", but it would be really nice if we could have branching. eg "roll vs competence; on success, increase population happiness in 2 years; on failure, reduce population health in 2 years".

Currently, actions return nothing; and when executed they are thrown away. When executed, an action could instead return a continuation action, which is the action to execute the next time. Then one could write a combinator action with signature fn(bool, action, action) -> action.

Anyway, I don't want to write up the forum post because in this case I know I'm abusing terminology. So I'll leave it there!


rollVsCompetence(5,12, kROLE.Development,

   inEra(2, adjustSimVar(kSVAR.Morale, 1)),

   inEra(2, adjustSimVar(kSVAR.Health, -1)))

Share this post


Link to post
Share on other sites

Oh man, today I am my head against a problem I'm kind of scared that the problem really wants to be solved with continuation passing style (wiki). I'm not so much worried about writing the code but writing up the forum post is going to be murder.

The basic problem is that we have a data-driven system that processes "actions over time" -- ie, on turn 3 after this edict is submitted, kill some dude; or tweak someone's loyalty; or unlock a piece of tech after a period of time. Until now they've been simple and linear sequences of "actions", but it would be really nice if we could have branching. eg "roll vs competence; on success, increase population happiness in 2 years; on failure, reduce population health in 2 years".

Currently, actions return nothing; and when executed they are thrown away. When executed, an action could instead return a continuation action, which is the action to execute the next time. Then one could write a combinator action with signature fn(bool, action, action) -> action.

Anyway, I don't want to write up the forum post because in this case I know I'm abusing terminology. So I'll leave it there!


rollVsCompetence(5,12, kROLE.Development,

   inEra(2, adjustSimVar(kSVAR.Morale, 1)),

   inEra(2, adjustSimVar(kSVAR.Health, -1)))

Share this post


Link to post
Share on other sites

There exist programming languages like Haskell (so named for Haskell Curry; guess what he invented) which are built around currying, delayed evaluation, combinators, and other such techniques. Haskell is famously difficult to wrap your head around, especially coming from procedural languages; but that doesn't mean one can't borrow from its bag of tricks. Just do it wisely and with discretion ;-)

Sorry to be nitpicking, but mathematicians (Frege, Schönfinkel) were using currying before Curry applied it to the lambda calculus. Anyway, really nice post!

Share this post


Link to post
Share on other sites
Oh man, today I am my head against a problem I'm kind of scared that the problem really wants to be solved with continuation passing style (wiki).

...

The basic problem is that we have a data-driven system that processes "actions over time" -- ie, on turn 3 after this edict is submitted, kill some dude; or tweak someone's loyalty; or unlock a piece of tech after a period of time.

Delayed continuations, eh... who'd've thunk it?

Share this post


Link to post
Share on other sites
mathematicians (Frege, Schönfinkel) were using currying before Curry applied it to the lambda calculus.

Indeed; thanks for the correction!

Delayed continuations, eh... who'd've thunk it?

Nice one ;)

Share this post


Link to post
Share on other sites
Delayed continuations, eh... who'd've thunk it?

Nice one ;)

:)

Incidentally, wanted you to know that your musing on code (and indeed those of Oliver & Brandon) may have a small audience, but one that does appreciate your efforts. In fact, some of us even understand, are learning about engine programming techniques from this, and plan to incorporate bits and pieces of these lessons into our own game dev hobby!

So... thank you.

Share this post


Link to post
Share on other sites

One more vote for more Paul Du Bois code & comments (whenever you have the leisure suit time & hat).

I might also do a lambda calculus involving hands on everyone wearing a Haskell or Erlang or Bad Golf 3 Conference T-Shirt, if I see you on an airport, around the world. Don't be afraid, silent minority report readers.

The "free lunch" maybe "over", but Herb Sutter never told me I can't buy you a drink.

Share this post


Link to post
Share on other sites

Ouch, this reminds me how much I've forgotten since getting out of school. Nowadays, I only get to do some programming in Excel/Access (VBA).

Share this post


Link to post
Share on other sites
Sign in to follow this