Flash, Forms, or DHTML?

I've been trying to learn more and more about web development over the last few months. In part just because there's a lot to the wider world of software than games, and I think that there's much that game developers can learn from that wider world ( and vice versa for sure ).

Deliberately unemploying yourself helps a lot I might add. There's generally so much to do when working on a game, it's hard to pursue extra-circular activities.

At any rate, there are a lot different UI solutions out there in the world for applications other than games, for lack of better terms let me lump them into the (probably incredibly poor ) categories: DHTML, Flash, and Forms.

Categories

Dynamic HTML is typified by HTML w/ embedded JavaScript, CSS, and the DOM. For the uninitiated the DOM is a set of semi-standardized interfaces that allow a browser to present HTML ( and XML ) for parsing/manipulation by JavaScript.

Flash, in this particular context, refers to the more generic concept of a platform for UI development and delivery than necessarily Flash itself, but of course, Flash is the foremost example of this.

Forms, here cover standard windowing applications, dialogs, and the APIs used to create them. To name a few: Java's AWT and Swing; MacOSX's Cocoa; Windows Win32, MCF, and .NET Forms; wxWindows; Tkl/Tk.

HTML wasn't originally designed with much more than simple, single page presentation in mind, but it has grown to the point that, with DHTML, it's a flexible, if work intensive, way to provide custom user interfaces for all kinds of content.

Unlike HTML, Flash is geared toward content over time. While DHTML has come close to some of Flash's capabilities, Flash was designed with user input and immediate feedback in mind. Flash also provides a very rich display mechanism, and in this sense becomes a complete platform for delivering user interface.

Forms, like Flash, are usually, though by no means always, part of a larger platform. Unlike both (D)HTML and Flash, Forms are geared towards making a consistent user interface across an entire application, and in some cases, across an entire OS.

These categories aren't completely rigid of course. The space between strict forms and the web has been blurring as more and more developers seek ways to build web based applications quickly. While there's "always" been HTML forms: buttons, text input boxes, etc. more recently there's been full on dialog like support. Among others there's: Microsoft's WebForms, and Mozilla's XUL. Flash likewise has been growing it's own native form extensions, whereas Windows latest .NET work is heading the direction of Flash.

Game UI Comparisons

User interface for games falls roughly into two categories: front end menus, and in game HUD. I say "front end" but of course there are in game options and inventory screens; I say "in game" but sometimes front end screens are over real time graphics. My phrasing here, like the UI models above, are meant to be more evocative than accurate or scientific.

That said, none of the models above match up really match up well with these two categories.

For instance, while Form-like consistency might be a good thing for a game's main menu I can't think of anything less consistent than game HUD. Even within the same game, there's tons of different elements that all do their own unique things. Further, Forms simply aren't as dynamic as game UI tends to be. Forms generally, well, just sit there. Game interfaces, even main menus, tend to jump up, blink, spin and turn every which way. MacOSX flying windows don't really even come close.

Flash, on the other hand while incredibly dynamic, is really, for lack of a better word, an engine for user interface. That may be good for some games, it really does come at a significant cost. Because it's a closed, proprietary system, extending Flash ( or any other UI system of this model ) to the needs of a particular game, and integrating it well with the rest of a particular game engine is no small feat. Both the editor and the language, for instance, really need to provide facilities for manipulating and displaying game elements, as well as facilities for talking to and interacting with game state.

DHTML is interesting to me precisely because it's so flexible, so widely used, and so relatively open. Like Flash, there is no model for talking to or displaying game elements, which is a problem. On the other hand, even if somewhat “transaction-oriented”, there are standard ways of talking to, and manipulating, state on servers. All that may be moot however. While there are some web-page based games out there, there are no commercial games that I know of that have ever attempted to replace custom UI with HTML.

Another Take

My simple analysis that no model matches exactly does miss an important point however – a fairly basic theme underlying these models. JavaScript, PHP, and even Flash are popular in a way that Form based programming isn't. Non-programmers feel free to use both Flash and DHTML. Unlike Form programming, they don't need compilers, or linkers. They don't really even need a complex editing environment. Though something like Eclipse does wonders: notepad ( or emacs ) works just fine. The language and the content are intermixable. A single html page can contain: markup, style, and programming all in one place.

