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

22 comments:

  1. Smells like poo, looks like poo...

    ReplyDelete
    Replies
    1. why?? he has a good idea here ... if you did not understand ... it is your poo mind ... cannot see beyond your poo-ish logic!!

      Delete
  2. agreed… if you need such a rigid structure,
    you might want to rewrite your code, or use
    a real « OO » language (for a convenient
    definition of object oriented).

    what's up with those TYPENAME_ anyway.

    ReplyDelete
    Replies
    1. Because we are only allowed to use C in this semester.

      Delete
  3. I would have used C++, but like I said the limitation was C.

    ReplyDelete
  4. Well, look at all the vitriol without any sort of reasonable criticism.

    For my part, I like the general idea, though I wonder about the overhead cost of storing all those FP's in the struct like that. I wonder if there isn't a better way -- perhaps relying more heavily on a command-pattern-style approach. For instance -- shouldn't the draw code be largely the same in every case? If a small change is needed in a few cases, for efficiency purposes it may be better to hardcode around them, in a more general setting, I wonder if some clever use of void pointers could get a memory savings (at, perhaps, the cost of some safety).

    ReplyDelete
    Replies
    1. You can generalize code for whatever you like. I chose to place the pointers inside of the object themselves, but I could have simply abstracted them away into a manager. You can run introspection on the object from a manager of some sort due to the enumerated ID, and then handle function calling there. The real benefit to placing the pointers in the objects however was mostly just syntactical. See the example code of looping through a linked list of objects? It's really just personal preference as the extra memory for storing pointers in the objects was pretty negligible for this project.

      Delete
  5. I think this article actually demonstrates the major problem with this approach - there is no automatic support to keep the definitions for related "struct"s consistent.

    In the definition for _GameObj ID and image are defined in the opposite order from the subsequent _Bat and _VeryLargeBat.

    ReplyDelete
  6. Hi. There are several people, including me, that have to work in "pure C", emulating Object Oriented Programming, even that C++, was around.

    There is even a virus like that:
    http://www.wired.com/threatlevel/2012/03/duqu-mystery-language-solved/
    http://en.wikipedia.org/wiki/Duqu

    And, even a G.U.I. framework
    http://en.wikipedia.org/wiki/GObject

    ReplyDelete
  7. is this blog going to keep going? I was enjoying it...

    ReplyDelete
  8. This is not completely clear to me...
    How do you assign the function pointer and eventually the arguments to the objects?

    Let's assume the case I'm initializing an object in this manner:

    void init(Obj *pobj, void (*move)())
    {
    pobj->move= move;
    }

    and I wanna assign a generic movement function to it, like this to the object.

    void moveObj(Obj *pobj) { pobj->x++; }

    How can I pass the arguments along with the function pointer?
    Something like this init(&bat, moveObj($bat)); I mean...

    Hope to be clear...

    ReplyDelete
    Replies
    1. Hi guys, first thing i wanna say is that i enjoy reading your nice article.
      I would have done things differently with another structure to handle function pointers because of the cost in term of memory.
      (Nb_objects * 5 * sizeof(void (*)(gameobject *))) VS (5 * sizeof(void (*)(gameobject *)) + memory overhead due to the manager)

      One depends on the size of the linked link whereas the second one doesn't.
      If you're willing to have many entities it could be better to choose the second solution.
      If you tend to have only a few ones, the first proposal is ok :)

      to Pix3l : init(&bat, &movObj) is the right prototype.



      I

      Delete
    2. Yes, I solved the issue by calling the function later like this: object[i].movObj(&object[i]);

      Delete
    3. @ Rexuo: http://cecilsunkure.blogspot.com/2012/08/object-oriented-c-virtual-table-vtable.html

      Delete
  9. Hi everyone,
    In my time I've seen several practical uses of C written to mimic OOP techniques.
    I've also had to maintain such code, and here is where the problem lies. The call trees are not obvious or discernible from static code analysis.
    However, that is not to say that this OOP approach is not interesting, because I do find it intriguing. But I would hesitate to use it in a situation where most of your devs are c programmers who have not had exposure to OOD and languages such as java.

    ReplyDelete
  10. I'm guessing the assembly for this code and for standard C++ object-oriented code is very similar. Since C++ operates by silently passing pointers to objects in its member functions, you have a very similar structure when you look at how things are operating closer to the hardware. Understanding how this code operates allows a much deeper understanding of how C++ programming works.

    ReplyDelete
  11. The fact that you link to a book at the end of the post that teaches object-oriented programming in C only helps confirm my thinking. Remember, the original C++ compiler was a preprocessor just converted C++ into C.

    ReplyDelete
  12. I was trying to looping over my game entities, a simple singly linked list.
    Check every entity if collide with the player and if so, destroy it from the list with free, but I continue to get segfaults.
    What is wrong in this code snippet?

    http://pastebin.com/pzdKMxBD

    ReplyDelete
    Replies
    1. I can't tell why you're modifying headList, and I'm not sure what tailList is. Usually with a singly linked list you'll use two variables: currentNode and previousNode. You loop through the list with currentNode, and make sure previousNode is always pointing at the previous node to currentNode. You can then do: previousNode->next = previousNode->next->next to disconnect currentNode, allowing you to call free on it.

      Try restructuring things a little bit. You can also consider using my linked list: https://github.com/RandyGaul/AsciiEngine/blob/master/AsciiEngine/LinkedList.h

      There's the function LIST_CALLER that does actions on each node in the list, so you could use it to perform update and gravity applications. The way I have AsciiEngine setup, is I actually use a callback to send all entities in the list a message, which can be update or collision tests: https://github.com/RandyGaul/AsciiEngine/blob/master/AsciiEngine/EntityManager.c

      Delete
  13. Headlist is the head of the list, tailList is simply the tail.
    In the first check, I control if the current node is the head, if so I set the head pointing to the next node, since the current will be destroyed.
    After, I control if the node is the tail of the list and set the "next" pointer of the previous one to null, since it will be the new tail.
    In the last I'm handling a common middle list node, delete it and rebuild connections.

    Previous pointer is valued with the last looped node, in the first cycle will be null, in the secondo will be head, and so on....

    All ok if I destroy every single node from head to tail, but if i try to destroy a middle one the game crash, this is my problem...

    Anyway, I will check your little library, maybe I will find something good, thanks :]

    ReplyDelete
  14. Oh I see, you must not be handling things properly if you try to remove something from the middle. Try stepping through your code during a test-case to see exactly what is happening. You should be doing something like: previousNode->next = currentNode->next; free( currentNode ).

    ReplyDelete

Note: Only a member of this blog may post a comment.