Puzzle Game Randomization

It seems that shapes in the official versions of the puzzle game are never truly random: the game tries to avoid delivering the same shape three times in a row. The GB game used a moderately broken routine that incorrectly produced some shapes more frequently than others. Most modern games adopt an approach seemingly inspired by Scrabble, in which all 7 shapes are added to a bag and pulled out at random until the bag is empty. This is a wonderfully simple algorithm, but it sounds like it would lead to horribly predictable games. It also makes it impossible to receive three of a given shape in a row rather than merely very unlikely.

My version of the game started out with a real randomizer (well, as random as you can get with rand()), but it sometimes made the game unenjoyable - lengthy repetitions of the same unhelpful block, long gaps between shapes I needed, etc - so I tried out the bag idea. Thinking it would be more enjoyable if it were possible to receive the same shape three times in a row I opted to make my bag hold two of each shape. It seems to work pretty well and eliminates the unenjoyable shape sequences, but it does introduce an element of predictability. There’s now a maximum number of shapes that can occur between two appearances of a given shape, which I can use to plan how I structure the playfield.

Worried that this predictability made the game too easy, I sat down for a lengthy play through. I reached level 19 and completed 194 lines. I can’t remember the last time I managed that on the Game Boy. Nuts. I switched to the Game Boy version to see how I did at that. Despite that version now seeming ugly and slow in comparison to my own, I managed to reach level 20 with 201 lines. It’s not easier after all.


A Puzzle Game

If you’re stuck on an aeroplane with nothing to do, what better way to pass the time than to write a new game? I’d written versions of this particular game in Flash and SQL before so creating a new version in C would be more of an exercise in dredging up old memories rather than creating something new (especially as the basics are so trivial to implement), making it an ideal project for a plane flight. I got the game logic working in the air, the rest of the game written over the next few days, and I’ve been mucking around with presentation and fluff for the last few weeks.

Here’s a slightly cropped video of the DS version:

Most of the game works the same way as the monochrome Game Boy version. Personally I think that everything added to the game since the Game Boy version - with the exception of color - has made the game worse, so this version intentionally sticks fairly closely to its minimalistic inspiration. Some of the graphics I redrew from scratch, using the Game Boy Color version as a reference, whilst some started out as screenshots of the GB version. The music came from The Mod Archive; after having no success in using large WAV files of the original audio I was happy to find some great versions of the original music on that site in XM format.

The only aspect of the game I intentionally changed was the responsiveness of the controls. Neither of the Game Boy versions of the game managed to get the controls right. The controls in the GB version of the game were sluggish and unresponsive. The controls in the GBC version grossly overcorrected the problem and made everything move far too quickly. This version finds a happy medium between the two.

I dug out the source code for the Flash version as a reference to see how I’d implemented that, opening it with a hex editor as I haven’t owned a copy of Flash XM or a computer capable of running it for years, but surprisingly there was barely any code in it. Thinking back, the two trickiest parts of the Flash remake were coming up with a function to rotate multidimensional arrays by 90 degrees (in order to rotate the shapes) and trying to increase the automatic drop speed by a constant amount in each level. The Flash version tried to solve the drop speed by using an ugly system in which, instead of regularly dropping the shape every n frames, drops were triggered by a repeating pattern of frames - eg a drop after one frame, then after two frames, then after one frame, etc - in order to simulate fractional frames. Rotating the shapes was tricky because each shape was contained within an array just large enough to accommodate the shape (the box was stored as a 2x2 array while the line was a 1x4 array, for example), so the rotation algorithm had to work with multidimensional arrays whose dimensions changed size as they rotated. Worse, each shape has a rotation point that can fall outside the bounds of its array making it difficult to reposition correctly in the grid once rotated.

For the DS version I avoided the rotation problem entirely by storing all possible rotations of the shapes as pre-canned data in the game, and solved the repositioning problem by representing all shapes using 4x4 arrays. There’s no need to reposition the shapes following a rotation because the arrays are large enough to contain the correct position of each rotation. I solved the drop speed problem by using the frame counts from the Game Boy version as listed over at HardDrop.

Of course, creating a new game led to a number of improvements and enhancements to the underlying libraries, which is the fun but time-consuming part. I wanted to support graphics that were 50% larger on the PSP and 3DS, which meant changing my PNG-to-C tool so that it could convert two PNG files into one C file with #ifdefs to switch automatically between small or large graphics depending on the target platform. I was already embedding two copies of the bitmap data - one for the DS and other platforms and one for the Dreamcast - so I first had to implement real fixes for the hacky system that handled the color space conversions for that platform and get rid of the unnecessary bitmap data.

Once I had support for multiple bitmap sizes I realized I’d also need to be able to support multiple font sizes. I finished off my objc tool for creating fonts from PNGs and added large font support to it.

Supporting XM mod files meant adding mod support to the sound system. That was straight-forward enough: SDL’s mixer library uses libmodplug for mod playback; the DS uses MaxMod; and I’m using MikMod for the PSP. I haven’t figured out mod support for the Dreamcast or any kind of sound for the 3DS yet. Hanky Alien, Chuckie Egg and this game all had their own sound implementations, so I divided the class into two pieces (a data provider and a sound server) and moved the server out into the shared hardware abstraction library. Chuckie Egg and this game now use the server code; Hanky Alien will use it eventually.

Finally, I’ve been adding macros for reducing the amount of boilerplate necessary when creating classes. I’ve also created a tool that will generate new source and header files for classes.

There’s still a bunch of tedious presentation work to do to finish this off. I wrote a hierarchical menu system for Amy Zing that I’d hoped would be the only menu system I’d ever need to write, but naturally the menu system I need here uses a different structure. It’s more like a graph of screens than a hierarchy, in which the decision about which node to visit next depends on logic in whatever object owns the menu instance rather than the option that the user just selected. I’m hoping that the high score system I wrote for Chuckie Egg will just drop in to this game, though I’ll need to write a new view to present it. I need a title screen, a “game over” screen, a “game complete” screen (for the B-type game), some alternative background graphics, launcher assets for the PSP, a two-player mode (on the same device) and music/sound on platforms that currently don’t have it.