Tuesday, September 18, 2012

Memory management 1/2

Hey guys!

As I promised before via Twitter, this post is about the memory management / tracking systems we use in our K15 EngineV2 (I hate that name...gotta change it soon).

Memory leak detection and memory tracking

Memory leaks...At least every serious C/C++ programmer has had several in his career. They are hard to track and solve sometimes. Sure, there are tools that help you with that such as Application Verifier from Microsoft or some other debug helper, but they are either ridiculously slow during run-time or hard to configure. 

I've decided to implement a very, very easy to program but nevertheless efficient memory leak detection system which also can be used to track memory usage of the engine at the same time.

Lets start off by creating a new struct to hold all those useful information that we want to track.

 struct MemoryBlock  
      {  
           MemoryBlock *Next;          /*Address to next memory block*/  
           MemoryBlock *Previous;     /*Address to previous memory block*/  
           const char *File;          /*File the allocation occurred*/  
           unsigned int Line;          /*Line at which the new call happened*/  
           unsigned int Size;          /*Size of the allocated memory*/  
           bool IsArray;               /*Was the memory allocated by new[]?*/  
      };  

The first two members (namely Next and Previous) are to keep track of each MemoryBlock in a linked list (we'll come to that later).

The next member File and Line are to keep track of where exactly the new call of the leaking memory occurred. That gives you a good idea of where to start looking for errors in your code.

Member Size is to keep track of how much memory has been allocated and with IsArray you can check whether or not the memory has been allocated via new[] or new.

The next step would be to overload global new, new[], delete and delete[]. This is easily done:

 void *operator new[](unsigned int iSize,const char* sFile,unsigned int iLineNumber);  
 void *operator new(unsigned int iSize,const char* sFile,unsigned int iLineNumber);  
 void operator delete[](void* pPointer);  
 void operator delete(void* pPointer);  

You may wonder where the parameter sFile and iLineNumber are getting filled in the new[] and new operators (iSize is getting filled automatically). For this purpose I created a simple macro that looks like this:

 #define K15_NEW new(__FILE__,__LINE__)  

Whenever you use K15_NEW instead of the normal new (or new[]) operator, the global new operators that we just declared are getting called (If you're unfamiliar with the __FILE__ and __LINE__ macros just look here).

What we do next is to declare a function that does all the dirty work for us (allocating memory, expand the linked list of MemoryBlock structs, counting the call to new and add the size of the new memory to an internal counter).

This would be the code of such a function:

 void *Allocate(unsigned int iSize,const char* sFile,unsigned int iLine,bool isArray)  
 {  
      //We need some more size for the MemoryBlock struct.  
      iSize += sizeof(MemoryBlock);  
      //Allocate memory.  
      char *pPointer = malloc(iSize);  
      //This function does fill the MemoryBlock struct and add it to the linked list.  
      ProtocolMemoryAllocation(pPointer,iSize,sFile,sLineNumber,bArray);  
      //We need to shift the memory so that the memory we return is the memory the user wanted.  
      pPointer += sizeof(MemoryBlock);  
      return pPointer;  
 }  

 void ProtocolMemoryAllocation( void* pPointer,unsigned int iSize,const char* sFile,unsigned int iLineNumber,bool bArray )  
 {  
      MemoryBlock* pBlock = (MemoryBlock*)pPointer;  
      //Set all the flags  
      pBlock->IsArray = bArray;  
      pBlock->Size = iSize;  
      pBlock->File = sFile;  
      pBlock->Line = iLineNumber;  
      //Add block to linked list.  
      _AddMemoryBlock(pBlock);  
      //Increase size of allocated memory (to keep track of the memory usage)  
      ms_iAllocatedMemory += iSize;  
      //Increment the counter that keeps track of new/delete calls.  
      ++ms_iAmountAllocations;  
 }  

The same goes for deallocation:

 void Free( char *pPointer,bool bArray )  
 {  
      //Shift the pointer so that it points to the whole memory block that we allocated previously  
      //(including MemoryBlock).  
      pPointer -= sizeof(MemoryBlock);  
      //Delete the linkedlist entry and do decrease the new/delete counter.  
      ProtocolMemoryDeallocation(pPointer,bArray);  
      //finally free the memory.  
      free(pPointer);  
 }  

 void ProtocolMemoryDeallocation( void* pPointer,bool bArray )  
 {  
       MemoryBlock *pBlock = (MemoryBlock*)pPointer;  
      //Does the memory gets freed with delete[] if it got allocated with new[]?  
       assert(bArray == pBlock->IsArray);  
      //Decrease the amount of currently allocated memory.  
       ms_iAllocatedMemory -= pBlock->Size;  
      //Decrement the new/delete counter.  
       --ms_iAmountAllocations;  
      //Remove the block from the linked list of MemoryBlock structs.  
       _RemoveMemoryBlock(pBlock);  
 }  

The next thing we need to do to implement the memory tracker is to call the above implement functions by our overloaded new, new[], delete and delete[] operators. This is an easy task:

 void *operator new[](unsigned int iSize,const char* sFile,unsigned int sLineNumber)  
 {  
      return Allocate(iSize,sFile,sLineNumber,true);  
 }  
 void *operator new(unsigned int iSize,const char* sFile,unsigned int sLineNumber)  
 {  
      return Allocate(iSize,sFile,sLineNumber,false);  
 }  
 void operator delete[](void* pPointer)  
 {  
      Free(pPointer,true);  
 }  
 void operator delete(void* pPointer)  
 {  
      Free(pPointer,false);  
 }  

To add a little bit of leak detection, we could implement yet another function that iterates over the list of MemoryBlock structs (which should be empty if there's no leak in your application) and print the desired information into a log file or a message box. Call this function at the end of your application and you're good to go!

That's it...We now implemented a fully working and yet efficient memory tracking and leak detection tool.

The next post will be completely about memory management. I'll introduce two different approaches to  memory management (being a memory pool and a memory heap).

Verse network protocol

I recently watched this video of Eskil Steenberg, the creator of Love, talking about the tools he created for Love and the Verse network protocol he used to synchronize the 3D models between his tools.

I find that technology amazing! I just downloaded some papers describing the protocol (how it works, etc.) - maybe we can add this technology to our very own tools, allowing the 3D artists working with their favorite modelling tool (Blender for instance has native Verse support) while examining the results live in the editor of our engine.

I bet our 3D modeler at K15 Games will wet his pants if I tell him about that ;)

Thursday, August 9, 2012

Book recommendation (3D Engine)

I'm currently busy coding the 3D renderer interfaces and the object model (mainly serialization) at the moment. Due to my lack of 3D renderer coding knowledge, I searched for books covering that topic.

The book I found most interesting (and bough eventually) is
3D Game Engine Design 2nd Edition by David H. Eberly

It covers nearly every topic you need for implementing a modern 3D renderer.
The source code for Eberlys Engine "Wild Magic" comes with the book and is always worth a look if you want to know implementation details.

Saturday, August 4, 2012

Server online - we're ready to roll

Our server is finally online.
We are currently busy configuring it.

We want to use it as a SVN-/, Web-/, Mail-/ and Buildserver (Probably Hudson).
Soon you can visit us at www.k15games.de (a .com domain will follow soon).

Once the website is online, I'll post again ;).

Everyone is very busy at the moment coding, designing and drawing.

I'm very happy with how things are doing right now and I hope that it'll stay that way.

Friday, June 8, 2012

We're getting bigger!


I'm happy to announce that "K15 Games" has 4 new members (5 in total now).
We now consists of 2 1/2 Programmer, 2 1/2 3D Artists, 1 Level Designer.

What that means and what you can expect from us will be "revealed" in later posts.

The next generation?

I just saw a video about the new Unreal Engine 4.
The video was about a technical artist showing what you can do with the
UED (Unreal Editor) 4.


Everything in the video looks very promising, but what caught me the most is what happens at the end of the video (at about 9:40). The guy showing the engine opens Visual Studio from within the UED and changes some c++ code (in the video he's manipulating the player's jump height).

When he returns to the game a little message appears saying "Compiling C++ Code...".
After a few seconds a new message appears saying "C++ Code successfully compiled".

After that he was jumping twice as high as before.
This is IMO one of the most astonishing things I've ever seen. In that way you could use C++ as a scripting language...A very powerful one.

I have absolutely no idea how they've implemented that, but that feature is just amazing and I'm eager to find out how that works ;).

Monday, April 2, 2012

Visual Studio 2011 Beta

I just downloaded the Visual Studio 2011 Beta.

I wonder how much they changed except the design. (I'm not a big fan of the new metro layout)

However, I look forward to some of the new C++11 features that have been implemented in VS11.

EDIT: Am I the only one having speed problems with VS2011? Yesterday I started a little project in VS2011 and when I wanted to debug it, it took like 2 minutes until the program even started. I wonder if any one else is having problems like that?

Monday, March 26, 2012

More C++11 features implemented in VS 11

Some features of C++11 that where missing in VS10 are now available in VS11. (e.g threads)

For a full overview check here: http://msdn.microsoft.com/en-us/magazine/hh852594.aspx

Most annoying error ever. (Visual Studio Watch Window)

Hi folks.

I just "fixed" the most annoying and strangest error I've faced so far.

I wanted to watch a GameObject object in Visual Studios Watch Window, to see if some attributes were set properly. The strange thing was, that the Watch window constantly showed me very strange result.

I had a function that was like that:

 //...Code  
 gameObject->setSize(32,32);  
 //..Code  
 GameObject::setSize(int w,int h){  
      this->size = Size(w,h);  
 }  

After the above function the watcher would show me something like
gameObject->size        Size -> w: 10000434     h: 10283848 (obviously totally wrong results)

It took me like 3 hours and a good bunch of nerves 'til I figured out that the header files of my engine were outdated in the project folder. I'm not sure how that exactly led to the above error but after I updated the engine header files in the project folder everything went properly again.


SO IF YOU'RE FACING STRANGE RESULTS IN THE WATCH WINDOW OF VISUAL STUDIO, MAKE SURE YOU UPDATE YOUR HEADER FILES OF 3RD PARTY LIBRARIES / FRAMEWORKS BEFORE YOU START WASTING 3 HOURS OF YOUR PRECIOUS LIFE!


Sincerely, the most annoyed person in the world.

Monday, March 5, 2012

New splitscreen approach.

As posted here, I implemented a splitscreen mode for the engine.
The implementation is sort of dirty as all graphics are getting recreated per camera.

For instance: you want to draw a graphic with 4 player split screen.The graphic will then get created 3 times (1 graphic for each camera). That ensures that every camera has its own graphic with which it can do what ever it wants (like zoom, rotation, etc.)

As you can imagine, that is quite expensive and for many graphics on screen pretty memory consuming.
That seemed like a wasteful but working implementation until now.

It's just theoretical, but I'm pretty sure it is possible to reimplement it so that every graphic will only get drawn only for one camera per tick. If there's more than one camera, the graphic will get drawn for the next camera the next frame.

It'll go like this (C style pseudocode):

 void draw(IGraphic graphics*[]){  
      if(CURRENT_CAMERA < AMOUNT_CAMERA){   
           CURRENT_CAMERA = 1;               // Start from first camera  
      }  
      for(int i = 0;i < AMOUNT_GRAPHICS;i++){ //go through all graphics.  
           m_cameras[CURRENT_CAMERA]->draw(graphics[i]); //draw graphics into buffer of the current camera  
      }  
      CURRENT_CAMERA++; //Increment to camera counter and leave the draw function.  
 }  

So if the game uses 3 cameras it'll look like this:

Frame 1 : Draw graphics for camera 1
Frame 2 : Draw graphics for camera 2
Frame 3 : Draw graphics for camera 3

Frame 4 : Draw graphics for camera 1
Frame 5 : Draw graphics for camera 2
Frame 6 : Draw graphics for camera 3
....

I don't know if this implementation will cause a big delay, but I guess it's for me to find out ;)

Edit:
This approach will obviously split the FPS in half.
e.g. 60FPS / 2 Cameras = 30 FPS per camera.

That means that the game needs to run with ~120 FPS to look smooth with 4 cameras....
Shouldn't be a problem with a 2D game.

Tuesday, February 21, 2012

Use typedef to make your code easier to read.

I want to talk about the C++ keyword "typedef" in this post and how it can make your life easier.

I assume that you often work with hard to read template classes (like 90% of the STL).
Consider this code given the above assumption:

 void foo(){  
   std::list<Class> myList;  
   //...  
   for(std::list<Class>::iterator iter = myList.begin();iter !+ myList.end()iter++){  
    //..  
   }  
  std::tr1::smart_ptr<Class> myInstance(new Class());  
 }  

This type of code layout can get very confusing very fast.
If you just add 3 typedef's at the beginning of this code, you'll make the code much easier to read.

 typedef std::list<Class> MyClassList;  
 typedef std::list<Class>::iterator MyClassIterator;  
 typedef std::tr1::shared_ptr<Class> MyClassPtr;  

Using these typedefs, I'll show you what that code sample above will look like:

 void foo(){  
   MyClassList myList;  
   //...  
   for(MyClassIterator iter = myList.begin();iter !+ myList.end()iter++){  
    //..  
   }  
  MyClassPtr myInstance(new Class());  
 }  

That's much better, isn't it?

Wednesday, February 15, 2012

Yet another book

Today yet another book I've ordered, the CryENGINE Cookbook, got delivered.
I've ordered that book because we need to develop a game, in which the player must solve physical tasks,in one of my courses at the university.



I choosed the CryENGINE because I already got in touch with it during one of our courses.

If I have something worth showing, I'll post about it.

Monday, January 23, 2012

Splitscreen

Wohoo!
10 lines of code changed = splitscreen :) (Up to 4 cameras will be supported by the engine)


New arrivals!

Today the new books I ordered got delivered!
Including:

Unfortunately my exams are starting tomorrow. I guess I'll have to wait until my exams are over until I can start reading these books, altough I couldn't stop me to take a quick glance at the C++ book ;).

In addition, I hope the math book is good. I'm slightly starting to get to the boundries of my mathematical knowledge :-/.


Saturday, January 21, 2012

Generic 2D collision system.

Today I want to explain the system I use in my engine for collision detection.
I tried to keep the collision system as generic as possible.

My engine provides a class called "CollisionComponent". You can add one or more components to a game objects to make them collidable. (Collision detection is done via collision rectangles).

To make the collision handling as generic as possible I decided to realize the handling "response" (the point where it'll get decided what to do with the collided objects) with function pointers.

You can "subscribe" gameobjects via typename (String) or a specific id (int) and with a pointer to a function that receives two pointer to game objects(first is the object that did "the impact" and the second is the object that got hit) and returns void.

Here's a little code snippet to make it more clear how that works:
 void collision_handler(GameObject *object1,GameObject *object2)  
 {  
    //...Do fancy stuff here  
 }  
 int main()  
 {  
    GameObject object1("Type1");  
    GameObject object2("Type2");  
    //...  
    //...  
    CollisionComponent *collComp = new CollisionComponent();  
    CollisionComponent *collComp2 = new CollisionComponent();  
    object1.addComponent(collComp);  
    object2.addComponent(collComp2);  
    //..  
    //subscription with type  
    CollisionManager::subscribe(object1.getType(),object2.getType(),collision_handler);  
    //..  
    //subscription with id  
    CollisionManager::subscribe(object1.getID(),object2.getID(),collision_handler);  
    //..  
 }  

The difference between subscription via type and id is that multiple game object can have the same type (for very generic collision handling like "bullet hits player" or "weapon hits enemy").If you want to make more specific collision handling you can use the subscribe function that uses ids because the ids of the objects are unique.

The only problem is that each tick each game object gets checked with every other game object.
That's not very performant, but I don't know how to do it better, yet.

Sunday, January 15, 2012

Use DoxyGen to automatize the documentation of your projects.

I just want to point out tool I discovered after reading one of my new programming books.

The tool is called DoxyGen and you can download it from here.

DoxyGen is a tool which will surf through your source code and look for certain marks.
Consider you have a function like
 bool doSomething(int x);  

If you want to document this function, you need to enter the DoxyGen documenting marks like this
 /**  
 * This method does something  
 * @param x - amount of bla  
 * @return bool - true if successful or false if not.  
 */  
 bool doSomething(int x);  

When you start DoxyGen it'll find these marks (@param etc.) and create a html documentation based on the informations you write behind those marks.

After DoxyGen is finished, the result will eventually look like this (Its a screenshot of the documentation from my engine on which I work currently):


Monday, January 9, 2012

Type conversion using template functions

Yesterday I came up with a new way to make type conversions prettier.
I want to explain you how that works in this post.

As you might know, I work with a component based object model in my engine (see here).
In this kind of object model, you sometimes need to modify the component of certain objects after you added them.

To do that I implement a getComponent() function, which - in the past - returned a object of the type of the component interface (called IComponent). Type conversions needed to be made afterwards to work with the desired implementation. That used to look like this:

 GameObject gameobject;  
 RenderableComponent *renderableComponent = new RenderableComponent("graphic.png");  
 gameobject.addComponent(renderableComponent);  
 //Somewhere else in the code in another function.  
 IComponent *component = gameobject.getComponent("RenderableComponent");  
 RenderableComponent *renderableComponent = static_cast<RenderableComponent*>(component);  
 //.. do stuff with renderablecomponent.  

I found that code pretty ugly and unnecessary complicated, so I thought of another idea to do that user friendlier. The first step I did was to change the getComponent() function to a template function.

The function looked like this:

 IComponent *GameObject::getComponent(const String &componentName){  
      for(std::list<IComponent*>::iterator i = this->m_components.begin();i != this->m_components.end();i++){  
           if((*i)->getType() == componentName){  
                return (*i);  
           }  
      }  
      return NULL;
 }  

With template support it now looks like this:
 template<class T>  
 T *getComponent(const String &componentName){  
      for(std::list<IComponent*>::iterator i = m_components.begin();i != m_components.end();i++){  
           if((*i)->getType() == componentName){  
                return static_cast<T*>((*i));  
           }  
      }  
      return NULL;  
 }  
(Hint: If you don't know nothing about template functions, check here)

As you can see, the user determines the return type via the template type ( So there's no ugly conversion needed afterwards.)

The result is (in my opinion) much nicer source code.
The following is the above example reused with the new getComponent() template function:
  GameObject gameobject;   
  RenderableComponent *renderableComponent = new RenderableComponent("graphic.png");   
  gameobject.addComponent(renderableComponent);   
  //Somewhere else in the code in another function.   
  //IComponent *component = gameobject.getComponent("RenderableComponent");   
  //RenderableComponent *renderableComponent = static_cast<RenderableComponent*>(component);  
 RenderableComponent *renderableComponent = gameobject.getComponent<RenderableComponent>("RenderableComponent");   
  //.. do stuff with renderablecomponent.   
I don't know what about you, but I find it much nicer ;) .

Compared with a macro like:
 #define GET_COMPONENT(type)(getComponent<type>(#type))  

The example could even get more improved to look like this:
  GameObject gameobject;    
  RenderableComponent *renderableComponent = new RenderableComponent("graphic.png");    
  gameobject.addComponent(renderableComponent);    
  //Somewhere else in the code in another function.    
  //IComponent *component = gameobject.getComponent("RenderableComponent");    
  //RenderableComponent *renderableComponent = static_cast<RenderableComponent*>(component);   
  RenderableComponent *renderableComponent = gameobject.GET_COMPONENT(RenderableComponent);  
  //.. do stuff with renderablecomponent.