Page 1 of 1

touched which side? (2d box collision detection in C++)

Posted: Tue Jun 26, 2007 3:43 am
by AndrewAPrice
I'm writing an Arkanoid clone (called Andrewanoid) in C++, and I need some help with collision detection. How do I tell which side of the box the ball hit (like if the ball hit the top/bottom/left/right)? The ball is only 20x20px, and most blocks are 70x30. I'm only using box collision because the ball is small and moves fairly fast so I'm not gaim to try mixing box and circle collision.

Anyway here is the collision code I've got so far. I'm using a linked list of balls and a linked list of blocks.

Code: Select all

void BallManager::Update()
{
	int ballid = 0;
	int blockid = 0;

	Ball *current = m_firstBall;
	Block *currentBlock = 0;

	while(current != 0)
	{
		int x = current->GetXPosition();
		int y = current->GetYPosition();
		int width = current->GetWidth();
		int height = current->GetHeight();
		int direction = current->GetDirection();
		int speed = current->GetSpeed();

		int left = x - (width / 2);
		int top = y - (height / 2);

		switch(direction)
		{
		case 0: // nw
			x -= speed;
			y -= speed;
			break;
		case 1: // ne
			x += speed;
			y -= speed;
			break;
		case 2: // sw
			x -= speed;
			y += speed;
			break;
		case 3: // se
			x += speed;
			y += speed;
			break;
		default:
			break;
		}

		current->SetPosition(x, y);

		// check for collision
		currentBlock = m_blockManager->GetBlock(0);

		blockid = 0;
		while(currentBlock != 0)
		{
			if(currentBlock->GetCollidability())
			{
				int blockx = currentBlock->GetXPosition();
				int blocky = currentBlock->GetYPosition();
				int blockwidth = currentBlock->GetWidth();
				int blockheight = currentBlock->GetHeight();
				int blockleft = blockx - (blockwidth / 2);
				int blocktop = blocky - (blockheight / 2);

				if(blockid == 0)
				{

				}

				if (top + height < blocktop)
				{
				}				
				else if (top > blocktop + blockheight)
				{
				}
				else if (left + width < blockleft)
				{
				}
				else if (left > blockleft + blockwidth)
				{
				}
				else
				{ // woohoo collision :P
					char luabuf[50];

					sprintf(luabuf, "OnCollide(%d,%d,%d);",ballid,blockid, 0);

					m_lua->DoString(luabuf);
				}
			}

			currentBlock = currentBlock->GetNext();
			blockid++;
		}

		ballid++;
		current = current->GetNext();
	}
}
The last parameter of sprintf should be the side the ball hit the block (hardcoded to 0 until I work it out). If you're wondering what these numbers are, this is from my LUA script:

Code: Select all

-- Directions (for the ball)
DIRECTION_NW	= 0;
DIRECTION_NE	= 1;
DIRECTION_SW	= 2;
DIRECTION_SE	= 3;

-- Sides (for testing which side the ball collided from)
SIDE_TOP		= 0;
SIDE_BOTTOM		= 1;
SIDE_LEFT		= 2;
SIDE_RIGHT		= 3;
The ball won't move any faster than 10-15 pixels per update.

Posted: Tue Jun 26, 2007 7:47 am
by Combuster
one option:
take the x and y coordinates of the corner depending on which direction the ball is travelling - i.e. if the ball is moving up and to the left, you should take the bottom right corner.
next, compute corner.x - ball.x and corner.y - ball.y and take the absolute value. if the resulting x value is smaller, it hit the box on its side, if the resulting y value is smaller it hit the box on the top or the bottom. if they are equal (or almost equal), the ball hit the box straight on the corner. The only thing left to do is decide wether its the top/bottom or left/right edge. the corner you were using lies on both of those edges.

One potential issue I can see is if the ball 'chips off' a corner. It won't detect a collision since the ball does not intersect the box both before and after moving.

Posted: Tue Jun 26, 2007 11:08 am
by jhawthorn
This tutorial probably goes a fair bit more in depth than you need, and does cover mixing circle and rect collision detection. It's written by the guys who wrote N, the only good flash game ever made.
http://www.harveycartel.org/metanet/tut ... rialA.html
It solves your problem by calculating the projection vector, which they describe as "find[ing] the axis with the smallest amount of overlap between the two objects". Give it a read. If it doesn't help with your current project I guarantee you that it will allow you to make a great platformer.

I'm sorry to point this out if you've already looked in to lua's stack, but you should call your lua OnCollide function more like so (this is from memory, don't trust it too much):

Code: Select all

/* Get the functions address */
lua_getglobal(m_lua->L, "OnCollide");

/* Push the arguments */
lua_pushnumber(m_lua->L, ballid);
lua_pushnumber(m_lua->L, blockid);
lua_pushnumber(m_lua->L, 0);

/* do the actual call */.
if(lua_pcall(m_lua->L, 3, 0, 0)){ /*3 arguments, 0 results*/
	error(); /* There was an error of some sort */
}
where m_lua->L is your lua_State*

Posted: Wed Jun 27, 2007 6:59 am
by AndrewAPrice
Thanks.. From the advice given from both of you, I've decided to calculate a 3rd rectangle (the overlapping area) and if its width is greater than its height then we hit the top/bottom. It may not be exact, and it may fail occasionally (like if the ball is moving fast enough to go straight through the block to another edge - I've set a maximum ball speed so this won't happen), but the player is usually too involved into the game to notice a wrong bounce every 1/50 collisions.

@jhawtorn: Your advice is really helpful (and a lot less memory consuming than working with a buffer)! :) I've only looked into using the stack to get call arguments, not send them. My code is a little different because I'm using LuaPlus (the default LUA doesn't support registering methods in classes which have been dynamically allocated).

Posted: Wed Jun 27, 2007 12:27 pm
by Kevin McGuire
...like if the ball is moving fast enough to go straight through the block to another edge -
This is where you might be hurting the performance and making it slightly more troublesome for your self. You need to consider the ball's origin and a destination point (which could be in terms of ten seconds later). This ten seconds later might be well beyond the bounds of the environment, but the idea is to find where the line intersects a box. The from that you can use the slopes for X and Y to calculate a little before that when it is right next to the other box. Also produce the frames until collision, and when it matches the current frame index then you recalculate it's trajectory and do the same again.

You do multiple moving box by checking for their path lines intersecting each other, including checking static objects in the environment.