Memory pools and Artificial Intelligence

As I sit here on this fine friday evening with some chilinuts and a cold one I realize that I haven't done an update for a while, mostly since I haven't got that much going on. So in this post I will talk mostly about our previous project (Portal in 2D) and the touch briefly on what I think I'm going to do next or sometime in the future.

The past!

So It's been about a month since the last course ended (Advanced c++ for Games) where me and  Petter Vernersson made a "clone" of Valve's game Portal in 2D. Though I'm not really going to talk about that game here is a link for anyone who want to try it out. (people without VS12 might need to install this aswell)

Believe it or not that is all programmer art, all credit to Petter!

What I'm going to talk about is something I worked on in that game, the memory manager. It's not a visible thing, nor is it a noticeable object in this specific project. A memory manager or "memory pool" as I will refer to it as, is a class that handles *surprise* memory. In short what a memory pool does is to allocate a large amount of memory and then designates that memory to any one who needs it, this is ideal for programs that creates and delete a lot of objects often.

In the words of IBM:
"malloc and new make calls to the operating system kernel requesting memory, while free and delete make requests to release memory. This means that the operating system has to switch between user-space code and kernel code every time a request for memory is made. Programs making repeated calls to malloc or new eventually run slowly because of the repeated context switching."

N.B. I will not describe the entire process of creating a memory pool, if you want to know more about that read the IBM documentation linked further down.

Now for some code!

//In the header
static std::vector<void*> m_Pool;

static std::vector<void*> m_gameObjectList;

static const int POOL_SIZE = 2048;

static const int START_GUARD = 0xde;

static const int END_GUARD = 0xad;

static const int MAX_BLOCKSIZE = 72;

static const int GO_SIZE;

//In the cpp file

const int MemoryManager::GO_SIZE = sizeof(GameObject);

void* MemoryManager::allocate(size_t _object)

{

void* block = 0;

//Allocate GameObject

if (m_gameObjectList.empty())

  {

    block = new char[(GO_SIZE + 4) * POOL_SIZE];

    m_Pool.push_back(block);

    inGOList(block);

  }

void* blockPtr = m_gameObjectList.front(); //Gets a block

*((static_cast<char*>(blockPtr)) + GO_SIZE + 3) = 1; //Block no longer free

  m_gameObjectList.erase(m_gameObjectList.begin());

  return blockPtr;

}

In this example we have a class known as GameObject, and every time an new instance of this object is created that instance  calls this function(this is done by overloading the new operator). 

And what this function does is to check if there are any free memory adresses in the list of memory adresses(m_gameObjectList), if there is, this instance requests the first adress in the list and marks it as taken. If there isn't any, it allocates "POOL_SIZE"(in this case 2048) new spots or (GO_SIZE + 4)* POOL_SIZE bytes where GO_SIZE is the size of a GameObject, the +4 will be explained in a second.

And to allocate new space the memory manager uses the inGOList function:

void MemoryManager::inGOList(void* block)

{

  char* c = (static_cast<char*>(block));

  for (int i = 0; i < POOL_SIZE; i++)

  {

    char* guardByte = &(static_cast<char*>(block)[(i*GO_SIZE) + (GO_SIZE + (4*i))]);

    *guardByte = START_GUARD;

  guardByte++;

  *guardByte = END_GUARD;

  guardByte++;

  *guardByte = GO_SIZE;

  guardByte++;

  *guardByte = 0;

  m_gameObjectList.push_back(&(static_cast<char*>(block)[i*GO_SIZE + (4 * i)]));

}

}

The extra 4 bytes(the +4 in the previous part) are designated to two guard bytes, one byte that tells the size of the object, and the last byte is to show if the spot is available(0 = available,1 = taken). In this example the byte representing the size isn't really necessary since this manager is only used by the class GameObject, but if it were to use more classes it would need this to easily know what type of class this spot is for, so for re-usability I keept it in.

The guard bytes are there as failsafes, this is a custom memory management system and during development things can go wrong and so when an object tries to delete itself if the guard bytes aren't where they should be we know that memory is corrupt and we have to close the program. This is mainly used for debugging or if you work in a large group and someone tries to use your memory manager for a class that isn't compatible with.

For anyone who is interested in Memory Pool's/Managers read this documentation from IBM, they describe it much better than I can: Link to the IBM reference.

The Future

So Today Mike Sellers had a lecture on AI for the third year students, and since I'm already taking another AI course this intrigued me a lot. He talk alot about, everything really, but what I found most interesting when he talked about feelings for AI. I started to think about "The Sims" and how they work, and thought it would be interesting to implement "The Big Five" in an AI environment and make them interact with each other and react to each other.
We'll see when I have time for this and how it goes.

That's all for today, goodnight and thanks for reading.
-David Forssell