Saving Database Space through Bit-masking

This is a trick you can use to increase the efficiency and readability of your project. It is an argument for good up front design as utilizing this is only plausible when you take the time and effort at the beginning. The following is a real world example from my game TerraTanks.

The problem is that you have an object with a ton of properties that are incredibly similar and they describe the object in a yes|no fashion. In my case, players can do 24 types of research and the state of the player is “yes, I have done that particular research” or “no, I have not done that research”.

One solution is to make a table with a column that associates with the player id and a boolean column for every type of research that you have. Now if you have 24 types of research your table is 25 columns big. This can get out of hand pretty quickly. The table becomes hard to read and you have to use different code (or procedurally dynamic code) to set individual columns.

Another solution is to add a column to your player definition table and make it type INT UNSIGNED. Then you let your code efficiently handle interpreting the integer as the player’s research definition through bit masking. Here’s how it works.

The maximum value of an unsigned INT in MySQL is 4294967295. In binary this number looks like 11111111111111111111111111111111. That is 32 1’s in a row. Each of those digits can describe a research type as ‘have’ (it is a 1) or ‘have not’ (it is a 0). Now in a global file for your code you need to define each research type as a number that is a power of 2. It would look something like this in PHP:

$g_shield_research = 1;              // in binary 001
$g_armor_piercing_research = 2;  // in binary 010
$g_mining_research = 4;             // in binary 100

Now if you want to know whether you have a particular research you would perform a bitmask operation on the integer you retrieve from your database using the & operator.

// will mask players research and return true if the mining bit is set to 1
if ($element->research & $g_mining_research)

The bit masking procedure is extremely efficient and fast and you can see how it compresses all the research information into the size of an integer. Also, if you want to know everything about a player’s research you only have to retrieve a single integer from the database.

Assigning research to a player is also very easy. Simply bitwise OR the current research integer with the set bitmask using the | operator:

$newPlayerResearch = $element->research | $g_shield_research;

You can technically add the two numbers to get the same result, but this is unsafe because if you add the research when it is already there it will throw everything off.

There are some pitfalls to using this trick. While it is easy to add another type of research just by assigning its mask to the next highest power of 2, you are limited to 32 total research types. One way to get around this is to make the column type BIGINT which would give you 64 bits to work with, but at the end of the day you are still limited. Also, once a game starts the research you choose for that bit position is pretty much stuck there unless you want to do some math maintenance.

While this trick will tend to make your code more readable because database statements won’t be as long, your database entry will not be human readable so it could slow down your debugging efforts.

So there you have it. A very powerful tool if used wisely. Please design well before you start writing code. It makes life easier.

Wish there was more?

I'm considering writing an ebook - click here.

.

Jake is a games nut. He flips out and makes games without even thinking twice about it. He is good at rulesets, balancing (games, not on a beam you idiot), and knows things about coding. Like all mammals, Jake likes board and video games and makes both (like www.terratanks.com). Jake constantly fights his arch enemy Sarcastro and hopes knowledge of his weakness, visual design, never falls into the wrong hands.

Thursday, September 4th, 2008 SQL, database, optimization, php
  • I am using the same logic on a project, a very quick way to get around using reference tables. Good article, great ammunition in the tech group for my idea!

  • Good point Mattias. Just to explain a bit further what the operator notation is, the '&' will do a bit comparison where both members in the comparison need to have that bit set to 1. Because you are doing the AND operator all the bit places you don't care about need to be set to 1 so they maintain their value. The '~' operator inverts all the bits in the value so where a variable might look like 00010000, the inverse of that would look like 11101111.

  • Might want to note that in order to take off one of the researches (for some unknown reason) you need to AND with the complement of the bit.
    For example, if you had picked the g_shield_research and want to degrade it or something you use:

    $newPlayerResearch = $element->research &~$g_shield_research;

  • Blair Beckwith

    These tutorials are simply amazing! Thank you do much for writing them! You definately have a new fan.

blog comments powered by Disqus

About

Building Browsergames is a blog about browsergames(also known as PBBG's). It's geared towards the beginner to intermediate developer who has an interest in building their own browsergame.

Sponsors

Got Something to Say?

Send an e-mail to luke@buildingbrowsergames.com, or get in touch through Twitter at http://twitter.com/bbrowsergames