Red Button Bulletin 4 - Architecture Algorithm

Another technical article this week - this time digging into one of our active pieces of development.  Most likely, the algorithm will change sometime after this post, but it's what we've been doing the most heavy development on lately.  It will be one of the key systems that will provide the "fun" in the first Milestone for Codename: Jenga, but for now the actual algorithm is a little dry.

Problem

In Codename: Jenga, players will be building a structure, a "tower" of sorts.  We wanted the tower to have realistic physics, but we also wanted to allow some fantastical structures.  The universe in which the game is built needs that hybrid, straddling reality and fantasy.  So we needed a way to calculate how much "realistic stress" is being put on the building as a whole.  The "world" is a 3D grid - so each block has 4 neighbors adjacent to it, plus a block above and below.  The algorithm discussed below accomplishes that.

Terminology

A couple terms for those learning or need a quick reminder:

Set - A collection of objects.  The only use this collection has is to determine whether an object exists in the set.  There is no way to get a list of objects in the set, to iterate through the object, or to order it - but it's VERY quick to determine if an object exists.

Queue - A FIFO (First-in, First-out) collection of objects.  When getting the next object from the queue, it gets the object that was there the longest.  Think of it as a line at the coffee shop - the first person in the line is the first to get their order.

Block - A grid element in Codename: Jenga.  Not every object is literally a "block", but logically that's what they're called.

Leaf - An object in a tree or graph with no children.  In this case, it means that it's a block that we'll start calculating from.

Algorithm

The first step of the algorithm was to develop a method to "calculate everything" and would deterministically come up with the same output.  The general design of the algorithm was to start at the ground floor and iterate generation by generation until no more connecting blocks could be found.  As each block was added, if it caused additional stress it would add the stress to the total.  The first iteration of the design used the following steps:

• Add all ground level blocks to [SearchSet] and [SearchQueue]
• {A} Get next block [CurBlock] from [SearchQueue]
• Check neighbors of [CurBlock]
  • If neighbor is a generation earlier than [CurBlock], it can supply support to [CurBlock]
  • If neighbor isn't in [SearchSet], then add it to [SearchQueue] and [SearchSet]
• Add up the support of all neighbors, record the end stress and generation of [CurBlock]
• If blocks still remain in [SearchQueue], loop back to {A}

This is a simplified breakdown - but you get the idea.  It iterates over the 3D grid of blocks, sets the stress level and generation, and moves to the next block.

Metadata

Each block contains pieces of metadata - the weight generation, weight value, weight support, and external support.

Weight Generation - A number that represents how far away the block is from the "root," or in this case, the ground floor.  This is helpful in determining which blocks support other blocks.

Weight Value - The amount of weight stress the block puts on the structure as a whole.  A floor for example, has a value of 0.1, while a solid block has a value of 1.

Weight Support - The amount of support the block provides to blocks above it.  A floor's support value is 0, while a solid block has a value of 1.

External Support - The support that a block receives from the blocks below and around it.  The more external support a block has, the less stress it puts on the structure.

The final stress value for a block is calculated once external support is calculated:  [External Stress] = [Weight Value] * (1 - [External Support]).  External support is additive - so if a block is supported by multiple sources, the block is very stable.

Iterative!

But wait a minute...the algorithm above recalculates everything from scratch.  We don't want to recalculate the entire tower if we only added or removed one block, that'd be really expensive!  So we needed to refine the algorithm for how it's going to be used 90% of the time - recalculating local changes and figuring out how it affects the whole.  This ends up being really complicated, since there a lot of things to consider, but the key to local calculations was the Weight Generation data.  Using the data stored in each block, it's very easy to start at one block and find the set of affected blocks.  The general rule is: if this changed block has a generation smaller than its neighbor, add the neighbor to the recalculation set.  This rule is iterated until no more blocks are found that match the rule, and a variation of the above algorithm is applied to that set of blocks.

Once the set of recalculation blocks has been created, you find the leaf blocks with the smallest generation, and start the calculation there.  There is some additional filtering to prevent the recalculation from going outside the set, but the logic is essentially the same - recalculate support, determine possible support based on Weight Generation.

Destruction

Just when I thought everything was resolved, I started trying to remove blocks.  This got tricky because much of the algorithm depended on the "starting block," which was usually the block that changed.  However, when removing a block, there's no longer a seed to start the process!  This involved even more sets to track various coordinates - the removed block set, the recalculation set, and the leaf set.  We're still debugging this algorithm, and the logic is a bit too complicated for me to wrap my head around without examples or visual aids.  Trust me though - things get tricky.

But What About the Fun? 

This algorithm alone doesn't do much, but it does give us a lot of data we can use for cool effects.  In Codename: Jenga, you'll have a power source to support the structure.  If your power source is a higher value than the stress on the structure, then your structure is fine.  But if the stress ever surpasses the power source...well, things are going to fall apart.  And that's the biggest hook we'll have in our first alpha/pre-beta release - the structure creation and destruction.  We think it's a really cool concept that hasn't been done very well (if at all?) before, and it's part of the foundation for the world we're building.

