Tilemaps and Isometric Rendering

A lot of engines seem to focus on tilemaps and games rendered with such.  They also seem focused on isometric rendering for that 3D'ish look.  This past weekend I wrote a quick test to load a set of tilemaps and then I wrote a map loader to initialize an isometric world.  So far the tests are going nicely and it's looking like something that would benefit the engine.  I plan on adding the isometric demo to the engine demos so that people can get a look at loading the tiles, loading the world, and then streaming a world over the web.  I'll probably also use it as a foundation for a couple of other demonstrations such as simple multiplayer and generic AI with pathfinding.  Eventually this demo will be a showcase of technologies provided by The Render Engine.

It doesn't supplant the 2D sprite-based demo and game editor, but it's a step in a new direction that should help show the flexibility of the engine.  It's hard to get people to understand that The Render Engine is just a game engine and not a full game.  Showing them a mostly functional Asteroids clone, a simple physics ball bouncing demo, and a text renderer doesn't really showcase what the engine can do.  Instead, most people think that The Render Engine is an Asteroids clone or "a game from the early 1980's" which it isn't.  It's a framework for creating games, and the demos are just examples of the capabilities of the engine.  None of the demos are intended to be full games.

However, after spending some time cleaning up the Asteroids clone it occurred to me that it might be interesting to take that and expand on it.  Make it into a full game which can be played on Facebook, for example.  Add some more features to it and work out an interface with the Facebook API.  That might really show people what is possible with The Render Engine.  Not that I want people to think that the engine is there to make the next "Farm-whatever", but it might just be another person's stepping stone.

What to do?

I've been spending a lot of time thinking of ways to optimize the engine.  But I've also realized that I'm wasting time trying to optimize when I should be doing new development.  I'm missing out on creating the new technology to push The Render Engine over the top.  So, starting tonight I'm stopping my optimizations and going back to working on the new stuff.  Maybe it's silly, but I get caught up in trying to make everything perfect out of the gate.  So, back to the UI, tilemap renderer, multiplayer, and other things.  I'll be sure to record what I was working on so I can return to it, but for now it's back to the new tech.  =)

Engine Configurations lead to Optimizations

Yesterday I revisited the new configuration module in The Render Engine.  What I probably forgot to blog about was that I've been working on a way to load browser-specific configurations to help tune and optimize the engine.  The first iteration was simple and only loaded a simple object with configurations for the type of browser being used.  Turns out, that was too generic to handle some of the things I want to support.

Being ambitious, I've updated the config module to load a configuration which should be more flexible.  For example the Firefox config looks something like this:

{
   "versions": {
      "4.": {
         "transientMathObject": true
      }
   },

   "platforms": {
      "Windows 7": {
         "4.": {
            "hardwareAccel": true

         }
      }
   }
}

What this configuration does is allow us to set up some options which differ from the defaults.  For example, transient math objects and hardware acceleration are disabled by default.  With Firefox v4.0b6, hardware acceleration on Windows 7 has been enabled by default so this config sets a flag which the engine (or a game) could use to take advantage of that.  Also, in Firefox v4.x, using transient math objects tests faster than pooling them.

So, they're just flags but they do help in making determinations while the engine, or a game, is running.  For example, knowing that hardware acceleration is available, the drawImage() call of the CanvasContext is much faster.  So, it makes sense to use the Billboard2DComponent in the vector demo instead of always drawing the vector object's polys.  When I profile in Firebug, the calls to drawImage() in Firefox 3.6.9 take up > 5% of the overall time (right at the top) with only 3000 calls, compared to just drawing the polys which takes ~ 1% of the overall time with over 120,000 calls.  However, using the billboards in Firefox 4.0b6 those 3000 calls take up < 0.01% of the overall time.

You should know that these are just guesses based on the defaults that the different browsers use.  As such, if someone disabled the Direct2D acceleration in Firefox 4.x, the engine can't determine that purely in JavaScript.  So, while these aren't foolproof, they will help the majority of people who don't mess with their configurations.

Spatial Containers

I'm realizing that there are a number of places within The Render Engine that need to be tightened, cleaned up, optimized, or rewritten entirely.  That isn't a bad thing, because it means that the engine will either be faster or easier to work with.  One such example is that I've been trying to figure out how, or where, I can use threading with WebWorkers in the engine.  I had thought that maybe collision detection could take advantage of just such a thing.

