Showing posts with label C++. Show all posts
Showing posts with label C++. Show all posts

Sunday, August 26, 2012

Easy Buttons for your Game

In my past couple game projects, I never had a proper button system; every clickable button I wrote was ad-hoc and thusly very annoying to write.

I came up with a really simple but flexible button system for my C projects. This post is going to be pretty short, so here's a diagram to summarize everything:



As you can see, the button object takes a function pointer as a parameter during construction. This function is what I refer to as exec. The exec function allows for a button to perform any action on-click. The exec function can take a general purpose parameter, perhaps defaulted to type int or void pointer. Within the exec function any necessary typecasting can be hidden away within it.

The exec functions will often times have additional dependencies throughout your program, in order to provide their desired functionality. For example I might need my exec function to create a live game object on-click. I'd need to include any headers required for creating game objects into my button system in order for this to work. For this reason the exec functions should be abstracted into their own separate file.

Alternatively one can make use of a map of identifiers to exec pointers in order to cut down on file dependencies. By mapping, of perhaps a string identifier, to an exec pointer the button class can then take the identifier upon creation rather than the pointer itself. The various exec functions can then be placed into file systems that pertain to the type of functionality the exec function itself provides. A registration of each exec function into the table would be required.

As for button behavior, I decided to create a few different types of Update functions for each button. Once a button has detected an on-click and has called its exec function, the Update function is called each cycle until the button is ready to detect another click and call its exec again. Since there can be multiple types of buttons each requiring its own unique update, the button object also takes a pointer to an Update function on creation. Here's a couple examples of button updates I've written:

//
// ButtonUpdateStandard
// Purpose: Standard update function for a generic button.
//
RETURN_TYPE ButtonUpdateStandard( BUTTON *self, float dt )
{
  // Update dt only if non-zero.
  // For example when exec is called, set dt to 0.001 (seconds)
  // to begin debounce timer.
  if(self->dt != 0)
  {
    self->dt += dt;
  }
  
  // Debounce
  if(self->dt > STANDARD_BUTTON_DEBOUNCE && !IsKeyPressed( VK_LBUTTON ))
  {
    self->dt = 0;
  }

  if(self->dt == 0)
  {
    VECTOR2D pos = { 0 };
    pos.x_ = (float)GLOBAL_INPUTS.xPos;
    pos.y_ = (float)GLOBAL_INPUTS.yPos;

    // Test for button press
    if(IsKeyPressed( VK_LBUTTON ))
    {
      if(StaticPointToStaticRect( &pos, &self->rect ))
      {
        {
          self->exec( self );

          // Initiate debounce
          self->dt = 0.0001f;

          // End list caller routine if blocking
          if(self->isBlocking)
            return RETURN_FAILURE;
        }
      }
    }
  }
  
  return RETURN_SUCCESS;
}

//
// ButtonUpdateBrush
// Purpose: Standard update function for a generic button.
//
RETURN_TYPE ButtonUpdateBrush( BUTTON *self, float dt )
{
  // Update dt only if non-zero.
  // For example when exec is called, set dt to 0.001 (seconds)
  // to begin debounce timer.
  if(self->dt != 0)
  {
    self->dt += dt;
  }
  
  // Debounce
  if(self->dt > BRUSH_BUTTON_DEBOUNCE)
  {
    self->dt = 0;
  }

  if(self->dt == 0)
  {
    VECTOR2D pos = { 0 };
    pos.x_ = (float)GLOBAL_INPUTS.xPos;
    pos.y_ = (float)GLOBAL_INPUTS.yPos;

    // Test for button press
    if(IsKeyPressed( VK_LBUTTON ))
    {
      if(StaticPointToStaticRect( &pos, &self->rect ))
      {
        {
          self->exec( self );

          // Initiate debounce
          self->dt = 0.000001f;

          // End list caller routine if blocking
          if(self->isBlocking)
            return RETURN_FAILURE;
        }
      }
    }
  }
  
  return RETURN_SUCCESS;
}

These two buttons act like a standard button press in most GUI systems. One has a slight delay for how fast you can actually click the button, and a debouncer that requires a release of the mouse key before update actually starts using DT to calculate the current time duration. The other acts more like a spray brush where you can just hold down the click button on have exec called repeatedly with a pause between calls.

Thursday, August 23, 2012

Game Object Factory: Distributed Factory

When creating game objects within your game, you will likely want to start using new or malloc all over the place. This is bad! Every object should have a clear owner, and there should be a single interface for creating any object. Take a look at this code:

void ExampleFunc( void )
{
  object *GO = new SomeGameObjectType( );
  // Who owns this object?
  // What headers do I need to include?
}

The above code does work, although it creates a giant mess of file dependencies. Suddenly one would require a header file for all the various object definitions in order to use the new operator everywhere. Furthermore, handling of attaching the object to some sort of owner will have to be done everywhere that the new keyword is used.

A factory should be used to create game objects in a unified way. Here's an example of the simplest form of an object factory:


#include "RedBlock.h"
#include "BlueEnemy.h"
#include "FireBall.h"

// ID is an enumeration
object *CreateObject( ID type )
{
  switch( ID )
  {
  case REDBLOCK:
    return new RedBlock( );
  case BLUENEMY:
    return new BlueEnemy( );
  case FIREBALL:
    return new FireBall( );
  }
}

However there are some problems with this type of factory. One is that the factory will still have annoying file dependencies requiring the user to make another include, and modify the switch statement each time a new game object is designed. Examine the following:

// Map strings to object types
void ExampleFunc( void )
{
  object *GO = CreateObject( "RedBlock" );
}

The above example shows the usage of the object factory when strings are mapped to types of objects. This setup is the ideal interface one would desire, as a single include to the ObjectFactory header is all that is required to create any type of object. The previous examples were mapping integers of an enumeration type to object types, which would require modification to the switch statement run in the enum, as well as manual updating to the enumeration itself.

So now that we've identified the ideal interface for creating game objects, we still need to make sure that the game objects created have a clear owner. Mapping of strings to game object types will need to be implemented, and cutting down on file dependencies of the the GameObjectFactory file itself is still something to be solved as well. By using a map (perhaps std::map) or hash table we can use a string identifier to fetch some value. Here's what we want our factory to look like:

object *CreateObject( char *type )
{
  return map[type]->Create( );
}

By mapping a string to a creator function of the type of object desired, all file dependencies except that of those required to utilize the table (map in the above example) are eliminated. Furthermore, whenever a new game object type is designed, all that is needed to be done to ensure compatibility with our factory is a single registration call.

There are some details about the Create function that should be discussed. The Create function is specific to each type of game object, and the interface for each Create function needs to be identical. To ensure this, each type of game object should have a single class called the creator. The creator object for each class derives from a base Creator class to ensure a clear and consistent interface.

// Base class
class Creator
{
  virtual object *Create( void );
  virtual ~Creator( void );
}

// In another file...
// Specific derived creator for a single object type
class RedBlockCreator : public Creator
{
  virtual object *Create( void )
  {
    return new RedBlock( );
  }
}

// In another file...
// Register all game object creators in a single place in a unified way!
void RegisterCreators( void )
{
  map->register( "RedBlock", new RedBlockCreator( ) );

  // Or use a macro like I did:
  REGISTER_CREATOR( RedBlock );
}

What we've now created is called a distributed factory. All file dependencies are hidden by registration in using a hash table data structure to provide the mapping of typeless strings to actual types of game objects. The creation of objects has a unified interface, and there's a single access point (the object factory) that allows the creation of all types of game objects that are registered within its data table of types. There's one last small problem to solve: who owns the created objects? This answer can of course vary, but luckily there can be a single point of object management, like so:

object *CreateObject( char *type )
{
  object *newObject = NULL;

  newObject = map[type]->Create( );

  // Single point of management
  ... any other code necessary, like init, counting, etc.
  ObjectList->Insert( newObject );

  return newObject;
}

And there we have it! A properly structured object factory. To further the awesome might of the factory, one could easily add in deserialization to the factory, since the factory is already working with abstract strings as type identifiers. Serialization, however,  is for a future post!

Factories like this also interface very well with scripting languages :)

Additional reading:
C++ for Game Programmers: Noel Llopis - Chapter 13

Friday, August 10, 2012

Generic Programming in C

Generic programming is style of programming that is typeless, as in the type of data to be used is not determined at the time the code was written. In C++ this is achieved with templating. I know of two ways to perform generic programming in C. One way is to use pointer typecasting. It's important to understand that when you typecast a pointer no data is modified within the pointer; how the data the pointer points to is interpreted is changed. This can be utilized to create generic algorithms and functionality.

For example a linked list data structure can be created utilizing pointer typecasting where the data to be held by a node is typecasted to a single type no matter what the actual type of the data is. Usually a void * is used in this case to prevent a dereference to data of unknown type. However, this method can only be used when access to the data held by the node (the data pointed by the void *) does not need to be accessed.

A more well-rounded (in my opinion) approach to generic programming in C is to make use of the preprocessor directive ##.

## pastes two tokens together to create a new token. Usage of the ## operator is known as token pasting, or token concatenation. There's a whole lot of documentation on the ## operator. If you're not familiar with it, you need to do some familiarizing before reading on.

All it does is take two tokens within a macro and stick them together to create a new token. Example:

#define PASTE_TOKENS( a, b ) \
  a##b

PASTE_TOKENS( var, val ); // output: varval

In the above example varval will need to be defined in order to avoid compiler errors, perhaps by using it as the name of a variable to define.

Token pasting is utilized to solve an age old problem in C of creating various functions to achieve the same problem. For example, I've written many linked lists in C and one day, I finally decide "I will never write another linked list in C". I'm sick and tired of having to write a new set of functions for each type of data that I need a new linked list for.

By using the ## operator one can automate the process of duplicating code to create new functions and new definitions based off of data type. This is much like templating in C++, except not nearly as user-friendly, yet still fun and satisfying to try.

Since there's a great need in C to duplicate code for various data types, and the ## operator allows us to create new tokens with two other tokens, we can use the type of the data to create a new name for a new set of functionality for each type of data desired.

Examine the following:

// Old C style "function overloading"
int INT_MAX( int a, int b )
{
  return (a > b) ? a : b;
}

float FLOAT_MAX( float a, float b )
{
  return (a > b) ? a : b;
}

double DOUBLE_MAX( double a, double b )
{
  return (a > b) ? a : b;
}

// Generic definition
#define GENERIC_MAX( TYPE )          \
  TYPE TYPE##_MAX( TYPE a, TYPE b ) \
  {                                  \
    return (a > b) ? a : b;          \
  }

As you can see, it can be really annoying to write different code for different types of data, when the code itself is highly redundant or even identical. However by providing the GENERIC_MAX macro a data type, a new function can be automatically generated by the C preprocessor! The MAX token is concatenated with the TYPE parameter to form a new function definition. Providing the GENERIC_MAX macro with type int will result in a new function being defined named int_MAX. Creating new sets of functionality of anything can be as simple as declaring or defining with a couple calls to a macro.

It might seem a bit self-defeating however to have to figure out what the new name of your generated function is going to be in order to call it. A very simple utility macro should be used to wrap around your generated generic functions. More information on how to do this is shown later in the post.

This can be taken further and be applied to even an abstract data type, such as a linked list. I've constructed myself a generic linked list.

//
// DECLARE_NODE
// Purpose: Declares a node of a specific type.
//
#define DECLARE_NODE( TYPE )   \
  typedef struct _NODE_##TYPE  \
  {                            \
    TYPE data;                 \
    struct _NODE_##TYPE *next; \
  } NODE_##TYPE;

The above code is an example definition of a macro that defines a generic node type. The type of the node is used in creating new name definitions wherever the node's type is required in the structure definition.

//
// DEFINE_FUNC( TYPE )
// Purpose: Defines a function to create a node of specified type.
//
#define DEFINE_FUNC( TYPE )                          \
  NODE_##TYPE *NODE_CREATE_##TYPE( TYPE data )       \
  {                                                  \
    NODE_##TYPE *newNode =                           \
     (NODE_##TYPE *)malloc( sizeof( NODE_##TYPE ) ); \
    newNode->data = data;                            \
    newNode->next = NULL;                            \
    return newNode;                                  \
  }

Above is an example of how to define a macro to define a function to create a new node of specified type based on the previous node definition.

You might be thinking that it would be a bit annoying to call so many different define and declare macros for each structure and function. You can actually just declare all structures and function prototypes within a single macro, I called mine DECLARE_LIST, which declares all structure types and function prototypes, as well as some utility macros required to use the generic linked list. I also have a DEFINE_LIST macro that defines all functions used in the generic linked list.

For abstract data types such as lists or stacks or queues, you'll probably want some additional utility functions to actually call the various generic functions you've defined. Here is an example set of utility functions I've made for my generic linked list:

//
// LIST_CONSTRUCT
// Purpose: Constructs and returns a new list object of specified type.
//
#define LIST_CONSTRUCT( TYPE ) \
  LIST_CONSTRUCT_##TYPE( )

//
// NODE_CREATE
// Purpose: Constructs and returns a new node of a specified type.
//
#define NODE_CREATE( TYPE, data, DeleteData, order ) \
  NODE_CREATE_##TYPE( data, DeleteData, order )

//
// LIST_INSERT
// Purpose: Inserts a node of specified type in position determined by the order
//          data member.
//
#define LIST_INSERT( TYPE, listSelf, node ) \
  LIST_INSERT_##TYPE( listSelf, node )

//
// LIST_REMOVE
// Purpose: Removes (deallocates) a node of a specified type from a list.
//
#define LIST_REMOVE( TYPE, node ) \
  LIST_REMOVE_##TYPE( node )

//
// LIST_DESTROY
// Purpose: Removes (deallocates) a list and all its nodes of a specified type.
//
#define LIST_DESTROY( TYPE, listSelf ) \
  LIST_DESTROY_##TYPE( listSelf )

//
// LIST_CALLER
// Purpose: Uses a callback on all nodes while supplying a specified param.
//
#define LIST_CALLER( TYPE, self, callback, param ) \
  LIST_CALLER_##TYPE( self, callback, param )

//
// LIST_TYPE
// Purpose: Returns the type of LIST that pertains to TYPE.
//
#define LIST_TYPE( TYPE ) \
  LIST_##TYPE

//
// NODE_TYPE
// Purpose: Returns the type of NODE that pertains to TYPE.
//
#define NODE_TYPE( TYPE ) \
  NODE_##TYPE

As you can see wrappers for the various generic functions are needed to properly call them (unless you want to manually figure out what the name of the function generated for whatever type you're currently using is). There's also a couple macros for getting the generated type associated with a provided type.

Click Here for Source Code

////////////////////////////////////////////////////
// Copyright (c) 2012 ICRL
// See the file LICENSE.txt for copying permission.
// 
// Original Author: Randy Gaul
// Date:   8/9/2012
// Contact: r.gaul@digipen.edu
////////////////////////////////////////////////////

#pragma once

#include "StringHash.h"

//
// DECLARE_LIST
// Purpose: Declares a linked list of a specific type on the heap.
//
#define DECLARE_LIST( TYPE )     \
  typedef struct _NODE_##TYPE    \
  {                              \
    TYPE data;                   \
    void (*DeleteData)( TYPE );  \
    int order;                   \
    struct _NODE_##TYPE *next;   \
    struct _NODE_##TYPE *prev;   \
  } NODE_##TYPE;                 \
\
  struct _LIST_##TYPE; \
\
  typedef struct _LIST_VTABLE_##TYPE                                                \
  {                                                                                 \
    void (*Destroy)  ( struct _LIST_##TYPE *self );                                 \
    NODE_##TYPE *(*CreateNode)( TYPE data, void (*DeleteData)( TYPE ), int order ); \
    RETURN_TYPE (*Insert)   ( struct _LIST_##TYPE *self, NODE_##TYPE *node );       \
    void (*Remove)   ( NODE_##TYPE *node );                                         \
  } _LIST_VTABLE_##TYPE;                                                            \
\
  extern const _LIST_VTABLE_##TYPE LIST_VTABLE_##TYPE; \
\
  typedef struct _LIST_##TYPE           \
  {                                     \
    NODE_##TYPE *list;                  \
    const _LIST_VTABLE_##TYPE *vtable;  \
  } LIST_##TYPE;                        \
\
  LIST_##TYPE *LIST_CONSTRUCT_##TYPE( void ); \
  NODE_##TYPE *NODE_CREATE_##TYPE( TYPE data, void (*DeleteData)( TYPE data ), int order ); \
  RETURN_TYPE LIST_INSERT_##TYPE ( LIST_##TYPE *self, NODE_##TYPE *node ); \
  void LIST_REMOVE_##TYPE ( NODE_##TYPE *node ); \
  void LIST_DESTROY_##TYPE ( LIST_##TYPE *self ); \
  void LIST_CALLER_##TYPE ( LIST_##TYPE *self, RETURN_TYPE (*callback)( NODE_##TYPE *, void * ), void *param ); \
  TYPE LIST_PEEK_##TYPE ( LIST_##TYPE *self )

//
// DEFINE_LIST
// Purpose: Defines a linked list of a specific type on the heap.
//
#define DEFINE_LIST( TYPE )                       \
  const _LIST_VTABLE_##TYPE LIST_VTABLE_##TYPE =  \
  {                                               \
    LIST_DESTROY_##TYPE,                          \
    NODE_CREATE_##TYPE,                           \
    LIST_INSERT_##TYPE,                           \
    LIST_REMOVE_##TYPE                            \
  };                                              \
\
  LIST_##TYPE *LIST_CONSTRUCT_##TYPE( void )                                  \
  {                                                                           \
    LIST_##TYPE *linkedList = (LIST_##TYPE *)malloc( sizeof( LIST_##TYPE ) ); \
    linkedList->list = NULL;                                                  \
    linkedList->vtable = &LIST_VTABLE_##TYPE;                                 \
    return linkedList;                                                        \
  }                                                                           \
\
  NODE_##TYPE *NODE_CREATE_##TYPE( TYPE data, void (*DeleteData)( TYPE ), int order )  \
  {                                                                                    \
    NODE_##TYPE *newNode = (NODE_##TYPE *)malloc( sizeof( NODE_##TYPE ) );             \
    newNode->data = data;                                                              \
    newNode->DeleteData = DeleteData;                                                  \
    newNode->order = order;                                                            \
    newNode->next = NULL;                                                              \
    newNode->prev = NULL;                                                              \
    return newNode;                                                                    \
  }                                                                                    \
\
  RETURN_TYPE LIST_INSERT_##TYPE ( LIST_##TYPE *self, NODE_##TYPE *node )  \
  {                                                                        \
    NODE_##TYPE *scan = NULL;                                              \
    if(!self)                                                              \
      return RETURN_FAILURE;                                               \
                                                                           \
    scan = self->list;                                                     \
                                                                           \
    if(scan) /* if list is not empty */                                    \
    {                                                                      \
      while(scan->next)                                                    \
      {                                                                    \
        if(scan->order <= node->order)                                     \
          break;                                                           \
        scan = scan->next;                                                 \
      }                                                                    \
                                                                           \
      /* beginning of list */                                              \
      if(!scan->prev)                                                      \
      {                                                                    \
        node->next = scan;                                                 \
        scan->prev = node;                                                 \
        self->list = node;                                                 \
      }                                                                    \
      /* if not at end of list */                                          \
      else if(scan->next)                                                  \
      {                                                                    \
        node->next = scan;                                                 \
        node->prev = scan->prev;                                           \
        scan->prev->next = node;                                           \
        scan->prev = node;                                                 \
      }                                                                    \
      else                                                                 \
      {                                                                    \
        if(scan->prev) /* If more than one item in list */                 \
        {                                                                  \
          if(scan->order <= node->order)                                   \
          {                                                                \
            node->next = scan;                                             \
            node->prev = scan->prev;                                       \
            scan->prev->next = node;                                       \
            scan->prev = node;                                             \
          }                                                                \
          else                                                             \
          {                                                                \
            node->prev = scan;                                             \
            scan->next = node;                                             \
          }                                                                \
        }                                                                  \
        else /* One item in list */                                        \
        {                                                                  \
          /* Place before or after depending on zOrder */                  \
          if(scan->order <= node->order)                                   \
          {                                                                \
            scan->prev = node;                                             \
            node->next = scan;                                             \
            self->list = node;                                             \
          }                                                                \
          else                                                             \
          {                                                                \
            scan->next = node;                                             \
            node->prev = scan;                                             \
          }                                                                \
        }                                                                  \
      }                                                                    \
    }                                                                      \
    else /* if list is empty */                                            \
    {                                                                      \
      self->list = node;                                                   \
    }                                                                      \
                                                                           \
    return RETURN_SUCCESS;                                                 \
  }                                                                        \
\
  void LIST_REMOVE_##TYPE ( NODE_##TYPE *node )   \
  {                                               \
    if(node->prev)                                \
    {                                             \
      node->prev->next = node->next;              \
      if(node->next)                              \
      {                                           \
        node->next->prev = node->prev;            \
      }                                           \
    }                                             \
    else if(node->next)                           \
    {                                             \
      node->next->prev = NULL;                    \
    }                                             \
                                                  \
    if(node->DeleteData)                          \
    {                                             \
      node->DeleteData( node->data );             \
    }                                             \
    free( node );                                 \
  }                                               \
\
  void LIST_DESTROY_##TYPE ( LIST_##TYPE *self )  \
  {                                               \
    NODE_##TYPE *temp = NULL;                     \
    NODE_##TYPE *scan = self->list;               \
                                                  \
    while(scan)                                   \
    {                                             \
      temp = scan->next;                          \
      self->vtable->Remove( scan );               \
      scan = temp;                                \
    }                                             \
                                                  \
    free( self );                                 \
  }                                               \
\
  void LIST_CALLER_##TYPE ( LIST_##TYPE *self, RETURN_TYPE (*callback)( NODE_##TYPE *, void * ), void *param )  \
  {                                                                                                             \
    NODE_##TYPE *scan = self->list, *temp = NULL;                                                               \
                                                                                                                \
    while(scan)                                                                                                 \
    {                                                                                                           \
      temp = scan->next;                                                                                        \
      /* Stop the callback process if return type is not 0 */                                                   \
      if(callback( scan, param ))                                                                               \
      {                                                                                                         \
        scan = temp;                                                                                            \
        return;                                                                                                 \
      }                                                                                                         \
      scan = temp;                                                                                              \
    }                                                                                                           \
  }                                                                                                             \
\
  TYPE LIST_PEEK_##TYPE ( LIST_##TYPE *self ) \
  {                                           \
    return self->list->data;                  \
  }

//
// LIST_CONSTRUCT
// Purpose: Constructs and returns a new list object of specified type.
//
#define LIST_CONSTRUCT( TYPE ) \
  LIST_CONSTRUCT_##TYPE( )

//
// NODE_CREATE
// Purpose: Constructs and returns a new node of a specified type.
//
#define NODE_CREATE( TYPE, data, DeleteData, order ) \
  NODE_CREATE_##TYPE( data, DeleteData, order )

//
// LIST_INSERT
// Purpose: Inserts a node of specified type in position determined by the order
//          data member.
// Notes: Will return RETURN_FAILURE if list pointer is NULL.
//
#define LIST_INSERT( TYPE, listSelf, node ) \
  LIST_INSERT_##TYPE( listSelf, node )

//
// LIST_REMOVE
// Purpose: Removes (deallocates) a node of a specified type from a list.
//
#define LIST_REMOVE( TYPE, node ) \
  LIST_REMOVE_##TYPE( node )

//
// LIST_DESTROY
// Purpose: Removes (deallocates) a list and all its nodes of a specified type.
//
#define LIST_DESTROY( TYPE, listSelf ) \
  LIST_DESTROY_##TYPE( listSelf )

//
// LIST_CALLER
// Purpose: Uses a callback on all nodes while supplying a specified param.
//
#define LIST_CALLER( TYPE, self, callback, param ) \
  LIST_CALLER_##TYPE( self, callback, param )

//
// LIST_PEEK
// Purpose: Returns the data of the first in the list.
//
#define LIST_PEEK( TYPE, self ) \
  LIST_PEEK_##TYPE( self )

//
// General data type handling. These functions must be used to handle list and node
// objects/pointers directly.
//
#define LIST_TYPE( TYPE ) \
  LIST_##TYPE
#define NODE_TYPE( TYPE ) \
  NODE_##TYPE


Drawbacks:
There is one major drawback to the ## operator strategy; you cannot use * in the type name, or spaces in the type name. If you need to use a pointer as your type, you'll have to typedef your pointer into a single valid token and pass the typedef'd type to the generic macros.

There is another thing that can be considered a drawback: you cannot have a pointer to a macro. As such debugging macros can be very very tedious. I myself had to generate a processed file and compile with the expanded macro in order to pinpoint where I originally had some compiling errors when creating my generic linked list.

Object Oriented C: Virtual Table (vtable)

I wrote a previous post on Class-Like Structures for usage in C, in order to create objects that would allow for both inheritance and polymorphism. However, it's annoying to keep a pointer to each type of required function for each type of object, and often times you'll need fancy typecasting in multiple locations in order to avoid compiler warnings.

In C++ each class that contains methods also has a virtual table (vtable). A vtable is simply a pointer to a collection of function pointers. In C++ member functions pointers (pointers to member functions, or methods) aren't actually the exact same as function pointers, but the concept of the vtable in C++ is the same as in C; the vtable keeps track of what functions are available for use by the object.

Luckily the murkiness of member function pointers are completely avoided when working with C and pure function pointers. A vtable in C can consist of a structure with each data member as a function pointer, or an array of function pointers. Whichever style chosen should be chosen based on preference as either method of implementation can be fine. I personally like using a structure.

Lets take a look at the structure defined in my older post:

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_;

This structure requires memory space for each location. This is unnecessary and a bit annoying to handle during initialization, and can lead to annoying typecasting in various locations. Here's what the new object should look like if we introduce a vtable:

typedef struct _GameObj
{
  int HP;
  Vector2D_ position;
  GAME_OBJ_TYPE ID;
  Image_ *image;
  const _GAMEOBJECT_VTABLE *vtable;
} GameObj_;

This cuts the size of memory required for the virtual functions for this particular object down by a factor of 5. Here is what the definition of the vtable can look like:

typedef struct _GAMEOBJECT_VTABLE
{
  void (*Construct)( struct _GAMEOBJECT *self );
  void (*Init)     ( struct _GAMEOBJECT *self );
  void (*set)      ( struct _GAMEOBJECT *self );
  void (*Update)   ( struct _GAMEOBJECT *self );
  void (*Draw)     ( struct _GAMEOBJECT *self );
  void (*Destroy)  ( struct _GAMEOBJECT *self );
} _GAMEOBJECT_VTABLE;

Since a vtable is in use in the game object, typecasting may be necessary if the parameters of the various functions of the vtable differ from object to object. However a single typecast is all that is necessary during initialization. Typecasting the vtable itself to change the parameters of the functions within the vtable doesn't actually modify any memory. It's important to understand that when you typecast a pointer (and consequently a vtable pointer) no data is modified within the pointer; how the data the pointer points to is interpreted is changed.

So what about the code for this typecasting? Here's a small example of some initialization code for initializing the vtable data member:

const _SOME_OTHER_VTABLE SOME_OTHER_VTABLE = {
  SomeOtherConstruct,
  SomeOtherInit,
  SomeOtherSet,
  SomeOtherUpdate,
  SomeOtherDraw,
  SomeOtherDestroy
};

((GAMEOBJECT *)object)->vtable_ =
  (const _GAMEOBJECT_VTABLE *)(&SOME_OTHER_VTABLE);

// Example invocation of an object's vtable's function
object->vtable->Destroy( object );
((SOME_OTHER_VTABLE *)object->vtable)->SomeOtherUpdate( other params );

It's important to note that some extra parentheses are required to force typecasting to occur to avoid confusing operator precedence issues. The vtable should be initialized directly after allocation of the object. This ensures that the vtable pointer will never be accessed without being initialized.

The definitions of the SomeOther functions can have any type of parameters to your heart's desire!

It may be a bit confusing having a Construct function within the vtable when allocation of the object and initialization of the vtable data member happen outside of the Construct function. This is because you cannot actually call the Construct function from the vtable until the vtable is allocated and initialized. Handling of creation of objects would be best done with the Factory Pattern.

I'll likely write a post in the near future on the factory pattern :)

Tuesday, July 3, 2012

Windows Console Game: AsciiEngine

I've been creating a series of posts about creating a Window's console game from scratch in C. This post will act as a culmination of many different posts throughout my blog in the form of an open source game engine called AsciiEngine.

AsciiEngine is a game engine for Windows XP, Vista, and Win7 that allows the user to easily create and display images within a Windows console. The engine also automates the tedious task of customizing aspects of the console, such as a font or palette color.

Here's the link for AsciiEngine (visual studio 2010 project + source files): LINK


Man with sword!

Screenshot from older included demo~~

By using AsciiEngine, users can easily construct interactive programs (games!) without the overhead of setting up all of the various system components required to run a game within the Windows console.


Screenshot of the old AsciiEngine demo. Pressing enter pastes
sun images onto random locations.

AsciiEngine is documented heavily in-code and is open source - I want anyone willing to be able to learn from the example code provided.

Features include:
  • Complete game loop
    • Game loop integrated into Game State Manager via function pointers
  • Game State Manager
    • Allows for easy management/creation/deletion of game states
  • Functioning framerate controller
    • Allows the setting of framerate with a #define macro
    • Prevents large timesteps from passing through the program with a cap
  • Various console related functions for easy customization of the console window
  • Complete graphics functions set for drawing 2D images
  • Input template complete for simple keystroke detection and mouse event handling
  • Complete and very simple PRNG
  • Simple image format that allows for variable size
  • Integrated hash table for storing images
    • Allows for an optimized lookup, e.g.: TableLookup( "ImageName" )
    • Extremely simple creation/deletion of images
  • Implementation of my simple 2D collision library
  • Implementation of my simple 2D vector library
  • Highly organised object manager using the factory pattern
    • Allows for easy creation/handling/deletion of game objects
    • Incredibly simple to create new object types
  • Implemented my Tile mapping -- Binary Collision library
  • Image editor
  • file output
  • Automatic image file loading and parsing
  • Messaging system Object to object + global messaging system
  • Component base game object system (now renamed to game entity)
  • New button class for easy UI creation
  • Integration of generic Hash Table and Linked Lists
  • Simple serialization and deserialization support.

Here's the link for AsciiEngine (visual studio 2010 project + source files): LINK

Now hopefully I can see some console games created with true Ascii art! Please let me know if anyone creates a console game, or uses AsciiEngine to create a console game. I would be thrilled to see some projects from other people, as I just love Ascii art games, especially ones within the Windows console.

Series on creating a Windows Console game:
How to use AsciiEngine:
Using AsciiEngine is very easy. It's available here on github.

Almost all code creation you'll do with AsciiEngine will be in creating/modifying game state files. Since AsciiEngine uses a GameStateManager (GSM) you'll have to create your own states. More information about what a GSM can be found here. Creating a state is as easy as copy/paste from the example state within the download archive of AsciiEngine. Integrating a new state into the GSM should be straightforward if you examine the currently existing code.

Once a state is created all that is left to do for the user is to simply write code within the state! Almost all code written will be within the Update function. During the Update function all game logic will occur. Drawing specific functions should occur only with the stat's Draw function - this allows for easy implementation of the Painter's Algorithm.


To switch states there are three global variables within the GameStateManager.c file. These are nextState, currentState and previousState. In order to switch states simply change nextState to the desired state to switch to. The main loop will then call the Unload and Free function automatically of the current state you are in, and then load and initialize the next state automatically as well.

Creation of Game Objects can be handled any way by the user, I've written documentation on a very simple way of creating and handling Game Objects here, and it works extremely well with the GSM organization throughout AsciiEngine. I've implemented my own method of handling objects with the Factory pattern! Using the ObjectFactory within AsciiEngine it's very easy to handle game objects, as well as create new ones. See code for documentation -- it should mostly be copy/paste to create a new object. UPDATE: Game objects are now called Game Entities. As such, all game entities are now component based! Please see the source on github for details. A post in the future about component-based architecture will likely be written.


Creating Images:
Creating images in Ascii art will require a good tool for more complicated images. Here's an interesting thread on a few different programs for such. Perhaps it might be a good idea to create your own tool in the Windows console with AsciiEngine! Here's some additional documentation to pursue the idea of creating your own drawing tool: link.

Updating AsciiEngine
I'm completely open to most all suggestions on AsciiEngine. I've never written anything open-source before, so there may be good insight that'd help the project out! Feel free to contact me about questions on how to use AsciiEngine, or for feature requests, or just to talk/show off thing you've made :)

Sunday, July 1, 2012

Hash Tables: Introduction

I've just set up my first hash table after a bit of studying; it's time to write about it! Docendo discimus ~

Wikipedia has a nice definition of what a hash table is: LINK.
In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys (e.g., a person's name), to their associated values (e.g., their telephone number). Thus, a hash table implements an associative array. The hash function is used to transform the key into the index (the hash) of an array element (the slot or bucket) where the corresponding value is to be sought.

The idea of setting up a hash table is that by using a hash function you can index an array without actually knowing what the index is.


For example say you have an array of structures that look like this:

typedef struct _ASSETFILE
{

  char *fileName_;
  assetFile *asset_;
} ASSETFILE;

This array holds structures that represent asset files for some sort of project (images, sounds, data, etc). Imagine you want anyone to be able to access any asset file in this array by using a function like so: FindAsset( "filename" );. How would you go about creating this FindAsset function? The easiest way would be to use a linear search starting at the beginning of the array. Simply compare the string of the parameter passed to the FindAsset function with the string within the ASSETFILE structure until a match is found.


This can be a slow search. Perhaps the next optimization would be to order the entire list alphabetically from lowest to highest. This would allow a binary search through the array by using strcmp from the standard library. There wouldn't be any faster search method than a binary search in this scenario. Inserting into an ordered list would require a binary search as well.


However by using a hash function you can achieve even faster searches. By using a hash function you can convert the filename provided to the FindAsset function directly into an index to index the array of ASSETFILE structs. The filename is what is called a key. By hashing a key an index to the hash table is generated, and the corresponding ASSETFILE struct can be accessed very quickly. It's important to note that the order in which the entries are stored into slots is random. A good hash function will randomly map keys to indices with an even distribution (avoids clustering).

The relationship between keys and indices is not a one to one ratio however. Keys to indices is of a one-to-many ratio -that is multiple keys can resolve to the same address. Each key must be unique, however, in order for the hash table to function properly.


In short, using a hash table allows for indexing of an array by some other type of data than simply an integer. There are many different hash functions available on the internet, and a simple google search will yield many results.


I've set up a demonstration program to show the usage of a hash function here. I handle collisions with something called linear probing. A collision is whenever a key maps to a location in the table that already contains an entry (two or more keys are resolving to the same slot). A collision can be resolved in many different ways, though the way I chose in my sample program was linear probing. Linear probing is simply moving down one slot in the table until a free slot is found. The entry to insert is then placed. Each time the index is incremented (or decremented, direction doesn't matter as long as your are consistent) to find an empty slot it is called a probe. This means that for each lookup you'll need to compare the key to the entry being looked at and check for a match, as when you get a hashed index it doesn't necessarily mean that the key you have had been placed into that entry; a previous key may have inserted a value there already. When attempting a lookup first check the slot the hash resolves to. If no match is found, check the next slot (using the same direction as before) until you find a key match, or an empty slot. If you find an empty slot then that means your lookup concluded that no entry matches in your table.


Linear probing forms clusters of entries, however, since you resolve collision by placing entries into the next available slot. Each entry placed into the table increases the chances of a collision, and as the table fills up a lot of time ends up being spent on probing looking for an empty slot. There are ways of breaking up these clusters like double hashing, or by having each slot point to a linked list of entries. However with a good hash function clusters can be kept to a minimum as long as the table doesn't get too full.



Load factor is a term that represents the total number of current entries divided by the table size. Once a hash table has a load factor of .7 or so linear probing starts getting dramatically slow.


Image from Wikipedia. As you can see once the load factor of the table hits around .8 the time spent probing increases dramatically.


In order to retrieve an entry from the hash table (with linear probing, as in my sample program) all you'd have to do is take your key and pass it to your hash function. Once this is done you'll have the index to start your search. Check to see if the key matches the key within the index. If it does not match then increment (or decrement, whatever direction you probe in you must do here for consistency) the index by one and compare again. Once a match is found the lookup function has done its job! If no match is found and the search function runs into an empty slot, that means that no match had been found. Here's the lookup function from the sample program:

char *TableLookup( const char *Key, char *table[] )
{
  unsigned index = UHashMod( Key, TABLESIZE );
  unsigned indexStart = index;

  // Only search through clusters, don't hop over empty entries
  while(!IsEmpty( table, index ))
  {
    // Break from loop if found matching entry
    if(table[index] != DELETED)
    {
      if(strcmp(table[index], Key) == 0)
        break;
    }

    ++index;

    // wraparound to beginning of table
    if(index == TABLESIZE)
    {
      index = 0;
    }

    // If searched entire table
    if(indexStart == index)
    {
      return NULL;
    }
  }

  return table[index];
}

In the above example the data stored in the table was the same as the key, so the return type is a pointer to the stored data in this instance. In order to support the deletion of entries you must mark a slot as deleted. This is because if a slot is simply marked as empty, then it can mess up the order of searches! Searching relies on the fact that collisions are resolved with linear probing. If you delete an entry that had previous collisions, the entries next to it will not be found in searches. However if you mark slots as "deleted" with a special value, than you can modify searching to not stop on "deleted" slots, and you can modify insertion to insert values into slots that are marked "deleted". You can see in the above code that searches hop over deleted slots, but stop at empty ones.


Now lets talk about this hash function. Creating hash functions seems very difficult, but luckily for around 50 or so years research has been put into them, and as such there lots of well documented hash functions and hash libraries all over the place. Here's the one I chose to use in my demonstration program:

// Hashing function from Program 14.2 in the Sedgewick book
unsigned UHashMod( const char *Key, unsigned TableSize )
{
  unsigned hash = 0;      // Initial value of hash
  unsigned rand1 = 31415; // "Random" 1
  unsigned rand2 = 27183; // "Random" 2

  while (*Key)
  {
    hash = hash * rand1;     // Multiply hash by random
    hash = (hash + *Key);    // Add in current char, keep within TableSize
    rand1 = (rand1 * rand2); // Update rand1 for next "random" number
    Key++;
  }

  return hash % TableSize;
}

The hash function is simply converting the string into a random (yet consistent) interpretation as an integer. This integer is then modulo'd with the TableSize variable, which is the size of the table to be inserted into to ensure that it is placed randomly within the bounds of the table.


Here's the output of the sample hash table program I wrote. It creates a table with 157 slots (more on why I chose 157 later -hint: it's prime), and then reads a text file line by line and inserts each individual line into the table with a hash function. I then run a demonstration with a hash lookup function. I created support for deletion of entries, and the program gracefully handles the entire table being full (this is easily detected when a search goes through the array and ends up where it started by wrapping from the last element to the first):

Dump table contents (length 157 char pointers):
      * NULL
      * NULL
      * NULL
        Lexicon
        Tiger Express
        Tiny Tim
        Beer cans
        Bottle
        I LEIK TOITLES
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
        Teeter Totter
      * NULL
      * NULL
        test2
      * NULL
      * NULL
        das
        Snickerdoodle
        So many probes >.<
      * NULL
      * NULL
      * NULL
      * NULL
        test
      * NULL
        Baha Blast
      * NULL
        WTF
      * NULL
        SC Original
      * NULL
      * NULL
      * NULL
      * NULL
        Schism
      * NULL
      * NULL
      * NULL
      * NULL
        asd
        Tylanol
      * NULL
      * NULL
      * NULL
      * NULL
        Contraceptor
      * NULL
  --->  DELETED
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
        Dignity
        popo
        BrooD WaR
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
        Quadruple
      * NULL
        Typo
      * NULL
      * NULL
        alphabet
        StarCraft 2
        Rover Dover
        Extra power
        phantom
      * NULL
      * NULL
      * NULL
        Mountaineous
      * NULL
        skdjf
        a
        b
      * NULL
        Carbon
        This is a string!
      * NULL
      * NULL
      * NULL
        Alexis
      * NULL
      * NULL
        DIuasplOis
        Duplicate
        Contraption
      * NULL
      * NULL
      * NULL
        Beasty Boys
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
      * NULL
        Turdy Nerdy
        Meek
      * NULL
        Plasma
      * NULL
        asdf
        Turtles
        Flayva Flave
        Bumble Bee
      * NULL
      * NULL
      * NULL
      * NULL
        OMG
      * NULL
      * NULL
      * NULL
        tab
      * NULL
        LOL
        tad
      * NULL
        <3
        Lionheart
      * NULL
        Nonchalant
        Supercalifragilisticexpialladocious
      * NULL
      * NULL
        I lover yous
      * NULL
      * NULL
        Digestion
        Avalanche

Table lookup demonstration: <key index>
Lexicon 3 | Tiger Express 3 | Tiny Tim 5 | Beer cans 3 | Bottle 5 | I LEIK TOITL
ES 6 | Teeter Totter 31 | test2 34 | das 37 | Snickerdoodle 38 | So many probes
>.< 39 | test 44 | Baha Blast 46 | WTF 48 | SC Original 50 | Schism 55 | asd 60
| Tylanol 60 | Contraceptor 66 | Dignity 74 | popo 75 | BrooD WaR 76 | Quadruple
 82 | Typo 84 | alphabet 87 | StarCraft 2 88 | Rover Dover 88 | Extra power 90 |
 phantom 91 | Mountaineous 95 | skdjf 97 | a 97 | b 98 | Carbon 101 | This is a
string! 102 | Alexis 106 | DIuasplOis 109 | Duplicate 110 | Contraption 111 | Be
asty Boys 115 | Turdy Nerdy 123 | Meek 123 | Plasma 126 | asdf 128 | Turtles 128
 | Flayva Flave 129 | Bumble Bee 129 | OMG 136 | tab 140 | LOL 142 | tad 142 | <
3 145 | Lionheart 146 | Nonchalant 148 | Supercalifragilisticexpialladocious 148
 | I lover yous 152 | Digestion 155 | Avalanche 156 |

Error count: 0
Probe count: 19
Entry Count: 58
Table size: 157
Duplicate entries: 2
Load factor: 0.369427

The text file I used is provided in the source. Note that duplicate entries were handled by taking no action. I felt that there wasn't a need to hold duplicates within a hash table, and simply just reported that duplicates were found. Here are some final notes I took from one of my CS courses:
  • Hash tables rely on the fact that the data is uniformly and randomly distributed.
  • Since we cannot control the data that is provided (from the user), we must ensure that it is randomly distributed by hashing it.
  • Hash tables whose size is a prime number help to insure good distribution. Also, table sizes that are a power of 2 work well if the stride (second hash in double hashing) is an odd number.
  • Since the data is not sorted in any meaningful way, operations such as displaying all items in a sorted fashion are expensive. (Use another data structure for that operation.)
There are many different types of collision resolution for hash tables. Using chaining (linked lists) seems to be a great way to store lots of data. The chains can even be ordered to allow for optimized searching (though this is unlikely to be worth the trouble). However for a small amount of keys and a small table, linear probing should work perfectly fine. There are also other probing methods, such as quadratic probing, double hashing, pseudo random probing (seeding with the key). If probing is the collision method chosen, then support for growing the hash table like a vector may need to be implemented, depending on the requirements of the table. Chaining avoids the growing issue altogether.


I will be using the code constructed here for my next large project. It will actually be solving the hypothetical issue described at the beginning of the post! This will be very handy, as nobody will have to manually keep track of any files anymore; I'll have code traverse a single directory full of assets and then automatically add them as entries to a hash table. Lookups will be highly optimized (which is important, lookups are highly common in a game project).


Additional resources:

Tuesday, June 26, 2012

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