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!