Re: [Algorithms] In-place loaded data structures.
Brought to you by:
vexxed72
From: Charles N. <cha...@gm...> - 2005-11-29 04:39:08
|
Damn. :) On 11/28/05, Charles Nicholson <cha...@gm...> wrote: > > [reply off-list] > > I've been working on a system like this for the past 2 months or so. My > data structures are POD only (no vptr/vtable) with relative pointer > addresses (for the reasons Christer suggests). The biggest problem I've = had > was having both the tool and the game know the structure layout. > > The bungie guys (at least, as Butcher described at Game|Tech) do their > in-place loading by using a macro-language to describe the metadata for > their tools, a la > > struct Foo > { > int x; > char y; > } > > TAG_MACRO_BEGIN(Foo) > TAG_FIELD(int, x) > TAG_FIELD(char, y) > TAG_MACRO_END() > > This file gets compiled into both the game and the tool, so that the tool > can auto-generate GUI widgets and know how to spit them out in the > platform-native structure. When it's time to load, their engine streams = in > a huge chunked file and after pointer fixup they're all ready to go. The= y > actually did some vtable/vptr serialization for their havok stuff (all C+= + > objects) IIRC. > > I'm taking a more data-driven approach- I have XML files that describe > each structure, like > > <class name=3D"Foo"> > <field type=3D"int" name=3D"x" min=3D"0" max=3D"30" /> > <field type=3D"char" name=3D"y" /> > </class> > > this schema is read by the editor which generates UI widgets. Actual > level data gets spit out in schema-conformant XML, like > > <Layout> > <Foo name=3D"Designer_placed_foo_1"> > <x>15</x> > <y>c</y> > </Foo> > </Layout> > > An offline tool turns the above xml into raw bit patterns that can simply > be reinterpret_cast<>ed into their correct structures, which themselves a= re > generated by another tool. That tool takes a schema as input and spits o= ut > .h files, like > > struct FooDataBlock > { > int x; > char y; > } > > It also emits pointer fixup code. It can handle strings, arrays, pointers > (static & polymorphic), etc... > > The game only links with the generated code and none of the runtime > stuff. This keeps it lean and avoids needing things like an XML parser o= n > board, while the tools can use boost, MSXML, all the fun stuff. It's > interesting to note that the process of baking all of this verbose XML in= to > a binary file is akin to compiling and linking a static executable. Each > independent XML file (one per model, layout, entity archetype, trigger se= t) > is independently compiled into a binary with an unresolved external table= , > and the linker simply starts at the 'entry point' (top-level node in the > data graph) and pulls in everything it needs, doing linking and relative > address fixup along the way. The result is a perfect data graph of every > asset you need for whatever chunk of play you're entering. It seems to b= e a > complete solution for non-streaming games. > > I'm most excited about extending the compile/link metaphor to streaming > games- DLLs and runtime link-up. There are a ton of directions it could = be > taken. > > > Havok takes this approach to the extreme and doesn't even introduce the > concept of the 'schema'- every serializable class has an associated > meta-class that describes the memory/field layout for its target. Their > serialized XML simply has these meta-classes at the top, like > > <class name=3D"Foo"> > <field offset=3D"0" type=3D"int" name=3D"x" /> > <field offset=3D"4" type=3D"char" name=3D"y" /> > </class> > <Foo> > <x>3</x> > <y>c</y> > </Foo> > > They parse your C++ to generate the "FooClass" class that describes your > Foo class, and at runtime you get a static global object called 'hkFooCla= ss' > which you can use as a token for searching packfiles, like > > hkPackfileReader reader(memoryBlob, memoryBlobSize); > hkVariant* object =3D reader.FindFirstOf(hkFooClass); > > and an hkVariant looks like > > struct hkVariant > { > void* object; > hkClass* classType; > } > > Their packfiles do hold actual objects, though, rigid bodies that you can > use _in-place_, which is pretty cool. It gets ugly when their vectors gr= ow > past their memory boundaries and are dynamically re-allocated (seems to d= efy > the point a bit), but all in all it's very useful for limited-memory > consoles (psp i guess) where you don't want to keep around any prototype > data (from which you instantiate the _actual_ game objects, as i'm doing)= . > OTOH, the heavyweight prototype data is always in the form of textures, > sounds and vertex buffers, i'm not sure that game object data really take= s > up that much memory but i guess it depends on the game you're making. > > If i were better at C# or could take the time, i think another fine way t= o > take my approach would be to make an assembly that has the data schema, l= ike > > [MetaSerialize] > class Foo > { > [min(0), max(30)] > int x; > > char c; > }; > > Then tools would load this assembly and use introspection/reflection to > generate UIs and data. A C# tool could easily turn one of these > metadata-annotated classes to generate the C++ runtime stuff. > > Anyway, sorry if i skimped on some details or if this was wildly off-topi= c > (i had a few glasses of wine with dinner and just checked my mail to find > this conversation). If you're interested in seeing a little sample app i > whipped up, i could send it along. I'm always interested in talking abou= t > this stuff though. > > btw, are you at sony san diego by any chance? Do you know Max Elliot? > > Regards, > charles nicholson. > > On 11/28/05, Bra...@pl... < > Bra...@pl...> wrote: > > > > I remember some talk a while back about in-place loaded data structures= . > > As in, all you have to do to "unpersist" the data is load it up into a > > contiguous block of memory and (possibly) fix up relative offsets into > > absolute pointers. IIRC, someone mentioned that they had written an > > in-place hash table and put it up on SourceForge? Can anyone point me > > to > > this discussion in the archives? > > > > Anyway, is there a magic Google phrase for this type of stuff? Does > > anyone know of any gentle introductions to in-place data structures, or > > is > > it just part of the collective black-art of console programming that no > > one talks about? :) > > > > Thanks, > > > > Brad... > > > > > > > > ------------------------------------------------------- > > This SF.net email is sponsored by: Splunk Inc. Do you grep through log > > files > > for problems? Stop! Download the new AJAX search engine that makes > > searching your log files as easy as surfing the web. DOWNLOAD SPLUNK! > > http://ads.osdn.com/?ad_id=3D7637&alloc_id=3D16865&op=3Dclick > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > > > |