Messages From Beyond the Grave

Designing a game is different from designing a consumer application in a very basic way. Consumer applications tend to be event-driven with long periods of inactivity while waiting for input, while games tend to be constantly redrawing and recalculating in real time. The Android framework is designed to allow for easy creation of event-driven applications.

This leaves the game developer with an interesting quandary. To make a game, one must simulate a loop within an event driven environment. Many developers stuff their game logic inside of onDraw() and then invalidate themselves as quickly as possible. This accomplishes the job, but it prevents them from invalidating only the areas of the screen that need to be repainted. For games where much of the screen does not change often, invalidating only changed areas of the screen can provide a large performance increase.

Luckily, the Android framework proves a way to hook into the message loop which drives the application. The Handler class provides the ability for an application to send itself custom messages. This means that the game developer can separate game logic from rendering code for a cleaner structure.

When we first implemented a game in this fashion, it would continue to use 100% CPU after it had finished. I was confused when I verified that the game was receiving the onDestroy event, which indicates that the application's resources are about to be released.

It turns out that in order to speed up subsequent launches of an application, Android caches processes from terminated activities. When cached, the process' message loop can still receive messages, presumably so that the OS can wake it up when the user chooses to launch that application again. Since we were sending a new custom event every time we received one, the process would continue to receive and act on our custom messages after the activity had been destroyed.

A simple change that prevented the application from sending new messages after it had received a termination event fixed the issue.

Image Transparency (aka an absurd application of convex hull)

Android makes it very easy to load an image as a bitmap:

int resID = context.getResources().getIdentifier(...);
Bitmap bitmap = BitmapFactory.decodeResource(context.getResources(), resID);

But once you have that Bitmap, if it has significant transparency, kiss your performance goodbye. Getting decent performance back is going to be anything but easy. For our Penguins game we wanted to have all images of the penguins (one per frame of animation) to be identically sized so that they could be easily positioned. This means that each image (frame of animation) has a large amount of fully transparent pixels. Drawing all of these fully transparent pixels absolutely destroyed our frame rate in the emulator. Essentially, the emulator has dreadful alpha blending performance.

So, the question was - how could we keep our images with lots of fully transparent pixels and have good performance? The obvious answer was to have Android draw as few of the fully transparent pixels as possible. The Canvas class which is used for drawing has the following method:

Canvas#clipPath(Path path);

So it was now necessary to build the best possible Path around each penguin image. I wanted a programmatic solution, particularly because at the time of writing the code I was not working with the final artwork. So the first step was to figure out an efficient way to access all of a bitmap's pixels. Bitmap has a convenient method to access an individual pixel, but calling that methods tens of thousands of times for each image results in dreadful performance. (Even though this computation is only done while the game is loading, not each frame.)

Turns out there's a very easy way to get the pixels as a linear array:

int width = bitmap.getWidth();
int height = bitmap.getHeight();
int[] pixels = new int[width*height];
bitmap.getPixels(pixels, 0, width, 0, 0, width, height);

Now that we have the pixels we want find the boundary pixels. (Note: If our images had fully transparent pixels inside of non-transparent pixels this approach would not have worked as well.) So the next step was to find all of the boundary pixels:

ArrayList points = new ArrayList();
for(int x = 0; x < width; x++)
{
  int firstY = -1, lastY = -1;
  for(int y = 0; y < height; y++)
  {
    boolean transparent = (pixels[y*width+x] == Color.TRANSPARENT);
    if(!transparent)
    {
      if(firstY == -1)
      {
        firstY = y;
      }
      lastY = y;
    }
  }

  if(firstY != -1)
  {
    points.add(new Point(x, firstY));
    points.add(new Point(x, lastY));
  }
}

A Path could then be built from these pixels. (If we were to actually do this, it would be easier to build the Path using two ArrayLists, one for top half, the other for the bottom Path.) I gave this a try, and the performance was marginally better. The Path fit perfectly and therefore had an enormous amount of line segments in it. I had just traded one performance slow down for another. I wanted a way to have a Path that was guaranteed to include all of the penguin, would not have many fully transparent pixels, but also a lot less line segments. I had an absurd idea - why not implement the convex hull algorithm over the boundary points? So I did, and it worked. Performance increased dramatically. I was now drawing a few fully transparent pixels, but the Path object had far fewer line segments.


Below is a diagnostic mode where the clipping Path is being draw. The bottom penguin is in mid-left thwack.

A Personal Project

Fliptile!



This was a personal game I made 'off the books' two weekends ago. There's lots to be done, but hopefully this will whet your appetites ^_^

This is a clone of Tetris Attack. As promised, a link to some gameplay of the original (rather, a re-release as Pokemon Puzzle League). Since this is such a direct copy, I doubt I'll distribute it on a marketplace or anything (at least unless I think of a cute Lexulous-like workaround).

Penguins!

Hey all, here's a small video demo-ing our newest game, (the imaginatively titled) Penguins!



As promised in the video, here's a link to the Whitkin-Baraff papers from SIGGRAPH '97 for modeling physics. This was pointed out to us by Chad.

Also, I kind of lied in the video, I said we were running (in better conditions) at 17-18 FPS. I think we go significantly higher (closer to 23-25), I just slipped while narrating.

Matt is Awesome

Hey all,

Very soon we will introduce our newest game. In the meantime, to make up for the lack of updates, read about a very cool data structure hack our teammate Matt found. I think it's very cute; it blew my mind a little. He tells you how to implement a queue using only one instance of a stack ^_^

Soon, be ready for some hungry penguins!

-Paul

Home Screen Icons

I ran into an interesting issue while testing my minigame, Moles. Once I had the core game working, I decided to add an intro screen that would allow you to pick a difficulty. I made a separate Activity for it and changed the settings in the manifest to account for this.

Launching from Eclipse worked fine, but when I launched the game from the Home screen icon I had made for the game, I got this error:

02-18 01:51:43.750: ERROR/Launcher(106): Launcher does not have the permission to launch Intent { act=android.intent.action.MAIN cat=[android.intent.category.LAUNCHER] flg=0x10200000 cmp=cs134.adventure.minigames.moles/.MolesActivity }. Make sure to create a MAIN intent-filter for the corresponding activity or use the exported attribute for this activity.

After much fussing, I discovered that the Home screen icon didn't work, while the one on the programs menu did.

It seems that the Home screen icons are not deleted or updated when an application is uninstalled or reinstalled. Moreover, rather than referencing the manifest, the icon seems to cache the main Activity and ask Android to launch that directly.