As I was studying the code, I realized that the methods which update the collision model are contained everywhere except the spatial containers.  How odd, I thought to myself, that I should make such a simple mistake.  It would take a very specific knowledge of the collisions containers to know how to create your own or to utilize an existing one!  So, I did some rewriting and moved the code out of the ColliderComponent and into SpatialContainer.  This way, as objects move about, all they need to do is let the collision model know where they are (and, of course, who they are).  That simplified a lot, and cleaned up the code dramatically.

By componentizing the system, from the start, I've been able to keep these inner workings well enough hidden from the typical engine's user.  But this was just atrocious (in my opinion) and needed to be redone.  It's not a speed improvement, but it does take the burden off of the user.  That is a win to me that was worth implementing.

I know there will be more, and some will be more difficult to implement than others, but in the end I believe that The Render Engine v2.0 will be a better engine because of it.  Now, back to trying to figure out how I can take advantage of threading within the engine...

Red-black Trees and the Container

The problem with the Container class is that it is a linked list.  While it is not subject to fragmentation, like Array, it is extremely fast for linear operations, and it gracefully handles the removal of items while it's being iterated, it absolutely blows when doing lookups.  A lookup in a linked list is an O(n), or linear, operation which is bad, bad, bad on large collections.  Particles are an example of a very large, very active collection which needs a lot of lookups.

I remembered something from my earlier days of doing game programming with the Torque engine.  They use a red-black tree for their memory management.  It is a nicely balanced tree with O(log n) lookups.  I read something, earlier today, that said looking up an item in a red-black tree with 4 billion entries is at most 32 operations.  So, I found a nice implementation of a red-black tree in Java and did a port to JavaScript.  Unfortunately, it doesn't implement the remove() operation...  I've found a decent example of the operation, but I've got to translate it as well.

What I'm hoping to accomplish is that a new subclass of Container will use a backing red-black tree for speedy lookups.  I think this will offer the best of both worlds when trying to keep things relatively fast.  It will mean more data overhead, but then again I don't care as much about a small footprint -- only that the engine perform well.

Particle Engine Rewrite

Last night I rewrote the particle engine to use a Container instead of an Array.  The problem with arrays was that they could get messy when considering the way in which particles are created and removed from them on a regular basis.  I haven't fully decided if it's any faster, as of yet, but it doesn't appear to be a slowdown.  I had run into an issue in the latest version of Chrome where the ParticleEngine.sortParticles() method was "freezing" the browser when called.  I have determined that it's due to just calling Array.sort() with a compare function.  If the comparison did anything with the actual objects (even just checking if they were null), the browser would stop for a moment.

By replacing the Array with a Container, I can use an Iterator which will inherently skip destroyed objects.  Containers are simply linked lists, so when an entry is removed the link is broken, rather than coalescing the list.  Some operations, such as adding one Container to another, are simply pointer operations.  Adding one Container to another results in a single list which contains pointers to both.  Modifying the second Container will affect the first, so one need to proceed with caution.  At some point, I'll probably add "deep copy" methods which will be slower, but will ensure that the two lists won't affect each other.

UI Development

Over the last few days I've been working on the new UI system, going back and forth about how best to implement it.  Originally I had thought that simple objects which aren't pooled or anything would be easiest.  They would simply be a DIV overlayed on the rendering context, and it was going fine until I realized how much work I was going to create for myself since I already had components to render sprites and images, play sounds, etc.  So, back and forth I went...

Turns out, I already had everything I needed to generate UI's.  The new UI design is finalized and development is continuing.  Here is how it all came out:

• UI's are HTMLDivContext objects
• UI elements are Object2D objects
• Positioning of UI elements is handled automatically via Transform2DComponent
• Sprites and Images are rendered with components

There is a UIManager which loads user interface files and parses them into a UI with all elements generated from the UI file.  The part I'm working through right now involves how to position elements within the UI.  I want to give some flexibility so that UI elements can be positioned relative to each other.  That way, if you have a series of buttons which all need to be left aligned together, you only need to absolutely position the first then relatively position the remainder.  Next up, after that, will be enabling some sort of way to trigger methods from the UI using jQuery event binding.  UI elements currently in development:

