Tuesday, June 26, 2012

Custom Scripting Language

Not so long ago I helped create a game called Ancient Forest and Grumpy Monsters. We wanted a very easy way of creating levels for our game, and so one of our programmers named Colton created a very useful map editor, which we actually shipped along with our final product for consumer use. However our team also wanted a way to create interactive events within the levels without writing a lot of repetitive C code. The goal was to create something that would also potentially allow consumers to use for creating their own scenarios as well. Note: For this game we used only C (a limitation on the semester project)! Another limitation of the project was that we cannot use any scripting language unless we create one ourselves. I don't remember the reasoning behind this, but I believe it was to keep the scope of projects to a minimum.


We decided to create an event based scripting language for our game. The functionality of the scripting language allows the user to write scripts in plaintext and load the instructions from the text during run-time. This allowed for very rapid level development and gameplay testing! A designer can easily create a script for a level, and then load the level from the game without compiling any code at all. Sadly we didn't actually utilize the tool to its full potential during development, but it was an interesting learning experience to create the tool nonetheless.


There are a few different parts of the scripting language that work together to create the functionality used in our levels: read in the script from the text file; parse the text input into usable data structures.


In order to parse the text I decided to use a simple state machine. The state machine works by passing it a single token at a time. The state machine then returns some form of output depending on what token was passed to it and at what state the machine was in. This let me define trees of different action paths to follow, while having those actions stay rather modular. Here's a diagram of example functionality of such a state machine:




In this state machine it only responds to a few different tokens: Start; End; Red; Blue. In this example all other tokens received would result in a return of NULL and no action would be taken. The best thing about this setup is it is context sensitive. I can receive the same token at different points in the tree path (this example tree has only two branches) and take different actions.


In written code the state machine was actually just one very large switch statement, with the different cases being a large enumeration.  Here's some example code of what a portion of the state manager can look like:

