UPDATE: Thu 2/23/2012: new version 1.3

As mentioned below, Caterpillar intelligence is implemented as a recursive lookahead algorithm. Each move has 3 possibilities, so computation grows exponentially with the cube of moves looked ahead. Each level of recursion created a couple of Point(x,y) objects, so it was driving the Java GC crazy. A single step in the game could, worst case, create about a billion Point(x,y) objects which are virtually immediately thrown away.

I realized that there is a simple, elegant solution to this. The total number of positions on the board is a small finite number, something like 50 - 100 positions on X and on Y, making at most only a few thousand. I created a Point Factory that caches Point objects, using each unique combo of X & Y as the cache key.

It ended up being a little trickier than that, since I could not use any java.util classes like Map etc. Why? Because every java.util class can only use Objects as keys. What is the point of eliminating billions of Point objects only to create billions of hash key Objects? So the cache is an array indexed by an "int" primitive. Each call to the factory does a few simple arithmetic ops on primitives and returns an object. It never creates new objects, except for the case where a brand new X & Y position is encountered, in which case it creates it once and stuffs it into the cache, to be reused forever never to be created again.

This has a further secondary benefit: since every Point for every unique X & Y position is now guaranteed to be the same shared object, if and only if the X & Y coordinates match, all my "point1.equals(point2)" tests can now become "point1 == point2".

The hash key is computed by taking the lower 7 bits of X, and ORing it with the lower 7 bits of Y shifted left 7 bits. This gives the following limitations:

You can see the PointFactory and its hash function in the source code below.

UPDATE: Tue 2/21/2012: new version 1.2

A friend tried it on an HTC phone and I found a new bug. I confirmed the bug on a Motorola phone too, so it appears to be a difference in behavior between actual devices and the emulator. On these phones, the GUI sliders can move one notch higher than the range specified in the XML layout. This causes overflow of an internal array. Since it's selecting a value bigger than the XML layout allows, this appears to be a bug in Android. I cannot repro this in the Android simulator on any version from 1.6 to 4.03. That said, it was easy to work around. The app now checks each value it gets from the sliders to ensure it doesn't go beyond the allowed range. If it does, it silently sets it back to the max allowable value.

NOTE: It took a while to get this update on the market because Android's publisher site had some issues last night. I hit a worst-case scenario: I unpublished the app in order to activate the update. Google's site started misbehaving after I unpublished the app but before I could activate the new one. Because of this, the app was removed from the market for 12 hours or so. But Google fixed the site and now it's back...

UPDATE: Mon 2/20/2012: new version 1.1

Check it out: Caterpillar Game.

It should run on any device running Android 1.6 or later. It is small, efficient and fast even on emulators and old slow hardware. It is free and has no ads. I've tested it on the following environments:

I first wrote this game 20 years ago in Turbo C for DOS. I ported it to Android in order to learn the Android system. It is a simple app that exercises fundamental areas of the Android system. But it is more complex than the Android sample apps, so it can be a useful bridge for learning Android.

Here's the source code: cat-src.tar.gz

If you try this game, please let me know how it works (or doesn't work!), and what device and version of Android you're running it on.

Here's an overview of the stuff in this game, areas or features of Android that it uses:

Limitations, bugs and etc.

My daughter made the game icon and we recorded the sound effects together.

Every 15 seconds the game plays a quick melody (that's me playing my fife) and speeds up by 10%.

Accelerometer controls are "experimental". I've discovered that the accelerometer axis are different on tablets and phones, and I did all my testing on my tablet, so it may not work properly on phones.

Relative controls are right-left only, from the caterpillar's frame of reference. Thus if the caterpillar is moving downward, a swipe (or touch) to the left will make him move right, which is HIS left.

Absolute controls move in the direction of the swipe (or touch) regardless of the caterpillar's orientation.

Swipe controls move the caterpiller in the direction of the swipe. The swipe can be anywhere on the screen.

Touch controls split the screen into equal quadrants (or halves for relative controls). A touch in any quadrant (or half) is moves in that direction.

Game setup will let more than one caterpillar be human controlled, but the game only allows one caterpillar to be human controlled. Any others set to human control will simply go in a straight line until they crash into something.

You can play with no human controlled caterpillars. This can be interesting to watch the computer play against itself.

The computer controlled caterpillars always run for the apples and use a recursive lookahead algorithm to figure out where it is safe to move. The maximum lookahead is 30 moves, and each move has 3 possible directions (left, right, straight), so that is worst-case 3^30 = 2e14 moves to analyze. If the game pauses when on maximum intelligence, this is why. This doesn't happen often because it quits as soon as it finds a safe path, so it doesn't always analyze this many moves. These pauses shouldn't cause a problem since the pause is on the game thread, not the main Android thread. To eliminate this pause, slide the intelligence down a notch or two. Each notch reduces the maximum pause by a factor of 3.