The most useful advances in form programming of late, follow this same pattern, namely a tighter integration between form layout tools and the programming environment. This started long ago with the NEXT, but .NET finally has achieved a similar level, as has Java with the NetBeans IDE. ( NetBeans by the way, even though slow is pretty awesome even for those used to Microsoft's excellent programming IDEs. In fact, I would say it offers a lot of things that Microsoft could learn from. )

Perhaps if game developers are to learn anything from this, it's that if we really want non-programmers -- our designers and artists -- to be able to control front end menus and in game HUD, we need to begin to mix-up content, scripting, and presentation. I know this is anathema to good procedural programming but perhaps it's key to fast, flexible UI development.

A word of warning perhaps though. To be really advantageous to the game development process, I think we have a lot to learn about how to leverage the knowledge of existing user interface creators. 

Until we can use the hard won skills (D)HTML designers and Flash developers, we will probably be behind the curve -- continuing to spend large amounts of our development time on user interface development.

Final Note

Over the last few years there has been a growth in UI middleware for games. Where previously there was nothing there are now several different efforts. On the commercial front: Anark and Scaleform. On the open source front: Crazy Eddie's GUI. Microsoft's DirectX has simple GUI widget support. Shockwave/Director/Flash have always provided a platform for containing mini-games, but Flex may be providing some new steps towards going the other way: embedding Flash into games.

As I have some time I might, out of curiosity, see whether the middleware that's out there falls into any of my UI categories above, and just briefly, provide an update to this post as to which uses which.

See full post...

Blogging with XLST

For a while now I've been wanting to write something that would take a Microsoft Word document and transform it into post-able html.

Word has better formatting, editing, navigation, undo/re-do, and spell check than any standard blogging product I've found.

It took me all of today (oh boy but my XSLT was rusty) but I finally got something pretty decent working. You can get it here.

Ironically, this post was not written with Word, but most things from here on out will be.

Basic Features

For kicks I am using the O'Reilly Word document template (you can Google for "O'Reilly ORA.dot" to find a link to it) which once you get used to it is pretty fantastic. It has nice simple hot-keys and nice simple markup.

For my transform, for instance, I'm taking all the ORA "code blocks" from the Word document, and turning each new level of indentation into a new "ul" block. This avoids the Wordpress and html space normalization issues, and also means you can control how much indentation depth you want displayed.

How to Use it

Create a word doc! Note: If you are going to use my transform directly you will have to download the O'Reilly template and create your document based on its styles.

In Word:

• You need to turn off merge tracking (you only ever need to do this once) Menu:Tools/Options/Security/"Store random number to improve merge accuracy"
• Then, save the document in xml: Menu:File/Save As/Save As Type:"XML Document"
• If you have a transform already to go you can then select the "Transform..." button.
• Assuming you have saved your document in .doc form, go ahead and click the "Continue" button on the dialog that pops up.
• Exit Word

Rename the xml file to an html file, and open that file in a browser to verify its contents.

You can now paste the contents of that file into your Wordpress ( etc ) blog.

Pretty neat!

Future Work

There's still some stuff worth doing:

• I'd like to turn the cross references into links.
• I'd like to handle embedded clip art and other images ( maybe i will save the file once as a html page, use that to generate standardized image files, and then in the transform just like to the corresponding filenames )
• I'd like to learn how to group blocks of sibling elements together properly so that I can turn linear xml lists of bulleted paragraphs into a groupings of ul/li elements
• I'd like to break the O'Reilly habit and create my own markup scheme in Word that I can use for the transform instead.

I'll update the template as I improve it.

Closing Words

Much thanks to Miloslav Nic for the Zvon tutorials

Much thanks to NetBeans for nice XSLT editor. While it does once again prove Java slow, there are indeed a whole lot of nice features to the editor.

This whole effort makes me think about all the neat things that this could have applications for in games. Primary example: turning an rtc script or conversation system document into localizable string tables for in game subtitle display.
See full post...

String Hashes

This long overdue post takes a brief look at string hashes.

I was trolling through blogs ( in the passing ship sense, not the flame-baiting, nor monster under the bridge sense ) and came across John Gior's post on FNV in games. Having never heard of FNV, I thought I'd take a look. Recognizing that covering just FNV is likely to be pretty boring, I thought I might take a look at string hashes in general.

In case you haven't used them before, or you don't think their useful enough to bother using them in your game, I'd like to introduce to the string hash:

String hash, meet the reader, reader meet the string hash.

String hashes can shrink the size of your data, and speed the execution of your application. Even as PCs and consoles get ever more RAM, and ever faster processors, string hashes can still have a place.

Hashing: A Quick Introduction

Hashing is typically used to store objects into an array in such a way that the objects can be retrieved quickly later on. A normal hashing algorithm goes something like this:

An object is reduced to a number ( the hash ):

   unsigned long ComputeHash(Object * object);
   ComputeHash (object1)= 0xfade;

That number is used to generate an index into an array of buckets ( the hash table ) in some cases perhaps simply by the hash modulus (%) the number of buckets:

   int CalcIndex(int hash, int numBuckets);
   CalcIndex (0xfade)= 0;

The object then gets stored in the bucket at the index calculated from its hash:

   array[0].Add( Object )

Since there are a fixed number of buckets but a large number of potential hashes, the buckets are usually implemented as linked lists. That way when (not if) two objects fall into the same bucket, they still can be retrieved as needed.

   array[0] => { (0xfade,Object1), (0x1234d,Object2) }

You might use a hash table in an RPG. For instance, you might want to keep a big list of all the usable items in memory. Rather than forcing your designers to give each one a compact, unique index, you might instead use the name of the item definition to generate a hash. Any time you load a new item from disk you can hash its name, and store the item at the calculated position in the hash table. Later, when someone requests the definition by name, you can hash the requested name, peek into the hash table, and retrieve the desired definition.

Fast, quick, flexible lookups.

At some point, however, someone realized that you could also do away the string altogether, and in fact, reduce most internal string data down to just the hash itself.

String Hashes

Internal strings appear a lot in game development. They might be designer specified names for your RPG's usable items, class names in a custom scripting language, console commands typed in by a user, or the name of network packets.

Essentially, a string hash allows you to "ossy compress" an arbitrary length string down into a single, fixed bit length, number. Instead of passing those internal strings of characters, you can instead just pass around the hash.

Note that word "lossy“ you can't reconstruct your string from the hash number alone. This means you can't go out and string hash all your localizable text and hope to reconstruct that text later for display, but it does mean you can hash all those strings that you don't display. Alleviating the storage space needed for internal strings, and reducing string compares to simple integer compares.

Ideally, you'd be able to get completely rid of all these strings altogether, except perhaps in debug mode where it can be useful to have in order to track what data is flying around.

A good first step in this direction is to introduce a StringHash class. Instead of passing around the references to strings everywhere, pass around references to the StringHash class.

A StringHash Class

Example 1-1 provides a very simple string hash class. This class allows you to generate a hash from a string, and then pass that hash around for use as needed in your searching, storage, and lookup functions.

Note that there's actually two implementations.

When IOND_KEEP_STRINGS is defined, perhaps for instance in a debug build, the string hash class selected actually copies and stores the string that created the hash. When the "keep string" is not defined, the string hash class selected does not keep the string around; it only stores the hash itself.

   Example 1-1. StringHash wrapper
//unsigned long under 32-bit compilers
typedef boost::uint_least32_t u32;
u32 ComputeHash(const char *);
struct RawStringHash {
. RawStringHash( const char * src ) {
. . m_hash=ComputeHash();
. }
. u32 Hash() const {
. . return m_hash;
. }
. bool operator==(const RawStringHash&o) const {
. . return m_hash==o.m_hash;
. }
. bool operator<(const RawStringHash&o) const {
. . return m_hash o.m_hash;
. }
};

struct StringHashWithString : RawStringHash {
. StringHashWithString( const char * src ) :
. . RawStringHash(src)
. . m_string(src) {
. }
. const char * String() const {
. . return m_string.c_str();
. }
private:
. std::string m_string;
. u32 m_hash;
};
#ifdef IOND_KEEP_STRINGS
. typedef StringHashWithString StringHash;
#else
. typedef RawStringHash StringHash;
#endif

Evaluating Hashes

The big question, of course, is just what goes in that ComputeHash() function.

Metrics

Not all hashes are created equal, and there are several metrics worth considering when choosing a hash. A few metrics that I personally consider important include: speed to generate a hash from a string, complexity of hash code, frequency of collisions between hash values, and the ability to in-place strlwr.

The first two metrics are hopefully pretty understandable, the second two, however, probably deserve a brief explanation.

First: not all hashes are perfect. Try as they might, it's certainly possible for two different strings to wind up generating the same hash value. Some algorithms are better at avoiding collisions than others.

Second: when talking about internal strings, it's often worthwhile to ignore case. Whether a designer specifies "Magical Treasure Chest of Doo" or "Magical Treasure Chest Of Doom" they probably actually intended to refer to the same object. This is a matter of personal, and team, taste of course. I generally prefer case-insensitivity.

Given those metrics there are actually a large number of hashing algorithms worth considering out there. For purposes of this post, I simply chose some of the more common public domain ones.

25,760 Strings

In order to compare the speed and collision frequency of different hashes you will need some real world test cases. Ideally, you can use the actual data from your game.

For this post however I wanted to use a large set of strings that others could easily obtain to replicate my experiments.

Easier said than done. I needed a big batch of strings to test collision against, but all the games I could think of (and could hack into) had only tiny amounts of data. I was thinking I might try and hunt down some World Of Warcraft item and monster lists, but then decided instead to go to my shelf and crack open my copy of Freelancer. I went on to Lancer's Reactor, downloaded the data file un-packers, and *poof* twenty five thousand object names at my finger tips.

Comparisons

Table 1-1 compares the generation of 25,760 strings in a release build ( auto-selected optimizations ) using Visual C++ 2005 Express.

Table 1-1

Name	Bit Depth	Speed (ms)	Collision	Complexity	Lower
boost::crc_32_type	32	162	none!	high	no
fast_boost_crc	32	61	none!	high	no
custom CRC	32	54	none!	med	yes
FNVA	32	56	none!	low	yes
FNV	32	51	1	low	yes
Jenkins	32	37	none!	high	no

The native boost crc type is slow. It took me a while to understand why, but basically to be compatible with the crc "standard" (pkzip) the algorithm has to invert the bits of the source and destination hash -- believe it or not, that extra 100ms comes all from there.

The fast boost crc (shown in Example 1-2) tweaks the parameters of the boost crc template, to remove the bit inversions. I believe that this is the fastest boost crc possible.

   Example 1-2. Fast Boost CRC
typedef boost::crc_optimal<32, 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, false,  false> fast_boost_crc;

My custom CRC type is basically just the boost algorithm manually expanded and tweaked to lay the statements out in a good order. The nice thing about manually expanding the algorithm is that it's possible to manually insert the strlwr'ing along the way.

The FNV(S) aren't bad but the FNV collides (just once), and FNVA is a little slower than my custom CRC code.

Jenkins looks awesome but it is worth noting that it works 4 bytes at a time, and thus can't be easily in-place strlwr'd. Further, since it doesn't look at individual characters, it can't automatically detect the end of your strings, and therefore also needs to know how long your strings are in advance.

The Hash Algorithms

More information on the various hashes can be found at:

• Boost: http://www.boost.org/libs/crc
• FNV: http://www.isthe.com/chongo/tech/comp/fnv
• FNVA: http://www.bretm.home.comcast.net/hash
• Jenkins: http://burtleburtle.net/bob/hash

Of these, I like the custom CRC. It has a good speed, manages to avoid collision well, and can be outfitted with strlwr. Unfortunately, CRC generation does require a table -- in this case a 1K table. If you need the space, than FNV/A would be good alternatives.

It's interesting to note that the stdext::hash_map in Visual Studio C++ 2005 uses FNV for it's hash computations.

Future Work

I will post my code here a little later on, and I also follow up with two additional posts:

"A purist's guide to string hashes" taking a look at keeping consistent StringHash structure sizes between builds, computing crcs at compile time, and how to obtain the perfect hash

"Applications of the string hash" showing how the string hash can be used in practice.
See full post...

Sample Chapter

I've just put my sample chapter online....
Feel free to take a look: Chapter 8: Templates.

Feedback (positive or negative) welcome and appreciated.


See full post...

Game Engine Internals

About the Book

This book, tentatively titled 'Game Engine Internals', is an introductory to intermediate level programming book dealing with real world game development problems that you can sink your teeth into. It aims to be the systems engineering equivalent of a basic mathematics or physics programming book and is therefore intended for readers interested in the guts of game programming.

Tackling the game development process from a fresh perspective - that of the fuel feeding modern game engines - it examines the fundamental role that data plays in the game development process from the very lowest level data records, up through a game's tools, out via the run-time of a game's engine, and into players' hands. The book exposes the hidden internals of modern game engines using applied examples in common game genres to help illustrate and teach the concepts presented.

Specifically, "Game Engine Internals":

• Introduces you to the basics of data record and data format definition, data serialization, and the flow of data production in games.
• Teaches you both traditional and modern game object creation techniques including the use of archetype, prototype, and template definitions as well as data driven component composition.
• Explores various ways you can use data to control a game's run time including: game asset customization, data binding, function binding, and simple scripting.
• Shows techniques you can use to build data introspection into your code, and then, ways you can apply that introspection to automate tasks such as serialization, data validation, and generic data editing.
• Provides primers on player initiated load/save, multi-threaded loading, and data migration. It even shows you some ways you can usefully integrate relational databases into your games.

By specifically eschewing graphics, sound, input, and many of the other topics covered in typical game engine programming books, this book can give you a solid foundation from which to layer on those topics, or a way to weld the pieces of game engine knowledge you already have into a workable whole.


See full post...