Why Games on Android

• Traditional PC and console game markets have been come so high-risk that only a few companies an even compete.
• Smaller games on non-traditional platforms are steadily gaining popularity with both traditional gamers and folks new to the medium.
• Android provides an avenue for innovative games across a wide, internet-savvy audience.

Goal

My goal is three-fold:

• To produce a fun fame for Android.
• To produce a reusable, open source game engine to allow others to make fun games for Android.
• To stress test our platform with regards to games; only publically-available code and tools are to be used.

I went for an orthodox 2D side-scroller:

• Parallax layers, tile-based worlds, animated sprites, etc.
• Pushes all the right hardware buttons: input systems, OpenGL ES, sound, etc.
• Proper game is feasible with one 20% engineer (thatâs me) for six months and 1 full time artist for four months.
• Tools are pretty easy to write.
• Popular and recently under-served genre.

Writing real-time games is an exercise in finding the perfect balance between flexibility and performance.

My (non-language-specific) approach is:

• Start with the simplest possible implementation, but design for future rework.
• Choose flexibility over speed every day of the week... until the gameplay is damaged.
• Profile early and constantly.

Game Engine Architecture

Lots of approaches, but the basic problems are similar.

game graph

My approach is a "game graph" that can be traversed every frame, taking time and motion events as input and resulting in a list of things to draw to the screen.

• The root of the graph is the main loop.
• Children of the main loop get called once per frame.
• Children further down the tree might get called once per frame,depending on their parent.
• Game objects are children of a game manager node, which only visits children within a certain activity bubble around the camera.
• Game objects themselves are sub-graphs of game components,each implementing a single characteristic or feature of the object.

来自参考资料1

Important point:

• Time is passed to each node in the graph so that framerate independent motion is possible.
• This system collects things to draw in a draw list each frame, but it doesn't actually draw anything to the screen.

Thread based:Three threads

来自参考资料1

• The main thread spawned by the Android activity.
  1. Responsible for bootstrapping the game and receiving input events.
  2. Mostly dormant.
• The game thread.
  1. Handles all non-rendering parts of the game: physics, AI, collision detection,animation, etc.
  2. Owns the game graph.
• The rendering thread.
  1. Controlled by a SurfaceHolder.
  2. Just runs through its draw list and fires off commands to OpenGL every frame—knows nothing about the game content.

Writing Java Code that is fast

Memory Management

• Never allocate memory, or release it.The GC will stop your game for 100~300ms. That's death for most real-time games.
• Revised: Allocate as much as possible up front, don't release things until you have natural pause time. Invoke the GC manually when you know it to be safe.
• Use DDMS to track allocations.

Don't Call Functions

• Ok, that's extreme. But function calls are not cheap and you can't rely on inlining.
• Use static functions whenever possible.
• Don't call functions through an interface. 30% slower than regular virtual functions!
• Be wary of JNI functions.In particular: lots of gl.glXX() functions.

Other Tips

• Use local variables, especially in inner loops.
• Use the final keyword on fields whenever you possibly can.
• Some hardware (like the G1) has no FPU, so avoid float math.
• Always use Log.d() or similar rather than System.out.print(). Printing takes time!
• Use Traceview.

Drawing stuff on the screen efficiently.

Android Drawing Methods

• Canvas
  1. CPU-based 2D drawing. Used for most of the Android UI.
  2. Fast for a small number of blits. (~ 10 sprites < 16 ms in my tests)
  3. Very straightforward and easy to use.
• OpenGL ES
  1. 2D and 3D drawing.
  2. Hardware accelerated on some platforms (like the G1).
  3. Scales to much more complex scenes than Canvas.
  4. Various 2D drawing methods:
     • Quads with orthographic projection
     • VBO³ quads (on supported platforms)
     • draw_texture extension (on supported platforms)
  5. Only OpenGL ES 1.0 is guaranteed.

Which Method is Best

来自参考资料1

• Clearly, OpenGL ES + the draw_texture extension is fastest for 2D drawing on the G1.
  • But that extension isn't guaranteed to be supported on all platforms. You MUST check glGetString(GL10.GL_EXTENSIONS) before using it.
• However, Canvas isn't bad if...
  • You have very few things to draw every frame, or
  • You don't have to draw every frame (puzzle games, etc).
• SpriteMethodTest provides a framework for swapping between drawing methods (and timing them) based on my game code.
  • http://code.google.com/p/apps-for-android/

Case Study: Drawing Tiled Backgrounds

Introduction

• Replica Island uses three background layers: one large static image, one mid ground tile-map, and the foreground tile map.
• The tile map layers are regular grids of 32x32 tiles. That means 150 tiles to draw per layer on any given frame (worst case).
• More layers would be nice, but drawing the background is the single most expensive operation in the Replica Island code.
  • Actually, the single static image is quick. It's just one 512x512 texture.
  • It's the tile maps that eat frame time, either on the CPU or the GPU, depending on the drawing method.

Layered Parallax Backgrounds

来自参考资料1

Layered Backgrounds Composited

来自参考资料1

First idea

use a single atlas texture as the tile map, use draw_texture to draw, and adjust cropping of the texture to select individual tiles.

• Only one glBindTexture() call needed, which is good.
• Otherwise, this was a terrible idea. glTexParameteriv() is expensive.
• Remember kids, state change is costly on fixed-function hardware!

来自参考资料1

Second idea:

draw the tiles individually with draw_texture extension using a bunch of really small textures.

• This actually works pretty well once some easy optimizations are made (RLE the tile map, etc).
• But it's still a lot of calls to OpenGL. 400 calls to glDrawTexfOES() in the worst case, plus lots of superfluous glBindTexture calls.
• Average case is good: less than 16 ms for the hardware to draw everything. But the actual submission of tiles to OpenGL is variable depending on the sparseness of the layer: 2 - 10 ms.
• Worst case is bad: 9 - 13 ms to make GL calls and 19 - 23 ms to draw. Way unacceptable.

Third Idea

Make "meta tiles" out of vertex arrays, UV⁴ them to the atlas texture, and project them using orthographic projection.

• Initial results were in line with the "basic vert quads" test in SpriteMethodTest: terrible.
• Switching to VBOs sped things up a lot.
• Lots of advantages to this approach: only one glBindTexture() call, very few total calls to other GL commands (only four meta tiles to draw per layer per frame).
• Worst case situation (two layers with no empty tiles) is much faster than the draw_texture approach. CPU spends only 3 - 5 ms submitting to GL and drawing takes less than 16 ms.
• Average case is the same! This makes it slightly slower than draw_texture in the average case (most maps are very sparse).

Last ditch Idea

pre-render the tile map and cut it up into meta tile textures, which can be drawn with VBO quads or draw_texture.

• I haven't actually implemented this yet.
• Level size will be restricted by total amount of VRAM if I use this method (unless I dynamically load textures).
• High main memory cost too.
• But, given all available information, drawing this way should be blazing fast.
• I'm close enough to 60hz now that this probably won't be necessary.

See Also

1. Writing Real-Time Games for Android
2. Texture Atlas
3. OpenGL Vertex Buffer Object (VBO)[Recommend]
4. UV mapping

About author

Chris Pruett works from Google's Japan office to support local Android application development. Prior to joining the Android team he worked as an engineer on Lively, Google's 3D online world. Before joining Google in 2007, Chris worked for several years at a subsidiary of Activision, Inc developing video games. In his free time Chris enjoys dissecting horror games. Read about his research at http://www.dreamdawn.com/sh .