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

Sunday, April 8, 2012

Object Oriented C: Class-like Structures

During my second semester while attending DigiPen IT I had to create a game in C. Since I wasn't allowed to use C++ until my Sophomore year for this game project I had to come up with a way of having strong organization during development. Class-like structures in C that allowed for polymorphism and inheritance were implemented! Virtual functions were also used to organize the functionalities of each type of object into a universal format!

In C the basic data structure is, well a structure. This is the tool used to create all objects. Here's the sort of thing you'd see for a typical game object:

typedef struct _GameObj
{

  int HP;
  Vector2D_ position;
  Image_ *image;
} GameObj_

As you can see there's data members for HP, the vector position and a pointer to the image.


There's a lot of limitations to a setup like this, however. It's difficult to write generalized functions that work on any type of game object you might have. You'd likely write different functions to handle your different types of game objects in order to handle the different needs of each type of object. Things start getting very difficult as complexity in your game objects arises, and the complexity of the project arises. There becomes a need for a higher form of organization in order to keep development moving along steadily.


A solution is to add in an enumeration type to the game object, so the GameObj_ struct becomes a generalized structure. This would allow you to write generalized functions for common actions, such as updating position, or damaging units. Although it isn't a good idea to have a singular structure as your only game object. You'd have to place everything that every type of object in your entire project would require into this single structure, and it'd be very hectic and waste a lot of memory, as some objects would not use data members other objects would. You could then split your GameObj_ structure into various different structure definitions for your different types of objects. This would allow you to write separate functions for different types of objects, and you could cycle your list and call them as necessary depending on what type of structure each object is.


It would be best, however, to be able to have a way to organize the different functions each type of game object could have into a single standard set. For example I used the following functions for each game object that was designed in my semester project: Construct, Init, Update, Draw, Destroy. By placing all functionality of each object into these separate functions you can easily copy and paste old code for reuse of new objects, thus limiting the amount of work the developer needs do. Here's a short detail of what each category would do for each game object:

  • Construct - deals with allocation of any necessary space.
  • Init - Initialization; sets the starting values for all the space allocated. Things like HP, the image pointer, and anything else needed.
  • Update - this function generally had the most code within it. This handles all updating of the object, and should be time-based. All calculations are made relative to the amount of time elapsed since the previous calculations. Attacks are fired, HP is modified, the object perhaps moves around, etc.
  • Draw - simply handles rendering of the object onto the screen.
  • Destroy - handles all deallocation of space allocated in the Construct funtion.

The great benefit of this type of setup is that there's a universal format for all game objects to function within the game. This allows for generalized code to be written. For example if there's a list of these game objects within your game, then you can cycle through the list and call each one's draw function and draw the entire list in an automated and organized manner. All you'd have to do is call the correct draw function based on the type of the object.


To further this concept one could also place function pointers into each structure, and these function pointers point to the object's specific set of functions. A structure with this sort of style could look like so:

typedef struct _GameObj
{
  int HP;
  Vector2D_ position;
  GAME_OBJ_TYPE ID;
  Image_ *image;
  void (*Construct)( GameObj_ *self ); 
  void (*Init)( GameObj_ *self );  
  void (*Update)( GameObj_ *self );  
  void (*Draw)( GameObj_ *self );  
  void (*Destroy)( GameObj_ *self );
} GameObj_;

When a new object is created these pointers can be set to the functions that correspond with the type of unit being created. These are what I referred to as virtual functions. It would then be very easy to create loops to cycle through lists of the different types of objects and call each function based on the current state of the game. For example, here's some code that could call all of the update functions for a linked list of a specific type of object:

while(node)
{
  node->Update( node );
  node = node->next;
}

This is very useful, but you'd still have to separate your objects into different lists for each type of game object available, since each game object would be made up of different types of structures.


The next step in organizing all of our game object related code is to generalize the GameObj structure itself. There is a way to do this without actually having a single structure definition that you have to cram all of your data members into. The idea is to utilize pointer typecasting.


Take our first GameObj_ structure and lets look at our modified version that could be for perhaps a Bat object in a game:

typedef struct _BatObj
{
  int HP;
  Vector2D_ position;
  Image_ *image;
  GAME_OBJ_TYPE ID;
  void (*Construct)( GameObj_ *self ); 
  void (*Init)( GameObj_ *self );  
  void (*Update)( GameObj_ *self, const float dt );  
  void (*Draw)( GameObj_ *self );  
  void (*Destroy)( GameObj_ *self );
  POISON poisonMultiplier;
} BatObj_

This setup will allow a programmer to have a GameObj_ structure have any type of desired ID, and have their corresponding function pointers point to any particular set of functions depending on what the ID is. A switch statement run on the ID can achieve the task of setting these function pointers. Then within a specific set of functions for a type of game object a pointer typecast can be used on the self parameter to treat the passed data as any type of data. The typecasting can be dealt with within the functions themselves. Here's an example set for a bat object:


BatUpdate( GameObject_ *self, const float dt )
{
  ((Bat_ *)self)->poisonMultiplier += dt;
}

By typecasting the self pointer as a Bat_ structure, you can then have access to whatever data was passed through the self pointer as if the data were actually a Bat_ structure. This is extremely useful as you can now write functions that manipulate the data members that all different types of objects have in common. In this case, the only new data member a bat had was its poisonMultiplier. However if the pointer to the Bat_ struct was not typecasted as a Bat_ struct, the data of the rest of the members could have been accessed as if it were a GameObject_ structure. This can now be done with all game objects created as long as the layout of the structure for the first nine data members are all identical in each type of game object created. Now all game objects can be placed into a single list and their functions can all be called by generalized code, instead of creating different code to handle each different type of object. The only code that needs to be re-written is code that handles the differing data members differently.


The reason this works is because when you typecast a Bat_ structure as a GameObject_ structure, the C language doesn't care that you cannot access the data of the poisonMultiplier any longer. As far as your program is concerned you are actually manipulating a GameObject_ structure -and you are; the top portion of a Bat_ structure is identical in memory to that of a GameObject_ structure. This achieves Polymorphism and Inheritance. The Bat_ structure inherits all of the GameObject_ data members, and adds on its own unique ones. The virtual functions allow for different behavior of the game objects, even though the top portion of each GameObj_ structure is identical.


Here's another example of another type of game object that can be created:

typedef struct _VeryLargeBat
{
  int HP;
  Vector2D_ position;
  Image_ *image;
  GAME_OBJ_TYPE ID;
  void (*Construct)( GameObj_ *self ); 
  void (*Init)( GameObj_ *self );  
  void (*Update)( GameObj_ *self, const float dt );  
  void (*Draw)( GameObj_ *self );  
  void (*Destroy)( GameObj_ *self );
  POISON poisonMultiplier;
  int size;
  int armor;
} VeryLargeBat_;

This VeryLargeBat_ structure inherits the data members of the Bat_ structure, which inherits data members of the GameObj_ structure. This allows for a VeryLargeBat to successfully use all functions that manipulate GameObj_ structures, as well as those that manipulate Bat_ structures. It also now has the ability to have its own specialized functions that only work on VeryLargeBat_ objects as well! Perhaps the size can become a factor in how much damage it deals, and the armor can reduce damage from enemies somehow within an algorithm.


There's one last thing you can do to make things a whole lot easier for yourself. You can modify your derived structs to contain structures of inherited structs like so (much less error prone and easier to read):

typedef struct _Bat
{
    GameObj_ gameObj;
    POISON poisonMultiplier;
} Bat_;

typedef struct _VeryLargeBat
{
  Bat_;
  int size;
  int armor;
} VeryLargeBat_;

Reference: http://www.planetpdf.com/codecuts/pdfs/ooc.pdf

Thursday, April 5, 2012

Tile Maps: Binary Collision

Back in the day binary collision maps (also known as a type of tile map) were used as a simple and efficient way to check for collision between an object with coordinates of floating point value, and square blocks. What sorts of games used binary collision arrays? Well, pretty much any game that had square tile based levels likely used some form of binary collision, here's a few NES screenshots:


Zelda

Mario

Metroid

Zelda
A binary collision array is an array of booleans representing collision or non-collision. In our above examples any square tile that the player could not walk on, or was not empty space would have been represented by a value meaning collision. There would then be a separate array of the same dimensions as the binary collision array, which would represent the different images to draw for each tile.


Example Collision and Data Arrays


Above is an example of what the collision and data arrays might look like for the Zelda screenshot with a bridge. Each 1 would be a block that is unwalkable by the character, and each 0 would be a space the character could walk on. The data array holds different numbers, and each number would represent a different image. These image values could perhaps have been stored in some sort of enumeration, or a CBlock in assembly.


Though, how is the character handled? The character in these games seems to have a position of floating point value. I'm not actually sure if they did or didn't for optimization reasons, but what I'll show you uses a floating point coordinate for different characters/enemies. Here's an image showing an example of a floating point coordinate perhaps representing the player's character:




This point would represent the center of the position of the player. The image drawn for this character at this point would be centered directly onto the point. So now how does one go about detecting when the sides of an image on this point are touching a box that represents collision? In order to do that I'll show a method I've learned called "hotspots".


Hotspots are simply points that are offsets of a coordinate, like the coordinate above. The smallest amount of offset hotspots you can have that I'd recommend is four: one for each side of your square image. When implementing a binary collision array for a simple platformer, I found that eight hotspots worked very well. Here's an example image showing eight hotspots on the edges of a square:




Each of those dots are offset by 1/4 of the square's side length, and 1/2 of the square's side length. For example the bottom two hotspots are offset from the center by -1/2 * side length (assuming origin bottom left of the screen). By using these hotspots you can then detect when any of these hotspots points are within the bounds of a binary tile. There are multiple ways to do this, but the way I chose to was to just floor the floating point value of each hotspot and look at only the integer value left. You can do these with an integer typecast, or a floor function. This works since any floating point value in the range of 1.0 through less then 2.0 will still be within the coordinate tile of 1. If this float truncation is confusing, read the next paragraph, if you understand go ahead and skip the next paragraph.


Say you have a coordinate of 3.7 and 4.3 representing one of your hotspots, and you need to check to see if this coordinate is within a tile that represents collision. If you take a look you'll realize that all values from 3.0 to just before 4.0 are all within the x axis on of the value 3 (as in on column 3 of your grid). This goes the same for 4.3; all values from 4.0 through just before 5.0 are in row 4. This means that any coordinate from 3.0 - 3.99999, 4.0 - 4.999999 are within the tile of 3, 4. So then to check to see where any floating point coordinate is on your integer coordinate system, just throw away your decimal value and treat your float as an integer. 3.7 would be 3, and 4.3 would be 4. Thus your resulting coordinate is 3, 4.


Once this is accomplished you can then execute your code to move the character back to the tile they are currently on. This can be done by also flooring the value of the character's coordinate (not the hotspots). However, you want to snap your character back to the closest tile, not just floor the entire floating point value. To do this you use a simple trick:

coordinate = (int)(coordinate + 0.5f);

This will round your floating point number to the nearest tile by offset the decimal portion of your value by 0.5.


Lastly, if you ever implement a coordinate system like here I suggest normalizing your coordinate system. That is have one tile be represented by the value of 1. This allows for simpler mathematics, and allows you to easily transform (scale, rotate, translate) your entire grid/game to whatever exact size you desire. If you normalize your entire grid in your data, you can separate the drawing logic from your data thus decoupling your code overall.


Here's a screenshot for a platformer I worked on for a CS assignment! I had a normalized grid system with the origin represented by the bottom left of the map. I was scaling this map by a factor of 3. I also implemented some simple AI with a statemachine for the red guys! They walk left and right up the edge of their platform, and turn around at the edge, or turn around when they hit a wall.



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!

Tuesday, February 21, 2012

Game Program Structuring/Design: Game State Manager

Not too long ago I created my own first game from scratch in pure C. I struggled most with program design. I'd like to share what I've learned about a proper game state manager.

A game state manager is a method of creating a highly organized main game loop, which is generalized to the point that it can apply to any situation without pre-runtime modification of code. The game should always be in a state during runtime. That state could be the main menu, a pause screen, or a specific level or scenario. A state is divided up into multiple categories, and these categories are generalized enough to apply to every state the game can be in.

The idea is to use function pointers, and a specific set of them. There are six different functions to know:
  • Load
  • Initialize
  • Update
  • Draw
  • Free
  • Unload
These are the six functions that will make up your main loop, and once constructed your main loop should need little to no modification throughout the development of your game. Each function represents a category of functionality during a state. Every state consists of these categories. Each different state will have six functions designed for each of the function pointers in the main loop to point to them. This way your main loop will simply point to different states with its six pointers whenever you want to switch from one state to another.

The load function takes care of loading all of a state's necessary data. Load should be called only once per state -not even if the state restarts. Load also initializes the loaded data. This function is called first when a state starts.

The initialize function prepares the state's data to be used initially. It should not load any data, only prepare it. This allows a fast restart of a state in the event a restart is required -no loading or unloading will be involved in a state restart.

The update function uses a change in time (dt) to hand off to necessary functions to update the game in realtime. dt is defined as the time elapsed since the last call to update. Input should be gathered once per update call before calculations are made. All gameplay logic should happen in this state, and all live objects should be updated here.

The draw function renders all required images onto the screen, and additionally plays any desired sound effects. A well organized program will send data off to a graphics manager in this state, allowing further decoupling of major system and logic components.

The free function is what frees any objects or data no longer required, and sets the state up for switching or restarting. No data is unloaded (image sources, sound sources, meshes, etc). The idea is to set everything up to be initialized cleanly again.

The unload function is called during state termination, and unloads all data loaded in the load state. Here is an example of a properly set up game flow of a main loop: 
Initialize system components
GSM_Initialize( firstState )
while not quitting
  if currentState is quitting
    nextState is Quit
  if currentState is restart
    currentState is previousState
    nextState is previousState
  else
    GSM_Update( )
    Load( )
  Initialize( )
  while currentState is nextState
    Update
      gather input
      get dt
      update game logic
    Draw( )
  Free( )
  if nextState is Restart
    previousState is currentState
    currentState is nextState
  else
    Unload( )
    previousState is currentState
    currentState is nextState
Unload

By analyzing the setup of the above game flow you should be able to see how it works. To change a state, you simply modify the global variables currentState and nextState. previousState is then kept on-hand automatically. GSM_Update is responsible for updating the function pointers Load, Initialize, Update, Draw, Free and Unload whenever a state is started. In the event the global variable currentState changes, these function pointers will then change to their appropriate values via a switch statement. This switch statement lies within the GSM_Update function. The switch runs on the value of currentState, and once it finds a match it assigns the function pointers in the main loop to the appropriate matching state. Here is an example of a GSM_Update function:

// Update the Game State Manager by syncing the three state indicators to their
// corresponding function pointers (all six of them).
int GSM_Update( void )
{
  switch(currentState)
  {
  case Level_1:
    Load = &Level1_Load;
    Initialize = &Level1_Initialize;
    Update = &Level1_Update;
    Draw = &Level1_Draw;
    Free = &Level1_Free;
    Unload = &Level1_Unload;
    break;
  case Level_2:
    Load = &Level2_Load;
    Initialize = &Level2_Initialize;
    Update = &Level2_Update;
    Draw = &Level2_Draw;
    Free = &Level2_Free;
    Unload = &Level2_Unload;
    break;
  case MapEditor:
    Load = &MapEditor_Load;
    Initialize = &MapEditor_Initialize;
    Update = &MapEditor_Update;
    Draw = &MapEditor_Draw;
    Free = &MapEditor_Free;
    Unload = &MapEditor_Unload;
    break;
  case Presentation:
    Load = &PresentationLoad;
    Initialize = &PresentationInitialize;
    Update = &PresentationUpdate;
    Draw = &PresentationDraw;
    Free = &PresentationFree;
    Unload = &PresentationUnload;
    break;
  /*case Template:
    Load = &Load;
    Initialize = &Initialize;
    Update = &Update;
    Draw = &Draw;
    Free = &Free;
    Unload = &Unload;
    break;*/
  case Restart:
    break;
  case Quit:
    break;
  }
  return RETURN_SUCCESS;
}

And there you have it; a proper organizational setup to allow an excellent method of managing game states. Using this sort of organization allows for each state to have a universal format which allows for modification of states, additions of states, and deletions of states during development to be very easy and time-efficient.

Monday, February 20, 2012

Window's Console Game: Variable Sized Object

In the previous post I had talked a little bit about image ordering, and image transparency. The way the image data was held in memory was very quirky! We had to create an entire header file for each image, and each image had to be an entirely different structure definition due to arrays of data being different from image to image. I'd like to show you a method that makes use of some clever macros in order to achieve an interesting variable-sized image structure! The idea was actually brought to me by a friend of mine named Malcolm Smith. Here's the structure design for an object to be dynamically sized during run-time, in our case for images:

typedef struct _Image
{
  int width; 
int height;
unsigned char *chars;
unsigned char *colors;
} Image_;


