Copyright Notice: This article is Copyright AI Factory Ltd. Ideas and code belonging to AI Factory may only be used with the direct written permission of AI Factory Ltd.
This article looks at some of the issue around creating games with large potential graphic needs to fit on small gaming devices. The game in question is our latest "Move it!" puzzle game, which is on release and described in our press release here.
The "Move it!" Game
This was detailed in the last issue under "Solving Deep Puzzles" that looked at the issues of creating the actual puzzles, but having done that these then need to be rendered on the actual device. Taking a look at our Android game in service:
This game is related to the world famous genre based around Yoshigahara's Rush Hour puzzle game, and many times copied under other names such as Traffic jam and Unblock me. Like Rush Hour, the goal is to move a key piece from one side of the board to the other. However Move it! has key differences:
The key point here for rendering concerns is point (2), the number of shapes. Rush Hour has this sorted as 4 shapes to render cannot be an issue. If you have a game supplied on a DVD for PC or PS3, with 0.5 of memory of more, then 72 shapes is also not an issue.
However, as indicated above, we were targeting mobile devices, which impose limitations of storage on the device and download time for delivery across 3G, or whatever wireless medium is in use.
Plan of Attack: How do we represent and render these?
This is a question that is made more complex by considerations of "just how big is a bit map?". If graphics are all held in buffers, expanded to full bitmap images, then these can be huge. However, certainly for the application image, this information can be stored as PNG images, which can radically compress images.
Of course at any one moment during an application's run, it only needs a small subset of the total possible images in a position where they can be quickly rendered.
Plan 1: Just store PNG files for each possible shape
First we need to consider what a full "shape" might be:
On the left above we can see several shapes where the defined 3x3 white square could contain all of these. At first glance this may look inefficient as obviously not all shapes require 3x3, but actually a PNG with a large transparent region is essentially the same size as the same shape with no extension for transparency. It is therefore convenient to create a square bounding shape that fits all.
However on the right we see a shape that needs a 5x5 bounding box, so all our bounding defined shapes need to be 5x5.
So all shapes will be represented as 5x5, with each rotation being a different shape. The first thing that might spring to mind is that you do not need rotations, as these could be represented by getting the SDK to rotate these on-the-fly. However the shapes above are rendered with shadows, so this option is not possible.
Costing Plan 1
Looking at the full bitmap size we have the following calculation. Note that we probably want 8 colours, so this scales up the requirement by 8x. It is possible to manipulate colours on-the-fly but generally this is inflexible and does not work well.
This gives us a total of 680 meg for the full bitmap set. Of course we use PNGs so this collapses somewhat. From tests it appears that the above shapes reduce to about 4.5% of the full bitmap size.
This gives us 680 meg x 4.5% = 30.9 meg
This is a huge size for a mobile game, which may even be restricted on download limits to 10 meg per app. This does not account for any other artwork so this is clearly not viable.
Plan 2: Modularising the shapes
These shapes are not amorphous designs but are clearly regular and invite modularisation.
The above two shapes offer obvious points were the shape can be cut up. If we examine all the shapes we require, we find that we actually need 20 possible components to make up any desired shape, as follows:
Note that this does not allow representation of all possible shapes we could imagine within a 5x5 grid.
The above solid shape uses a component we have not defined. If we were to accommodate such a shape it would require an additional 8 components, giving 28. As it happens such shapes are less interesting for our puzzle, so these were optimised out.
Costing Plan 2
Now the overhead is looking much less. Each PNG appears to need about 2.5 k so we have the following calculation:
2.5k x 20 components x 8 colours = 0.4 megabytes
This is clearly more reasonable. Many mobile apps are in the size range 1meg to 6 meg, so 0.4 meg is acceptable.
Control of puzzle definition and rendering
A key issue here is how to represent a puzzle in the source code and then deliver something that the UI can conveniently render.
We could define each shape in terms of the actual component names, as follows:
In this scheme we define each puzzle as a linear array and populate it with "__" for empty and the component name for the desired part of shape.
This is plausible but really quite inconvenient, as editing a shape on-line means that it would need to each time restructure each component to fit in the revised shape. That is unnecessarily complex. Also note that once the board is populated by interlocking shapes that it is complex to spot which component belongs to which shape.
Another more convenient plan is to represent a puzzle as a series of shape IDs such that each shape on the board is constructed from a series of markers using that unique ID.
In the diagram above the same array is used to define the puzzle that is shown below it, but uses the IDs _A_ through to _D_ to define the shapes. This has no component information. For the intents and purpose of the puzzle creation and analysis, the components are irrelevant so actually they need only be considered at render time.
To manage rendering there is a separate shape table that shows how each component can be created and these are scanned against the puzzle definition, row by row and column by column, until a match is found. In the above diagram the match is defined by the red rectangle. The four _B_ IDs are translated to U_R, C_D, C_U and U_L, which can be used to index into a bitmap table.
This coding method above also encodes solutions, so that any one puzzle is a linear stream of bytes, where an end of row is defined by ECell_EOL and end of board by ECell_EOB. The solutions are bound by ESolution and puzzle ends with ECell_EOP for end of puzzle.
Conclusion
The above scheme works well for "Move it!" and will be employed in the puzzles that will follow. It conveniently separates out rendering information from puzzle solving so that puzzles can be analysed using very simple reduced forms, with rendering only considered at the point that rendering is required.
Our Android "Move it!", with music is just a little over 2 megs and well within an acceptable size.
Jeff Rollason - September 2010
