Building libpcap

After a lot of false starts, it turned out to be fairly simple to build the native libpcap library. In my original attempts, I was working to build the entire Cyanogenmod ROM for my device so I could harvest the libpcap so file. While this might have eventually worked out, it was a very difficult path. In the end, the “proper” way to do this was to use the Android NDK to build the Android libpcap native code as part of my project.

Running As Root

Libpcap requires root access in order to access the low-level networking stack. On the surface, this seems pretty simple to do using the support provided by the RootTools project. However, it turns out that the combination of root applications and access to native libraries is a bit tricky.

When using RootTools, launching a root application actually involves multiple processes:

Processes Diagram

The initial process is the main application with an Android Activity. This activity interacts with the RootTools support which checks for root ability and, if found, launches a new shell process with root authority. That root shell mediates between the original Activity and root applications launched on behalf of the original activity. For short-running root applications, it is possible to communicate using the STDIN and STDOUT pipes. However, for a long-running service, it makes more sense to use some other communications channel to communicate between the Android activity and the root application. One possibility would be a Unix domain socket provided by the android.net.LocalSocket class.

Native Libraries And Root

While RootTools provides the infrastructure shown above, the problem I ran into was that when launching the root application (process 3), it would not be able to locate the native libraries that the JNI class was dependent on. The RootTools JavaCommandCapture class launches the Java class using a command similar to:

dalvikvm -cp /path/to/anbuild.dex com.android.internal.util.WithFramework com.stericson.RootTools.containers.RootClass my.package.RootCodeClass

This long incantation starts up a new Java Application using the Dalvik VM. The WithFramework class “Binds native framework methods and then invokes a main class with the remaining arguments” and then calls the RootClass class. Finally, the RootClass class invokes the RootCodeClass constructor passing along the remaining command-line arguments. RootTools expects the root functionality to occur as part of the construction of RootCodeClass, however if RootCodeClass has a JNI dependency on a native library the functionality will fail with an UnsatisfiedLinkError exception.

dalvik.system.BaseDexClassLoader

Normally, Java may be started with the “java.library.path” System property to set the location of the native libraries, however that doesn’t appear to work correctly in Android. In addition, the LD_LIBRARY_PATH from Linux won’t work either. It turns out that Android actually pulls the native library path from the Classloader that is used to load the class referring to the native static library.

The dalvik.system.BaseDexClassLoader class acts as both a Java class loader mechanism and a holder of the native library path. The initial classloader started by the Dalvik VM does not contain any references to the static library path leading to the linkage failures. I was able to solve this, by adding yet another layer of indirection:

Classloader Diagram

In this model, the initial RootCodeClass constructor creates a new BaseDexClassLoader instance referencing the native libraries path.

JavaRootClassloader targetLoader = new JavaRootClassloader(
				nativeClasspath, 
				null, 
				nativeLibPath, 
				getClass().getClassLoader());

In this case, the native classpath and native libraries have been passed in as command-line arguments from the originating Activity. The targetLoader must be used to load the target class in order for the target JNI classes to use the provided native libraries. It is important that these classes be kept in separate classloaders to avoid errors in the Dalvik VM about redefinition of classes.

Class<?>targetClass = targetLoader.loadTargetClass(targetClassName); 

The loadTargetClass method is a special Classloader method that uses classloader-first rather than parent-first lookup to avoid using the parent classloader which does not have the native library path defined.

/**
	 * Load the specified class, making sure to *not* do a parent-first load
	 * as we will end up with the wrong classloader.
	 * 
	 * @param targetClassName
	 * @return
	 * @throws ClassNotFoundException 
	 */
	public Class<?> loadTargetClass(String targetClassName) 
		throws ClassNotFoundException 
	{
        Class<?> clazz = findLoadedClass(targetClassName);

        if (clazz == null) {
        	// Look locally first for our target class
        	clazz = findClass(targetClassName);
        }

        return clazz;
	}

In the current implementation, all of the information necessary to launch the final targetted class with native library path properly set is provided by the originating Activity. Remaining command-line arguments are captured by the “launcher” class and provided as the arguments to the main method of the target class.

DEX Files

The default RootTools approach for creating Java classes that can be loaded in the root context is by adding the com.stericson.RootTools.containers.RootClass.Candidate annotation to the root classes and then processing with the com.stericson.RootTools.containers.RootClass class. The result of this process it to create an Android DEX file called anbuild.dex. I struggled to get this all to play nicely and get all of the proper classes into the proper DEX files. As mentioned, loading the same class in different classloaders can cause Dalvik VM errors that look like the following:

Class ref in pre-verified class resolved to unexpected implementation

In the end, I ended up with three separate DEX files:

• Standard application DEX file
  This file is automatically built and handled by the Android tools and the runtime. This file contains the code for the main Activity and associated logic
• Root Launcher DEX file
  This file contains just necessary classes to be loaded by RootTools and to create the special Classloader instance that can load the real root functionality while specifying the native libraries path. This DEX file is generated as rootlauncher.dex into the res/raw folder
• Root functionality DEX file
  This DEX file contains the Java functionality that will run in a root context that will have access to the native libraries necessary to interact with the system. This DEX file is generated as root.dex into the res/raw folder

Building The DEX Files

Because of this added complexity in creating the multiple DEX files, I had to take more control over the build process. Taking advantage of Eclipse’s ability to call out to an Ant build.xml as part of the build process. For instance, the build.xml file for generating the DEX files would look something like:

    <target name="build_root_dexs">  	
    	<property name="dx.path" value="${user.home}/software/unzipped/android-sdk-macosx-personal/build-tools/${build-tools-version}/dx" />
    	
    	<!-- Build the root launcher -->
    	<unzip src="libs/RootTools-3.3.jar" dest="bin/classes-launcher">
    		<patternset>
    			<include name="com/stericson/RootTools/containers/*.class"/>
    		</patternset>
    	</unzip>

    	<echo message="Building rootlauncher.dex" />
    	<exec executable="${dx.path}">
    		<arg value="--dex" />
    		<arg value="--output=res/raw/rootlauncher.dex" />
    		<arg value="--positions=lines" />
    		<arg value="bin/classes-launcher" />
    	</exec>
    	
    	<!-- Build the code that will run within the root container -->
    	<echo message="Building root.dex" />
    	<exec executable="${dx.path}">
    		<arg value="--dex" />
    		<arg value="--output=res/raw/root.dex" />
    		<arg value="--positions=lines" />
    		<arg value="bin/classes-root" />
    	</exec>
  </target>

An Ant build can be added to the build file via the Project properties:

Eclipse Builders

Add a new Ant Builder:

Eclipse Builder Type

Choose your Ant file:

Ant Build File

And save the resulting build launch configuration:

Build Configuration

Caveats

While this approach is working fine for Android 4.0+, there are a lot of pieces of this puzzle that are private/internal to the Android implementation. For that reason, many of these internals have the chance of changing over time. In particular:

• The com.android.internal.util.WithFramework is clearly marked as an internal class
• The dalvik.system.BaseDexClassLoader is yet another internal class that may disappear or change
• Even the Dalvik VM will likely go away in the future and be replaced by the new Android ART runtime

Depending on the device and operating system level, there are subtle changes in behavior. In most cases, there is a crash log written to the /data/tombstones folder. The most revealing tombstone file has come from a Samsung Captivate running a version of the AOKP ICS ROM.

Build fingerprint: 'samsung/SGH-I897/SGH-I897:2.3.5/GINGERBREAD/UCKK4:user/release-keys'
pid: 1758, tid: 1777  >>> com.seterasoft.mclock <<<
signal 11 (SIGSEGV), code 1 (SEGV_MAPERR), fault addr deadbaad
 r0 deadbaad  r1 00000001  r2 40000000  r3 00000000
 r4 00000000  r5 00000027  r6 50c53b40  r7 00000064
 r8 41338018  r9 00000024  10 50c53a6c  fp 50c53ab0
 ip ffffffff  sp 50c53a30  lr 400fdf79  pc 400fa694  cpsr 60000030
 d0  0000000000000000  d1  0000000000000000
 d2  0000000000000000  d3  0000000000000000
 d4  0000000000000000  d5  0000000000000000
 d6  0000000000000000  d7  0000000000000000
 d8  0000000000000000  d9  0000000000000000
 d10 0000000000000000  d11 0000000000000000
 d12 0000000000000000  d13 0000000000000000
 d14 0000000000000000  d15 0000000000000000
 d16 0000000000000000  d17 0000000000000000
 d18 0000000000000000  d19 0000000000000000
 d20 0000000000000000  d21 0000000000000000
 d22 0000000000000000  d23 0000000000000000
 d24 0000000000000000  d25 0000000000000000
 d26 0000000000000000  d27 0000000000000000
 d28 0100010001000100  d29 0100010001000100
 d30 0000000000000000  d31 3ff0000000000000
 scr 2800001b

         #00  pc 00017694  /system/lib/libc.so
         #01  pc 00007bb0  /system/lib/libcutils.so (mspace_merge_objects)
         #02  pc 0007b6c8  /system/lib/libdvm.so (_Z21dvmHeapSourceFreeListjPPv)
         #03  pc 00042ce0  /system/lib/libdvm.so
         #04  pc 00032f94  /system/lib/libdvm.so (_Z22dvmHeapBitmapSweepWalkPK10HeapBitmapS1_jjPFvjPPvS2_ES2_)
         #05  pc 00042c9c  /system/lib/libdvm.so (_Z27dvmHeapSweepUnmarkedObjectsbbPjS_)
         #06  pc 000337c0  /system/lib/libdvm.so (_Z25dvmCollectGarbageInternalPK6GcSpec)
         #07  pc 0005ff6c  /system/lib/libdvm.so (_Z17dvmCollectGarbagev)
         #08  pc 00072a8e  /system/lib/libdvm.so
         #09  pc 00030a8c  /system/lib/libdvm.so
         #10  pc 00034248  /system/lib/libdvm.so (_Z12dvmInterpretP6ThreadPK6MethodP6JValue)
         #11  pc 0006c692  /system/lib/libdvm.so (_Z14dvmCallMethodVP6ThreadPK6MethodP6ObjectbP6JValueSt9__va_list)
         #12  pc 0006c6b4  /system/lib/libdvm.so (_Z13dvmCallMethodP6ThreadPK6MethodP6ObjectP6JValuez)
         #13  pc 0005f7c0  /system/lib/libdvm.so
         #14  pc 00012c14  /system/lib/libc.so (__thread_entry)
         #15  pc 00012744  /system/lib/libc.so (pthread_create)

The failing function appears to be implemented in dlmalloc.c in the Android source, but I really don't have any good idea about what might be causing the crash. I also don't appear to be the only one, as there are other references on the web that look similar.

To this point, I've tried a variety of things to try to track down the problem. I've gone so far as to try to build my own version of the Cyanogenmod with the idea that I might be able to add more logging output. So far, I've not had any luck with this approach. I generally have no problem walking away from hobby projects when I lose interest. However, this has turned into a competition of me versus the computer and I'm not quite ready to give up.

Inertia is the resistance of any physical object to a change in its state of motion or rest, or the tendency of an object to resist any change in its motion.

For me, this also describes my tendencies toward side projects like my Pingus project. When I last worked on Pingus a couple of months ago, I updated the underlying AndEngine libraries and found a ton of breaking changes. I put Pingus on the shelf until I had more time to look at the breakage and how to solve it. The AndEngine changes are pretty significant and I’m going to need to rethink portions of Pingus in order to get things running correctly again.

Now my personal inertia is kicking in and causing me to put off this rework for a while. To me, this is the biggest difference between work and hobby projects… I don’t have to work on hobby projects if I don’t want to. Thus, Pingus is “on a break” for a while until I find the energy to bring it up to date relative to the underlying game engine.

In the meantime, I decided I wanted to spend a bit of time taking a look at Android’s App Widget support. Until I started digging into the documentation and examples, I had always assumed that a widget was provided a Canvas to draw directly on to the home screen. To me this seemed like it would have been the easiest way for developers to develop widgets.

It turns out that Android AppWidgets don’t work that way at all. AppWidgets are built on top of Remote Views. According to the Android documentation, Remote Views are

A class that describes a view hierarchy that can be displayed in another process. The hierarchy is inflated from a layout resource file, and this class provides some basic operations for modifying the content of the inflated hierarchy.

A Remote View is created in one process and passed into the process that owns the Android home screen. It is actually a Parcelable object, however due to class loading issues, there is only a very small number of Views and Widgets that are allowed to be passed across the process boundary. For anything that involves relatively complex graphical rendering, the only real way to drive the widget’s contents is by specifying a very simple widget layout:

and then sending bitmaps to the image view:

	private void updateWidget(Context context, AppWidgetManager appWidgetManager) {
		Bitmap bitmap = Bitmap.createBitmap(100, 100, Config.ARGB_8888);
		Canvas canvas = new Canvas(bitmap);
		
		this.drawable.draw(canvas);

		RemoteViews views = new RemoteViews(context.getPackageName(), R.layout.main);
		views.setImageViewBitmap(R.id.imageview, bitmap);

		ComponentName componentName = new ComponentName(context, MyAppWidgetProvider.class);
		appWidgetManager.updateAppWidget(componentName, views);
	}

While this seems like a high overhead way to handle updates to the widget contents, I have to assume that the Android developers had a good reason for doing things like this. I can only hope that there are some tricks being done in the Android implementation that lower the cost of this operation. Given that I’ve just managed to get this to work at all, I imagine there are is a lot of room for improvement in my use of this API. However, I found it confusing enough to figure out how to do and thought others might benefit from my pain.

In reading the Android supports-screen documentation, it is clear that it is necessary to set the xlargeScreens attribute to true. However, the xlargeScreens attribute is not supported below API level 9. Trying to shoehorn that attribute into my project that was attempting to support back to API level 5, resulted in the following error.

XLargeScreens Attribute Failure

With a bit of finagling, I was able to get things working. In order to allow the xlargeScreens attribute, it is necessary to specify a target SDK version of at least 9.

XLargeScreens Working

This screenshot shows how the minimum SDK version can be set below version 9 and the target version is set to 9, allowing the xlargeScreens attribute to be specified. In addition, it is necessary to change the Android version level in the project properties.

XLargeScreens Properties

With the project properties set to use API level 9 there does not appear to be any automated way to restrict access to API that was older than version 9. Because of this, I do worry about choosing Android API’s that will not work at the minimum SDK and will fail on-device. My plan at this point is to switch back to building primarily for low end and switch once in a while to try on my Xoom. If I were a bit more serious, I would probably handle this automatically as part of a build script.

I do wish that Google had handled things differently in regard to how this works.

Once it was clear that the correct tiles were being found and that the image alteration was working, the next step was to calculate the correct alterations to match the digger’s location as shown as red in this video.

Finally, terrain destruction was completed by clearing those same image pixels to transparent resulting in the following.

Clearing to Transparent

Clearing the image pixels to transparent turned out to be a bit trickier than I had guessed it would be. The default paint “transfer mode” is such that painting with a transparent color results in no changes to the image. In order to erase the image to transparency, the transfer mode needs to be changed like the following:

		// Set up a paint that can be used to clear pixels from a ground tile
		Paint paint = new Paint();
		paint.setColor(Color.TRANSPARENT);
		paint.setXfermode(new PorterDuffXfermode(PorterDuff.Mode.CLEAR));
		paint.setStrokeWidth(1);

With the paint set to CLEAR mode, the Android graphics functions can then be used to alter the image pixels.

New Things Uncovered

I recently picked up a Motorola Xoom that I have also thrown AndPingus on to. It showed me that there are a couple of pretty interesting issues with the current implementation:

• Proper Speed Scaling
  The digger handler doesn’t properly account for clock speed and digging happens way too fast on something as fast as the Xoom.
• Extra Large Screens
  Recent Android versions introduced extra large screen support. Unfortunately, AndPingus isn’t correctly utilizing the screen size yet. I’m still trying to understand how to properly handle older devices at the same time as the extra large screen size.

Planned Source Release

I’ve decided that I’m going to go ahead and release a couple of utility pieces of the AndPingus source code as open source for others to take advantage of. My plan is to make available the following pieces:

• QuadTree
  I created a QuadTree implementation for searching the sprites. At the moment, because of the ground tiles, that code is not being used. However, it seems like it may useful to others.
• Drawable Texture Support
  This is the underlying implementation of the destroyable terrain implementation in AndPingus.

As I mentioned before, I’m getting busy with soccer coaching these days, so I can’t offer a specific timeframe for the release. Before I can make that happen, I need to decide on appropriate licensing and hosting options. In addition, I need to do at least a bit of cleanup before unleashing it to others. Stay tuned to this blog for more information when it becomes available.

When I hit the wall with Android Pingus I decided to tackle a Rockbox database generator, based on the documentation in the Rockbox wiki. Using that documentation along with looking at the Rockbox source code and lots of binary comparisons, I managed to get a Java-based tool built for generating a Rockbox database on the PC that can be loaded onto my Fuze. I’ve released the first release of the Rockbox Tagcache Database Generator. This not necessarily a tool for the feint of heart, as it is a command-line tool driven by a configuration file. With that said, I do think it is pretty easy to use for its purpose and I’m happily using the results from the tool every day when I go to the gym.

As with many of my projects, this tool comes with zero warranty or support. “It works for me” is the best I can say for this tool at this point. The source is available on the page as well for those that may want to tinker or offer patches. At the moment, I have no need or interest in adding new features to this tool, since it is getting the job done for me. With that said, patches to the source would be something I would consider creating a new version to track.

I added support to separate the sprite images when a sprite needed to be altered, but it took me a while to realize I was forgetting to set the correct position for the newly created sprite. This resulted in this confusing result.

Once I realized that the issue was due to incorrect image/sprite generation, I had a much better result.

It became clear very quickly that my current approach for ground sprites was not going to work very well. Using the same images scaled and rotated in various ways makes it very difficult to find the correct sprite and, as you can see from the red X’s, it also means that many sprite images may need to be altered in the course of digging out a particular chunk of terrain.

Ground Tiles

To improve this such that the sprites would be more aligned and easier to deal with, I’m switching to using pre-generated ground tiles. The tooling that currently generates the collision map has been extended to generate a set of square ground tiles. Starting with an image that contains all of the ground sprites:

Full Ground Image

This image can be cropped down to include only the non-transparent area:

Cropped Ground Image

Finally, it is broken down into individual tiles:

Ground Tiles

Each non-transparent tile is stored individually. A new ground tile map object tracks the images and transparent tiles. At the moment, the tiles are being generated as 128×128 pixel images, which plays well with the OpenGL requirement that textures must be sized as a power of 2. Dependent on the maximum texture size, multiple ground tiles may be laid out within the texture with a minimum wasted space. The trick will be to pick an appropriate size to balance the various costs involved in loading and manipulating the sprite textures when destruction occurs.

While I had hoped to actually show this work via video in this post, I’ve run up against a bit of a roadblock. While fixing one problem, I’ve introduced another issue that I can’t seem to resolve. At this point it is better for me to walk away from this project for a few days and come back with a fresh set of eyes. With any hope, my next entry will show a final working destroyable terrain implementation.

In Early Digger Support I covered the initial digger support. At that point I had managed to update the in-memory collision map, but updating the actual textures driving AndEngine was proving to be a bit more difficult. I’m still not there, but I think I’m moving in a positive direction. The following video shows the current state of things. The textures are being updated with a full red fill to make it clear that they have been hit.

So, why is everything turning red? Well, that turns out to be the next item that will need to be dealt with… shared textures. To save memory, many of the sprites share common textures and texture regions. Thus, in the current implementation, changing the underlying texture information affects all sprites that share that information. This is something I knew would have to be dealt with eventually, so it appears that eventually is now.

Quad Trees

When I initially started playing with altering the texture data, I was worried about performance. My first attempt to locate the sprites to be altered used the standard AndEngine functionality to query collisions using the “collidesWith” method for shapes. This proved to be really expensive for gross-level collision detection. My performance tests using the built in Android tools for capturing trace data showed that much of the cost of the terrain destruction was accountable to simply finding the sprite to be altered.

I had heard previously about the use of Octrees in 3D to help do quick searches on the boundaries of objects. In the 2D world, Quadtrees are used instead. I was surprised not to find an actual Quadtree implementation on the web, but was able to piece together a nice generic implementation based on lots of research. With the Quadtree, I was able to get closer to reasonable performance, as you can see in the video capture. My hope is that using a Quadtree and doing the necessary cloning to split sprite textures will lead to a reasonably performant destroyable terrain implementation, but that is still yet to be seen.

Java Generics Aside

My Quadtree implementation initially was built to accept a single object type. It seemed more useful to use Java Generics to make the Quadtree more generally useful. I was hung up by one thing though. I wanted to be able to allow the Quadtree to accept objects with a certain interface declaration. Basically, I wanted this:

public class Quadtree<T implements IBoundedObject> {

Where IBoundedObject is simply defined as:

public interface IBoundedObject {
	Rect getBounds();
}

However, the implements extension is not supported by the generics syntax. This had me confused for a while until I realized that it is possible to do what I wanted to do, but needed to specify extends:

public class Quadtree<T extends IBoundedObject> {

I’m sure there is some perfectly good technical reason for doing things this way, but personally I find the lack of consistency confusing and unnecessary.

Next Time

With any luck, I will be able to show a reasonably performant implementation of destroyable terrain by pulling the various pieces together.

The next step was to start implementing some behaviors for the Pingus. The digger behavior seemed a good place to start. In order to implement the digger, it is necessary to actually alter the collision map generated by the tool. In the end, this part was pretty easy to handle. The results are captured in the video capture.

While it was relatively easy to carve out a path through the in-memory collision map, updating the actual graphics is proving to be much more difficult. AndEngine implements 2D graphics using 3D/OpenGL. This implies that in order to update the graphics, the underlying texture images need to be updated. I’m in the process of building AndEngine support for altering the underlying texture images. At the moment, this appears to be slow and may need to be abandoned. Just like while I worked on the collision map, the lack of guarantee for clipping and Z buffer on Android devices further complicate the situation.

While there are times that I wonder if using AndEngine for this project is makes it more difficult, I’m not quite ready to give it up. More to come…

As you can see from this video, things are still a bit twitchy, but at least Pingus is able to step up and down. To get to this point, I considered a couple of options for improving the collision detection in the system.

• Use the OpenGL stencil buffer
  While this might be an interesting approach, the stencil buffer is not guaranteed to be available on all devices.
• glReadPixels at collision point
  Using glReadPixels “around” the point of a potential collision might be possible, but appeared to be a fairly expensive operation. In addition, it would be difficult to determine whether a pixel was “ground or “solid”.
• glReadPixels to build a full collision map during startup
  This approach would be an improvement over continually using glReadPixels, by caching the results, but suffers from many of the same problems. In addition, the cached image would be large if 4-byte pixels were used.

Pre-generated Collision Map

In the end, I decided that the best approach was to use an external tool to generate a collision map. Unlike many other games, the Pingus world is fairly static, allowing the pre-generation of the map. It is clear that some future aspects of the gameplay will require more dynamic collision detection, but pre-generating this much of the collision map offered a lot of positives:

• Allowed the hard work of calculating the collision map to be moved outside of the constrained mobile environment.
• Allowed the collision map output and associated object wrapper to be tested outside of the constrained mobile environment.
• Allowed the collision map data to be heavily processed to provide the smallest usable map.

Initial Map Image

The first step in the generation of the collision map is to create an image representing the world objects. This initial image is generated using the Java image API’s in the RGB colorspace using the full color sprite images. Between the bit-depth and the excess transparent space in the image, this image is much larger than needed for the collision map. The following image (scaled down), demonstrates the wasted space.

Indexed Image

In an attempt to reduce the size of the individual pixels, the image was converted to a indexed color model. However, the Java image API’s will always attempt to match the closest color, yielding a collision map that looks like the following. Just not quite what we need.

Indexed Image Corrected

Instead of drawing the sprite images directly into the indexed collision map, it is necessary to first convert the sprite images, marking opaque versus transparent images before drawing the collision map. In the following image, the colors have been mapped to mean:

• cyan – Transparent
• blue – Liquid
• green – Ground
• red – Solid (not shown)

The original PNG that this scaled version originated from is 1400×700 pixels and is 3.5K on disk (with compression, etc). Uncompressed, it is a fairly large image to deal with in memory.

It turns out that dealing with alpha values in the Java image library is somewhat tricky. The way alpha is dealt with depends on the underlying color model that is being used. To avoid having to always check during the conversion of the RGB sprite images into the opaque/transparent image, the following class helped.

	class ColorMapTransparencyHelper {
		private ColorModel colorModel;
		private boolean hasTranparentPixel;
		private int transparentPixelRGB;
		
		ColorMapTransparencyHelper(ColorModel colorModel) {
			this.colorModel = colorModel;
			
			if (colorModel instanceof IndexColorModel) {
				IndexColorModel indexColorModel = (IndexColorModel) colorModel;
				
				int transparentPixel = indexColorModel.getTransparentPixel();
				if (transparentPixel != -1) {
					hasTranparentPixel = true;
					transparentPixelRGB = indexColorModel.getRGB(transparentPixel);
				}
			}
		}
		
		boolean hasAlpha(int rgb) {
			return hasTranparentPixel ? 
				(rgb == transparentPixelRGB) : 
				(colorModel.getAlpha(rgb) != 0);
		}
	}

Crop and Corrected Indexed Image

The final step was to eliminate as much transparency as possible. The following cropped image is the final image result. The PNG image in this case is 1400×440 pixels and compressed to 3.1K.

Moving Beyond the Image

Originally, I had thought I would use a packaged PNG image as the basis for the collision map on the device. While this might have worked out, the biggest problem was that the Android graphics API does not make it easy to get the index of the pixel rather than the RGB value. The multiple conversions required to deal with the image as a collision map ended up being more heavyweight than it seemed worthwhile. Thus, the final step the tool takes is to convert the PNG image into an array of bytes representing the states of the pixels. These bytes are written to the package and read by the device as the collision map.

The model class that wraps this data is aware of the transparent regions that are not part of the collision map values and those are automatically taken care of by the model class. This yields a very simple API for callers:

public class CollisionMap {
	public static byte PIXEL_TRANSPARENT = 0;
	public static byte PIXEL_SOLID = 1;
	public static byte PIXEL_GROUND = 2;
	public static byte PIXEL_WATER = 3;

	/**
	 * Get the collision value at the specified location.
	 * 
	 * @param x
	 * @param y
	 * @return
	 */
	public byte getCollisionValue(int x, int y);

	/**
	 * Get an array of bytes representing the map values for the specified
	 * column.
	 * 
	 * @param x_start
	 * @param y
	 * @param width
	 * @return
	 */
	public byte[] getHorizontalCollisionEdge(int x_start, int y, int width);

	/**
	 * Get an array of bytes representing the map values for the specified row.
	 * 
	 * @param x
	 * @param y_start
	 * @param height
	 * @return
	 */
	public byte[] getVerticalCollisionEdge(int x, int y_start, int height);

	/**
	 * Set the specified collision map value.
	 * 
	 * @param x
	 * @param y
	 * @param value
	 */
	public void setCollisionValue(int x, int y, byte value);
}

With the collision map in place, it is then possible to query for information about the world around the Pingus. This information will be further useful in implementing things like the visual world map and determining whether a Pingus can dig at a particular location.

To be continued…