Thanks for reading!  If you have any comments or questions, or have suggestions for topics for future Red Button Bulletins, contact us either on Facebook, Twitter, or email (info [at] redbuttongames [dot] com).  Follow us on Twitter and Facebook as well!

Red Button Bulletin 3 - Goodbye, XNA. Hello, Unity.

As a heads-up to non-developers: today's entry will be a little technical, but I've had a lot of mini-discussions about our shift in development tools, and I wanted to address it fully for those that are interested.

Our previous two games, Olu and All Your Creeps, were both written with Microsoft's game framework XNA.  Our next game, currently just called Codename: Jenga, is being written with Unity.  There's a lot of reasons behind the shift (rather than just a bulleted list), and it isn't any one reason why we're switching - it's a combination.

Engine/Editor instead of API

XNA does one thing very well - provide a managed framework for programmers to build games.  However, for any non-technical team member, it's a headache to use.  It's built around the idea of a codebase, with some afterthought put into content management.  There is no designer to speak of, and there's technically an "engine," but really it's just a set of classes that saves you some time.  Unity, on the other hand, is an editor and engine first, with the ability to customize any object with your own scripting.  At any point during game execution, you can pause the scene an inspect it and change any publicly-exposed variable (such as location in a scene or material). Also, it is generally more malleable since everything is exposed through the editor.

3D support versus 2D support

Although both tools can do both 3D and 2D, XNA is targeted towards 2D games, and Unity is targeted towards 3D.  XNA includes an extremely optimized sprite batch system, and Unity's coordinates are always three dimensions - even if one is only used for layering.  Throughout the process of building Olu and All Your Creeps, many systems I built from scratch would have been available from the start in Unity.  This sort of leads into the next point as well...

Many more systems included in the engine

XNA provides very few systems out of the box.  For example, you can draw a 3D object, but without animation.  If you want animation (2D or 3D), particles, or physics, you'll have to find a third-party library to use.  Unity provides all of these (and many more) in the engine.  It provides plenty of options to manage content, adjusting import settings, swapping textures, changing shaders - all through the editor.  In XNA, you'd have to develop your own tools or solutions to these problems.  Either that or just change a setting in the game and restart.   And in case Unity doesn't include a solution or the included solution isn't good enough...

Unity's Asset Store

XNA's community is strong - at least, in the early days it was.   However, one area I felt it always struggled was sharing reusable code and systems.  A few solutions became pretty popular to solve common problems (EasyStorage comes to mind), but it was hard to seek out solutions and spent time integrating them into your codebase.

Unity's solution to this was the Asset Store.  It provides a place for anyone to sell anything related to game development - from game assets to UI systems.  It created a culture that sharing your reusable content was valuable - and the more "plug-and-play" your system was, the more valuable it was on the Asset Store.  So far I've only bought a pathfinding and UI system, but these polished systems saved me dozens of hours in work.  And due to the modular structure of Unity's scripts, they're much easier to "plug-and-play" than a normal addition to your codebase.

Same development environment

This is a short note - but I'm still using C# and Visual Studio for "scripting," so there isn't much of a transition from a programming perspective - I'm just using different systems.

Easier and wider cross-platform development

This is the BIG one.  If there was one reason that I chose Unity over XNA, this is it.  XNA lets you develop one place and deploy to Xbox 360, PC, or Windows Phone 7.  The codebase can stay the same - but many limitations of the deployment you can only determine by testing.  Graphics card not working well enough on a testing PC?  Then you'll be troubleshooting until you figure out what part of the code to revise.  They've improved this by creating two "profiles" of PC's (high-end and low-end), but you're still left with the risk of PC development - every system is different.  Not to mention that you're limited to XBLIG, Windows Phone 7 Marketplace, and PC.  I'm not going to address XBLIG concerns in this post, but I will say that many people would not expect their game to succeed on XBLIG.

With Unity, there are 6-7 different platforms you can develop on (depending on how you define "platform").  We're targeting PC/Mac/Web at first, but can easily expand to mobile when we decide to go down that path.  And for PC - there are already predefined performance profiles for different graphical levels (which can be further customized).  It helps mitigate some of the risk associated with deploying a game to PC, along with not knowing every iteration of PC specs.

Familiarity

Although we used XNA for our previous two games, Jesse (our Art Director) has used Unity for over 2 years - so we have a resource on the team that's very familiar with the tools.

XNA is still a good choice for many people - it just didn't make sense for our next project.  My hope is that this info doesn't necessarily drive people away from XNA, or blindly toward Unity, but educates on the benefits and risks associated with both.  As always, you can contact us with questions, either on Facebook, Twitter, or email (info [at] redbuttongames [dot] com).  Follow us on Twitter and Facebook as well!