Thursday, March 25, 2010
An Exercise: Porting a Java Applet to Android
Since the initial implementation of the game was an assignment to introduce the concept of double-buffering and simple animation, not much attention was paid to organizing the game logic in a manner that made it easy to add new game modes and rules. To facilitate this, the code was completely reorganized into a few discrete components. In the newly refactored game, the overall architecture is still pretty simple. It consists of a model class that implements all the game rules, score keeping, and the current state of the game, a custom data-structure to maintain the state of individual "balls", an animation thread that determines if and when to draw the objects and a view class that services as the bridge between the Android system (and things like touch events, menu key presses, etc) and the game. In the sections that follow, each of the components will be outlined with special emphasis on anything that was done differently due to capabilities/limitations of the Android platform.
Model & Data Structures:
The model class was responsible for maintaining the current state of the game. This state includes the score, the current level, the amount of time remaining, the list of all the Ball objects which, in turn, contain their position, that will be displayed and the current game mode (running, paused, game-over, etc). For simplicity of maintaining game state upon activity pause, all members of the model class must be serializable since they will be serialized into and out of a Bundle object when the game's Activity is suspended or resumed.
In addition to holding the state, the model class needed to contain the game logic. This consists of two main functions: determining if a particular set of coordinates are within the "target" ball and determining if two balls have collided. In the original implementation, this was done via an inelegant, brute-force manner that was expensive in terms of both memory and CPU cycles. Since the Android platform is more resource-constrained than your average desktop, reducing the processing required for each iteration through the program's main loop was necessary.
Collision Detection:
In the old version of the game, a two-dimensional array of bits the same size as the screen was allocated and the bits were set to either 0 or 1 based on whether or not some ball occupied that pixel. Every time the ball moved, the bits at its origin location were cleared and the bits at the destination were checked. If they were already set, a collision occurred and the ball changed direction and speed (i.e. it bounced) but if the bits were clear, then the space was empty so the ball's position was updated and the bits were set.
To reduce the need to iterate over every pixel on the screen, the new implementation segments the playing surface into a grid where each cell is approximately 100x100 pixels. An ArrayList is allocated for each cell in the grid and balls are to the list that corresponds to the cell in which their center lies. Since balls are always smaller than the cells, a ball in cell i,j can only collide with a ball that is in the 9-cell "superblock" surrounding it (cell i,j and the up-to 8 cells that surround it). To check for collisions, the list of all balls in the superblock is retrieved and the Euclidian distance is calculated between the ball being checked and every other ball in the list. If the distance measure is less than the sum of the balls radii, then the balls are overlapping and thus have collided.
Animation:
The actual logic for updating the state of all the model components (i.e. moving all the balls) remained fairly unchanged from the original implementation. What was added, however, was logic to attempt to keep the frame rate constant regardless of the CPU clock speed on the target device (something that, in retrospect, should have been in the original implementation too). To keep the animation looking smooth, a frame rate of 25 fps was desired. This equates to 40 milliseconds per frame. The code in the animation loop tracks how long it takes to do the state update and the drawing and if that time was less than 40 ms, it will sleep for the remaining time. This approach is about as simple a mechanism as can be employed and, obviously, it is totally ineffectual if the actual time needed to render the frame exceeds 40 milliseconds. Luckily, for this game, that time is sufficient on all device configurations tested.
Communication between the animation thread and the UI thread was another item that needed to be handled in an Android-specific manner. Some events in the game were not triggered by user interaction but rather by a condition within the model (the timer expiration, for instance). When the timer expired, a modal dialog box showing the final score was to be displayed. Rather than drawing one on the surface manually, it was much easier to use the built in DialogBuilder to pop-up an AlertDialog. If this was done directly in the model class as part of the updateState method (the method called by the animation loop to update the ball positions, timer and other state information) it would throw an exception since this was not running on the UI thread. Instead, a Handler had to be used to pass a message from the animation thread back up to the UI thread. The message could, in turn, contain a custom GameEvent class that allowed the UI thread to react appropriately.
View:
To adapt the view classes, the first thing that had to be done to port the game was to re-plumb all the drawing logic. Since the original implementation was created using the Java AWT and drawn directly to the ContentPanel of an Applet using the methods of java.awt.Graphics all the code that actually wrote the pixels to the screen needed to be revisited.
Android provides a Canvas upon which arbitrary shapes and text can be drawn. If you want to add the canvas to a view that may or may not contain other views, a SurfaceView is a good choice since it provides a drawing surface embedded in the normal view hierarchy. As the developer, you can control the contents and size of the surface but the system takes care of positioning it at the right place on the screen (based on whatever else is in your view hierarchy).
Drawing on an Android Canvas was not that different from drawing on a JPanel. The difference, however, was in the view life cycle. Just like any other Android application, the system can suspend your Activity any time the user does something that causes app to lose focus (like taking a call, for instance). At that point, the surface on which you're drawing may be destroyed (but not always).
In response to the Activity pause event, the game pauses the animation (by setting a volatile flag on model class) which tells the animation routine to stop updating the position of the balls and to stop decrementing the timer. At this point, the animation thread runs to completion (to be a good citizen and avoid busy-waiting in the background). When the user returns to the game, the game animation can be resumed. What we cannot do, however, is resume the thread (since you cannot call Thread.start() on the same thread more than once). Instead, the handler must create a new thread and seed it with the information from the "old" game model (instead of creating a new model instance) and start the thread.
Understanding the life cycle of the view classes is important. It is worth pointing out that it is not handled correctly in the Lunar Lander sample application included on the Android development site. In that example, the surfaceCreated method on the view class starts the thread that was initialized in the constructor. The problem is that surfaceCreated can be called by the system whenever the surface regains the foreground (even though the View's constructor may not have been called since it is the same view instance). Since the thread is a member variable and may have already been started, calling start could (and often does) result in an exception. This isn't meant to be a critique of the example code (I've said it before and I'll say it again: the wealth of examples and documentation is one of the strengths of the Android platform) but it should be noted that not everything in the example code is 100% correct all the time and if something "feels" wrong, it very well may be.
Impressions and Future Work:
Porting this application was a worthwhile exercise. Since the "game" portion was already done, it allowed me to focus on the nuances of the platform itself rather than the mechanics of the game play. All said and done, it took approximately 15 hours from start to finish (it could have been a lot shorted had I kept the brute-force collision detection instead of refactoring that). It was time well-spent in that it helped illustrate some of the finer points of handling the animation (frame rate limiting, surface life cycle, percolation of events back up to the UI thread).
Despite the fact that game itself is exceedingly simple, I plan on adding to it in the coming weeks. I am contemplating using the game as a proof-of-concept for a server-side component that can handle reporting high scores, issuing user challenges and handling teams/clans. I plan on exposing the server platform via a REST API and building a client library that could be included in any Java application for easy integration. I'd be interested in hearing if any of the (few) people who read this think there is any merit in a system like that and, if so, what other features it should support. I hope to have more to say on this topic soon.
Friday, May 1, 2009
Proper System Properties
In sandboxed programming platforms like .Net and Java, the developer is insulated from the details of the underlying machine upon which the code is running. At times, however, it is often useful to have more knowledge about the environment. One way to provide such information without introducing any machine-dependent code into the sandbox is via system properties. They can be implemented in a number of ways, but the most common is a set of name/value pairs that can be accessed via a core class in the language runtime. In java, one can get a list of all the system properties using System.getProperties().
The properties are not limited to those set by the language virtual machine; they can be extended to include any property the developer wants to set. Most languages provide a way to do this at virtual machine initialization or programmatically within the application code. Having system properties is a powerful tool and can enable code to handle certain conditions based on the capabilities of the underlying machine in an elegant way. With power, though, comes responsibility.
Some developers have been abusing this construct and using it as if were a container for global variables: instead of passing parameters into methods, a method will simply look up a value from the system properties. This is especially egregious when the property is not universally true from the system perspective. One such example is specifying a HTTP proxy. In Java, the default HttpConneciton class uses system properties to specify a proxy. In most cases, this is fine, but in some enterprise environments, the proxy server one must use depends on the address being accessed. If your program needs to access two addresses that use different proxies, then changing proxies involves updating the values in the system properties. Again, this is usually not a big problem, but if you have a multi-threaded program, this could cause a race condition unless one enforces the atomicity of the property update with the HTTP request. Depending on the application requirements, this may or may not be an acceptable answer.
While there is not much one can do about the proxy issue (outside of using some other library to make HTTP requests), developers can prevent imposing similar limitations on their own code. Since it is impossible to anticipate every way in which code may be used and it is equally impossible to know every possible system configuration, the use of system properties that do not actually describe the system upon which the code is executing should be avoided.
Friday, April 24, 2009
Threads & Exceptions
In this age of multi-core processors, being able to write efficient and correct multi-threaded programs is becoming increasingly important. Unfortunately, however, writing such programs is not a trivial task. Deadlocks, race conditions, and thread starvation are among the myriad pitfalls that could break one's programs. Complicating matters further are “legacy” (for lack of a better term) third-party libraries that may or may not be thread-safe.Errors due to threading issues are among the worst class of bugs: the elusive Heisenbug. The use of a good profiler tool is essential in tracking down and eradicating bugs like this.
Just as important as knowing how to avoid writing code subject to deadlocks and race conditions is knowing how your programming environment responds to bugs that occur in child threads. In the Java programming language, for example, one's program could find itself in an unexpected state due to an uncaught exception in a child thread. When one is running a single-threaded program and an uncaught exception occurs the system will exit and print the exception's stack trace to standard error. Not graceful, but also not a very subtle error condition. When an uncaught exception occurs in a child thread, however, the flow of control is as follows:
- The JVM checks the UncaughtExceptionHandler of the Thread object. This is null by default. If you wish to specify your own handler, you must call the setUncaughtExceptionHandler method on the thread instance (usually before starting its execution). Setting this handler only applies to the thread instance upon which you installed the handler (not descendant threads).
- If the thread does not have an UncaughtExceptionHandler, then the ThreadGroup is checed to see if it has a handler of its own.
- If the thread's ThreadGroup does not provide a handler, then the default handler is invoked. Unless the programmer changes it (by calling the static Thread.setDefaultUncaughtExceptionHandler method) the default handler simply prints the exception's stack trace to standard error.
The Java API documentation contains a very important warning for those programmers who want to provide their own default UncaughtExceptionHandler:
The default uncaught exception handler should not usually defer to the thread's ThreadGroup object, as that could cause infinite recursion.
When developing code that has any potential for reuse in other applications, one has a responsibility to take threading considerations into account. If it is decided that a method or class will not be thread-safe, then it is the developer's responsibility to clearly document this limitation in both the in-code documentation (i.e. JavaDoc) and any other API/Development guides.
Wednesday, March 18, 2009
Oracle RAC Load Balancing
Relational databases play a central role in many software systems. In many enterprises, Oracle is the RDBMS of choice. Among those, many mission-critical systems make use of Oracle's Real Application Cluster (RAC), a load-balanced multi-node database that can handle failures of individual nodes without causing an outage. This article provides a decent summary of RAC.
While RAC has many features and advantages (as well as trade-offs), that isn't why this post is here. It is here because the way in which the Java ODBC driver establishes a connection to the RAC is worth understanding in the event that one suspects a connectivity issue between the client code and the database server.
For a Java developer, using RAC is very similar to any other Oracle database. Usually, the only indication that you're using a RAC is the contents of your connect string. It typically lists a number of database server addresses in an ADDRESS_LIST element. For the purposes of illustrating the discussion, an example may be helpful:
jdbc:oracle:thin:@(DESCRIPTION =(ADDRESS_LIST =(ADDRESS = (PROTOCOL = TCP)(HOST = dbserver1.somedomain.com)(PORT = 12345))(ADDRESS = (PROTOCOL = TCP)(HOST = dbserver2.somedomain.com)(PORT = 12345))(LOAD_BALANCE = yes)) (CONNECT_DATA = (SERVER = DEDICATED) (SERVICE_NAME = dbServiceName.somedomain.com) ) )
There are two types of load balancing offered by the RAC: client-based load balancing and server-based load balancing. The system can be configured to use one, both or neither forms of load balancing.
The LOAD_BALANCE element in the connect string above specifies that the client code should perform its own load balancing. Essentially, this means that the client will randomly choose one of the servers from the ADDRESS_LIST whenever a connection is requested.
If server-based load balancing is enabled, a listener service provides automatic load distribution across all nodes in the RAC. The listener will use the query optimizer to determine which node in the RAC should service the request (based on their current workload, machine profiles and, in newer versions of Oracle, admin-specified rules).
If one were to use the connect string above and server-based load balancing were enabled, the sequence of events that would occur when a call to DriverManager.getConnection(...) is invoked are:
- The driver selects dbserver2.somedomain.com (this choice was made at random by the driver) and issues a connection request.
- The listener on dbserver2.somedomain.com determines that the most under taxed node in the RAC is dbserver3.somedomain.com and returns it to the client. NOTE: this assumes that the RAC has 3 nodes. It is important to note that all the nodes do NOT need to be included in the connect string... the nodes in the ADDRESS_LIST simply indicate which nodes the client will balance its initial "getConnection" requests against
- The client will attempt to establish a connection to dbserver3.somedomain.com.
Monday, February 23, 2009
A Dearth of Debugging
I suppose a reason for this is the perceived difficulty in debugging server-side code from a client machine, but this is more a case of lack of knowledge than an actual technical issue. Most application servers support some facility for remote debugging. Similarly, in Java, at least, the virtual machine itself can be configured to accept connections from remote debugger clients (if, for example, you wanted to configure the JVM to listen for debugger connections on port 8000, you'd include this in the command-line arguments: -Xdebug -Xnoagent -Xrunjdwp:transport=dt_socket,server=y,suspend=n,address=8000). Once started in this way, the debugger can connect to the remote JVM and do everything it could do if it were running on the same machine.... you can set breakpoints, inspect the contents of memory, evaluate statements and see the full stack trace for all the running threads... all of which are quite powerful when looking for an elusive bug.
The heuristic I use for deciding whether to use the debugger or a logger to find the root of an issue is as follows:
If the bug occurs infrequently and it is not clear how to duplicate it, I use a logger to see if I can detect a pattern. If I can, then I'll use the debugger to look deeper into things. Conversely, if it's clear how to duplicate the bug, I'll usually jump right in with the debugger.
Here are some resources for remote debugging:
Sunday, February 22, 2009
Volatility
The semantics of the volatile keyword are similar to those of the synchronized keyword, but they're not equivalent. When one thinks of multi-threaded programs, they have 3 primary properties: visibility - the ability of one thread to see the work of another thread, atomicity - defining sets of indivisible actions, and ordering - enforcing that some operations in one thread happen before others in another. Using synchronized, a developer can enforce all three properties. When one uses volatile, however, one cannot enforce atomicity.
Why would one want to use volatile over synchronized since it seems to be a less powerful construct? Well, for one thing, it incurs slightly less overhead than obtaining locks with synchronized. Additionally, volatile can be used on primitives and null values (you can't directly synchronize on a primitive). One common use case is for a flag value that is updated by one thread but read by another. Declaring it volatile ensures that the other thread is reading the current value and not its own cached copy.
Java is an interesting programming language for many reasons, not the least of which is the way it insulates the developer from so many concerns of the low-level machine. The difference between volatile and synchronized, however, illustrates that, despite this abstraction, developers are obligated to understand the inner workings of the JVM if they are to write correct and efficient code.