Most days, no matter how productive I’m being with traditional programming languages like C++ or Python, you’ll easily draw me into an argument about how terrible they are as tools for creating decisions or behavior of any kind. In fact, most of my musings on this blog (RSS) and my personal research are pushing me in a direction where visual editors meet planning technology.
Along those lines, it’s always refreshing for me to find researchers that have taken similar thoughts down different paths. The work of Jonathan Edwards from MIT’s CSAI research laboratory on a project called Subtext particularly fascinates me.
Subtext provides schematic tables as a way to express decisions (a.k.a. conditionals) that can be edited visually. The interpreter allows changes to be made in realtime and the appropriate calculations happen on the fly so it’s easy to make changes and add features. That’s the theory at least, read on to find out how this stacks up in practice!
This research is driven by the belief that there’s a better way to program conditionals than mainstream programming languages offer. In particular, the following arguments can be made:
Plain text ASCII documents are a poor way to specify many forms of logic, including boolean conditionals.
The syntax of modern programming languages makes programmers jump through hoops to figure out what’s really going on.
As a consequence, it’s very error prone and labor intensive to create logical expressions and conditionals in “code.”
In the context of game AI, conditionals are used at many levels in the hierarchy of scripts or FSM to figure out which sub-behavior to pick. For example, when should a certain attack be used: melee, ranged, with/without cover? When is it appropriate to even enter combat? Being able to specify conditionals effectively makes it much easier to avoid bugs when such decisions are programmed.
Figure 1: A schematic table expresses both computation and decisions.
Generally speaking, the innovation of this paper is example centric programming — which helps you create code by specifying what it should do in specific cases. In particular, this involves:
Using computers to perform boolean calculations to help visualize, create and manage conditionals.
Providing a front-end for programmers to express behavior instead of requiring a text editor.
Avoiding editing linear programs (as a bunch of if / then statements) to conditionals.
In practice, this is achieved in the following way:
The basic idea is to use schematic tables, inspired by old-fashion decision tables popular in the 60s, combined with function expressions. These can be used as a functional programming language to calculate any value.
Each column in the table contains a set of values for each variable taken into account in the decision. One and only one column may be true at any time, and the result of the column is used as the result.
In more advanced cases, cells in the table may perform full calculations using a function that can be combined into a visual tree, like most programming languages have under the hood…
The editor itself provides many interesting features, including the ability to debug the program in the very same way it’s visualized (like a live spreadsheet), as well as being able to layout tables in visually pleasing ways. Be sure to watch this video for more information on the subject, including an example of calculating attack damage for a typical game.
Figure 2: Subtext’s visual editor for schematic tables.
Abstract & References
Here’s the abstract for the paper itself:
“Schematic tables are a new representation for conditionals. Roughly a cross between decision tables and data flow graphs, they represent computation and decision-making orthogonally. They unify the full range of conditional constructs, from if statements through pattern matching to polymorphic predicate dispatch. Program logic is maintained in a declarative canonical form that enforces completeness and disjointness among choices. Schematic tables can be used either as a code specification/generation tool, or as a self-contained diagrammatic programming language. They give program logic the clarity of truth tables, and support high-level direct manipulation of that logic, avoiding much of the mental computation demanded by conventional conditionals.”
You can download the paper from the website:
No Ifs, Ands, or Buts: Uncovering the Simplicity of Conditionals Jonathan Edwards OOPSLA 2007. Download PDF (1.9 MB)
Unlike other papers reviewed so far in this Thursday theory series on AiGameDev.com, this research is pretty much a full programming language. Here’s how I think it would apply to game AI.
- Applicability to games: 8/10
- Games have many special cases, including custom pieces of logic that need to calculate values based on a set of inputs. Whether you use object-oriented programming or not, these are be a pain to create and maintain correctly. The example of calculating damage is only one of many. This kind of system could help resolve these problems.
- Usefulness for character AI: 7/10
- While this research helps get decisions right by making it easy to build conditionals, it does not help express sequential behavior — which is arguably even more important to game AI. So the ideas presented here would need complementing with some kind of linear scripting system.
- Simplicity to implement: 2/10
- The down side of this approach is that it’s still fringe technology. Understanding the ramifications of these ideas, building an editor and the underlying interpreter would take a long time.
All these ideas may take a while to find its way into game development, but the implications on object oriented programming are very profound. Anyone who’s tried to maintain large hierarchies of game objects will know how much hassle it can be to maintain the logic scattered in multiple places. Schematic tables could help by hiding the underlying complexity — at the cost of some modularity possibly.
A more practical tip for you today would be to use small tables more often to specify decisions, rather than having to build complex trees of unmaintainable if / then statements in your AI scripts. Do you think this is viable or is this a step backwards?
How useful do you think schematic tables and such visual editors are in practice for AI in games?