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.