GB101:Collision Detection

GB101 Class Notes
	Sections Home Installing Gameboy Development Tools Introduction to the Gameboy Advance Hello Background Working with Palettes Tiles and Background Maps Sprites Scrolling Backgrounds Collision Detection Fixed point math Affine Sprites Sound Where do I go from here?

Introduction

Sadly, the GBA features no hardware based collision detection. We'll just have to do it ourselves. The easiest way to do collision detection is with a bounding box. We'll imagine one around our sprite, and then we'll use the screen entry map right out of video memory to figure out if we should stop or not.

Gotchas

Currently we've been moving two pixels at a time so the movement is relatively quick. We'll have to make sure we're doing our collision detection at the pixel-by-pixel basis so that we don't mess up and collide too early or too late.

Implementation

#include <tonc.h>
#include "data.h"
#include "sprites.h"

#define MAP_WIDTH 64*8
#define MAP_HEIGHT 32*8
#define SPEED 2
#define COLLISION_X 1
#define COLLISION_Y 2

// The buffer to store the OAM entries between vblanks
OBJ_ATTR obj_buffer[128];

// Converts x and y into the appropriate screen entry
int se_index(int x, int y) {
	int base = 0;
	
	if (x >= MAP_WIDTH/2) {
		x -= MAP_WIDTH/2;
		base = 32*32;
	}

	return base + (y>>3<<5) + (x>>3);	
}

// Returns true if we have a collision tile at x,y
int point_collision(int x, int y) {
	int i = se_index(x,y);
	int tid = se_mem[30][i];
	tid = tid & 0xFF; // Chop off the lower bits
	
	return (
		tid == 64 ||
		tid == 65 ||
		tid == 66 ||
		tid == 96 ||
		tid == 97 ||
		tid == 98 ||
		tid == 99 ||
		tid == 128 ||
		tid == 129 ||
		tid == 130 ||
		tid == 131 ||
		tid == 161 ||
		tid == 162 ||
		tid == 163
	);
}

// Test if there would be a collision given the bounding box and the proposed
// x and y offsets
int collision_test(int x1, int y1, int x2, int y2, int xofs, int yofs) {
	int result = 0;

	if (xofs > 0) {
		if (point_collision(x2+xofs,y1) || point_collision(x2+xofs,y2))
			result = COLLISION_X;
	}
	else if (xofs < 0) {
		if (point_collision(x1+xofs,y1) || point_collision(x1+xofs,y2))
			result = COLLISION_X;		
	}
	
	if (yofs > 0) {
		if (point_collision(x1,y2+yofs) || point_collision(x2,y2+yofs))
			result = result | COLLISION_Y;
	}
	else if (yofs < 0) {
		if (point_collision(x1,y1+yofs) || point_collision(x2,y1+yofs))
			result = result | COLLISION_Y;
	}
	
	return result;
}

void loop() {
	int x = 10;
	int y = 10;
	int window_x = 0, window_y = 0;
	int player_x = 0, player_y = 0;
	int dx, dy, i, collision = 0;
	char str[32];
	
	// Get a pointer to the first OAM entry
	OBJ_ATTR *sprites= &obj_buffer[0];
	obj_set_attr(sprites, 
		ATTR0_TALL | ATTR0_8BPP,  // Tall 64x64 = 32x64				
		ATTR1_SIZE_64,			  // 64x64
		ATTR2_PALBANK(0) | 0);    // pal0, tid0

	while(1) {
		// Wait for VBlank
		vid_vsync();
		
		// Get the state of the input controls
		key_poll();
		
		// Need to check pixel by pixel, so we can't simply += 2 anymore..
		for (i=0; i<SPEED; i++) {
			// Get the state of the D-pad, adjust our x/y accordingly
			dx = key_tri_horz();
			dy = key_tri_vert();
			
			// Check to see if there would be collision
			collision = collision_test(x,y,x+31,y+63,dx,dy);
		
			// If no collision on x-axis add to x
			if (!(collision & COLLISION_X)) {
				x += dx;
			}
			
			// If no collision on y-axis add to y
			if (!(collision & COLLISION_Y)) {
				y += dy;
			}
		}
			
		// Bound x and y by the size of the map.
		if (x < 0) 
			x = 0;
		else if (x > MAP_WIDTH) 
			x = MAP_WIDTH;
		
		if (y < 0) 
			y = 0;
		else if (y > MAP_HEIGHT) 
			y = MAP_HEIGHT;
		
		// If we're in the 1st quarter, lock the window on 0 and move the sprite
		if (x < VID_WIDTH/2) {
			window_x = 0;
			player_x = x;
		}
		// If we're in the 4th quarter, lock the window as far as possible 
		// without looping and move the sprite
		else if (x > MAP_WIDTH-VID_WIDTH/2) {
			window_x = MAP_WIDTH-VID_WIDTH;
			player_x = x - window_x;
		}
		// In the 2nd and 3rd quarter center the sprite and move the screen
		else {
			window_x = x - VID_WIDTH/2;
			player_x = VID_WIDTH/2;
		}

		// Same thing as before, but vertically.  If we're too close to the top
		// lock the screen and move the sprite.
		if (y < VID_HEIGHT/2) {
			window_y = 0;
			player_y = y;
		}
		// If we're too close to the bottom, lock the screen and move the sprite
		else if (y > MAP_HEIGHT-VID_HEIGHT/2) {
			window_y = MAP_HEIGHT-VID_HEIGHT;
			player_y = y - window_y;
		}
		// Lock the sprite and move the screen otherwise
		else {
			window_y = y - VID_HEIGHT/2;
			player_y = VID_HEIGHT/2;
		}

		// Set the window offset of BG2
		REG_BG2HOFS = window_x;
		REG_BG2VOFS = window_y; 
		
		// Change the sprite position
		obj_set_pos(sprites, player_x, player_y);

		// Copy the bufferred OAM entries to the actual OAM memory
		oam_copy(oam_mem, obj_buffer, 1);	// only need to update one
	}
}

int main()
{
	// Load the toiles into page 0
	memcpy(&tile_mem[0][0], (u8*)TS_PORTAL, 256*128);
	// Load the palette
	memcpy(pal_bg_mem, (u16*)PAL_PORTAL, 256*2);
	// Load the sceen entries into page 30
	memcpy(&se_mem[30], (u16*)LEVEL1, 64*32*2);
	// Load the sprites sprite into tile memory vram page 4
	memcpy(&tile_mem[4][0], spritesTiles, spritesTilesLen);
	// Load the palette memory into palette memory
	memcpy(pal_obj_mem, spritesPal, spritesPalLen);
	
	// Set mode 0, bg 2, sprites on, 1D sprites
	REG_DISPCNT = DCNT_MODE(0) | DCNT_BG2 | DCNT_OBJ | DCNT_OBJ_1D;

	// Setup BG2 to use 256 colors, with tiles on page 0, 
	// screen entries on page 30 and the size of 64x32t
	REG_BG2CNT = BG_8BPP | BG_CBB(0) | BG_SBB(30) | BG_REG_64x32;
	
	loop();

	return 0;
}

Optimization

Considering we only reach a tile's edge every 8 pixels, we should be able to optimize this. If we use modulus we could figure out if we're at an edge and then do the check. Unfortunately modulus is very slow on the GBA. Bit math to the rescue! If we simply look for some bits set out of the lowest 3 we'll know we're not on a multiple of 8.

Implementation

// Test if there would be a collision given the bounding box and the proposed
// x and y offsets
int collision_test(int x1, int y1, int x2, int y2, int xofs, int yofs) {
	int result = 0;

	if (xofs > 0 && !(x2+xofs & 7)) {
		if (point_collision(x2+xofs,y1) || point_collision(x2+xofs,y2))
			result = COLLISION_X;
	}
	else if (xofs < 0 && !(x2-xofs & 7)) {
		if (point_collision(x1+xofs,y1) || point_collision(x1+xofs,y2))
			result = COLLISION_X;		
	}
	
	if (yofs > 0 && !(y2+yofs & 7)) {
		if (point_collision(x1,y2+yofs) || point_collision(x2,y2+yofs))
			result = result | COLLISION_Y;
	}
	else if (yofs < 0 && !(y2-yofs & 7)) {
		if (point_collision(x1,y1+yofs) || point_collision(x2,y1+yofs))
			result = result | COLLISION_Y;
	}
	
	return result;
}

Better bounding boxes

You may have noticed that the sprite in this example collides early in some cases, especially when moving up. Our bounding box is surrounding the entire 32x64 pixel sprite, but the graphics within aren't using all 32x64 pixels. What we should do is calculate the the ideal bounding box by running through the sprite and calculating a min and max for x and y. We have to be careful when doing these types of boxes because the sprite may not be symmetrical. In the case of asymmetry we'll have to know whether the sprite has been vertically or horizontally flipped and do the same to the bounding box. Things get much more difficult when we get into sprite rotation, at which time you'll probably want to simply give up and use a bigger box. :)

Other Approaches

Alternatively we could load up a collision array and do some bit math instead of inspecting video memory. Remember that working with memory in 16-bits is twice as slow because the ARM works in 32-bits natively. Theoretically we could pack an array of 64 32-bit ints and use bit math to come up with our collision map. I leave this as an exercise for you.