Keeping C++ Lists in Sync

Here's a small idea that you might find useful for your C++ code. I learned this while working at Sega of Japan.

In a lot of programming and especially in games we need lots of tables. Of the those tables need to have constants to access them or there may be parallel tables that need to stay in sync. Having a list of constants (defines or enums) and also having one or more tables those constants have to stay in sync with is a real pain in the ass. On top of that almost every programmer that's used them has run into problems where one of their tables was out of sync and it took time, could even be hours, to track down the bug only to finally figure out they were out of sync.

So, a solution is needed. Back in the 8 bit days we could not even do structures so all data was stored in parallel arrays. For example all enemies might need hit points, damage, speed etc. All that in today's world would be stored in an array of structures but back then it was much more efficient to store them in parallel arrays. Unfortunately, trying to find the 49th line in each array to edit it was massively slow and error prone so I wrote a tool to take an structure like array and break it into parallel arrays.

Once we moved to structures that problem disappeared but using constants like PLAYER=1 and BUGEYEDMONSTER=47 and keeping those in sync with your tables was still a problem. And, other times you'd still need more than one table and all of it needed to stay in sync. Add something to one table and forget to update another and crash!

For that purpose my friend John Alvarado wrote a program called definer. It will take that kind of data and write out multiple files like a .h file with your constants and a .cpp file with your table, even a .inc file for your assembly language and anything else you might need as well.

That's great and it has it's place but sometimes it's overkill if you just have a small localized problem to solve. 

This trick I learned at Sega involves using a macro to define your constants and tables and enclosing each item in the list in an undefined macro. Then, anytime you need to you can generate a table and use the info you need. Since there is only 1 place to edit everything (the table macro) you never have to worry about things getting out of sync. Less work, less error prone, everybody wins.

To give you an example, here's some sample code you might see in a game to startup the various characters in a game. Somewhere you would have or load an array of data that lists the types of objects you need to appear and where they appear and then you'd walk the list and generate all the objects maybe something like this:



#include "limits.h"


struct VECTOR3
{
    float x;
    float y;
    float z;
};

/**************************** enums for types ****************************/

class GameTypeID
{
public:
    enum ID
    {
        Player,
        Ogre,
        Orc,

        last,
        force_int = INT_MAX,
    };
};

/****************** one entry in a table of game object ******************/
/******************  to introduce when the level starts ******************/

struct IntroData
{
    GameTypeID::ID  gameType;   // they type of object
    VECTOR3         position;   // where it starts
    VECTOR3         rotation;   // the way it faces
};

/************************ base class game object *************************/

class CGameObject
{
};

/******************************** Player *********************************/

class CPlayer : public CGameObject
{
};

/********************************* Ogre **********************************/

class COgre : public CGameObject
{
};

/********************************** Orc **********************************/

class COrc : public CGameObject
{
};

/***********************************  ************************************/
// some function that would take are new object and add it to our
// game system setting the object's position, orientation and other stuff

extern void AddObjectToSystem (CGameObject* pOb, IntroData* pIntro);

/******************************* InitLevel *******************************/
// takes an array of IntroData and
// starts up all the objects in that list

void InitLevel (IntroData* pData, int numObjects)
{
    while (numObjects)
    {
        CGameObject*    pNewOb = NULL;

        switch (pData->gameType)
        {
        case GameTypeID::Player:
            pNewOb = new CPlayer;
            printf ("made player\n");
            break;
        case GameTypeID::Ogre:
            pNewOb = new COgre;
            printf ("made ogre\n");
            break;
        case GameTypeID::Orc:
            pNewOb = new COrc;
            printf ("made orc\n");
            break;
        default:
            printf ("error: unknown type\n");
            break;
        }

        if (pNewOb)
        {
            AddObjectToSystem (pNewOb, pData);
        }

        ++pData;
        --numObjects;
    }
}

Maybe that was a bad example since there is not much to keep in sync there   But dang it, I already wrote it so we'll go with it. You can see that every time we add a new type of GameObject we have to edit the case statement in InitLevel() to match and we have to update the GameTypeID enum with a new type. Also there is a case statement which might be slow (it might have to check every case) and there is lots of redundant code (the assignment to pNewOb and the 4 printfs)

Here's the same example using the define macro list trick



#include "limits.h"


struct VECTOR3
{
    float x;
    float y;
    float z;
};

/***************************** list of types *****************************/

#undef GAMETYPE_OB
#define GAMETYPE_LIST   \
    GAMETYPE_OP(Player) \
    GAMETYPE_OP(Ogre)   \
    GAMETYPE_OP(Orc)    \

/**************************** enums for types ****************************/

class GameTypeID
{
public:
    enum ID
    {
        #undef GAMETYPE_OP
        #define GAMETYPE_OP(name) name,

        GAMETYPE_LIST
        last,
        force_int = INT_MAX,
    };
};

/****************** one entry in a table of game object ******************/
/******************  to introduce when the level starts ******************/

struct IntroData
{
    GameTypeID::ID  gameType;   // they type of object
    VECTOR3         position;   // where it starts
    VECTOR3         rotation;   // the way it faces
};

/************************ base class game object *************************/

class CGameObject
{
};

/******************************** Player *********************************/

class CPlayer : public CGameObject
{
};

/********************************* Ogre **********************************/

class COgre : public CGameObject
{
};

/********************************** Orc **********************************/

class COrc : public CGameObject
{
};

/***********************************  ************************************/
// some function that would take are new object and add it to our
// game system setting the object's position, orientation and other stuff

extern void AddObjectToSystem (CGameObject* pOb, IntroData* pIntro);

/******************************* InitLevel *******************************/
// takes an array of IntroData and
// starts up all the objects in that list

void InitLevel (IntroData* pData, int numObjects)
{
    while (numObjects)
    {
        CGameObject*    pNewOb = NULL;

        switch (pData->gameType)
        {
        #undef GAMETYPE_OP
        #define GAMETYPE_OP(name)   \
                case GameTypeID::name:  \
                pNewOb = new C ## name; \
                printf ("made " #name  "\n");   \
                    break;  \


        GAMETYPE_LIST
        default:
            printf ("error: unknown type\n");
            break;
        }

        if (pNewOb)
        {
            AddObjectToSystem (pNewOb, pData);
        }

        ++pData;
        --numObjects;
    }
}

As you can see we make a list called GAMETYPE_LIST and generate both the enum and the case code. That saved us at least one place, we no longer have to edit the case code but it's still going to be a lot of code when we get to hundreds of objects.

Let's optimize a little. Here's what I would probably do now-a-days



#include "limits.h"


struct VECTOR3
{
    float x;
    float y;
    float z;
};

/***************************** list of types *****************************/

#undef GAMETYPE_OB
#define GAMETYPE_LIST   \
    GAMETYPE_OP(Player) \
    GAMETYPE_OP(Ogre)   \
    GAMETYPE_OP(Orc)    \

/**************************** enums for types ****************************/

class GameTypeID
{
public:
    enum ID
    {
        #undef GAMETYPE_OP
        #define GAMETYPE_OP(name) name,

        GAMETYPE_LIST
        last,
        force_int = INT_MAX,
    };
};

/****************** one entry in a table of game object ******************/
/******************  to introduce when the level starts ******************/

struct IntroData
{
    GameTypeID::ID  gameType;   // they type of object
    VECTOR3         position;   // where it starts
    VECTOR3         rotation;   // the way it faces
};

/************************ base class game object *************************/

class CGameObject
{
};

/******************************** Player *********************************/

class CPlayer : public CGameObject
{
public:
    static CGameObject* create ()
    {
        return new CPlayer;
    }
};

/********************************* Ogre **********************************/

class COgre : public CGameObject
{
public:
    static CGameObject* create ()
    {
        return new COgre;
    }
};

/********************************** Orc **********************************/

class COrc : public CGameObject
{
public:
    static CGameObject* create ()
    {
        return new COrc;
    }
};

/***********************************  ************************************/
// some function that would take are new object and add it to our
// game system setting the object's position, orientation and other stuff

extern void AddObjectToSystem (CGameObject* pOb, IntroData* pIntro);

/*************** a table of the function for making objects **************/

typedef CGameObject* (*GameObjectCreationFuncPtr)();
struct CreationData
{
    GameObjectCreationFuncPtr   func;
    const char*                 typeName;
};

CreationData CreationFuncTable[] =
{
    #undef GAMETYPE_OP
    #define GAMETYPE_OP(name) { &C ## name::create, #name, },

    GAMETYPE_LIST
};

/******************************* InitLevel *******************************/
// takes an array of IntroData and
// starts up all the objects in that list

void InitLevel (IntroData* pData, int numObjects)
{
    while (numObjects)
    {
        if (pData->gameType >= 0 && pData->gameType < GameTypeID::last)
        {
            CGameObject*    pNewOb = NULL;

            CreationFuncTable[pData->gameType].func();

            printf ("made %s\n", CreationFuncTable[pData->gameType].typeName);

            AddObjectToSystem (pNewOb, pData);
        }
        else
        {
            printf ("ERROR: unknown game type\n");
        }

        ++pData;
        --numObjects;
    }
}

I gave each type a static (ie, global) function to create one of itself (you gotta do that in C++ since the internal vtable pointer for each new instance has to be initialized. Then, I instead of using the case statement I made a parallel array of pointers to functions to create those objects.  That array is always in sync with the enums since they are both auto generated. The code has also gotten slightly simpler and smaller as there is only one printf now were as there used to be one per object. Also, the function table code will be faster and less code than a giant case statement.

That a good example and possibly where I would stop but in this particular example we can go overboard.  You can see that each of the create() function is the same. Any type specific code could appear in that type's constructor so using the define macro list trick we can generate those functions as well.  Here's that example.



#include "limits.h"


struct VECTOR3
{
    float x;
    float y;
    float z;
};

/***************************** list of types *****************************/

#undef GAMETYPE_OB
#define GAMETYPE_LIST   \
    GAMETYPE_OP(Player) \
    GAMETYPE_OP(Ogre)   \
    GAMETYPE_OP(Orc)    \

/**************************** enums for types ****************************/

class GameTypeID
{
public:
    enum ID
    {
        #undef GAMETYPE_OP
        #define GAMETYPE_OP(name) name,

        GAMETYPE_LIST
        last,
        force_int = INT_MAX,
    };
};

/****************** one entry in a table of game object ******************/
/******************  to introduce when the level starts ******************/

struct IntroData
{
    GameTypeID::ID  gameType;   // they type of object
    VECTOR3         position;   // where it starts
    VECTOR3         rotation;   // the way it faces
};

/************************ base class game object *************************/

class CGameObject
{
};

/******************************** Player *********************************/

class CPlayer : public CGameObject
{
public:
    static CGameObject* create ();
};

/********************************* Ogre **********************************/

class COgre : public CGameObject
{
public:
    static CGameObject* create ();
};

/********************************** Orc **********************************/

class COrc : public CGameObject
{
public:
    static CGameObject* create ();
};

/***********************************  ************************************/
// some function that would take are new object and add it to our
// game system setting the object's position, orientation and other stuff

extern void AddObjectToSystem (CGameObject* pOb, IntroData* pIntro);

/************************** creation functions ***************************/

#undef GAMETYPE_OP
#define GAMETYPE_OP(name) CGameObject* C ## name::create() { return new C ## name; }

GAMETYPE_LIST

/*************** a table of the function for making objects **************/

typedef CGameObject* (*GameObjectCreationFuncPtr)();
struct CreationData
{
    GameObjectCreationFuncPtr   func;
    const char*                 typeName;
};

CreationData CreationFuncTable[] =
{
    #undef GAMETYPE_OP
    #define GAMETYPE_OP(name) { &C ## name::create, #name, },

    GAMETYPE_LIST
};

/******************************* InitLevel *******************************/
// takes an array of IntroData and
// starts up all the objects in that list

void InitLevel (IntroData* pData, int numObjects)
{
    while (numObjects)
    {
        if (pData->gameType >= 0 && pData->gameType < GameTypeID::last)
        {
            CGameObject*    pNewOb = NULL;

            CreationFuncTable[pData->gameType].func();

            printf ("made %s\n", CreationFuncTable[pData->gameType].typeName);

            AddObjectToSystem (pNewOb, pData);
        }
        else
        {
            printf ("ERROR: unknown game type\n");
        }

        ++pData;
        --numObjects;
    }
}

Of course in that example the table was only the name of each type. If you needed more data in your table you just added to the macro and then update your _OP macros to match something like this



/***************************** list of types *****************************/

#undef GAMETYPE_OB
//              name     hp dmg, spd
#define GAMETYPE_LIST   \
    GAMETYPE_OP(Player, 100, 10, 15) \
    GAMETYPE_OP(Ogre,    50,  5, 20) \
    GAMETYPE_OP(Orc,     75,  8, 13) \

/**************************** enums for types ****************************/

class GameTypeID
{
public:
    enum ID
    {
        #undef GAMETYPE_OP
        #define GAMETYPE_OP(name,hp,damage,speed) name,

        GAMETYPE_LIST
        last,
        force_int = INT_MAX,
    };
};


/******************** a table of data for the objects ********************/

struct ObjectData
{
    GameObjectCreationFuncPtr   func;
    const char*                 typeName;
    const int                   startHitPoints;
    const int                   damage;
    const int                   speed;
};

ObjectData ObDataTable[] =
{
    #undef GAMETYPE_OP
    #define GAMETYPE_OP(name,hp,damage,speed) \
       { &C ## name::create, #name, hp, damage, speed, },

    GAMETYPE_LIST
};

And there you have it. I've found it pretty useful. Of course there are times where I still need to use something like definer to keep things in sync across languages or tools but for small internal stuff this works well for me.


Pass it on

Comments:

Very good article! Impressive use of macros! Makes me wish I'd have known that trick 6-7 years ago when I had to deal with a lot of C++ code containing long repetitive lists...!
I'll surely put this to use someday.

posted by PatrickAugust 17, 2004 at 4:28 [ e ]
whoah -- Brief (the DOS editor) flashback...

it seems data-driven polymorphism is the better way to go. You shouldn't have constants in your code at all, but in a data file that is encoded/serialized as part of the build process.

What are your thoughts of C# in the industry, oh wise greggman?

Coming from an Objective-C++ background on OS X, I think managed code is really going to take off in Windows. Once you dip your toe in it you can't help jumping in, it's like kudzu.

It's not like the next-generation consoles can't handle a lightweight runtime...
posted by anonymousTroyAugust 21, 2004 at 18:46 [ e ]
what?

>You shouldn't have constants in your code at all?

I'm not sure I understand that statement.

As for C#.  It looks pretty exciting to me but I haven't really got a chance to look at it.  My world is still the world of consoles most of them have serious performace issues meaning the genericness and usefulness of things like C# and Java are generally not a good match.

That might change a little with the next generation of consoles but I doubt it.

Still, I'd like to learn more about C# for tools.  For example rt/shader is written in managed C++ I think.  I'm impressed with it's interface.  On the otherhand it's pretty slow even on my 2.7Ghz PC with 1 meg ram an an ATI 9800 and it often gets a .NET out of memory exception for some reason.  I hope both of those issues are bugs on rtzen's part and not issues with having used managed code.

posted by greggmanAugust 21, 2004 at 22:57 [ e ]
yeah
I was kinda unclear...

With managed code, static data need not live in source code, but a data file, hopefully a structured data file like an xml property list.

Via the runtime and polymorphism these data elements can be read in and later serialized as dynamic data structures.

Objective-C can easily instantiate a class object from an abitrary string, and I assume C# can too, eg:

while (String* object_class = pData->NextObject())
 AddObjectToSystem(new ClassFromString(object_class
));

eg2. in Objective-C++ this is perfectly legal code:

Player* player = [NSClassFromString(@"Player"
) new];

or in straight C++ style:

Player* player = new Runtime::ClassFromString("Pl
ayer")();

once you go dynamic language you never go back... it's like the difference between C and C++...

Also, you have a typo in your sample: GAMETYPE_OB should be _OP I believe. Or you could just delete that line.

BTW, your "life" thread earlier this month got kinda big, so I didn't post there... I am in a similar boat, and am leaning toward moving out of graphics programming into more generic physics/AI/networking coding. The latter is more interesting, challenging, and reusable anyway.
posted by anonymousTroyAugust 22, 2004 at 1:20 [ e ]
dynamic data

Is great for webpages, apps and tools but in games it leads to long load times and lots of memory wasted on overhead.

and what do think "Player" is in your example.  It's a static constant it just happens to be a string static constant instead of an static integer constant.  Integer constants from a lookup table are looked up instantly, string constants have to be searched for or hashed and take far more space to store.

> once you go dynamic language you never go back... it's like the difference between C and C++...

Correction: Once you go to a dynamic language you never WANT to go back.   Unfortunately reality often hits and you have to.

A simple example is Java in cell phones.  All the things that make Java cool, easy to use and object oriented don't work on cell phones because they have so little memory that if those features are used it would mean one couldn't acutally make a game.  For example, in Java, just declaring a new class requires 3K of overhead.  On a cell phone with 16K of memory you can't afford to have more than 1 global class. No classes in Java means no object orientedness.

posted by greggmanAugust 22, 2004 at 4:49 [ e ]
waste...
... is what waste does. C++'s claim to fame is to be no less efficient than C, but dynamic runtimes do not have to be inefficient, Java to the acknowledged contrary. I'm looking forward to what Microsoft is doing with the xbox2 and C#, I think it will be an excellent platform, and wish Microsoft would build the box as a real desktop replacement, with 1GB RAM and HD options.

"Player" was just an explicit example of the previous ClassFromString(). There is no need for that to be in source code...

In my previous job the engine guy actually made it possible for us to instantiate arbitrary C++ classes from datafiles. Can't remember how he did it, we may have been #including the datafiles directly somehow.
posted by anonymousTroyAugust 22, 2004 at 12:18 [ e ]
Java

has not been proven to be efficient (speed of execution) at all except when the cards are stacked in its favor.  C++ "can" be no less efficient than C when used as C.  When used a C++ it can be extremely inefficient.  I don't remember which item off hand but the book Effective C++ shows a simple line of code that written in C would have like 3 function calls and written in C++ would have over 20.

The plus of those languages is the genericness often makes it faster for you to create the program but rarely do they run as fast.

Anyway, that's beside the point.  If you don't find the techinque above useful then don't use it.  I happen to find it useful.

posted by greggmanAugust 22, 2004 at 21:08 [ e ]
possibly related
re: balance between easy to write and performance:

http://blogs.msdn.com/ricom/
archive/2004/06/25/166373.as
px
posted by wlngSeptember 11, 2004 at 1:17 [ e ]
Compiler Correctness?

Interesting stuff.  We did something like this for a while, but eventually quit because nested macros are not correctly supported in all compilers (we often get stuck with odd, half-finished compilers for hardware that hasn't been released yet).  

I suspect that you could accomplish something similar with templates, though I am not sure it would be any more compiler-friendly than what you have.

We've moved on to pushing our polymorphism (and list creation, for the most part) into data, and it's working out pretty well.

waka
posted by wakaSeptember 23, 2004 at 22:41 [ e ]

Post an example of what you mean.

My example was of connecting data to functions, I'm not sure how you go about making that 100% data.

As for your compiler sucking, you can always use a preprocessor or like I mentioned as we did in the past, an external tool.  The problem with the external tool as it's often more of a pain to use.  Of course if you have a bullshit compiler like CodeWarrior into which you can't add your own build tools unless you forkout for the native version of the compiler well then you either need the money to buy the native version or you need to evaluate if you should be using a different compiler

posted by greggmanSeptember 27, 2004 at 5:38 [ e ]