Page 1 of 1

Collision Detection Space Invaders Issue

Posted: Mon Jun 15, 2009 2:41 pm
by hurstshifter
Hey Guys,

That's right, I'm back for more :mrgreen: . So I started working on the collision detection for my space invaders clone and it's, errr.....sort of working. I don't have the code on me now (at work currently) but this is roughly what it looks like out of memory...

Code: Select all

player::checkcollision();
{
    for(int counter = 0; counter < 10; counter++)
    {
        if(pBullets.bDead == 1)  //only check for active bullets
        {
            for(counterY = 0; counterY < 5; counterY++)
            {
                for(counterX = 0; counterX < 8; counterX++)
                {
                    if(pbullets.bRect.y > (blocksRects[counterY][counterX].y + BLOCK_HEIGHT)
                       && pbullets.bRect.y < (blocksRects[counterY][counterX].y - BULLET_HEIGHT)
                       && pbullets.bRect.x > (blocksRects[counterY][counterX].x + BLOCK_WIDTH)
                       && pbullets.bRect.x < (blocksRects[counterY][counterX].x + BULLET_WIDTH)
                       && blocksAlive[counterY][counterX] == 1
                       && pBullets.bDead == 1)
                       {
                           pBullets.bDead = 0;                             //set the bullet to dead
                           blocksAlive[counterY][counterX] = 0;   // set the block to dead
                           break;                                               //break the loop
                        }
                  }
             }
         }
     }
 }

Damn, I hope I got all that right from memory. Anyways, what is basically happening with this detection is as follows...

1. Bullet travels through the first 4 blocks in the column (5 blocks in a column)
2. Collision detection takes effect at the 5th block. Seems to be the right location, but of course it just ignored the first 4 blocks on its way there.
3. 5th block disappears. Bullet disappears.
4. 2nd shot fired, collision takes effect at the exact same location (5th block).
5. 2nd block in the column disappears? (wtf?)


I will post the real code on here when I get home. Any ideas on what I've shown so far? BTW I am calling this detection loop every frame.

Re: Collision Detection Space Invaders Issue

Posted: Mon Jun 15, 2009 4:51 pm
by avansc

Re: Collision Detection Space Invaders Issue

Posted: Mon Jun 15, 2009 5:01 pm
by hurstshifter

While I understand that this may not be the best way of going about this process, it is by no means unreadable. Loops through the bullets, loops through the 2 dimensional array of blocks....thats about it. I'm not going for efficiency here, just function.


Now that I'm home, here is the actual function. Seems like I got it mostly right. Although I described the way the blocks disappear backwards. Check this short video I uploaded.

http://www.youtube.com/watch?v=6MleYq-5lyI


Code: Select all

void player::checkcollision()
{
	for(int counter = 0; counter < 10; counter++)   //loop through the bullets on screen
	{
		if(pBullets[counter].bDead == 1)              //only if the bullet has been fired
		{
			
			for(int blockY = 0; blockY < 5; blockY++)     //loop through the array of blocks on the screen
			{
				for(int blockX = 0; blockX < 8; blockX++)
				{
					if(pBullets[counter].bulletRect.y < (blocksRects[blockY][blockX].y + BLOCK_HEIGHT)
						&& pBullets[counter].bulletRect.y > (blocksRects[blockY][blockX].y - BULLET_HEIGHT)
						&& pBullets[counter].bulletRect.x > (blocksRects[blockY][blockX].x - BULLET_WIDTH)
						&& pBullets[counter].bulletRect.x < (blocksRects[blockY][blockX].x + BLOCK_WIDTH)
						&& blocksAlive[blockY][blockX] == 1
						&& pBullets[counter].bDead == 1)  //if the bullet in question is within the bounds of a live box, and is not dead
					{
						blocksAlive[blockY][blockX] = 0;  //kill the block
						pBullets[counter].bVel = 0;          //kill the bullet's velocity
						pBullets[counter].bDead = 0;       //kill the bullet  
					}
				}
			}
		}
	}
}

Re: Collision Detection Space Invaders Issue