In the above structure we have two pointers, one to chars and one to colors. These pointers will point to arrays of unsigned characters, which is the datatype that represents both colors and characters for the Window's console. In order to access these arrays, you should recall that the name of an array can be treated the same as a pointer to the first element in the array. So after we allocate space for our arrays we'll need to initialize chars and colors properly by setting them to point to the first element in our arrays.


In order to go about allocating our space properly we need to allocate the space of the Image_ structure, space for the width * the size of our character array * height, and finally space for our color array * width * height. Here's a call to malloc to this in one single swoop:


Image_ *image = (Image_ *)malloc( sizeof( Image_ ) +
                                  sizeof( width * height * sizeof( unsigned char ) +
                                  sizeof( width * height * sizeof( unsigned char ) );

The nice thing about this sort of allocation is that it isn't broken up into separate allocation calls, which speeds up the process since allocation is slow. This also keeps all the parts of memory in the same location in memory all adjacent to one another, as opposed to who knows where in memory when malloc is called multiple times, thus lessening memory fragmentation.


Now we have our problem of getting our chars and colors pointers to point to their proper locations in memory. We aren't going to set up a conventional array of pointers, like proper C would dictate. Instead we'll use a couple macros to help us index the array ourselves, thus saving some references and memory in the process. We'll make use of a few macros to take over the job from the compiler; observe:


#define unsigned char CHAR
#define unsigned char COL

#define PtrAdd( ptr, offset ) \
  (((char *)ptr) + offset)

#define CharAt( image, x, y ) \
  (CHAR *)(PtrAdd( image->chars, ((y) * image->width + (x)) * sizeof( CHAR ) ))

#define ColorAt( image, x, y ) \
  (COL *)(PtrAdd( image->colors, ((y) * image->width + (x)) * sizeof( COL ) ))


The first macro is a nice macro to have as it is generalized. It simply takes a pointer and an offset in bytes, then returns a pointer in memory that is ahead (or behind) the original pointer by the offset bytes. It's a macro for pointer addition/subtraction that works by typecasting the pointer supplied as a char, which is a byte in size, thus forcing the addition of the offset to work in chunks of 8 bits. As such the units of offset is in bytes. This can be used to initialize our chars and colors pointer!


// Initialize chars pointer to directly after Image_ struct
image->chars = PtrAdd( image, sizeof( Image_ ) );

// Initialize colors pointer to directly after chars array
image->colors = PtrAdd( image->chars, width * height * sizeof( CHAR );

Now that we can properly initialize our pointers in our struct, it's time to start making use of our CharAt and ColorAt macros to index our two arrays! First though lets initialize our arrays to zero with a looping function.


void ZeroImage( Image_ *image )
{
  int x, y; // used for indexing

  CHAR *thisChar;
  COL *thisColor;

  for(y = 0; y < image->height; y++)
  {
    for(x = 0; x < image->width; x++)
    {
      thisChar = CharAt( image, x, y );
      *thisChar = 0;
    }
  }

  for(y = 0; y < image->height; y++)
  {
    for(x = 0; x < image->width; x++)
    {
      thisColor = ColorAt( image, x, y );
      *thisColor = 0;
    }
  }
}

A function that loops through all elements of the chars and colors array is very easy to write with our macros. You might be able to guess how we're going to fill out our arrays. You can actually copy/paste the ZeroImage function and change the lines that assign a zero to lines that assign a character value. You can use the x and y iterators to index an array of image data as well! Here's an example function:



void ImageSet( Image_ *image, CHAR *charData, COL *colorData )
{
  int x, y; // used for indexing
  CHAR *thisChar;
  COL *thisColor;

  for(y = 0; y < image->height; y++)
  {
    for(x = 0; x < image->width; x++)
    {
      thisChar = CharAt( image, x, y );
      *thisChar = charData[(y * image->width) + x];
    }
  }

  for(y = 0; y < image->height; y++)
  {
    for(x = 0; x < image->width; x++)
    {
      thisColor = ColorAt( image, x, y );
      *thisColor = colorData[(y * image->width) + x];
    }
  }
}

Now all you'd need in order to implement this variable-sized image format is image data! You can write image data by hand, use some interesting tools, or parse the data from an image (like a BMP) yourself. Later on in another future post I may perhaps write about how to parse a BMP for it's image data. For now however, I suggest getting comfortable with the tools I've linked to.


Series on creating a Windows Console game: