» CS 491 Lecture 22 – Bluecheckers

CS 491 Lecture 22 – Bluecheckers

December 6, 2011 by Chris Johnson. Filed under cs491 mobile, fall 2011, lectures.

Agenda

case study of making a NDK/OpenGL powered game

Bluecheckers

A couple of weeks ago I got the latest issue of Make magazine in the mail. On page 56, Charles Platt describes a 2-player Chinese Checkers game. I thought, “That’d be fun on a mobile device.” We don’t have time to code it all from scratch, but we should take a few moments to be real computer scientists and think about the algorithms and data structures we’d use to make such a game. In particular, discuss with a partner the following:

What are the rules of the game?
What data structures would you use to represent the game state?
How do user’s move their marbles?
Based on your data structures, what algorithms would you use to determine what marble was clicked on?
How do you detect a winner?
How do you position the marbles?

Designing the game

For our last big hurrah, We don’t have time to code everything from scratch, but let’s address a few interesting issues.

Aspect ratio

No one mentioned it last time, but our sphere wasn’t really a sphere. It was an ellipsoid. Why?

By default, OpenGL maps incoming geometry in [-1, -1], [1, 1] to fill the viewport of the rendering surface. If the viewport is not square, then the geometry will be stretched. To specify a different space to map to the viewport, we can use a non-square projection transformation. If the viewport has an aspect ratio of width:height, we want the projection matrix to carve out a space with the same aspect ratio. Suppose the board spans [0, 11] on the x-axis. What stretch of y should we show?

Issues of aspect ratio are especially important on mobile devices because very few of them are square.

The grid

I chose to represent the board using a 2-D array. Each element holds one of four enum values: MARBLE_A, MARBLE_B, MARBLE_VACANT, or MARBLE_VOID. The last of these is for the invalid grid positions, which are an unfortunate consequence of using a 2-D array to represent the board. The main advantage of this data structure is that there’s a simple arithmetic mapping between screen positions and array indices. So, if the user taps or clicks on the screen, I can quickly (in constant time) see what is at that grid location.

Rendering marbles and anti-marbles

We wrote a sphere vertex array object last lecture. Our board is comprised entirely of spheres (marbles) and hemispheres (holes). It turns out we can draw the hemispheres using the sphere VAO by enable the culling of front faces and inverting the normal.

Animation

On a turn change, I wanted to smoothly rotate the light source to the opposite player. It’s position was rotated from its base by rotate(elapsed * speed, vec(0, 0, -1)). To get the elapsed seconds on my desktop version, I used SDL. SDL_GetTicks() gives me a measure for the number of milliseconds since some event (library load maybe?). Porting to Android required a custom means of getting the time. All my time-dependent code is running in the native rendering loop, so I looked for a solution at the C/C++ level. Since we’re in a Linux environment and libc is available, clock_gettime seemed a likely choice. There are several clocks to choose from, like a realtime clock (subject to changes), a couple of CPU timers, and a monotonic clock which moves steadily forward regardless of time zones. Since mobile devices are mobile, getting a robust timer is important. So, I measure the number of milliseconds with:

struct timespec now;
clock_gettime(CLOCK_MONOTONIC, &now);
return now.tv_sec * 1000 + now.tv_nsec / 1000000;

Communicating a win

The game is over when a player gets all his marbles home, but how do we let the users know who the winner is? We flash a message. Suppose we want to draw on the screen rather than pop up a big ugly dialog. OpenGL has no builtin facility for drawing text. Instead, we can create a FrameLayout whose topmost view is a TextView and whose bottommost view is our OpenGL surface. The TextView can stay blank for most of forever, but when a winner is detected, we can show a message and outlaw further interaction with the marbles.

It made sense to me to let the renderer determine the winner message. That was in C++. The TextView is reached through Java, on the UI thread. This led to a couple of interesting issues. First, how can we turn a C++ string into a Java String?

JNIEXPORT jstring JNICALL Java_org_twodee_bluecheckers_BluecheckersLib_getStatusMessage(JNIEnv *env, jobject obj) {
  return env->NewStringUTF(renderer->GetStatusMessage());
}

The env argument is a pointer to the Java VM environment, which has methods for creating new Strings. After adding this BluecheckersLib.java, we can call this method from Java. Where we should do so leads to an interesting situation. Our UI thread handles the touch events, and after a touch event seems like a likely place to look for a winner. The touch event has to synchronize with the drawing thread to communicate the touch event, and after the touch event is handled, the drawing thread has to synchronize with the UI thread to update the TextView. It’s kind of like a dream within a dream:

@Override
public boolean onTouchEvent(final MotionEvent event) {
  queueEvent(new Runnable() {
    @Override
    public void run() {
      int x = (int) event.getX();
      int y = getHeight() - 1 - (int) event.getY();
      if (event.getAction() == MotionEvent.ACTION_DOWN) {
        BluecheckersLib.touchDownAt(x, y);
      } else if (event.getAction() == MotionEvent.ACTION_UP) {
        BluecheckersLib.touchUpAt(x, y);
        final String message = BluecheckersLib.getStatusMessage();
        activity.runOnUiThread(new Runnable() {
          @Override
          public void run() {
            activity.onTurn(message);
          }
        });
      }
    }
  });
  return true;
}

Sound

Dropping a marble needs to make a noise, right? I used sfxr to try and generate an interesting blip.

Earlier in the semester, we used a MediaPlayer to play audio resources. MediaPlayer.create loaded and decoded the resource to a raw PCM stream to play through the speakers on our device. That loaded and decoding may cause our sounds to be delayed. To combat this, Android provides a SoundPool class that loads, decodes, and holds sound resources in memory for quick playback. We can load several and just trigger them based on their ID. Multiply sounds can play at the same time. To incorporate a SoundPool, we add a few instance variables:

private SoundPool soundPool;
private AudioManager audioManager;
private int releaseSound;

The documentation doesn’t quite say where to allocate this. Our choices are onCreate, onStart, or onResume. The friendliest place is probably onResume. But is it?

soundPool = new SoundPool(1, AudioManager.STREAM_MUSIC, 0);
audioManager = (AudioManager) getSystemService(Context.AUDIO_SERVICE);
releaseSound = soundPool.load(this, R.raw.bluecheckers_blip, 1);

The last argument to load is a priority. If the sounds being played amount to more than the maximum amount specified at construction, the one with the lowest priority will be aborted. In onPause, we have:

soundPool.release();

Playing a sound is accomplished with:

float streamVolume = audioManager.getStreamVolume(AudioManager.STREAM_MUSIC);
streamVolume = streamVolume / audioManager.getStreamMaxVolume(AudioManager.STREAM_MUSIC);
soundPool.play(releaseSound, streamVolume, streamVolume, 1, 0, 1.0f);

We only want to play a sound when a move is made. How do we check for that?

Persisting

This game can get kind of long and is prone to interruption. Persisting our game state is pretty important. There are several things we need to persist: the board, the selected marble, the number of jumps made so far, the player whose turn it is, etc. I’ve made getters for all these things in our JNI code. The translation from bool to jboolean and int to jint is pretty straightforward, but the array is an interesting case. We have to rely on the Java VM environment to make our array from C++ primitive array:

JNIEXPORT jintArray JNICALL Java_org_twodee_bluecheckers_BluecheckersLib_getBoard(JNIEnv *env, jobject obj) {
  int size = CheckmateRenderer::GRID_WIDTH * CheckmateRenderer::GRID_HEIGHT;
  jintArray board = env->NewIntArray(size);
  env->SetIntArrayRegion(board, 0, size, (int *) renderer->GetBoard());
  return board;
}

Now in Java, on a pause, we can persist out to some preferences:

SharedPreferences prefs = PreferenceManager.getDefaultSharedPreferences(this);
Editor editor = prefs.edit();

int[] board = BluecheckersLib.getBoard();
StringBuilder builder = new StringBuilder();
builder.append(board[0]);
for (int i = 1; i < board.length; ++i) {
  builder.append(",");
  builder.append(board[i]);
}

editor.putString("grid", builder.toString());
editor.putInt("turnOf", BluecheckersLib.getTurn());
editor.putInt("pickedX", BluecheckersLib.getPickedX());
editor.putInt("pickedY", BluecheckersLib.getPickedY());
editor.putInt("nJumps", BluecheckersLib.getJumpCount());
editor.putBoolean("didOneShot", BluecheckersLib.didOneShot());

editor.commit();

We serialize the board to a comma-separated String. On the reverse side, in onResume, we thaw any existing game state:

SharedPreferences prefs = PreferenceManager.getDefaultSharedPreferences(this);
String serializedBoard = prefs.getString("grid", null);

if (serializedBoard != null) {
  String[] cells = serializedBoard.split(",");
  final int[] grid = new int[cells.length];
  for (int i = 0; i < grid.length; ++i) {
    grid[i] = Integer.parseInt(cells[i]);
  }

  final int turnOf = prefs.getInt("turnOf", -1);
  final int nJumps = prefs.getInt("nJumps", -1);
  nJumpsPrev = nJumps;
  final int pickedX = prefs.getInt("pickedX", -1);
  final int pickedY = prefs.getInt("pickedY", -1);
  final boolean didOneShot = prefs.getBoolean("didOneShot", false);

  surfaceView.queueEvent(new Runnable() {
    @Override
    public void run() {
      BluecheckersLib.resume(grid, turnOf, pickedX, pickedY, nJumps, didOneShot);
    }
  });
}

A gotcha here is that you can’t call this in onResume, because BluecheckersLib.initializeGL won’t have been called yet to make our renderer! It’s not clear to me how best to handle the situation. I just made a dialog that popped off if there was frozen state.

BluecheckersLib.resume just pushes the game state out to the renderer. I shouldn’t say just, because it gets a 1-D Java array for the serialized board. We’ve got to copy that over to a statically allocated 2-D C++ array. Once again, the Java VM environment helps us:

JNIEXPORT void JNICALL Java_org_twodee_bluecheckers_BluecheckersLib_resume(JNIEnv *env, jobject obj, jintArray grid, jint turn_of, jint picked_x, jint picked_y, jint njumps, jboolean did_one_shot) {
  CheckmateRenderer::marble_t new_grid[CheckmateRenderer::GRID_HEIGHT][CheckmateRenderer::GRID_WIDTH];
  int size = CheckmateRenderer::GRID_WIDTH * CheckmateRenderer::GRID_HEIGHT;
  env->GetIntArrayRegion(grid, 0, size, (int *) new_grid);
  renderer->Resume(new_grid, (CheckmateRenderer::marble_t) turn_of, td::QVector2<int>(picked_x, picked_y), njumps, did_one_shot);
}

Haiku

simple little game
from where the complexity?
oh, creator me