Fast Scripting - a pre-compiled approach
by Micheal Ireland
©2001, Airzone, Ireland Software.

Introduction

First off, I'm going to make some assumptions. You know a programming language (this idea should work in any, but I have it coded in VB), but it's a little object orientated. You know what scripting is - i.e. your game engine doing stuff on it's own accord. Whatever source code snippets I include in here will be in VB or psuedocode, but seriously, if you know C++ or Java then you'll have no trouble interperating it. Also, you'll probably find me a bit wordy, but it explains it all. Also, there won't be any copy / pasting of my hard earned source code into your projects - it will work better if you write this engine to your specs, not mine.

By "fast scripting" I don't mean quick to code - that's "lazy scripting". No, fast scripting is a way I dreampt up (as have many others, I dare say) that eliminates most parsing and syntax checking and tokenizing, and all the other joys of interpreted scripting. You see, that all takes CPU time. We're programming games here, and we're *always* using too much CPU time. But face it, somewhere in your game engine / editors you'll need a syntax checker for scripts and parsing and all that stuff. So why not delegate that responsibility to the script editor? When you're programming a script editor, I'll wager you're not so concerned about frame-rates and all the other fun stuff that separates the men from the boys. But how do we get rid of lexical parsing / tokenizing and stuff like that? My game engine has none of that, and my script editor has none of that either. Scripts are each only a few bytes at max so far - it's very compact (and I'm also using compression, but that's another story for another time), and the important thing is that my game engine reads and executes them, and it does it fast. Hence the name, "fast scripting".

The Script Anatomy

/me pulls out a surgeon's knife - let's open this up.
/me also spends too much time on IRC.

While I was tinkering around with making Assembly grahpics functions, I thought it was pretty simple:

Instruction Data.
Instruction Data.

You tell the CPU what you want done, and pass it data. The program was made up of many instructions.

Guess what! A script is a program written in the programming language you're about to make! So, wouldn't it be a reasonable idea to "borrow" the ASM idea for our own use?

A "Script" is made up of "Instructions". Instructions may or may not have "Data". Instructions are always followed by another Instruction, unless it's the last instruction.

I've found that the best way (after finding out the hard way) for me to represent this is to have a class called CScript, and a class called IInstruction. (You'll find I prefix the name of interface classes with an I, and general classes with a C)

IInstruction does nothing - it's an interface for all the different types of instructions you have. Each possible instruction has a class. My scripting language allows for things like "End Script", "Simple If", "Set Variable", "Show Window", and they are represented by the classes CEndScript, CSimpleIf, CSetVariable, and CShowWindow respectively. BTW, I have more than just these 4 :-P CEndScript implements (or extends if you want) IInstruction.

IInstruction has the following members:

PrevInstruction As IInstruction (the previous instruction executed)
NextInstruction As IInstruction (the next instruction to be executed)
InsID (I'll get to this later - it's an opcode)

IInstruction has the following methods:

Load( whatever_filing_system_here ) (loads the instruction data from a file)
Save( whatever_filing_system_here ) (same as above, just opposite!)
Run() (I wonder...)
Whatever else you deem necessary put in here.

CScript has the following members:

FirstInstruction As IInstruction (the first instruction)

CScript has the following methods:

Load( filename ) (loads the script into memory)
Save( filename ) (a/a)
New() (umm..)
Run() (this is hard too)

If you do not know what interface classes are, then learn! This will be hard to understand at the best of times, so I really don't want to imagine learning this stuff without knowing about interface classes.

You'll probably have to read that again, I'm hopeless at explaining things. But basically, the CScript class contains one linked list of IInstructions. It's all simple!

Making IInstruction do stuff

As I said before, IInstruction doesn't do stuff. So why this section?

For an example, I want the most basic instruction supported: End Script. Upon executing this command, the script will cease execution. End Script needs no data.

I will therefore make a class called CEndScript. It will implement IInstruction. Therefore, you will have to implement all the functionality / state of IInstruction in CEndScript. PrevInstruction, NextInstruction, etc will always remain references to IInstruction classes, because this is how we keep all the instructions compatable with each other.

Now, when loading the scripts, how do we differentiate an End Script from another command? Well, how does a CPU recgonise what to do? We use an OpCode. I find that if you use a 32-bit opcode, you'll give your scripting language a maximum library of 4.2 billion different types of instructions. I tend to use the OpCode 0 to mean a read error. If ever the script parser reads the opcode 0 from a file, abort, and crash Windows while you're at it! So I'll use the OpCode = 1 to signify an End Script.