Posted: Mon Jun 15, 2009 5:50 pm
by Bakkon
Well, you check if(pBullets[counter].bDead == 1) twice. That won't be the problem, it's just redundant.
Why do you have two separate 2D arrays for your enemy blocks? Why don't you just do it the same way you did bullets so you can say blocksRects[blockY][blockX].bDead?

Seems weird to me that you have [Y][X]. Is that the way you set up the array?

Re: Collision Detection Space Invaders Issue

Posted: Mon Jun 15, 2009 6:02 pm
by hurstshifter
Bakkon wrote:Well, you check if(pBullets[counter].bDead == 1) twice. That won't be the problem, it's just redundant.
Why do you have two separate 2D arrays for your enemy blocks? Why don't you just do it the same way you did bullets so you can say blocksRects[blockY][blockX].bDead?

Seems weird to me that you have [Y][X]. Is that the way you set up the array?

Well. In the beginning I had an array of integers that defined whether they were alive or not. Then I also have an array of SDL_Rects defining the collision boxes. I suppose I should condense this down into a single class. I'll get working on that.

The reason why I checked twice was just in case the bullet hit a block on the first run through the loop. If so, it wouldnt bother running through the rest of them. It does the same thing if I remove the second if bdead == 1, just maybe .0000000001 seconds less to process, lol. I know theres a better way of doing it, I just didn't want to think about it until I had at least got the collision working right.

Re: Collision Detection Space Invaders Issue

Posted: Mon Jun 15, 2009 7:00 pm
by MarauderIIC
Are you sure blockRects and blocksAlive are loaded in the same order? It could be blockRects is checking from the end of screen closest to player but blocksAlive is loaded from end of screen farthest from player, and so the y-index activeBlocks[blockY]... is wrong.

I think I would make it so that the activeBlocks have their own collision rectangles, by the way. That would prevent this sort of thing from happening in the future.

Re: Collision Detection Space Invaders Issue

Posted: Tue Jun 16, 2009 8:00 am
by hurstshifter
Haha, well, I was getting a bit frusttrated trying to work through some of these issues and ended up turning my code completely fubar. I am going to take what I have now and rewrite it, this time focusing a bit more on organization and overall structure. Anyone know why VS2008 Express seems to automatically save changes you make to your files even when you don't tell it to save?

Re: Collision Detection Space Invaders Issue

Posted: Tue Jun 16, 2009 12:41 pm
by dani93
Why do you always check all blocks? You only need to check the block closest to the block where the bullets come from (certainly in each column). If the column is empty set the value to -1 (not 0, cause arrays start at 0). Here a piece of code just out of my mind (not tested!):

Code: Select all

void player::checkcollision()
{
    for(int counter = 0; counter < 10; counter++)   //loop through the bullets on screen
    {
      if(pBullets[counter].bDead == 1)              //only if the bullet has been fired
      {
          
        for(int blockX = 0; blockX < 8; blockX++)
        {
        
            blockY = first[blockX];
        
            if (blockY != -1)
            {
        
              if(pBullets[counter].bulletRect.y < (blocksRects[blockY][blockX].y + BLOCK_HEIGHT)
                && pBullets[counter].bulletRect.y > (blocksRects[blockY][blockX].y - BULLET_HEIGHT)
                && pBullets[counter].bulletRect.x > (blocksRects[blockY][blockX].x - BULLET_WIDTH)
                && pBullets[counter].bulletRect.x < (blocksRects[blockY][blockX].x + BLOCK_WIDTH)
                && blocksAlive[blockY][blockX] == 1
                && pBullets[counter].bDead == 1)  //if the bullet in question is within the bounds of a live box, and is not dead
              {
                blocksAlive[blockY][blockX] = 0;  //kill the block
                pBullets[counter].bVel = 0;          //kill the bullet's velocity
                pBullets[counter].bDead = 0;       //kill the bullet 
                first[blockX]--;
              }
            
            }
            
        }
         
      }
    }
}
So you need to check 8 rects instead of 40 each frame. That can save a lot of time ;)
You just need to initialize first[] correctly.

------------
EDIT: You also check

Code: Select all

pBullets[counter].bDead == 1
twice?!
------------
hurstshifter wrote:Anyone know why VS2008 Express seems to automatically save changes you make to your files even when you don't tell it to save?
Doesn't it save automatically when you recompile the project? Maybe you wanna have a look at SVN or git for project management.

Re: Collision Detection Space Invaders Issue

Posted: Tue Jun 16, 2009 1:25 pm
by hurstshifter
dani93 wrote:Why do you always check all blocks? You only need to check the block closest to the block where the bullets come from (certainly in each column). If the column is empty set the value to -1 (not 0, cause arrays start at 0). Here a piece of code just out of my mind (not tested!):

Code: Select all

void player::checkcollision()
{
    for(int counter = 0; counter < 10; counter++)   //loop through the bullets on screen
    {
      if(pBullets[counter].bDead == 1)              //only if the bullet has been fired
      {
          
        for(int blockX = 0; blockX < 8; blockX++)
        {
        
            blockY = first[blockX];
        
            if (blockY != -1)
            {
        
              if(pBullets[counter].bulletRect.y < (blocksRects[blockY][blockX].y + BLOCK_HEIGHT)
                && pBullets[counter].bulletRect.y > (blocksRects[blockY][blockX].y - BULLET_HEIGHT)
                && pBullets[counter].bulletRect.x > (blocksRects[blockY][blockX].x - BULLET_WIDTH)
                && pBullets[counter].bulletRect.x < (blocksRects[blockY][blockX].x + BLOCK_WIDTH)
                && blocksAlive[blockY][blockX] == 1
                && pBullets[counter].bDead == 1)  //if the bullet in question is within the bounds of a live box, and is not dead
              {
                blocksAlive[blockY][blockX] = 0;  //kill the block
                pBullets[counter].bVel = 0;          //kill the bullet's velocity
                pBullets[counter].bDead = 0;       //kill the bullet 
                first[blockX]--;
              }
            
            }
            
        }
         
      }
    }
}
So you need to check 8 rects instead of 40 each frame. That can save a lot of time ;)
You just need to initialize first[] correctly.

------------
EDIT: You also check

Code: Select all

pBullets[counter].bDead == 1
twice?!
------------

Good suggestion. Of course in the end these blocks will not always be lined up. Ideally they will end up moving around the screen and eventually even shooting back so I think it makes sense to test all blocks for now. And I mentioned why I checked for the dead block a couple posts back. Basically to keep it from checking any more blocks if it had already collided with one that had been tested (which in turn causes its bDead to == 0). I realize this probably did not save me any time checking whatsoever. Anyways, I am going to be rewriting this so hopefully I'll have something more functional and cleaner to show off soon. Thanks for everyone's help.

Re: Collision Detection Space Invaders Issue

Posted: Tue Jun 16, 2009 3:20 pm
by Innerscope
I'll agree with refactoring, but I'm also going to recommend that in the future you create an object management class that handles collision checks. That way you can iterate through a list of "active" objects and check for collisions appropriately. (i.e. don't compare things that don't collide)

Code: Select all

 if(pBullets[counter].bulletRect.y < (blocksRects[blockY][blockX].y + BLOCK_HEIGHT)
                && pBullets[counter].bulletRect.y > (blocksRects[blockY][blockX].y - BULLET_HEIGHT)
                && pBullets[counter].bulletRect.x > (blocksRects[blockY][blockX].x - BULLET_WIDTH)
                && pBullets[counter].bulletRect.x < (blocksRects[blockY][blockX].x + BLOCK_WIDTH)
                && blocksAlive[blockY][blockX] == 1
                && pBullets[counter].bDead == 1)  //if the bullet in question is within the bounds of a live box, and is not dead
              {
                blocksAlive[blockY][blockX] = 0;  //kill the block
                pBullets[counter].bVel = 0;          //kill the bullet's velocity
                pBullets[counter].bDead = 0;       //kill the bullet
                first[blockX]--;
              }
Having a collision function that takes those values (or the rects) as parameters and returns a boolean would also make this look/function better.
(i.e.)

Code: Select all

if(collisionCheck(&bulletRect, &blockRect)) {
//code
}