Tuesday, July 24, 2012

Scripting Languages for Games - the good, the bad, and the appalling

Having worked on a lot of games, I've also encountered and worked with a lot of scripting languages embedded within games. Here's a list of a few of the ones that I have worked with:

  • SAGA and SAGA 2 (Scripts for Animated Graphic Adventures), my own language which I created for Inherit the Earth and Faery Tale Adventure 2.
  • Lua, a lightweight general purpose language for embedding, used in many games including World of Warcraft
  • Edith, the scripting language used for The Sims and The Sims 2.
  • Swarm, a particle system language developed by Andrew Willmott at Electronic Arts, used in Sim City 4, Sims 2, Spore, and many other EA games.
  • Edibles, a scripting language created by PostLinear Entertainment (1998).
  • UnrealScript, the scripting language for the Unreal game engine.
Some of these languages were a pleasure to work with - tight, well designed languages that provided clear benefits to the game development process. Lua and Swarm are both shining examples of this.

On the other hand, some of these languages were not so wonderful - poorly designed and cumbersome to work with.

And then there is a third category - cases where the game developers shouldn't have used a scripting language at all. The Sim City 4 city advisor system comes to mind - there was no reason to use a general purpose scripting language for this, the advisor messages could have been stored as text string resources with far less complexity.

Imperative Scripting Languages


Another observation is that most of these languages aren't terribly innovative as languages. With the exception of Swarm, all of the above languages are fairly standard imperative programming languages, not much different from BASIC, Pascal or JavaScript.

Take Edith for example. Edith's main innovation was that it was a "graphical" programming language, where game content designers could place functional blocks on the page and wire them together. Semantically, however, these diagrams were nothing more than flowcharts - one of the least expressive forms of programming known to computer science. As one developer put it "Edith is basically Assembly language with the user interface of LEGO Mindstorms".

UnrealScript had a built-in "state machine" control flow construct - but the same thing could have been done using a conventional switch statement with almost the same number of lines of code.

Lua, which is the most general purpose language on the list, also has the largest number of innovative language features - for example, Lua supports continuations, which is a powerful way to deal with asynchronous processes. But for the most part, there's not much difference between what you can do in Lua and what you can do in Python.

In general, there is very little that can be expressed in these languages that cannot be expressed in C++ or Java or Python just as easily. Which leads to the obvious question - what's the benefit of using these languages instead of coding the game logic in C++? Why go through all the trouble of embedding a language in the first place?

The answer lies not in the language syntax, but rather in it's compilation and runtime environment. These embedded languages all have three major advantages over C++:
  • Compilation is very fast.
  • Individual modules can be recompiled without recompiling and re-linking all other modules.
  • Recompiled modules can be dynamically loaded into a running version of the game without having to restart it.
This means that the iterative development cycle is extremely fast. Instead of waiting 5 minutes for the program to compile and link - which is the experience of the typical C++ developer - the programmer using these script languages can have the new behavior manifest within the game within seconds after they hit "save" in their editor.

Another benefit is that the complexity of these languages is often much lower than the language that the game engine is written in, so that game companies can hire less skilled (and less expensive) staff to create the game content with a minimum of training. This means that the programming staff for a game tends to be divided into two separate "castes" - software engineers and "scripters".

Although one might be tempted to think of scripters as being on a somewhat lower level than the software engineers, in many cases the job of a scripter was just as challenging and demanding as any. For example, one of my experiences working on Faery Tale 2 was that scripters would discover bugs in the underlying game engine, and being impatient with the slow pace of bug fixes, would write scripts that were essentially workarounds for those bugs.

Non-imperative languages: Swarm


Now I want to talk a bit about Swarm, because it is so different from all the others. Swarm is not an imperative language - there is no flow of control, no "if" statements or conditional branches, no "for" loops or iteration statements, and so on. However, even without these language constructs, it can be used to specify complex behavior.

Swarm is a declarative language for describing particle system. Particles are visual effects like sparks, smoke, water droplets, bullets, clouds, dust, and other entities that typically appear in large swarms with short lifetimes. A particle system consists of an emitter - an object that generates particles - and a particle specification, that is a description of the type of particles that the emitter generates.

