Gamer area Developer area

Introduction for developers
Asteroid Zone has been developed with wireless gamers as well as developers in mind. I have tried to present the game design, implementation trade-offs and detailed source code as clearly as possible. I hope this will encourage other developers to write their own MIDlets and contribute to the success of this platform.

Table of contents
Information about the development of Asteroid Zone is divided in four sections.

Development objectives
Asteroid Zone is my first MIDP project. I chose to develop an Asteroids clone for various reasons. Though it is old and simple, the game has aged well and I still find it fun to play. It uses vector graphics instead of raster graphics, something MIDP is not very good at currently (because MIDP images do not currently support  transparency). Vector graphics seemed like a good choice too in order to be able to scale the graphics to accommodate the very diverse screen sizes j2me devices are equipped with. It also appeared well adapted to the cell phone interface, since most phones provide a four-direction "joystick" which I thought would work well to control the ship.

Game design

1. Abstract base class to provide pseudo-floating point coordinates
I tried to keep a clean object-oriented approach (otherwise, why use Java ?) in the game design. Basically, there is one class per object visible on the screen. asteroids.Ship, asteroids.Rocket, asteroids.Asteroid all inherit from asteroid.Mobile, an abstract class which provides the floating point coordinates emulation using rational numbers. The most obvious problem was indeed the lack of floating point number, which is a pre-requisite for the rotation of the ship and the control of the trajectories of the various game mobiles.

The solution was to emulate floating point using rational numbers (fractions), using a large power of 2 (2^6=64) as the denominator of the fractions. All the coordinates and velocities are magnified 64 times. When the actual value is needed, the division by 64 can be computed quickly by shifting the numerator. I also precomputed a table of sines and cosines which I use in the game.
 

2. The asteroids.Game class provides integration with the j2me device
The application class is called asteroids.Game, and inherits from javax.microedition.midlet.MIDlet, as do all MIDlets. It also implements javax.microedition.lcdui.CommandListener, another pattern frequently observed. This lets the application handle the high level application events, such as those sent when the player pushes the start button or wants to exit.

The trickiest part has to do with correctly implementing startApp() and pauseApp(): a MIDlet has to be able to switch between an active and a dormant state. When it enters its dormant state, it should free as many resources as possible. In my case, I decided that all the application threads would exit when pauseApp() was call, and be restared when startApp() was called.
There are two application threads: one to execute the game loop, and one to trigger the transitions between the various game screens using a timer.
 

3. The asteroids.Field class controls the game loop

The main class is asteroids.Field. It inherits from javax.microedition. lcdui.Canvas, in order to be able to draw on the screen directly and to catch low level MIDlet events (key pressed). The game main loop is implemented at this level, which is why the class implements java.lang.Runnable.
 

4. The game progres is modeled by a state machine
I wanted the game to switch among various presentation screens (such as main title, best scores or control descriptions), just like a real arcade game. So I decided to cleanly model the various game states as a finite automaton, and to create an asteroids.Slideshow class which has the following responsibilities: it triggers the transition from one state of the automaton to the other, causing the various game screens to follow one another ; it also contains all the code required to draw the various game screens.
 

5. The score database
I added this functionality because it provided a good opportunity to play with both the javax.microedition.lcdui forms package, as well as with the javax.microedition.rms database package. I tried to minimize database usage as much as possible: the database is used once to initialize the scores, and completely overwritten when a high score is achieved. This enables not having an open database connection at all times. Another consequence of having implemented this functionality is that there are now two possible javax.microedition.lcdui.Displayable in the game: one is asteroids.Field, the other one a javax.microedition.lcdui.Form used to enter the name of the high performers. This has to be remembered at the game level in order to be able to correctly implement startApp and pauseApp, hence the notion of a currentDisplayable at the asteroid.Game level.

Source code
Asteroid Zone Javadoc home page can be accessed from here.
The java source code is available online also.
File
Asteroid.java
Explosion.java
Field.java
Game.java
Geometry.java
Mobile.java
Pool.java
Rocket.java
Scores.java
Ship.java
Slideshow.java

Optimization

Version 1.0

For version 1.0, I broke the number one rule of optimization: "If it is not broken, do not fix it". Having read several articles describing how resource limited a cell phone environment can be, I decided before releasing the game to re-read the source code and to try to make it leaner and more efficient. Here are the areas where I tried to improve things.