• Image/Sprite
• Button
• Textbox
• Text Input
• Check/radio box
• Slider
• Sound

I figure that those should cover most of the basics for creating a UI.  Of course, all of this will be extendable so you can create your own UI elements.  That way, UI's can be created and used within your games as well (not just for menu and option screens).  While doing all this, I modified the multi-resource loader a bit.  I've decided that I want to be able to use the loader without having to specify what is being loaded.  As such, I've created my own extensions for files which describe meta formats such as bitmap fonts and levels:

• Level: *.level (*.lvl)
• Bitmap Font: *.font (*.fnt)
• Image: *.image (*.img)
• Text: *.text (*.txt)
• Sprite: *.sprite (*.spr)
• User Interface: *.ui

Formats like JSON, XML, and sounds have their own extensions already so I don't need to specify those.  Each of the meta formats is still a JSON object that describes the actual contents to load, so you can call the loaders in the same way, but the multi-resource loader will simplify things for you.

When the multi-resource loader is used, you can either specify the type of loader to use or let it decide based on the extension of the file being loaded.  That way, you can just use the multi-resource loader as if it were all the loaders rolled into one without thinking about what it's actually loading.  It will use the correct loader for you.  The only difficulty comes when requesting cached resources from the multi loader by name.  The name doesn't indicate what it is, so I'll have to tackle that one at a later date.

HTML5 - What direction should we take?

I've been spending my time, lately, working on an Android port of The Render Engine to allow developers to create games in JavaScript, yet be able to take advantage of the platform in a native way.  While working on this approach, I've also been thinking about the best way to market the engine.  It seems that a lot of people have a preconceived notion in their heads about what, exactly, makes a game an "HTML5" game.

The feeling I get is that most people think "tile based game rendered in the DOM" when they imagine an HTML5 game.  However, it goes so much further than that... With the advent of the Canvas, people have been trying (myself included) to utilize it much the same way as developers did for games when EGA and then VGA showed up on the PC.  Rather than textual characters and lengthy text descriptions which made up a lot of games, the game players were wanting more so they invested time in learning how to access the graphics, directly.  This doesn't necessarily mean  that games written to use the DOM as their rendering "context" are bad.  But it can be limiting when trying to do advanced effects.

I don't want people to think that The Render Engine is solely a Canvas-based game engine.  It still supports the DOM, and it can do so with very little difference when writing a game for Canvas.  This allows developers, to make a choice when writing their game, to choose what their target audience is.  The way the Canvas works is similar to the way modern games are written for the PC, Xbox, Wii, or other gaming platform.  You render all of your content to a buffer which is then displayed to the player a frame at a time.

When writing a DOM-based game, however, it isn't the same.  The DOM is always live which means that a change to the DOM happens immediately.  There isn't the "clear and redraw" that occurs for "typical" games.  If the standard method of drawing a frame using CanvasContext were applied to HTMLDivContext, the engine would end up creating thousands of objects in the DOM.  Instead, the engine uses the DOM-created object as a mini-canvas (if you will) which is updated, as needed, to run animations and draw the world.  Ideally you wouldn't have to know about this and the engine would take care of all of that for you, but this isn't the case.

To truly make a game run in every browser, you have to design for the least common denominator.  In this case, that would be the DOM since IE (at least until IE9) doesn't support the Canvas.  While the engine tries to alleviate some of the work from the developer, not all of it will work as expected.  As such, a developer writing a game should probably make the decision from the start as to whether they want to use the DOM or the Canvas and stick to it.  Originally, I had intended The Render Engine to be able to "hot swap" rendering contexts but that paradigm just isn't feasible.  So I'm starting to wonder if I should do one of two things:

1. Focus on only creating the best engine for graphical contexts (canvas, web-gl, etc.)
2. Still support any context, but make the separation cleaner/clearer

Some feedback would be great because this would be a fundamental shift in the platform.  Neither one is a bad choice, but ideally the engine would be just an engine which allows the developer to make decisions for themselves rather than being limited by what the engine can do for them.  So, I ask you for some help in determining the future of The Render Engine... Vote in the poll and let us know your thoughts.