An emitter will typically have properties such as emission rate (how fast particles are generated), a delay time before the first particle is emitted, a duration, and a specification for the initial trajectory of the particles. For example, you can have omnidirectional emitters that emit particles in all directions, cone-shaped emitters, square emitters, and so on.

Particles generated by a given emitter have a set of properties, such as:

  • color
  • transparency
  • size
  • velocity
  • duration (how long the particle lasts)
  • whether the particle as affected by gravity, wind, or other forces
  • whether the particle can collide with terrain, buildings, characters, or other particles
  • whether the particle is displayed using a 2D image or a 3D model
  • whether the particle's orientation is aligned with it's trajectory or with the player's view
...and so on. Virtually all of these properties can be specified as functions of time - such as a particle that starts out opaque and slowly becomes transparent. And virtually all of these properties can have a random component added to them as well.

In addition, particles have conditions which can trigger actions when a particular event occurs. For example, a particle representing a bomb or grenade could have a trigger condition when the particle collides with a surface or with the ground. The triggered action could be to create a new particle emitter representing the resulting explosion.

All of the emitters, particles, and trigger actions can be specified within the Swarm source files. Complex behaviors are specified by setting up chains of effects - a particle of type A might create an emitter of type B when a certain condition is reached, and the particles emitted by B might create a new particles of type C, and so on.

For example, one artist on Sim City 4 (Ocean Quigley) created a complex alien invasion script with a giant robot descending from the skies on a blast of rocket jets who then attacked the city with flying discs of destruction, and then blasted back off into space - and all of this was done with a single Swarm script, with no changes to the game engine!

Another impressive demo (which, alas, did not make it into the shipped game) consisted of a water erosion simulation. Andrew had added a new particle effect type which would cause a small depression in the terrain whenever it was struct by that particle. He could then create emitters which represented water sources emitting droplets of water, which would then flow downhill, eroding gullies and channels in the terrain.

If you think about particles as processes, then Swarm is a language of implicit parallelism - computation consists of lots of simple actions and behaviors going on simultaneously and asynchronously. And yet the language itself was so simple that it only took a few hours for a game artist to master it. In particular, artists did not need to learn the complex concepts of flow-of-control, recursion, iteration, and other features of imperative programming languages.

Another cool feature of Swarm was the way it handled reloading of source files: The Swarm interpreter would use the filesystem API to be notified whenever any files in the source directory changed. So all an artist had to do was hit Ctrl-S in their text editor, and immediately see their changes take effect. Typically artists would arrange their desktop so that the text editor and the game window were both visible side-by-side.

Alternatives to scripting languages


Scripting languages are often used to specify the behavior of objects within the game. However, an alternative which has frequently proved successful is to treat objects as bundles of properties, where the presence or value of a property influences the object's behavior. This means that instead of editing text files, the game developer uses a property editor - a UI widget that allows them to set the values of these properties from within the game.

Typically a property editor widget is generic and is driven by a schema definition. The schema definition contains a description of all of the properties a given object is allowed to have, and what the types and allowable values of those properties are. The type of a property determines what type of editor to use to edit that property - so a "string" property will generate a text input box, while a "color" property will generate a color picker widget.

An example of this is the building definitions in Sim City 4. There were many hundreds of different types of buildings, and each one had many dozens of properties such as zoning requirements, electricity consumption, flammability, and so on. The content producers who entered this data needed to have lots of domain knowledge about cities in order to create a city simulation that was appropriately believable.

Of course, the interpretation of these properties - such as how the flammability property influences the chance of the building catching fire, and how quickly the fire would spread - were coded in C++ as part of the game engine. But from a game production standpoint, the benefits of using properties was the same kind of rapid development afforded by scripting languages, but with far less complexity.

Wednesday, July 11, 2012

Tart still on hiatus, but not dead

I've been greatly enjoying working on my Android game project lately - here are some screen shots of my most recent progress: https://plus.google.com/102501415818011616468/posts/51UaQviTyfM

