Elegance is a solution with the minimum number of moving parts.
As kids, my brother and I would make all kinds of games to play with one another. Not with computers, but with real world materials. We had this old, brown, chapped leather satchel, that had somehow survived the 1970s without being burned for the crime of existing. It contained a seemingly inexhaustible supply of felt pens; stickers; pencil crayons; lettering transfers; French curves and set squares. Our father would put inordinate stationary orders through at work and nobody ever saw fit to question where it all went. He was a busy man, after all. So we were never short of construction card; adhesives; notebooks.
"The order enforced by all of those lines and the chaos of your burgeoning creativity were simply two aspects of the same thing."
And graph paper.
Graph paper became a mainstay in your formative years. You did everything on it, from early illustrations to board games and designs for impossible machines. You drew single-square-wide mazes that would spread from edge to edge, filled with long, twisting dead-ends and devious solutions. The order enforced by all of those lines and the chaos of your burgeoning creativity were simply two aspects of the same thing.
It served you well. Because when creativity demands adherence to a set of rules, be it logic, physics, or statistics; you really cannot afford to flinch. Not when you’re making a commercial video game all by yourself.
Having by this point designed a prototype and dreamed up a theme for our game, we now need to devise a means of creating and managing the layouts for our levels. Whatever we come up with will be updated in real time, keeping track of everything going on in our level throughout a game round. So we need to work smart.
Let’s say that a level comprises a 7 x 7 grid. First, we need to populate the grid with some permanent obstacles that allow orthogonal (i.e. up, down left and right) movement only.
We can store all of the above in a list or 2D array, using a simple coordinate system in which the origin [0, 0] is at the top-left and the furthest grid cell [6, 6] is bottom-right.
If we assign a number to each game object type, then we can place these numbers at their corresponding coordinates within the grid. For the example above:
0 = Empty
1 = Obstacle
So the coordinates [0, 0] would contain a 0, meaning empty. At [1, 1] we would place a 1, meaning obstacle. Placing either a 0 or a 1 in each grid cell will therefore store the above layout perfectly.
This is fine if you only want to store empty cells and obstacles. But what if you want to record other entity types, like players, mines and powerups? It may be tempting to simply use a 2 to store a powerup, a 3 to store a mine and so on. But consider this: How would you record a cell that contains more than one type of entity? For example, a player and a mine should certainly be able to exist in a grid cell simultaneously within our game; can we still do this by storing single numbers in each cell?
We solve this with some simple logic, based on a system that is over 300 years old: Binary. Don’t flinch. You can’t afford to.
Gottfried Wilhelm Leibniz. Inventor of Binary. And massively stupid hair.
Binary has many great uses, one of which is setting flags for individual parameters within a single number. First let’s look at what our usual representation of numbers actually means, using the old hundreds, tens and units model that they taught to us at school.
Here is a decimal representation of the number 342. It comprises 3 hundreds (100), 4 tens (10) and 2 units (1). For each column, you simply multiply the quantity by the column value, then add them all together, thus:
(3 X 100) + (4 X 10) + (2 X 1) = 342
This is probably second nature to you. Which is great, because this same workflow is precisely how we work with binary, only instead of each column being 10 times the value of the previous, columns in binary are 2 times the previous:
This also means that each column in binary can only store either one or zero of each quantity. So above we have:
(1 X 4) + (1 X 2) + (0 X 1) = 6
So 110 (read as “one-one-zero”) in binary is 6 in decimal. Let’s try a larger number with more columns:
(1 X 16) + (0 X 8) + (1 X 4) + (1 X 2) + (0 X 1) = 22
Because the columns multiply by two each time, it is impossible to see the same number twice in the structure. For example, there can only ever be one 4 within the whole number, as there is only one column for it and we can only hold a single value in that column. So if you think of each column as a ‘flag’ – that can be set to either on or off — then we can use them to enumerate a specific object type, like so:
In this example we store a player, a mine and a powerup in the same number by using their assigned columns as flags. As stated earlier, the way that binary is structured means that there can only ever be one of each number within the whole. So the number 22 (16 + 4 + 2) as represented above can only be interpreted as these three entities, sharing the same space.
We can now store multiple entity types within each cell of our list. In fact, we can store one of every single entity type in the same cell if we need to. This approach is so optimal that we can even fire it across a network, keeping multiple online players updated as the map changes throughout the game. We simply set and unset the ‘flags’ for each entity that is added or removed from any cell, then update the sum that the entities in the cell add up to.
Behind all of the fancy graphics and bluster of our video game then, will be what is essentially a traditional board game, in which we move pieces around and modify a simple set of numbers to keep track of everything.
Playing with graph paper all those years ago seems to have paid off. As with mine, I hope that your solutions satisfy your own definition of elegance.
Darby Costello is a software developer, learning technologies consultant, solo game dev, graphic designer, mad scientist and educator. If you ever see him out, he'll either be sat in the corner exchanging views on Chomsky with a pot plant, or in the centre of the dance floor befriending complete and probably non-reciprocating strangers.
Other articles in this series: