Showing posts with label Game Programming. Show all posts
Showing posts with label Game Programming. Show all posts

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 :)

Ancient Forest and Grumpy Monsters

Hello all! I've been away for a little while over the summer. This summer is the one that came right after my Freshman year, and so I wasn't able to get an internship. This means that this summer is likely going to be the last one I'll ever have to really just relax. So I took a month or two off from programming and did some other things. I've been working a lot at hotkeyit.com creating content.


I've finally have a finished product to show off from my second semester at DigiPen! The game is called: Ancient Forest and Grumpy Monsters. The whole idea is to as an ancient magical forest to fight off a faction of Grumpy Monsters! Placing down tree structures is the main mechanic. These structures act as defensive towers, spawn creatures of the forest, and spread purification onto the land to counteract the spreading corruption of the Grumpy Monsters.


Here's a little info on the team qMopey that created the game:

The team, qMopey, is a team of four programmers that are currently attending DigiPen IT that are developing the game Ancient Forest and Grumpy Monsters. This game is our second semester project. The game was coded in C using a DigiPen in-house DirectX library. The only functionality used from this library was loading images into memory, and displaying them on screen -even mesh creation is handled by our team. The team consists of:
  • Anh Do
  • Kevin Giang
  • Colton DeGraw
  • Randy Gaul (CecilSunkure)
Gameplay Screenshot of corruption and purified land.
In order to gain resources you place any structure underneath a sun tile! Each tree under a sun tile produces a single extra income point.


Aren't the sunrays absolutely adorable?
As the player progresses through the campaign levels new monsters and technologies are introduced. Here are a couple images of some of the various units on the Grumpy Monster's unit roster:
 
Here's the download link to the actual game's installer:
LINK

RANDOM TRIVIA:
  • 21786 lines of code
  • 220 source files
  • 1 million hours of work (joking, but it felt like 1 million)
  • All art was created by programmers on the team who actually get no class credit for the art
  • Anh Do is terrible at the game Lol

Wednesday, February 22, 2012

Basic 2D Vector Physics: Acceleration, Orientation and Friction

This post aims at covering the basics of 2D vector physics, that of which can be used in application to create something like this Asteroids project for my CS230 class.



The simplest way I know of to move an image across the screen over time is by using a static velocity and apply it to the the position of an image every time-step:

pos += vel * dt;

dt should be calculated every frame loop and passed to this equation, this way your displacement will be time-based instead of frame-based. To calculate dt you can use the following flowchart:




In order to have variable velocity you can apply the same idea from our displacement (position) equation. To change velocity over time and have acceleration and deceleration you can use:

vel += accel * dt;

Pretty simple! However in order to apply this in programming you'll break up the x and y velocities into separate values like so:

pos.x += vel.x * dt;
pos.yx += vel.y * dt;
vel.x += accel.x * dt;
vel.y += accel.y * dt;

Now what about turning, and a sense of orientation? It's no use if your object can only go in a single line, which is all the above equations will support if implemented alone. Your object should have a data member to hold it's orientation in radians. If you don't really have a mental grasp of radians, that's fine. Take a look at the unit circle: link. In order to know the value of any given 2D direction relative to a standard axis (x and y plane not rotated or anything) just look on the graph in that direction. For example straight upward in radians is pi / 2. Straight downwards is 3 * pi / 2. Very simple. The unit circle is just a way of representing directions as a value. The range of this value is 0 through 2 * pi.

You can initialize your object's direction value with a preset or randomized value within the range of zero through 2 * pi. However it's easier to implement calculations in 2D if you set your range of values to pi to -pi (see below psuedo code for reason why). This means, for example, a full 360 degree angle is represented by either zero or -pi. The downward direction, for example, would be -pi / 2. Once you have this set up, you can easily use this radians orientation value to find a direction vector for your object. A direction vector is a vector whose length is 1, which allows you as a programmer to multiply it by a value and easily get a vector in a specific direction of a specific length.

For example say your object has an x velocity of 6 and  y velocity of 10. Every timestep you'll move by a factor of 6 to the right and up by 10. This is all good, and the distance the ship will cover can be found with the Pythagorean theorem: sqrt( 6^2 + 10^2 ). But, what if you want the ship to move 5 units in a direction per timestep? What if you want to be able to easily move your object around in any direction by 5 units per timestep? This is going to be pretty difficult without doing what's called normalization. Normalizing a vector is the process of taking a direction vector, like (6, 10) and generating a vector that points in the exact same direction, whose value is equal to 1.

If you are able to find a direction vector of the direction your object is going, you can easily multiply the x and y components by 5, and achieve your goal. If your direction vector is derived from your radians orientation (like I said we'd do), then you can get the direction vector no matter what direction you are going, all the while you can modify your orientation value however you like! In order to get your normalized direction vector from your angle of orientation, just use:

dirVect.x = cos( radianOrientation );
dirVect.y = sin( radianOrientation );

You now know all the necessary ideas needed to implement some simple 2D vector physics! You can rotate your object's orientation with addition/subtraction on your radians value, and then move your ship according to the angle of orientation by a specific velocity value, all the while updating your velocity with a constant acceleration value.

Here's a (psuedo) code example:

// Find current direction vector
dirVect.x = cos( radianOrientation );
dirVect.y = sin( radianOrientation );

// Apply forward acceleration
if(keypress( UP ))

  vel.x += ACCELERATION_FORWARD * dirVect.x * dt;
  vel.y += ACCELERATION_FORWARD * dirVect.y * dt;
  // Simulate friction
  vel.x *= .99
  vel.y *= .99


// Apply backward acceleration (negative forward)
if(keypress( DOWN ))
  vel.x += ACCELERATION_BACKWARD * dirVect.x * dt;
  vel.y += ACCELERATION_BACKWARD * dirVect.y * dt;

  // Simulate friction
  vel.x *= .99
  vel.y *= .99


// Add a value scaled by dt to rotate orientation
if(keypress( LEFT ))
  radianOrientation += ROTATION_SPEED * dt;
  // Bound checking for pi and -pi
  if radianOrientation > PI

    radianOrientation = -PI
  else if radianOrientation < -PI
    radianOrientation = PI


// Subtract a value scaled by dt to rotate orientation
if(keypress( RIGHT ))
  radianOrientation -= ROTATION_SPEED * dt;
  // Bound checking for pi and -pi
  if radianOrientation > PI
    radianOrientation = -PI
  else if radianOrientation < -PI
    radianOrientation = PI


// Update position with our new calculated values
pos.x += vel.x * dt
pos.y += vel.y * dt

Another thing to try to explain is the reason for the range of pi to -pi. Using a range of pi to -pi allows for easy calculations because it makes the lower half of the unit circle negative, which means you can directly apply resulting values from sin and cos onto your velocity/displacement, and move your image in all four directions (up, down, left, and right).

Now, what if you need to solve for the angle between two points? This could be useful for homing missiles, or AI. Knowing the angle between an enemy and the player, for instance, could be used to let the enemy know which direction to go from there. In order to solve for the angle between two points I used atan2:

angle = atan2( player.y - enemy.y, player.x - enemy.x )

This lets me find the angle between two points, namely between an enemy object and the player. You can then use this result and compare it with the angle of orientation of the enemy in order to deduce of the enemy should turn clockwise or counterclockwise, or anything else you'd want!

You may have noticed those lines that multiply the velocity by .99 after the update calculation was made. This actually simulates friction. The higher the velocity gets the greater the reduction per timestep! This will allow your object to accelerate slower the faster it goes, until it reaches an equilibrium. It should also seem to float friction-less at slower speeds. You can use a larger or smaller value for different amounts of simulated friction.

And there you have it -all the essential concepts required to implement a game using simple 2D vector physics!