1. Collision detection
This one is the obvious bottleneck, as the time complexity of the algorithm used is O(NM), where N is the number of asteroids and M the number of rockets shot. I considered various other alternatives (BSP trees, quadtrees, etc...) and finally gave up, thinking they were going to be more trouble (temporary objects) than they would be worth. Instead, I tried to make each collision detection test as efficient as possible by mapping the bounding box of each object to an integer. ANDing of these integers provides a way to quickly find out if two bounding boxes overlap. The actual collision detection algorithm when two bounding box overlap is still very crude though and can certainly be improved.

2. Drawing
To improve drawing, I added a back buffer which I only use for machines which do not support double buffering (this can easily be tested with javax.microedition.lcdui.Canvas.isDoubleBuffered()). It  makes screen refresh cleaner on PalmOS devices. I do not think there are many more possible improvements in this area of the game

3. Minimal use of garbage collection
Initially, the game used java.util.Vector based collections, and created new objects when it seemed appropriate (for instance, a new asteroids.Rocket every time the player shoots, or two new asteroids.Asteroids when an asteroids.Asteroid is hit by a asteroids.Rocket and splits). Many j2me articles describe java.lang.OutOfMemoryError as the number one cause of failure of MIDP applications and make of convincing case of preserving heap space and limiting the use of the garbage collector. So I decided to use object pools and pre-allocate all my objects at the beginning of the game. I replaced all my  java.util.Vectors with asteroids.Pools, which provide efficient addition, removal and traversal. The performance improvement is not noticeable with java.System.currentTimeMillis() but I feel more confident that the application will not crash in the middle of a game because of some memory problem.

4. Use of char arrays instead of Strings
The game uses a lot of character strings, mainly every time the score changes. In order to preserve heap space, and avoid the allocation of many useless temporary String instances, I decided to add my own conversion method to transform ints to char[]. char[] is very easy to use since javax.microedition.lcdui.Graphics provides drawing methods which accept them without transformation.

5. Use of short data types
I re-read the code and changed to byte many of the ints I normally use to code. I frankly do not know all the consequences of this choice, and the performance measures I was able to make using java.System.currentTimeMillis() are inconclusive one way or the other. On the one hand, I think one can be fairly sure it makes the memory footprint of the application a bit smaller. On the other hand, having to upcast to bytes to ints to pass them to various MIDP APIs might have a performance penalty.

6. Use of final modifiers
I also declared final most of the methods, as James Gosling says in the Java Programming Language this can help the JVM execute the code more efficiently.

7. Use of an obfuscator
This is perhaps the single most useful optimization I have done and I warmly recommend it. The obfuscator renames the classes and variables to one char names, and  removes various usued fields in the class encoding. I decided to use a free obfuscator developed in Java, called Jode. Before obfuscation, the MIDlet was 23K in size. After obfuscation, it shrinked to barely above 15K, a 35% improvement.

Version 1.1

For version 1.1, I had received some feedback from users and code reviewers, so I had a better idea at what to look for.

8. Reduce method calls as much as possible
I have tried to reduce method calls in the critical sections of the game, such as often called loops. I tried not to sacrifice code readability though. One of the major area of improvements is in collection traversals. I use a simple for loop instead of an iterator pattern. Wherever possible, I added methods which act on a whole collection instead of individual instances. This resulted in a roughly 30% performance gain. Further gains a certainly possible, though a good profiling tool would be necessary to achieve them.

Version 1.2

For version 1.2, I tried again to boost performance to a level adequate for actual java phones.

9. Change the collision detection algorithm
In version 1.0, I had used a purely geometric approach to collision detection, using a segment intersection algorithm and bounding boxes. It gave very good precision when detecting collisions but proved too slow. In version 1.2, I decided to drop this approach and start afresh with another algorithm. I now scan convert the asteroid polygons in memory: the resulting images are useless for drawing, since they are not transparent, but they give an instantaneous point-in-polygon answer. It works well enough, though some precision is lost there, especially in the ship / asteroid collision detection. Indeed, since I do the test for just a few of the ship pixels, the ship may brush with an asteroid without actually exploding.

10. Event handling
In version 1.0, I handled the events directly in the keyPressed() methods. I have had users reporting slow event handling (a key event being processed up to 1-2 seconds after having been pressed). In an effort to improve this, I now return immediately from keyPressed(), where I just store the key code. The actual event processing is done in the game main loop. This is closer to the MIDP specification, which advises to spend as little time as possible in keyPressed(), and it enables a kind of "event compacting", since repeated calls to keyPressed() do not generate several events.