PARSE_STATE ParseStateManager( char *token )
{
  switch( ParseState )
  {
  case PARSE_START:
    if(strcmp( token, "START" ) == EQUAL_TO)
    {
      ParseState = PARSE_EVENT_LIST;
    }
    else
    {
      return PARSE_NONE;
    }
    break;
  case PARSE_EVENT_LIST:
    if(strcmp( token, "EVENT 1" ) == EQUAL_TO)
    {
      ...
      do stuff
      ...
    }
    else
    {
      return PARSE_NONE;
    }
    break;
}

Reading in the data should be separated as much as possible from the state machine and the handling/creating of data structures. This way code created can possibly be reused in the future. Luckily I didn't have to write a function to retrieve a token from a text file, as strtok is apart of the standard C library. I was on a very tight time-budget and the creation of my own tokenizer would have likely doubled the dev time of the entire scripting language system.


During the file read I used a single call to fgets to read in the entire file's contents all at once and place it into a buffer. I would then call strtok on the buffer created until the end of the buffer had been reached.


Now for the most interesting part! The interface and implementation of the events within the scripting language. We used structures for all of the different objects, and with the use of void pointers and function pointers it was fairly easy to design an interesting interface. Here's a few different structure definitions used:


typedef struct _CONDITION
{
  CONDITION_ID ID; // The type of condition
  void *param; // The condition's parameters
} CONDITION_;

typedef struct _ACTION
{
  ACTION_ID ID; // The type of action
  BOOL active;          // Inactive or not
  void *param; // The action's parameters
} ACTION_;

typedef struct _EVENT
{
  VALUE numConditions;
  CONDITION_ *conditions;
  VALUE numActions;
  ACTION_ *actions;
  PRESERVE_COUNT preserveCount;  // The amount of times this event will fire
} EVENT_;


As you can see we created an event object which is comprised of conditions and actions. The idea is that while the game is running it holds a list of events. This list is traversed and whenever an active event is found (preserve count was not zero) it then would check all of the conditions. If each condition were true then the actions would then be taken. After all actions are complete the preserve count of the event would be decremented by one.


The definitions of conditions and actions were generalized structures with void pointers called param. This param would point to a data structure that represents some sort of condition or action. In order to tell what sort of data the void pointer is pointing to each condition and action has a data member of an ID (from an enumeration). The param pointer can by typecasted into the particular type of condition or action it is pointing to.


There's one type of action we created which is called "Create unit at location". This structure looked like so:

typedef struct _CREATE_UNIT_AT
{
  OBJECT_TYPE unit_id; // The type of unit to create
  LOCATION_ location1; // The tile to create at
} CREATE_UNIT_AT_;

The only data that this structure holds is the parameters necessary to call a function. So the conditions list within an event is just a list of parameters, and each parameter is meant to go to a corresponding function. So each condition and each action type actually have a corresponding function that receives parameters held within events. In the above example, there would be an action (perhaps called CREATE_UNIT_AT) that would receive a _CREATE_UNIT_AT structure as its parameter. The same works with conditions except the return type for conditions is boolean, as it's simply testing to see if a series of checks pass or not.


The state machine, talked about earlier, is what actually creates the and fills out these data structures of conditions, actions, and events depending on what tokens are passed to it from the input file.


And that's that! This system reads in a text file of instructions of specific syntax as defined by the developer. This data from the file is then parsed by a tokenizer and state machine and translated into data structures. These data structures are comprised of an array of events. Each event holds an array of conditions and actions. During run-time the game traverses the array of events and checks the conditions of all active events. If all conditions of a particular event pass (return boolean true), then each action in the event's array of actions is called.


Using this condition and action based scripting language we were able to create loads of different dynamic and interactive events within our levels in a very easy to use and time-efficient manner.


Here's a final example of a functional scripting file:

START NUM_EVENTS: 4

EVENT PRESERVE 1
  NUM_CONDITIONS: 1
    CONDITION UNIT_EXIST
      AT_LEAST 5 PLAYER_DEFTREE_OBJ
  NUM_ACTIONS: 2
    ACTION CREATE_UNIT_AT
      ENEMY_WIZARDTOWER_OBJ 8 12
    ACTION CREATE_UNIT_AT
      ENEMY_WIZARDTOWER_OBJ 11 8

EVENT PRESERVE 1
  NUM_CONDITIONS: 1
    CONDITION UNIT_EXIST
      AT_LEAST 5 PLAYER_OFFTREE_OBJ
  NUM_ACTIONS: 2
    ACTION CREATE_UNIT_AT
      ENEMY_TOWER_OBJ 8 14
    ACTION CREATE_UNIT_AT
      ENEMY_TOWER_OBJ 12 11

EVENT PRESERVE 1
  NUM_CONDITIONS: 1
    CONDITION UNIT_EXIST_AT
      AT_LEAST 1 PLAYER_REGTREE_OBJ 2 12 5 14
  NUM_ACTIONS: 1
    ACTION CREATE_UNIT_AT
      ENEMY_TOWER_OBJ 7 15

EVENT PRESERVE 1
  NUM_CONDITIONS: 1
    CONDITION UNIT_EXIST_AT
      AT_LEAST 1 PLAYER_REGTREE_OBJ 12 1 14 3
  NUM_ACTIONS: 1
    ACTION CREATE_UNIT_AT
      ENEMY_TOWER_OBJ 14 5

END

This file creates four events. Altogether these events create opposing towers if the player places tree structures at certain areas during gameplay. This simulates the opponent expanding their forces in reaction to the player taking specific actions.


You might have noticed that the writer of this file would have to manually write down how many actions are in an event, how many conditions are in an event, and how many events in total there are. This is so so that the state machine parsing the text file's data can allocate the correct amount of memory space before translating the script's contents of how to fill in the memory allocated. It would be entirely possible to add the feature to the parser that checks the size of everything before translating, though this feature would have taken a lot of time during the development of our project, and the returns were just not great enough to warrant such. Consequently the scripting language can easily cause crashes if any of the numbers of events, conditions, or actions are incorrect.


There was also little to no error checking implemented within the scripting language. Error checking would be handled by the state machine if it were to be created.


The start and end tokens are also a bit redundant, as detecting whether or not you're at the beginning or end of the input file can be automated, however the requirement of having START and END within the script made for development of the scripting language system much faster. Time was very valuable when this game was being made!


There was however support for comments within the file. Comments are handled by the state machine. We decided that whenever a # character is tokenized, all subsequent tokens are ignored and no actions are to be taken until another # token is found. This lets you encapsulate blocks of multi-line text within comment characters. These act like old C-style comments :)

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.