Trees of Objects & Meta

Posted onLeave a comment

Tree data structures provide the foundation for most interactive systems. In most cases one can take an existing app, class, or collection of objects and represent it with a tree structure. HTML, XML, JSON, DOM, Flash displayList, file systems, and programming languages are all hierarchical in nature.

I have been interested in serializing & deserializing tree based systems for a long time and feel like there is a gap in terms of file formats. Tag based formats (XML/HTML) tend to be fragile given closing tags and are generally hard to read and edit accurately without tools. Minimalistic formats like JSON and YAML lack type metadata and can be confusing to read and edit as well. Also parsers for these formats tend to lean towards generating a complete object hierarchy as a result vs emitting stream of events allowing a single pass of object generation.

Long story short, I havent found somethings that fits well and decided to build one. I settled on calling the format Meta. Here is the base definition:

Meta A simple readable ASCII based format for typed tree serialization & deserialization.

The driving use case for Meta was storing levels of a game where you would simply clear the display list and generate objects representing a level of the game. The key was having an event based parser that allowed for type generation on a line by line basis. I tested this in JavaScript, ActionScript, Lua, and Python and in every case it was trivial to generate typed objects from a single .meta file. This is when I started to think about this as a file format and generally how the project came to mind.

Basics:

//comment
<NAME>:<TYPE>=<VALUE>
<NAME>:<TYPE>
<NAME>:<TYPE>=<VALUE>
<NAME>:<TYPE>
<NAME>:<TYPE>=<VALUE>
Rules:

<NAME>,<TYPE>,<VALUE> are strings using any non-whitespace char, must quote if : or = is used.
Indention denotes object heirarchy
Types follows the colon : similar to type declarations in ActionScript 3
Values follows the = and vary in syntax to the type used.
Examples:

s1:String = “Hello”
n1:Number = 1234
b1:Boolean = true
//comment
innerobj:Object
src = logo.png
x : Number = 0
y : Number = 0
isFullResolution : Boolean = true
rotation : Number = -30
alpha : Number = 0.5
c1 : Color = #FF00FF55
an1 : Array = [1,2,3,4,5,6,7]
obj0:Object
1:Number = 1
2 = 2
3 = 0
4: Boolean = true
obj1:Object
src = “logo.png”
//comment
x : Number = 0
y : Number = 0
isFullResolution : Boolean = true
rotation : Number = -30
innerObj:Object
src = “logo.png”
x : Number = 0
y : Number = 0
isFullResolution : Boolean = true
rotation : Number = -30
alpha : Number = 0.5
One thing I really like about the format is that it is streamable in that parsing of the file can start as soon as downloading begins, all you need is a complete line regardless of hierarchy. This makes it very useful for data exchange as sometimes it is handy to stream data(large array collections or ui) to a client. Within the game usage the format sets up large object trees of box2b enabled displayobjects (think of a level in Angry Birds). Combined with a class that manages object creation/destruction/recycling and it gets really scalable. I especially like the readability aspect, just glancing at the file you can see the object tree and all you need is a text editor. Within the game engine I implemented Library and Reference types to allow for reuse of generated objects within downstream objects and properties. This sort of mapping made wiring up function handlers and material types far easier.

Obviously Meta is far from complete but I have found it very useful thus far. As soon as I apply a bit more polish to the codebase I will post the Lua and ActionScript classes for parsing and serialization.

Leave a Reply

Your email address will not be published. Required fields are marked *