SCXML in Torque

Hello; I'm Greg Beauchesne. I guess you could say I'm new here, although I'm not new to Torque development. I've worked a great deal with TGE at work, so I'm quite familiar with the underlying code.

Having recently purchased TGB Pro for personal use, it occurred to me that there didn't seem to be a good state machine implementation for what I wanted to do.

At work, I also use Qt, and so I keep up on the various developments that go on there. One such development is this one, detailing their efforts to add support for SCXML to Qt. SCXML is the W3C's effort to come up with a standard state machine language using XML. This intrigued me, as it seems like it could be implemented for Torque to great effect.

SCXML is based on Harel statechart semantics. Harel statecharts are a visual representation of state machines that add some nice features to reduce the complexity of a traditional state machine, which normally requires that every combination of parameters gets its own unique state. Here are some of the things found in Harel statecharts and supported by SCXML:

• Compound states - States within states. Transitions out from a parent state also apply to all its children. For example, consider most platformer games: Characters can only jump when they're on the ground, and not while they're in the air. But on the ground, a character could be walking, running, crouching, or attacking, and in the air, a character could be rising, falling, or performing a mid-air attack. With a compound state, all of these can be grouped into an "on the ground" or "in the air" state, and then if a "jump" transition were placed in the "on the ground" state, it would mean that the character could jump from on the ground regardless of what he or she was doing.
• Parallel states - Not parallel in the sense of multithreaded, but parallel in that it's basically like multiple state machines running at the same time and reacting to the same events. This is good for splitting the logic from the animation in the same state machine, or controlling multiple animated sprites and having them act as one.
• History pseudo-states - The state machine itself can automatically keep track of the state or states it was in in a specific sub-section of the machine and then return to it later.

SCXML is designed in a mostly scripting language-agnostic manner. It seems their primary target is ECMAScript (JavaScript, more or less), but it can be used with other scripting languages as well. And what will we use here? TorqueScript, of course.

SCXML is not yet an official W3C recommendation. The SCXML specification is still evolving, so some of the details are not nailed down. Caveat emptor.

So, with that in mind, I set off putting together an SCXML state machine for Torque.

The first problem was the XML part. Being a W3C project, it makes use of XML namespaces, and Torque's XML parser didn't appear to have namespace support. But furthermore, I didn't want to read XML in Torque anyway. There's a lot of overhead in that, and if I was reading Torque script code out of it, it would mean I would have to use eval(). I have a strong aversion to eval()-type constructs in any scripting language unless absolutely necessary, as it means we are wasting time compiling things that in many cases could be precompiled. As far as I know, Torque does not have a means of precompiling a piece of dynamic code and then saving it for later short of writing it out to a disk file and then exec()ing it.

So, what was the solution? Script code generation. The language? XSLT. XSLT is another W3C language, and this one's an official recommendation. XSLT is XML, and it specializes in transforming XML to XML or XML to text. It's supported by both Internet Explorer and Firefox for rendering XML documents as HTML. In fact, if you're running Windows and have one of Microsoft's more recent MSXML packages installed, you probably already have an XSLT processor installed without even realizing it (go to a command prompt and type "msxsl" -- this is the same engine Internet Explorer uses).

In any case, for this to work, I would need to write an XSLT script that could convert SCXML to TorqueScript. There were a few bumps, but overall it was pretty straightforward.

The next problem would be actually implementing SCXML properly. Thankfully, the specification has an implementation algorithm right at the bottom. The algorithm in the spec assumes, however, that the state machine is running in a standalone environment, which is no good for Torque, because there happens to be a game running at the same time which can't be held back. So I had to do some rearranging to make it suitable for in-game use.

Initially I created an implementation of SCXML using only TorqueScript. The XSLT script was responsible for dividing the state and transition data into many different scripted functions that had precalculated as much data as possible so that it wouldn't have to be processed by the script itself during the main execution phase. The scripted implementation worked wonderfully, with full support for compound and parallel states, except for the fact that it ended up being far too slow. It actually probably could have been fast enough to be useful, but it turns out that calling scripted functions in Torque has a severe overhead penalty (more on that in the future) and inlining a lot of functions via the magic of copy and paste did not help enough to overcome this.

Which brings me to today. I'm now working on a C++ version of the state machine implementation that I'm hoping will scream compared to the scripted one. The way it works is that you build up the state machine definition using Torque objects, and then when the first instance of the machine is created, the state machine is compiled into an optimized form. The C++ implementation currently supports parallel and compound states, as the scripted one did, and soon I'll add support for history states.

Initial results look promising. Having been burned above by the TorqueScript function call overhead, I've put additional effort into making sure the scripted callbacks aren't called upon more than they have to be. All of the multi-state logic and such is handled by the C++ code, and the only thing scripts do is handle the state entry and exit code, transition code, and transition guard conditions.

----

There are some other benefits to using SCXML. As I mentioned above, I use XSLT to translate an SCXML file into TorqueScript. Like many other scripted languages, XSLT has the ability for scripts to include one another. XSLT is also a rule-based language. That makes it very easy to add new constructs that might be useful. For example, in my implementation, I have a core XSLT script which only converts the SCXML into TorqueScript and does nothing else. But then I have a second script which includes the first and adds some rules that A) turn the script into a full-on behavior script that can be used in the TGB editor, and B) scan the file for all sprite animations used and automatically add behavior template entries for them.

Second, as I also mentioned above, SCXML is an ongoing W3C project. Although not a recommendation yet, when it does become a recommendation, you can probably expect many people to create support tools for it. The Apache Commons project would be a good example of what's happening now. I also understand that IBM has created an SCXML visual statechart editor for Rational Architect (though I don't think that's free), and that Eclipse may or may not have some SCXML support.

I have also examined the possibility of using a free UML tool with state chart support such as ArgoUML or StarUML to visually create state machines that could be used in Torque. If I'm not mistaken, they both use some form of XML as their project storage format, and that could mean XSLT to the rescue once again. Nothing yet, though -- the core stuff first.

----

I will say up front that my intention is to eventually sell this as an add-on in the GG store once I nail down some of the finer points, but either way, I'm looking to see what kind of interest others might have in this little project. Being in C++ does mean it will require a Torque source code license to use it, at least until/unless that SimComponent stuff I'm hearing about comes to fruition. I have written it for TGB, but I'm hoping it will be usable with any of the Torque variants.