Naturally this means that I haven't been doing any active coding on Tart for the past 8 months or so. However, that's not necessarily a bad thing. You see, even though I'm not actively working on it, it's still percolating in my subconscious mind, and occasionally an idea pops out. I've often found that some problems are best solved by stepping back and letting go for a while - sometimes the focus on solving a particularly vexing problem causes a kind of tunnel vision, while stepping back and getting some distance from the problem can lead to a new perspective on how to solve it - or even how to avoid it being a problem at all.

I thought I would take some time to jot down some of the issues that I have been thinking about.

I think that there are some aspects of Tart for which I never quite had a clear design idea. That is, there were certain parts of the language design where I figured that I would fill in the blanks at a later time, and looking back on the project I realize that those areas never did get filled in properly. Worse, I realize that some of those design aspects should have been designed up front rather than being put off until later, because the design choices affect the compiler's output in a fairly fundamental way.

1) Dynamic Linking

An example of this is dynamic linking of modules. Being able to divide an application into separately loadable chunks is fairly fundamental these days. Of course, at the lowest level we know how this is all supposed to work - the semantics of shared libraries and dynamic linking are well understood. But high-level languages need something more than just stitching together of linker symbols. They need to be able to do method calls across module boundaries, which means that the class definitions in the various modules must be interoperable. If two modules both import references to a particular class, those two class definitions must be combined somehow - otherwise you end up with two distinct classes that happen to have the same name, and instances of those classes will no longer be comparable, even though they may have identical values. 

In the past, the Tart compiler has generated a large quantity of static metadata for each class (dispatch tables, reflection data, GC stack maps, etc.), and relied on LLVM's linker to combine identical definitions. This is fine for static linking, but doesn't address the problem of dynamic linking at all. To address the problem of dynamic linking, a different approach is needed.

My current thinking is to replace a lot of the statically defined data structures with one or more global registries. For example, you would have a global registry of types. Whenever a module is loaded which contains a reference to a type, it would look it up in the registry (by name if it's a named type, by type expression otherwise), and if the type exists then the module would use the returned value as the type pointer. If the type does not exist, then the module will contain a static string that is a serialized description of the type that can be used to construct the actual type object. In other words, the first module that uses a given type gets to set the definition of that type, and all other modules will use that definition.

Note that the serialized description of the type could potentially be smaller than the instantiated type object, since there would be no need to store NULL pointers, and the serialized information could be compressed.

Of course, this can lead to problems if two modules have incompatible definitions of a type. For example, two modules might not agree on the length or structural layout of the type. To solve this problem, we need to be able to check if two type definitions are compatible. A strict check is fairly easy - see if the definitions are identical. But strict checks lead to brittleness and versioning hell - ideally you want some flex in the system so that a dependent module can be modified without recompiling the world.

A very flexible approach involves constructing the class dispatch tables at runtime instead of at compile time. This allows you to add or delete methods of a class and still remain compatible with old code. This works because the method offset into the dispatch table is no longer fixed at compile time, but calculated at runtime, so if the dispatch table slots change (because methods are added or removed) it won't break older code.

One can go even further and use a dispatch map rather than an array, similar to what Objective-C does: For each method signature, you generate (at runtime) a selector ID. Calling a method involves looking up that selector ID in a hash map, which returns the actual method pointer. While this does cause some additional overhead for certain kinds of method calls, other types of calls (such as calls through an interface) might potentially be sped up.

2) Debugging

Support for DWARF has been the bane of my existence, and has caused me more frustration than any other aspect of working on Tart. And to add insult to injury, almost all of the DWARF information is duplicative - that is, it's simply repeating information that's already present in the reflection data (such as a description of fields and methods of a class), but encoded differently.

I recently learned, however, that lldb (the LLVM debugger project) can potentially support custom debugging formats. That is, it would not be impossible to write an extension to lldb that directly parses the reflection data of a module instead of using DWARF.

This does mean, however, that source-level debugging would only work with lldb, and not gdb. That may be too much of a price to pay - for one thing, I like the Eclipse integration with gdb, and not being able to debug in Eclipse would be sad.

3) The name "Tart"

I've never been completely satisfied with the name "Tart", but unfortunately all the good names are taken. However, I'm concerned about possible confusion or conflation with "Dart", which is yet another language that Google is trying to promote.

Anyway, this is not a complete list of all the things I have been thinking about, but its late, and I shall leave the rest for another time.

--
-- Talin