'Binary XML' for game data?

Question

I'm working on a level editing tool that saves its data as XML.

This is ideal during development, as it's painless to make small changes to the data format, and it works nicely with tree-like data.

The downside, though, is that the XML files are rather bloated, mostly due to duplication of tag and attribute names. Also due to numeric data taking significantly more space than using native datatypes. A small level could easily end up as 1Mb+. I want to get these sizes down significantly, especially if the system is to be used for a game on the iPhone or other devices with relatively limited memory.

The optimal solution, for memory and performance, would be to convert the XML to a binary level format. But I don't want to do this. I want to keep the format fairly flexible. XML makes it very easy to add new attributes to objects, and give them a default value if an old version of the data is loaded. So I want to keep with the hierarchy of nodes, with attributes as name-value pairs.

But I need to store this in a more compact format - to remove the massive duplication of tag/attribute names. Maybe also to give attributes native types, so, for example floating-point data is stored as 4 bytes per float, not as a text string.

Google/Wikipedia reveal that 'binary XML' is hardly a new problem - it's been solved a number of times already. Has anyone here got experience with any of the existing systems/standards? - are any ideal for games use - with a free, lightweight and cross-platform parser/loader library (C/C++) available?

Or should I reinvent this wheel myself?

Or am I better off forgetting the ideal, and just compressing my raw .xml data (it should pack well with zip-like compression), and just taking the memory/performance hit on-load?

Answer 1

We used binary XML heavily for Superman Returns: The Videogame. We're talking thousands and thousands of files. It worked OK, but honestly didn't seem worth the effort. It ate up a noticeable fraction of our loading time, and the "flexibility" of XML didn't scale up. After a while, our data files had too many weird identifiers, external references that needed to be kept in sync, and other strange requirements for them to really be feasibly human-edited any more.

Also, XML is really a markup format, and not a data format. It's optimized for a lot of text with occasional tags. It isn't great for fully structured data. It wasn't my call, but if it had been and I knew then what I know now, I probably would have done JSON or YAML. They're both terse enough to not require compaction, and are optimized for representing data, not text.

Answer 2

Store and edit your levels as normal XML, but have your game engine lazily bake it into binary XML during loading, and save the binary XML back to the disk so that it can load that next time (if the raw XML hasn't changed).

Something like this:

data loadXml(xmlFile)
{
    if (xmlFile has changed OR binFile doesn't exist)
    {
        binFile = convertToBinary(xmlFile)
        save(binFile)
    }
    return loadBinaryXml(binFile)
}

That way you get the best of both worlds. On release, you just need to make sure all the binary files are there.

Answer 3

Google Protocol Buffers seem like the way to go, but I haven't used them myself.
http://code.google.com/p/protobuf/

You define a .proto file which describes the file format:

message Person {
  required int32 id = 1;
  required string name = 2;
  optional string email = 3;
}

This is then compiled with a command line tool which generates C/C++ classes to write and parse binary data files in the previously defined data format. There are also a couple of extension for different programming languages.

The downside to ProtocolBuffer is that they aren't a plaintext format. You would need a tool to generate, read and edit them. But this shouldn't be a problem if you're using them only to exchange data between your game editor and your game. I wouldn't use it to define config files ;)

Compressing the raw xml files should also work. What type of game are you making? If it is level-based then you should load all necessary resources only once when the level is loaded.

update: There are several projects for other languages such as C# to work with ProtocolBuffers:
http://code.google.com/p/protobuf/wiki/ThirdPartyAddOns

Answer 4

What about the JSON-format?

http://www.json.org/xml.html

Answer 5

Use JSON.

(Building on Munificent's response, and largely in response to your concerns expressed elsewhere)

You've mentioned concern that JSON has the issue of wasting space naming elements, like XML. It doesn't.

JSON is built on two structures: name/value pairs (objects) and ordered lists of values (arrays). XML is built only on name/value pairs.

If you think JSON relies on objects you've been reading JSON that's built to be self-descriptive and human-readable, like this (using octal digit pairs to represent single bytes):

{
    "some": ...,
    "data": ...,
    "fields": ...,
    "cars": [
        {"name":"greg","cost":8C,"speed":FA,"age":04,"driverID":384FFFFF},
        {"name":"ole rustbucket","cost":00,"speed":00,"age":2A,"driverID":04FF54A9}
    ]
}

However you also have the option of writing it like this, so long as you know where everything will be (and so can look for index 4, rather than object "cars", to get your list of cars):

{
    [
        ...,
        ..., 
        ...,
        [["greg",8C,FA,04,384FFFFF],["ole rustbucket",00,00,2A,04FF54A9]],
        ...,
    ]
}

Does it get more concise than just having [, ], , and your values?

Well, it does if you're willing to just get closer and closer to a pure binary stream.

"cars":{"names":["greg","ole rustbucket"],"stream":8CFA04384FFFFF00002A04FF54A9}
or
[["greg","ole rustbucket"],8CFA04384FFFFF00002A04FF54A9]

Just don't shoot yourself in the leg by optimising too much.

Answer 6

I know you've accepted an answer, but Google both "Fast Infoset" (binary XML) and vtd-xml.

Although latter (VTD) might not resolve the compression aspect of you XML usage, it might speed up node access across large files, considerably (it uses a binary offsets 'dictionary' to jump to nodes, and doesn't create objects for each node, instead work on the original XML string). Therefore, it's XML lookup are [said to be] both faster and it doesn't require as much in-process memory to access/manipulate the XML doc.

Both of the above have bindings in the popular languages (which include C#).

Cheers

Rich

Answer 7

You could try Karvonite. It's supposed to be agile. It's a persistence framework that will adapt to the changes in your data fairly well (which is nice compared to handling binary your self). I'm not actually sure how the data is structured, but the files are a lot smaller than xml bloated files. (I'm assuming it saves the data in a binary format instead of text like xml)

The only con I can think of with this is that if your data gets corrupted or some how messed up in a way that Karvonite doesn't like it, your kind of at the mercy of it's creators unless you figure out how the structure of the data works.

The way you specify how to save/load your data is you just open up their persistence editor, import your assembly with all the data objects and check some check boxes to show what objects you want supported and what fields/properties to save.

It might be worth a try. Since your using C#, this fits right in with your language since it works with XNA (Windows, Xbox360, and Windows Phone 7 which I think your interested in since you mentioned the iPhone?).

Edit: Just noticed your only using C# for the tools. This probably wouldn't fit very well in your workflow. For some reason I had XNA in my head.