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.
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.
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,
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,
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
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.
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
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
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 Zone Javadoc home page can be accessed from here.
The java source code is available online also.
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.
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
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.
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.
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.