CScript_Open( filename )
  Declare OpCode as 32bit Integer
  Declare TempIns as IInstruction
  Open the file.
  While Not Eof
    Read OpCode from file
    '// When OpCode = 1, create CEndScript
    Set Temp = New (whichever class signified by the opcode)
    Temp.Load( file_handle )
    Append Temp to be the last element in the linked list.
  EndWhile
  Close file
End Method

This is *very* simplified. No support for child objects.

There are ways to make this simple to code, but I'll let you work this out. The important thing to note here is that we're loading the *whole* script in at once - it's not streamed from the disk as it's executing. You might wish to stream it, but that's up to you to implement.

Child Instructions

First, make sure you understand the previous section. This one extends on it.

In the last section I introduced a linear script format, in the form of a linked list. Now, you're more than likely going to have to make an If type instruction. I have Simple If, Compound If, and a Switch (Select Case in VB) which implement all I'll ever want when it comes to decisions. You might decide to be clever and inplement proper looping as well. I'm implementing a Pre-test, Post-test and a For loop in my language. How can we implement this easilly in our language though?

Let me write some Visual Basic code here:

Sub DoIt()
  Debug.Print "Doing it!"
  If Game.Flags(456) < 344 Then
    Debug.Print "We had best make the flag up to 344!"
    For Counter = Game.Flags(456) To 344
        Game.Flags(456) = Game.Flags(456) + 1
    Next Counter
  Else
    Debug.Print "All is well."
  End If
End Sub

I'll not guarantee that'll work, since I just wrote it, but you'll see several layers of indenting. If you know anything about programming, you'll be indenting your code - it's much easiser to read. And it also makes it much easier to work out a way to implement something similar in our language. Could we not say that the incrementation of Game.Flags(456) is a child instruction of the For loop? And what about that If statement. I'd like to say that it's got 2 children - the True and the False case. A Switch could have any number of children instructions.

Let's add 3 extra members to IInstruction:

NumChildren As 32bit Integer (The number of child branches)
ParentInstruction As IInstruction (The parent instruction of this instruction)
Child() As IInstruction (An array of child instructions - NumChildren tells how many there are.)

First, let's get this Child() bit straight. If the above source code were my language, then the If instruction would have 2 children. One would be Debug.Print "We had....." and the other would be Debug.Print "All...". What about the For instruction you say? Well, it's the NextInstruction of Child(0).. In more of a programming sense: CIf.Child(0).NextInstruction.

About the ParentInstruction: I find it beneficial to be able to move around my data structures easilly. PrevInstruction takes you to the previously executed instruction (which is mainly for the editor's use), and ParentInstruction takes you back up the tree. It gives a really fast way to escape from the "nesting" of our instructions. It also allows for a instruction called CToStartOfLoop - this is like a continue in c? Trust me, it's very little extra effort, and it makes a lot easier later on. And the ParentInstruction will be null or Nothing (in VB) if the instruction is in the highest level of the script (i.e. anything in line with CScript.FirstInstruction), but you already knew that.

I'll leave it up to you to implement the decision and looping specifics. My language doesn't have ending instructions for these types of instructions (i.e. no End If, End Switch, End While, Next Counter, etc). Whenever an instruction's NextInstruction is Nothing, it's eary to use the ParentInstruction to go back to the start of the loop, if necessary (I also have a ParentsChild integer in IInstruction to tell the instruction which child it belongs in.. It saves fumbling around).

How can this be loaded from a file? Recursion is always an option for this. VB people: beware of stack overflows! Another part of my game engine *used to* use recursion, and after loading about 3,500 maps, it'd die. I'm told on good authority that this is less of a problem in C++, but I dare say if you tried to load a script with 60,000 instructions in it, the stack would overflow. With that in consideration, you could run the risk of having some smart-arse trying to make your program crash that way, or you could use a single method to load it using a few loops, a user-implemented stack, temporary object references, and a few other tricks. I use that way, but not because I'm concerned about stack overflows (seriously, who in their right mind would want to have to add 4,000 instructions using RPG Studio??), but because I find the code runs faster than a similar recursive algorithm. This might not be the case in C++. Recursion is a lot easier than the alternative though. And chances are, there are many other ways of doing this. I'm not teaching you how to program, so you can work this one out yourself :-)

Instruction data / parameters

Ok, you've implemented CMessageBox. It will show a message box in-game, and it will display some text on it. Where does the text come from?

CMessageBox has a variable implemented in it called Msg. It's a String. In the Load method of CMessageBox, all you have to do is load the string from the file handle.

Read the linked source code to Script_Teleport.txt. You should see how I implemented all this stuff.. It's a bit messy, but I'm still developing it. I might take this oppotunity to elaborate on a possible file format:

Load OpCode (create appropriate object and execute the load method)
Load each data item in sequence (I like to store the length of a string before storing the string. It tells me when I'm loading how long the string buffer should be)
For instructions with a variable child count, load the child count. (Switches come to mind here)
For each child instruction, load a boolean to see if that child is null / Empty. Remember, just because an Instruction can have a child instruction, it doesn't mean there has to be one.
Load each child instruction (recursion is handy here)
Load a boolean to see if there is a NextInstruction (False means Null, and that is the end of the branch in the tree)

Ok, that was simple :-)

The Script Editor

In "Fast Scripting" the script editor is very important! There are 2 ways you can do this: Write the scripts in a text file and write a script compiler, or combine them. I have a point-n-click editor. It's not the easiest thing to do, but it's very easy for the user to write scripts, and when I get all my code bug-free (there's still 1 obscure bug), it'll be impossible to have syntax errors, unless you try binary hacking (and since my scripts are compressed, hex editing the code will render the script unloadable).

I'll not cover having a seperate compiler. This scripting format doesn't lend itself to such editors in the hands of "novices". An all-in-1 editor works very well. Here is an old screen dump of my script editor. Never mind the Audio Player - Audio's important for games, but this is about scripts! :-P Seriously, this is how simple the user interface can be. And it's even more powerful than some of my competitors "compiling" editors. Those 2 arrow buttons on the side move the currently selected instruction up or down in the script. The main area is a standard list box control. In VB, it's increadibly easy to make. It's also a custom control, so if I wanted, I could make a window capable of editing 10 scripts simultaneously. Of all things, the up and down buttons are the hardest to do, and it's with those I have my bug.

Script Execution / Multitasking

I've covered loading in some depth. Saving is just the opposite to loading. Running is even easier still. Each Instruction implements a Run method, because it's part of the IInstruction interface. Therefore, it's the responsibility of each instruction to execite itself. The Run() method in CScript just starts the execution of FirstInstruction.Run(), and also just keeps the script executing in sequence.

Normally, this is fine, but occasionally you will need to have a script running all the time - kinda like having a thread. VB can't multi-thread as such, so we VB'ers have to improvise. Even so, with multithreading, you need to be careful to keep it all in sync with the game engine. So, in my scripting language, I have implemented "foreground" scripts and "background" scripts. The only difference is a boolean variable being set, and they're handled slightly different in the game engine. A CScript can switch between these 2 states with a CSetForeground and a CSetBackground instruction.

I have allowed for a collection class called CBackgroundScripts, which holds CScripts. Basically, there's a section in the game engine that handles running of scripts. For a foreground script, they're just individual scripts being run in turn. For background scripts, you cycle through the elements in the collection and call the run method.

For a normal script, it starts at the start, and ends at the end. But for a backgrounding script, this doesn't always have to be the case, and in some cases, it would be impractical to script this way. Also, a typical situation would be to have a script looping in the background, providing advanced graphical / gameplay services (this is one possible way a user can extend your game engine to suit them a little better). But, we all know, a CPU can only process one thing at once, so if you send a script into a long loop required for those services, then your game engine is going to lock up. This is where you could use multi-threading in C++ or Java. Another good way to skirt this problem is to have an instruction called CDoOtherEvents - you guessed it VB'ers, a Doevents equavalent in your language. For all those who don't know what Doevents is, it's a command that pauses execution at that place and allows for the system to attend to other things, like the User Interface, etc. This is ideal in our scripting language - if we can get the CScript to pause at that instruction, and finish execution temporarily, and then use the Run method in CScript to pick it up again, then we're there. If you add a member in CScript called CurrentInstruction (type IInstruction) and set it to reference the CDoOtherEvents before jumping out of the script's execution cycle, and then resuming execution of the CurrentInstruction.NextInstruction, then you're set. I'll let you work out all the little technicalities, but that's the easiest and most effective way I imagine it to be.

Be careful though - although I havn't tested this, if you process all the backgrounded scripts every cycle of the game engine, you are liable to drop your FPS. This can be addressed by executing them every 5 cycles or so.

Conclusion

Well, that's the framework I suggest for a nice, flexible, and fast scripting system. It hasn't failed me sofar, and even my more primitave version (not object orientated in the slightest) worked ok - just looping was out of the question without impolementing a Goto instruction, which is, as we all know, evil :-)

Feel free to use this model in anything you write, and to adapt it to your needs. If you come up with a killer concept that really enhances the model, drop me a line: airzone@rpgmaker.net

Discuss this article in the forums

Date this article was posted to GameDev.net: 5/31/2001
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
Scripting Languages