Using Bit-Wise Operations To Create A Repeatable Sequence Of Procedurally Generated Levels

A few years ago, when creating my game for the Urban Squall 4K Competition , I decided to go back and try to remake an old game that was written in ActionScript 1, and bring it into the modern era. Since Breakout is one of my favorite games of all time, I decided to take my old Brickbasher game and see if I could redo it in 4K. I recalled that the the original prototype for Brickbasher was about 8K, and I also knew I had better programming chops now than back in 2002, so I was fairly confident that it could be done.

After stripping out all the useless code, and re-writing a more efficient game engine, the core was about 3K. This was cool, but it left me with one problem: How do I create interesting levels to play? While the original Atari Breakout had just one level design, modern "Breakout" style game have dozens of intricate levels to destroy. Brickbasher used a "one byte per brick" design that simply would not allow enough levels to make it interesting in 4K. To make this work, I would have to dig back to some advice I received from one of the star Atari VCS programmers, David Crane.

Back in 2001, David Crane came to my place of work to pitch a game idea for an RFP we were conducting. After the meeting, I caught him in the hallway, and professed my undying appreciation for his work. Since he did not instantly run way, I asked him something that always bewildered me: how did he get so many screens into the game Pitfall! The Atari VCS could only address 4K of memory (more with RAM bank-switching), but Pitfall! (and River Raid, a game he helped design) had 256 different screens. This always seemed impossible to achieve within those limitations. He told me that to create the Pitfall! world on a VCS cartridge, he used a combination of a polynomial sequence, and bit wise operations. In short, he took a set of 256 randomly generated numbers (mind you, only randomly generated the first time ), and then checked specific bits in each number to know what to draw on the screen (pits, scorpions, treasure, etc.). When that was done, he found the perfect place in the sequence to start the player, and the Pitfall! world was born.

I had never done anything like this before, but this seemed like a good way to try to create multiple levels for a 4K breakout style game.

My first idea was to create completely random brick placements based on a sequence of seeded (repeatable) random numbers. However, when I tried this the levels looked predictably lame: like a set of completely random bricks, and this is not what I wanted at all.

Instead, I came-up with another concept, also loosely based on the Atari VCS. When programming the VCS, developers had a "background" screen available to them. However, this "background" only took-up 1/2 the screen. The logic for this was based on what the Atari VCS was originally designed to do: play 2-player Pong and Tank! games.. Each of those games has an play field that is essentially identical at both ends. If the play field was going to be identical, the VCS hardware designers did not have to waste extra power trying to create a full background, when they could just copy 1/2 the background, mirror it, and have the same effect. This is why many Atari VCS games have symmetrical play fields.

Armed with both these ideas, I tested what a play field would look like using a set of blocks, copied 3 times (upper left:normal, lower left:flipped, upper right:mirrored, lower right:mirrored, flipped). When I did these copies, what originally looked like a set of random bricks, became a symmetrical play field.

(First set of randomly generated bricks)

(Copied, and flipped second set of bricks)

(Copied and mirrored 3rd set of bricks)

(Copied, mirrored, and flipped 4th set of bricks)

Now I had a concept for how I would build levels out of random (but repeatable) placed bricks, but I still needed a way to generate those levels. Going with David Crane's idea, I needed a repeatable set of numbers. After playing around with this for a long time, I settled on the level number (1,2,3,...). Yes, this was not really a random sequence, but it very well could have been. Since I did not have the bytes to spare in 4K to hold a list of numbers or complex random seeding function, this would have to do.

Next I needed to test the bits of levels number to see if I should place a brick. Each set of bricks was 6x6 (copied 4 times to make a 12x12 grid of possible bricks). My decision was to bitwise AND the level number with the product of of the row and column of the brick I was placing. If the value was was "1" (on, true,yes), I would place a brick in that position:

 if (l & j*i)

If the brick was supposed to be placed, I would place put it in all 4 places (upper left, lower left, upper right, lower right) the screen, achieving my symmetry:

makeBrick((j) * 50,(i * 18) +20, level,i);
makeBrick((j) * 50,182 - (i * 18), level,i);
makeBrick(600-(j+1) * 50,(i * 18) +20, level,i);
makeBrick(600-(j+1) * 50,182 - (i * 18), level,i);

Here is the full code I used to test for the bricks and place them on the screen:

while (bricks.length <= 0) {

for (i = 0; i < 6; i++) {
   for ( j = 0; j < 6; j++) {
      if (l & j*i) {
         makeBrick((j) * 50,(i * 18) +20, level,i);
         makeBrick((j) * 50,182 - (i * 18), level,i);
         makeBrick(600-(j+1) * 50,(i * 18) +20, level,i);
         makeBrick(600-(j+1) * 50,182 - (i * 18), level,i);
      }
   }
}
l++;
}

Using this method, I was able to create 20 distinct screens. I added difficulty by making bricks that had to be hit multiple times (different colors), and the number of possible levels increased almost two-fold. If I had decided to increase the grid size from 6x6 to anything larger, the possible symmetrical designs would have increased as well. I plan to remake this game in the future with more bricks, and even more interestingly random, symmetrical levels. (See HTML5 Brick Basher link at the end of the story)

Since Neon Bricks 4K is quite a difficult game, I have taken screen shots of the first 20 levels, so you can see the product of the bit wise operation, number sequence, and screen copy ideas all in one place:

(Level 1)

(Level 2)

(Level 3)

(Level 4)

(Level 5)

(Level 6)

(Level 7)

(Level 2)

(Level 8)

(Level 9)

(Level 10)

(Level 11)

(Level 12)

(Level 13)

(Level 14)

(Level 15)

(Level 16)

(Level 17)

(Level 18)

(Level 19)

(Level 20)

And that is it. A very simple use of some old ideas, to create a richer game than would have been possible otherwise.    Play the final version of Neon Bricks 4K.

By the way, there were a few other optimizations I used to keep the game under 4K. For instance,  the relatively simple graphics allowed me to reuse the same single  vector image for all the bricks, backgrounds, balls, shots, etc.   I used the built-in AS3 functions for scaling,  tinting, alpha, and glow effects to achieve the retro look I was striving for from that single image.

I've very recently used a similar concept for a prototyped HTML5 Canvas version of Brick Basher.    This version uses "progressive" set of bricks that continuously come down the screen, so there are no "levels". It's mobile-ready and uses touch controls (you need to click and drag the mouse on the web to move the paddle). 


Steve Fulton is Vice President Of Software Development for Producto Studios, an independent development house in Redono Beach, California specializing in animation, games, e-learning, Flash,  HTML5, web and mobile.