Saturday, May 24, 2014

The ABCs of Android game development: Detect collisions

In the fourth installment of his five-part app developer series, William J. Francis provides the code to be able to detect when the asteroid and the ship collide in this Android game.


The goal of the Android game we are developing in this series is to adjust the flying saucer’s momentum in order to avoid getting smashed to bits by the asteroid. While simplistic, the project incorporates all the essential aspects of a video game: a canvas, sprites, animation, collision detection, and user input.

In our last tutorial we managed to get our sprites moving around the screen. (If you're new to this series, catch up on parts one and two, respectively: Prepare the canvas and Load and display sprites.) Now we need to be able to detect when the asteroid and the ship collide. There are basically two techniques for collision detection: bounding algorithms and image masking. Bounding is easier and takes up fewer CPU cycles than image masking; however, bounding is not normally accurate enough for arcade type games. Just what is the difference? Well, consider our two images. I have them both on a 50x50 pixel background, but the contents of those sprites don't fill the entire 50x50 pixel grid. Take a look at the illustrations in Figure A and Figure B.

Figure A



Our UFO sprite including transparent areas.

Figure B

The asteroid sprite with its transparent areas.

If we were to use bounding to detect collisions, we'd simply check each time through our loop to see if the 50x50 rectangles overlap; if they do overlap, we consider it a collision. Using the images above, you can see this technique can be fudged to work for collisions on the X-axis. Collisions on the Y-axis are not so cut-and-dry.

(Figure C) Figure C

Basic bounding collision detection and its lack of accuracy.

As I said before comparing the proximity of the two sprites on a pixel-by-pixel basis (sometimes called bit masking and sometimes referred to as pixel perfect collision detection) results in a much more accurate collision detection mechanism. This can be time-consuming, because it basically requires you to scan the individual pixels in both images and look for overlaps. In most games, a combination of the two gets used, and that is the approach we will use as well.

As long as the outer rectangles do not overlap, we will mark the collision flag as false. When the rectangles do overlap, we will scan only those pixels in the overlapping section. Any time we have a pixel in the overlapping section that is not transparent in both images, our sprites have crashed into one another.

Detecting collisions

This tutorial builds on what we created in part three. To really understand what is going on, it helps to see the code in the context of the whole; therefore, the code listing in the tutorial will be our complete working base, with the new code commented inline. You can follow along with the step-by-step instructions or download and import the entire project into Eclipse.

1. Create a new Android project in Eclipse. Target Android 2.1 or higher. Be sure to rename the startup activity Main.java and the corresponding layout to main.xml.

2. While there are no changes in our manifest file or layout since part three, I've included both below for completeness.

AndroidManifest.xml
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
    package="com.authorwjf.gamedevtut04"
    android:versionCode="1"
    android:versionName="1.0" >
   <uses-sdk
       android:minSdkVersion="7"
       android:targetSdkVersion="15" />
   <application
       android:icon="@drawable/ic_launcher"
       android:label="@string/app_name"
       android:theme="@style/AppTheme" >
       <activity
           android:name=".Main"
           android:label="@string/title_activity_main"
           android:screenOrientation="portrait"
android:configChanges="orientation|keyboardHidden">
            <intent-filter>
                <action android:name="android.intent.action.MAIN" />
               <category android:name="android.intent.category.LAUNCHER" />
            </intent-filter>
        </activity>
    </application>
</manifest>

main.xml
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    android:layout_width="fill_parent"
    android:layout_height="fill_parent"
    android:orientation="vertical" >
    <TextView
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:layout_gravity="top|center"
        android:text="ABC's of Android Game Dev" />
   <Button
                android:id="@+id/the_button"
                android:layout_width="wrap_content"
                android:layout_height="wrap_content"
                android:layout_gravity="center"
                android:gravity="center"
                android:enabled="false"
                android:text="Reset" />
   <TextView
       android:layout_width="wrap_content"
       android:layout_height="wrap_content"
       android:layout_gravity="center"
       android:text="Sprite Speed (?,?)"
       android:id="@+id/the_label" />
   <TextView
      android:layout_width="wrap_content"
      android:layout_height="wrap_content"
      android:layout_gravity="center"
      android:text="Last Collision XY (?,?)"
      android:id="@+id/the_other_label" />
   <com.authorwjf.drawing.GameBoard
              android:layout_width="fill_parent"
              android:layout_height="fill_parent"
              android:layout_margin="20dip"
              android:id="@+id/the_canvas"/>
</LinearLayout>

3. Just as in the previous tutorials, we have created a /drawable folder in the /res directory where we place our two sprite images: ufo.png and asteroid.png. Now that we are doing collision detection, the size becomes more important, so if you are using your own images, I recommend sizing them both to 50x50 pixels. Also you will need to make sure the images have been saved with a transparent background.

4. Most of the magic this time around happens in the com.authorwjf.drawable.GameBoard.java file; this is where we will be checking for a collision each time through the on draw loop. If a collision occurs, we will update the flag and the coordinates and draw a red x indicating where the collision occurred.

If the check for collision function still seems confusing to you at this point, it's okay -- you can use it in your projects largely via cut and paste, and gradually over time you will get more comfortable with the technique.

GameBoard.java
package com.authorwjf.drawing;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import com.authorwjf.gamedevtut04.R;
import android.content.Context;
import android.graphics.Bitmap;
import android.graphics.BitmapFactory;
import android.graphics.Canvas;
import android.graphics.Color;
import android.graphics.Matrix;
import android.graphics.Paint;
import android.graphics.Point;
import android.graphics.Rect;
import android.util.AttributeSet;
import android.view.View;
public class GameBoard extends View{
       private Paint p;
       private List starField = null;
       private int starAlpha = 80;
       private int starFade = 2;
       private Rect sprite1Bounds = new Rect(0,0,0,0);
       private Rect sprite2Bounds = new Rect(0,0,0,0);
       private Point sprite1;
       private Point sprite2;
       private Bitmap bm1 = null;
       private Matrix m = null;
       private Bitmap bm2 = null;
       //Collision flag and point
       private boolean collisionDetected = false;
       private Point lastCollision = new Point(-1,-1);
       private int sprite1Rotation = 0;

private static final int NUM_OF_STARS = 25;
       //Allow our controller to get and set the sprite positions
       //sprite 1 setter
       synchronized public void setSprite1(int x, int y) {
             sprite1=new Point(x,y);
       }
       //sprite 1 getter
       synchronized public int getSprite1X() {
             return sprite1.x;
       }

synchronized public int getSprite1Y() {
             return sprite1.y;
       }
       //sprite 2 setter
       synchronized public void setSprite2(int x, int y) {
             sprite2=new Point(x,y);
       }
      //sprite 2 getter
      synchronized public int getSprite2X() {
            return sprite2.x;
      }

synchronized public int getSprite2Y() {
            return sprite2.y;
      }

synchronized public void resetStarField() {
            starField = null;
      }
      //expose sprite bounds to controller
      synchronized public int getSprite1Width() {
            return sprite1Bounds.width();
      }

synchronized public int getSprite1Height() {
            return sprite1Bounds.height();
      }

synchronized public int getSprite2Width() {
            return sprite2Bounds.width();
      }

synchronized public int getSprite2Height() {
            return sprite2Bounds.height();
      }
      //return the point of the last collision
      synchronized public Point getLastCollision() {
            return lastCollision;
      }
     //return the collision flag
     synchronized public boolean wasCollisionDetected() {
           return collisionDetected;
     }

public GameBoard(Context context, AttributeSet aSet) {
            super(context, aSet);
            p = new Paint();
            //load our bitmaps and set the bounds for the controller
            sprite1 = new Point(-1,-1);
            sprite2 = new Point(-1,-1);
            //Define a matrix so we can rotate the asteroid
            m = new Matrix();
            p = new Paint();
            bm1 = BitmapFactory.decodeResource(getResources(), R.drawable.asteroid);
            bm2 = BitmapFactory.decodeResource(getResources(), R.drawable.ufo);
            sprite1Bounds = new Rect(0,0, bm1.getWidth(), bm1.getHeight());
            sprite2Bounds = new Rect(0,0, bm2.getWidth(), bm2.getHeight());
      }

synchronized private void initializeStars(int maxX, int maxY) {
            starField = new ArrayList();
            for (int i=0; i=252 || starAlpha <=80) starFade=starFade*-1;
           p.setStrokeWidth(5);
           for (int i=0; i=0) {
                 m.reset();
                 m.postTranslate((float)(sprite1.x), (float)(sprite1.y));
                 m.postRotate(sprite1Rotation,
(float)(sprite1.x+sprite1Bounds.width()/2.0),
(float)(sprite1.y+sprite1Bounds.width()/2.0));
                 canvas.drawBitmap(bm1, m, null);
                 sprite1Rotation+=5;
                 if (sprite1Rotation >= 360) sprite1Rotation=0;
         }
         if (sprite2.x>=0) {
                canvas.drawBitmap(bm2, sprite2.x, sprite2.y, null);
         }
         //The last order of business is to check for a collision
         collisionDetected = checkForCollision();
         if (collisionDetected ) {
                //if there is one lets draw a red X
                p.setColor(Color.RED);
                p.setAlpha(255);
             p.setStrokeWidth(5);
             canvas.drawLine(lastCollision.x - 5, lastCollision.y - 5,
lastCollision.x + 5, lastCollision.y + 5, p);
             canvas.drawLine(lastCollision.x + 5, lastCollision.y - 5,
lastCollision.x - 5, lastCollision.y + 5, p);
              }
       }
} 

5. We still have a few changes to make in the /src/Main.java file. First we want to add a check of the collision flag to the frame update. If a collision did occur, we update the x y label and then abort. Second, we want to make sure our Reset button invalidates the screen. This insures pressing Reset will start the game over.

Main.java
package com.authorwjf.gamedevtut04;
import java.util.Random;
import com.authorwjf.drawing.GameBoard;
import android.os.Bundle;
import android.os.Handler;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.TextView;
import android.app.Activity;
import android.graphics.Point;
public class Main extends Activity implements OnClickListener{
       private Handler frame = new Handler();
       //Velocity includes the speed and the direction of our sprite motion
       private Point sprite1Velocity;
       private Point sprite2Velocity;
       private int sprite1MaxX;
       private int sprite1MaxY;
       private int sprite2MaxX;
       private int sprite2MaxY;
       //Divide the frame by 1000 to calculate how many times per second the screen will update.
       private static final int FRAME_RATE = 20; //50 frames per second
       @Override
    public void onCreate(Bundle savedInstanceState) {
       super.onCreate(savedInstanceState);
       setContentView(R.layout.main);
       Handler h = new Handler();
       ((Button)findViewById(R.id.the_button)).setOnClickListener(this);
       //We can't initialize the graphics immediately because the layout manager
       //needs to run first, thus call back in a sec.
       h.postDelayed(new Runnable() {
                     @Override
                     public void run() {
                            initGfx();
                     }
        }, 1000);
    }

private Point getRandomVelocity() {
              Random r = new Random();
              int min = 1;
              int max = 5;
              int x = r.nextInt(max-min+1)+min;
              int y = r.nextInt(max-min+1)+min;
              return new Point (x,y);
        }
        private Point getRandomPoint() {
              Random r = new Random();
           int minX = 0;
           int maxX = findViewById(R.id.the_canvas).getWidth() -
((GameBoard)findViewById(R.id.the_canvas)).getSprite1Width();
               int x = 0;
           int minY = 0;
           int maxY = findViewById(R.id.the_canvas).getHeight() -
((GameBoard)findViewById(R.id.the_canvas)).getSprite1Height();
           int y = 0;
              x = r.nextInt(maxX-minX+1)+minX;
              y = r.nextInt(maxY-minY+1)+minY;
              return new Point (x,y);
        }
    synchronized public void initGfx() {
        ((GameBoard)findViewById(R.id.the_canvas)).resetStarField();
        Point p1, p2;
        do {
               p1 = getRandomPoint();
               p2 = getRandomPoint();
        } while (Math.abs(p1.x - p2.x) <
((GameBoard)findViewById(R.id.the_canvas)).getSprite1Width());
       ((GameBoard)findViewById(R.id.the_canvas)).setSprite1(p1.x, p1.y);
       ((GameBoard)findViewById(R.id.the_canvas)).setSprite2(p2.x, p2.y);
       //Give the asteroid a random velocity
       sprite1Velocity = getRandomVelocity();
       //Fix the ship velocity at a constant speed for now
       sprite2Velocity = new Point(1,1);
       //Set our boundaries for the sprites
       sprite1MaxX = findViewById(R.id.the_canvas).getWidth() -
((GameBoard)findViewById(R.id.the_canvas)).getSprite1Width();
       sprite1MaxY = findViewById(R.id.the_canvas).getHeight() -
((GameBoard)findViewById(R.id.the_canvas)).getSprite1Height();
       sprite2MaxX = findViewById(R.id.the_canvas).getWidth() -
((GameBoard)findViewById(R.id.the_canvas)).getSprite2Width();
       sprite2MaxY = findViewById(R.id.the_canvas).getHeight() -
((GameBoard)findViewById(R.id.the_canvas)).getSprite2Height();
       ((Button)findViewById(R.id.the_button)).setEnabled(true);
        frame.removeCallbacks(frameUpdate);
       ((GameBoard)findViewById(R.id.the_canvas)).invalidate();
       frame.postDelayed(frameUpdate, FRAME_RATE);
   }
   @Override
   synchronized public void onClick(View v) {
         initGfx();
   }
   private Runnable frameUpdate = new Runnable() {
       @Override
       synchronized public void run() {
             //Before we do anything else check for a collision
             if (((GameBoard)findViewById(R.id.the_canvas)).wasCollisionDetected()) {
             Point collisionPoint =
((GameBoard)findViewById(R.id.the_canvas)).getLastCollision();
             if (collisionPoint.x>=0) {
                   ((TextView)findViewById(R.id.the_other_label)).setText("Last
Collision XY


("+Integer.toString(collisionPoint.x)+","+Integer.toString(collisionPoint.y)+")");
              }
              //turn off the animation until reset gets pressed
              return;
      }
              frame.removeCallbacks(frameUpdate);
              Point sprite1 = new Point
(((GameBoard)findViewById(R.id.the_canvas)).getSprite1X(),
                               ((GameBoard)findViewById(R.id.the_canvas)).getSprite1Y()) ;
              Point sprite2 = new Point
(((GameBoard)findViewById(R.id.the_canvas)).getSprite2X(),
                              ((GameBoard)findViewById(R.id.the_canvas)).getSprite2Y());
             sprite1.x = sprite1.x + sprite1Velocity.x;
             if (sprite1.x > sprite1MaxX || sprite1.x < 5) {
                    sprite1Velocity.x *= -1;
             }
             sprite1.y = sprite1.y + sprite1Velocity.y;
             if (sprite1.y > sprite1MaxY || sprite1.y < 5) {
                    sprite1Velocity.y *= -1;
             }
             sprite2.x = sprite2.x + sprite2Velocity.x;
             if (sprite2.x > sprite2MaxX || sprite2.x < 5) {
                     sprite2Velocity.x *= -1;
             }
             sprite2.y = sprite2.y + sprite2Velocity.y;
             if (sprite2.y > sprite2MaxY || sprite2.y < 5) {
                     sprite2Velocity.y *= -1;
             }
             ((GameBoard)findViewById(R.id.the_canvas)).setSprite1(sprite1.x,
sprite1.y);
          ((GameBoard)findViewById(R.id.the_canvas)).setSprite2(sprite2.x, sprite2.y);
             ((GameBoard)findViewById(R.id.the_canvas)).invalidate();
             frame.postDelayed(frameUpdate, FRAME_RATE);
        }
    };
} 

Load the tutorial on a device or an emulator and wait for the ship and the asteroid to collide. If it is taking too long, hit the Reset and both the UFO and the asteroid will get new trajectories. At this point, you have a game, albeit the world's most frustrating one. While both the sprites bounce around and collide, you have no control over either. The next post in this series will cover basic user input and give us just enough control over the alien spacecraft to scoot out of the way of that inbound asteroid.

1 comment: