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: