Upcoming Events
Unite 2010
11/10 - 11/12 @ Montréal, Canada

GDC China
12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010
12/24 - 12/27  

GDC 2011
2/28 - 3/4 @ San Francisco, CA

More events...
Quick Stats
104 people currently visiting GDNet.
2406 articles in the reference section.

Help us fight cancer!
Join SETI Team GDNet!
Link to us Events 4 Gamers
Intel sponsors gamedev.net search:

Enginuity, Part 5
Serialization, Triggers/Interpolators, and the Build Stamp
or, I Can't Think Of A Witty Subtitle For This One

I'm back, after a bit of a break to build up the codebase and the example game a bit. And to catch up on Real Life . ;-)

Many thanks to all the people who've written in recently, urging me to continue with the series; I assured you all that I was not stopping, and this should be proof of that. From the list of topics I've got to cover, I estimate that our first demo game - CY - should arrive around article 8. So I've still got more to go, and I plan to continue after that, so...

This article I'm going to show off a few tricks I came up with for Enginuity which aren't really something that every engine *needs* - they come under the heading of 'nifty features,' but you can get along without them. However, nifty as they are, I thought I'd show them to you. Four things: Serialization, the Triggers and Interpolators systems, and the build stamp.

Serialization

You'll like this one, you really will. I know that when I thought of it up in Edinborough, I was still grinning about it when the train reached Birmingham. (Doesn't being easily amused just *rock* on long journeys? :-) )

'Serialization' is the general term for the processes of 'flattening' your data, for byte-stream uses such as storage in a file or transmission over a network, and then 'inflating' it again at the other end. Typical situations are messages for networked games, saved games, loading levels... hell, any custom resource that is loaded from or saved to a file needs a serialization mechanism (and the 'standard' resources, like bitmaps and sounds, need them too, but as far as Enginuity is concerned the libraries we use provide their own mechanisms).

There are a large number of problems. Firstly, what data do you need to save out or load in? Your entire heap? The positions and velocities of every single object and entity, down to individual particles in the particle systems, for everything that is loaded into memory? Probably not. Then, there's the problem of actually structuring that data - after all, saving pointers straight to file is no good when you load them back in again, so you can't just do a dump of your objects. You need to determine a 'flat' structure for them - something I call a 'serialization structure.' Dators are a bit slow, and only really need to be used when a variable is going to be set by name.

If you've ever worked with Quake BSP files, you'll have come across these 'serialization structures.' When a BSP file is actually in memory there's quite a bit more information than when on disk - a fair number of pointers between objects, for example - and that information is constructed when the level is loaded. The serialization structures - which, in Quake's case, are quite literally C structures - dictate how each piece of information in the BSP file is laid out - how a block of 32 bytes is divided into 4 longs, 6 ints, and 4 chars.

So, while the first major problem - what to serialize - will depend on the situation, the second problem - how to do it - is something we can address with a strong framework. See, creating an entire C structure for each piece of information you want to serialize is not just messy, it's also inflexible - it's fixed at compile-time. I'm going to present to you a mechanism that uses function calls, rather than C structures, to establish serialization structures. That way you can easily control which functions get called through something as basic as if() blocks.

There's also one of the original design requirements to be taken into account - the requirement that the engine be cross-platform. Well, while it's possible to write tools to load data files, swap the bytes around, and save them out again for different architectures, it's also a pain - and something which, in a time-critical situation, can really bite. It stinks of 'primary platform, plus ports' rather than 'cross-platform development;' it also requires the development of tools for each individual project, because a generalised program wouldn't know about the actual structure of the data and thus wouldn't know which bytes need swapping. The technique we look at today is completely architecture-independent; it actually uses SDL_Net's buffer read/write macros to serialize all data into network byte order (big-endian). If you don't like depending on SDL_Net to do that, it's very simple to replace the macros with your own equivalents.

Firstly, let's look at a typical scenario. Say we have a ball object, CBall, and we want serialization functions on it. All it needs, to begin with, is position information.

CBall::Flatten(ostream &out)
{
 out << position.x;
 out << position.y;
}

CBall::Inflate(istream &in)
{
 in >> position.x;
 in >> position.y;
}

Now, that works pretty well in simple situations, but it's potentially very problematic. Firstly, it's inflexible in that it depends on having STL streams to serialise to/from - that may well not be the case. Secondly, it's either going to be using a text-based format for storing the data - which is inefficient - or a binary format which will not necessarily be cross-platform. Thirdly, there's no real scope for error in there - things like buffer overflow aren't really tracked. Lastly, the existence of two seperate serialization functions means that you have to keep them both synchronized - some may argue that it's just one of the habits of a good programmer, like pairing calls to 'new' with calls to 'delete,' but I still maintain that everyone makes mistakes, and the smaller the chances of them happening, the better.

It's 'hard-coded.' I don't just mean that if you change it you need to recompile - soft code often needs that too - but changing it requires changes in more than one place, and, depending on the change, could potentially require changes in many places - adding support for a new type of source or target, for example. The solution we're going to look at is more 'soft-coded' - the serialization structure is defined in one place and one place only, the system is pretty extensible, and - best of all - you can accurately calculate other things about the serialization structure, like how much space it *actually* needs (rather than just hoping that a sizeof() is big enough).

What we have is simple - our objects support a 'serialize' method, which takes a single pointer to a 'target' object as its parameter. That 'serialize' function is all an object needs to provide to work with the system. That may sound a little familiar to those of you who have some MFC experience, but even MFC requires that you define the structure twice - once for loading, once for saving. The serialize function calls methods on the 'target' object, and those calls define the structure: the target object's methods are things like IOChar, IOFloat, IOLong, IOString, and so on. See where I'm going with this yet?

With each of those calls, a reference to the variable in question is passed. So, IOChar(char &value), IOFloat(float &value), etc. Then - and here comes the cruncher - we derive different objects from the base 'target' interface - CSerialFlattener, CSerialInflator, CSerialSizer, and so on. They can then write the values to a buffer, read the values in from a buffer, or simply add to a running total of bytes written. The object itself never touches the actual read/write buffer - assuming there is one - and any change to the structure is felt across all operations on the structure. You could write 'serializer objects' to do pretty much anything - count the number of different types of variable used, generate code for a C-structure based on the serialization structure, whatever. The first three have suited me just fine so far. By forcing buffer read/writes to happen through a sort of 'visitor' object, we can do things like ensure that strings are always written out in a consistant way (I opt for size followed by unterminated string, but you could just as easily make all strings null-terminated), or check for buffer overflow/underflow (because underflow can be just as bad a sign as overflow).

In fact, we can even take advantage of another nice feature of C++ - overloading. Instead of seperate IOChar/IOFloat type names for things, we just have a single IO() function overloaded for different types. Though, don't go too far - this might seem like one of the places where templates would work well, but remember that each type will probably need to be handled differently, making templates useless (because they're for applying the *same* operations to different types). Using overloading, though, is much nicer; it means that we don't have to check that the type of the variable matches the function, because the compiler will pick the correct function for us.

The end result is a system which is a little bit like C++ iostreams, but does away with the concept of 'input' or 'output.'

Let's pull out some code. Firstly, our base ISerializer interface:

class ISerializer
{
public:
 virtual void IO(unsigned char &value)=0;
 virtual void IO(unsigned long &value)=0;
 virtual void IO(std::string &str)=0;
};

If that looks a bit short, it's just because I've not needed any more types than unsigned char, unsigned long, and std::string just yet. It's pretty easy to add new types, as you'll understand soon. Let's start looking at the Serializers themselves with the simplest one, the CSerialSizer:

class CSerialSizer : public ISerializer
{
protected:
 unsigned long length;
public:
 CSerialSizer() { length=0; }

 void IO(unsigned char &value)
 { ++length; }

 void IO(unsigned long &value)
 { length+=4; }

 void IO(std::string &str)
 { IO(length); length+=str.length(); }

 unsigned long getLength() { return length; }
};

Pretty simple. A char adds 1 byte to the size; an unsigned long adds 4 bytes. Why do I use literals instead of sizeof() expressions? Because - while in this case, the sizes of char and unsigned long are pretty much guaranteed - we want to be writing out the size of the data when serialized, rather than the size of the data when in memory. If I were to add an 'unsigned int' overload, would the size of it be 16 bits or 32 bits? Because we're trying to keep this cross-platform, we can't really guarantee either; and given that we're trying to keep the data *itself* cross-platform too, we have to pick one and stick with it (I'd probably opt for 32 bits). Thus, the size of an 'unsigned int' when serialized - 4 bytes - might not correspond to the size of an 'unsigned int' when in memory - 2 bytes. For consistency I decided to write things the same way for the non-ambiguous types too; you're perfectly free to use sizeof() if you want, just bear in mind that sizeof() isn't always the right answer.

Incidentally, the 'length' variable is protected, rather than private, for a simple reason: you will quite probably introduce your own basic data structures in projects, which should be kept specific to that project. So, to minimize polluting the Enginuity codebase itself with overloads for your custom data types, you only need to overload in once place - ISerializer - and then you can derive your own CExtendedSerialSizer (or whatever) which implements those new overloads; the Enginuity serializer classes themselves will (aside from ISerializer itself) be unchanged. (If you wanted to be *really* neat and avoid polluting the Enginuity codebase all together, you could create another interface class - IExtendedSerializer - which has ISerializer as a virtual public base class. Then, you derive your CExtendedSerialSomething from both CSerialSomething *and* IExtendedSerializer; the end result should be an extended class which has overloads from both base classes in it, and you can still use IExtendedSerializer as an interface to all your extended serializer objects).

When you use CSerialSizer (or your own extension of it), it'll probably be to allocate a buffer for use with a CSerialSaver.

class CSerialSaver : public ISerializer
{
protected:
  unsigned char *buffer;
  bool bHasOverflowed;
  unsigned long length;
  unsigned long bytesUsed;
public:
  CSerialSaver(unsigned char *buf, unsigned long size)
  {
    buffer=buf; length=size; bytesUsed=0; bHasOverflowed=false;
  }

  void IO(unsigned char &value)
  {
    if(bHasOverflowed)return; //stop writing when overflowed
    if(bytesUsed+1>length){bHasOverflowed=true; return; }
    *buffer=value;
    ++buffer; ++bytesUsed;
  }
  void IO(unsigned long &value)
  {
    if(bHasOverflowed)return; //stop writing when overflowed
    if(bytesUsed+4>length){bHasOverflowed=true; return; }
    SDLNet_Write32(value,buffer);
    buffer+=4; bytesUsed+=4;
  }
  void IO(std::string &str)
  {
    unsigned long l=str.length();
    IO(l);
    if(bHasOverflowed)return;
    if(bytesUsed+l>length){bHasOverflowed=true; return; }
    memcpy(buffer,str.c_str(),l);
    buffer+=l; bytesUsed+=l;
  }

  bool hasOverflowed() { return bHasOverflowed; }

  //should be equal to 0 when we're done
  long getFlow() { return length-bytesUsed; }
};

There. The constructor takes a pointer to the buffer you want it to fill, along with the size of that buffer (so it can track when it's overflowing). Then, we have three overloads. The first two are very similar: they check that the overflow flag hasn't been set (and if it has, they bail out). Then, they check that the write wouldn't *cause* the buffer to overflow (and it if would, flag the overflow and bail out). Then they perform the write itself; the unsigned char overload simply copies through the byte, while the unsigned long overload uses an SDL_Net macro to make sure the value is written out in network byte order (it's a simple macro, so if you don't like depending on SDL_Net, it's easy to replace). Then, each increments the buffer pointer (the current write position) and the number of bytes used up.

The last overload - std::string - is pretty similar, but it actually calls one of the other overloads to write out the size of the string before the string itself. You can create such 'composite serial members' in this way; an overload for a vector class, for example, would probably just be implemented using three calls to IO(float). (If you're using my IExtendedSerializer suggestion, that's one of the beautiful bits - you can actually implement the overload in the base IExtendedSerializer class, and when you later derive from it with CSerialSaver/CSerialLoader the IO calls from the overload will be mapped to the correct virtual functions. That is, your extended overload calls IO(long), which successfully goes through to the CSerialSomething that you extended).

The last two functions, hasOverflowed() and getFlow(), are for error detection. The first of the two is pretty simple - it tells you whether the overflow flag has been set (there was an attempt to write more data than the buffer could hold). The second is for detecting underflow; this isn't such a serious error as overflow, but it still might be indicative of something not having worked correctly - especially if you're using a buffer with the size given by a CSerialSizer and the object you're serialising hasn't changed. The serialisation structure should be exactly the same in both cases, so if it hasn't filled the buffer perfectly, something's screwy. If you don't use a CSerialSizer, and just pass a buffer that you think is large enough, then you can use the flow to work out how much of the buffer was actually used (to save you writing out the extra padding at the end).

Now, the CSerialLoader:

class CSerialLoader : public ISerializer
{
protected:
  unsigned char *buffer;
  bool bHasOverflowed;
  unsigned long length;
  unsigned long bytesUsed;
public:

  CSerialLoader(unsigned char *buf, unsigned long size)
  {
    buffer=buf; length=size; bytesUsed=0; bHasOverflowed=false;
  }

  void IO(unsigned char &value)
  {
    if(bHasOverflowed)return; //stop writing when overflowed
    if(bytesUsed+1>length){bHasOverflowed=true; return; }
    value=*buffer;
    ++buffer; ++bytesUsed;
  }
  void IO(unsigned long &value)
  {
    if(bHasOverflowed)return; //stop writing when overflowed
    if(bytesUsed+4>length){bHasOverflowed=true; return; }
    value=SDLNet_Read32(buffer);
    buffer+=4; bytesUsed+=4;
  }
  void IO(std::string &str)
  {
    unsigned long l;
    IO(l);
    if(bHasOverflowed)return;
    if(bytesUsed+l>length){bHasOverflowed=true; return; }
    char *szBuf=new char[l+1];
    szBuf[l]=0;
    memcpy(szBuf,buffer,l);
    str=szBuf;
    delete[] szBuf;
    buffer+=l; bytesUsed+=l;
  }

  bool hasOverflowed() { return bHasOverflowed; }

  //should be equal to 0 when we're done
  long getFlow() { return length-bytesUsed; }

};

Pretty damn similar to the CSerialSaver, I think you'll agree. The constructor is exactly the same; the first two IO overloads simply flip the assignments over, so that the buffer is now copied to the value rather than the other way around. The third overload looks a little more complex, but it's actually still pretty simple - it reads back in the size as an unsigned long, and then allocates a temporary buffer to hold the string; reads the string, converts it to a std::string, and delete the temporary buffer. Once again, at the end, we have hasOverflowed() and getFlow(), doing exactly the same thing as before. Underflow is more of a problem here, as it means the whole buffer wasn't read in - if you thought you'd handed it a complete resource, evidently the serialization structure of the data is different to that of the object, so the data is either corrupt or you're trying to feed it into the wrong object.

Let's take a look at a sample serialization function on an object, then. This is taken from the high-scores table code in the upcoming demo game, CY. Here are the relevant parts of the class definition:

class CHighScoresTable : public Singleton<CHighScoresTable>  
{
public:
  CHighScoresTable();
  virtual ~CHighScoresTable();

  void Serialize(ISerializer *s);

  bool Load();
  bool Save();

  struct hs 
  { 
    std::string name; 
    unsigned long score; 
  }scores[10];

  inline int getScoreCount() const { return 10; }
};

While there are seperate Load/Save functions in this object, they don't actually touch the serialization structure - all they do is create the Serializer objects and work with the highscor.dat file, as you'll see.

The constructor initializes all the values in the table to the default highscores. If the highscor.dat file can't be opened, the scores will reset to defaults, and then get written out in a new file. So, to reset the high scores you can just delete the highscores file.

CHighScoresTable::CHighScoresTable()
{
  for(int i=0;i<10;i++)
  {
    scores[i].name="Nobody";
    scores[i].score=100-i*10;
  }
}

Here's the serialization function itself. For each entry in the table, it just gives the name (a std::string) and score (an unsigned long).

void CHighScoresTable::Serialize(ISerializer *s)
{
  for(int i=0;i<10;i++)
  {
    s->IO(scores[i].name);
    s->IO(scores[i].score);
  }
}

This is how loading the table is actually done. The function has no relation to the serialization structure; changes to the Serialize() function will not affect it. All it does is open the file, read in the contents, and hand it to the Serialize function (in a CSerialLoader) to be actually loaded.

bool CHighScoresTable::Load()
{
  unsigned long size=0;

  FILE *fp=fopen("highscor.dat","rb");
  if(!fp)return false;

  fseek(fp,0,SEEK_END);
  size=ftell(fp);
  fseek(fp,0,SEEK_SET);

  unsigned char *buffer=new unsigned char[size];
  fread(buffer,1,size,fp);
  fclose(fp);

  CSerialLoader sl(buffer, size);
  Serialize(&sl);
  assert(sl.getFlow()==0);

  delete[] buffer;

  return true;
}

And here's the complimetary save function. Again, it opens the file; it uses both a CSerialSizer *and* a CSerialSaver to get the size of the data to write out, though in fact this could be made more efficient by writing a CFileSaver which writes directly to the file rather than to a buffer. The same goes for the Load function.

bool CHighScoresTable::Save()
{
  FILE *fp=fopen("highscor.dat", "wb");
  if(!fp)return false;

  CSerialSizer ss;
  Serialize(&ss);
  unsigned long size=ss.getLength();

  unsigned char *buffer=new unsigned char[size];
  CSerialSaver sv(buffer,size);
  Serialize(&sv);
  assert(sv.getFlow()==0);

  fwrite(buffer,size,1,fp);
  fclose(fp);
  delete[] buffer;

  return true;
}

I think you'll agree that's pretty simple, especially when you're dealing with a large number of different objects - if you've got, say, a set of 100 objects of varying classes, all implementing some kind of ISerializable interface, then you can have a single save/load function pair to loop through all of them and call Serialize() functions on them.

Now, the method isn't without its caveats. For one, it requires that you plan your serialization structures with a bit more care; for example, if the number of entries in a serialization structure is going to be variable, you *have* to record that number at the beginning, rather than simply reading/writing till all the bytestream is used up. Such structures, though, are what I'd call 'deterministic;' you always have the information to read/write without needing any knowledge at all of the underlying byte-stream. After all, if you had serializers which sent data to and from sockets directly, you wouldn't necessarily *have* an end-of-file to test against.



Triggers & Interpolators

Contents
  Serialization
  Triggers & Interpolators
  The Buildstamp

  Source code
  Printable version
  Discuss this article

The Series
  Part I
  Part II
  Part III
  Part IV
  Part V