Building Browsergames

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.

Diary of a Browsergame: Setting up the database

One of the first things I do for any new project of mine is design the database - so that’s what’s going to happen to Working Title today. This design will probably change slowly over the course of development - it’s just a good starting point for now.

To begin with, we’ll need a users table.

CREATE TABLE users (
	id int NOT NULL AUTO_INCREMENT,
	username text,
	password text,
	PRIMARY KEY(id)
);

And once we have that, a stats table:

CREATE TABLE stats (
	id int NOT NULL AUTO_INCREMENT,
	display_name text,
	short_name varchar(25),
	PRIMARY KEY(id)
);

If this all looks familiar so far, that’s because it should - this is the exact same table structure(currently, anyway) as the game we’ve been working on. I’m taking all of the design decisions and changes that we made in our other project, and doing my best to apply them here - thereby continually improving my code, and my design.

Because Working Title will have a few distinct ‘entities’, my entity_stats is going to look a little bit different than the one we’re using right now. According to the design document, there are 4 main entities - players, rooms, monsters, and items. Those will make the enum in the entity_stats table:

CREATE TABLE entity_stats (
	id int NOT NULL AUTO_INCREMENT,
	stat_id int,
	entity_id int,
	value text,
	entity_type ENUM('User','Monster','Item','Room'),
	PRIMARY KEY(id)
);

Thinking about it a little more, I’m pretty sure that I don’t need separate tables for each of the entities that can exist within Working Title - all I need is a single table to keep track of their name, ID, description, and type. So that’s what I’m going to do:

CREATE TABLE entities (
	id int NOT NULL AUTO_INCREMENT,
	name text,
	entity_type ENUM('Monster','Item','Room'),
	description text,
	PRIMARY KEY(id)
);

One of the things that the design document mentions is that “users will move between rooms” - which means that I will need way to track which room a user is currently in. I’m going to use a stat to do this:

INSERT INTO stats(display_name,short_name) VALUES ('Current Room','cur_room');

There are also supposed to be players, monsters, and items inside rooms - so I’ll need a table to keep track of all the entities within a room:

CREATE TABLE room_entities (
	id int NOT NULL AUTO_INCREMENT,
	room int,
	entity_id int,
	entity_type ENUM('Monster','User','Item'),
	PRIMARY KEY(id)	
);

Monsters will be able to drop items, so I’m going to need to add a table to do that. Because all they’re going to be able to drop is items(not other monsters or rooms or anything), I can make it so that the monster_drops table only contains information on what items, and what the percentage chance is for them to drop:

CREATE TABLE monster_drops (
	id int NOT NULL AUTO_INCREMENT,
	monster int,
	item int,
	drop_rate int,
	PRIMARY KEY(id)
);

The next table I need to add is one to track a user’s inventory - so I’ll add the user_items table:

CREATE TABLE user_items (
	id int NOT NULL AUTO_INCREMENT,
	user_id int,
	item int,
	quantity int,
	PRIMARY KEY(id)
);

The design document mentions “____ of holding”'s, which is something I haven’t quite figured out yet. I could just use a stat to keep track of the player’s current inventory limit, or I could come up with a better idea. For the moment, I’m going to leave this piece of functionality out of my database design - I’m not sure how to build it yet.(If you know a good way to do this, send me an e-mail at buildingbrowsergames@gmail.com, or comment on this blog post)

Based on the list of commands players can use, there are a few stats that I can add into the database right now:

INSERT INTO stats(display_name,short_name) VALUES ('Maximum Health','max_hp');
INSERT INTO stats(display_name,short_name) VALUES ('Current Health','cur_hp');
INSERT INTO stats(display_name,short_name) VALUES ('Current Weapon','cur_weapon');
INSERT INTO stats(display_name,short_name) VALUES ('Current Armor','cur_armor');
INSERT INTO stats(display_name,short_name) VALUES ('Current Ring (Left Hand)','cur_ring_left');
INSERT INTO stats(display_name,short_name) VALUES ('Current Ring (Right Hand)','cur_ring_right');
INSERT INTO stats(display_name,short_name) VALUES ('Gold In Bank','bank_gc');
INSERT INTO stats(display_name,short_name) VALUES ('Gold In Hand','hand_gc');
INSERT INTO stats(display_name,short_name) VALUES ('Current Level','cur_lvl');
INSERT INTO stats(display_name,short_name) VALUES ('Current Experience','cur_exp');
INSERT INTO stats(display_name,short_name) VALUES ('Experience to Next Level','next_exp');

That sets me up with some of my starter stats, although it’s definitely not all of them - I’m sure I’ll end up adding more stats as Working Title grows into more of a finished product.

The last table that I’m going to add for now is simply for keeping track of exits off of rooms: room_exits:

CREATE TABLE room_exits (
	id int NOT NULL AUTO_INCREMENT,
	name text,
	from_room int,
	to_room int,
	PRIMARY KEY(id)
);

I’ll be tracking the entity_id of both of the rooms, and using the name value to select which exit. For example, an exit to the North from room 1 to 2 might look like this:

INSERT INTO room_exits(name,from_room,to_room) VALUES ('North',1,2);

With all this finished, there’s only one more system to add - spells. I’m not quite sure how I want to implement spells yet, either - do I want to have them do a set amount of damage, or base it on level, or something else? I’m going to hold off on designing any database tables for my spells system for now - once I have Working Title in a playable state, I’ll work on adding spells. For now though, I’m going to stick with what I have - I’ve got the basics of my database in place, and I can safely start developing now.

Designing a flexible items system

When building an inventory system, there are a lot of different approaches that you can take. Some developers simply hard-code everything, while others make sure that nothing is hard-coded - and in between both of these two extremes is a comfortable middle point, where we have most of the flexibility of not having anything hard-coded, while still being able to develop with the same level of ease as if we had hard-coded it.

Designing an inventory system like this takes time - you can’t just throw everything together and hope it works. You need to plan it out first.

One question you need to ask yourself is: what about different item types? If there are weapons, armor, and general items, how will you handle that?

A hard-coded solution would be to create three tables - weapons,armor, and items. But at that point, you have a problem; how will you link specific items to something like monsters? You would need to create three more tables - monster_weapons, monster_armor, and monster_items. And then figuring out what particular item a monster might drop at any given time would be a major headache.

An easier solution to this is to create a single items table, with a ‘type’ column that can be used to track the type - that way, we only need to link monsters up to single items, and we can retrieve all of the monster’s droppables with a single, simple database query. Here’s what a simple items table might look like:

CREATE TABLE items (
	id int NOT NULL AUTO_INCREMENT,
	name text,
	type text,
	PRIMARY KEY(id)
);

At this point, we now have a single table that we can use to track our different items - and the flexbility to categorize them all by type if we so choose. This allows us to do something like this to create three different items(each a different type):

INSERT INTO items(name,type) VALUES ('Wooden Armor','armor');
INSERT INTO items(name,type) VALUES ('Wooden Sword','weapon');
INSERT INTO items(name,type) VALUES ('Red Potion','consumable');

By building our items table in this way, we only need one table to link a monster to the items that they will drop - and we can easily make them drop any type of item we want them to. We can also create an item_stats table, so that all of our items can have stats applied to them:

CREATE TABLE item_stats (
	id int NOT NULL AUTO_INCREMENT,
	item_id int,
	stat_id int,
	value text,
	PRIMARY KEY(id)
);

And this way, we can leverage our stats system to allow our items to have the same stats as our players or our monsters. We can easily add and remove stats for any item we choose - if a potion should have a defence of 4 and a maximum HP of 8, we can do that. The flexibility is there.

While it’s not the perfect system, this inventory system is ‘good enough’ - as long as the only thing you know is that you will need to add and remove item types, and have different items with different stats, this item system will work perfectly for you.

Do you know of a better way to design an inventory system? Shoot me an e-mail at buildingbrowsergames@gmail.com, or leave a message in the comments!

Edit: sepp has pointed out that the item.type column would be a perfect location to use what’s known as an enum. According to the MySQL documentation on enums, an enum is “a string object with a value chosen from a list of allowed values that are enumerated explicitly in the column specification at table creation time.” - which is perfect for what we need. Because we will only have so many item types within our game, using an enum will ensure that we can’t have situations where we make a typo and end up with an item with a type of ‘weapoh’ or anything. Here’s the table creation code, using a basic enum to set up 3 item types:

CREATE TABLE items (
	id int NOT NULL AUTO_INCREMENT,
	name text,
	type ENUM('Weapon','Armor','Usable'),
	PRIMARY KEY(id)
);