Collision Detection

[Pynolathgeen]

Hello, I wrote a 2D game with some simple Collision Detection.

I used the function IntersectRect() but I think it's slow.
This is the code right now:

int Collision(CHARACTER* object1, CHARACTER* object2)
{
D3DXVECTOR3 pos1 = object1->GetPosition();
D3DXVECTOR3 pos2 = object2->GetPosition();

RECT a, b, *des;
a.left = pos1.x;
a.right = pos1.x + object1->width;
a.top = pos1.y;
a.bottom = pos1.y + object1->height;

b.left = pos2.x;
b.right = pos2.x + object2->height;
b.top = pos2.;
b.bottom = y2 + object2->height;

return IntersectRect(des, a, b);
}

Do anyone know some algorithm? D:

[emilo35]

int Collision(CHARACTER* object1, CHARACTER* object2)
{
D3DXVECTOR3 pos1 = object1->GetPosition();
D3DXVECTOR3 pos2 = object2->GetPosition();

RECT a, b, *des;
a.left = pos1.x;
a.right = pos1.x + object1->width;
a.top = pos1.y;
a.bottom = pos1.y + object1->height;

b.left = pos2.x;
b.right = pos2.x + object2->height;
b.top = pos2.;
b.bottom = y2 + object2->height;

return IntersectRect(des, a, b);
}

Hi there. Please use code tags from now on, it's much prettier, and makes your code a lot easier to read.

Why not try out radial collision detection? Should look something like this in your case:

#include <math.h>

int Collision(CHARACTER* object1, CHARACTER* object2)
{
    D3DXVECTOR3 pos1 = object1->GetPosition();
    D3DXVECTOR3 pos2 = object2->GetPosition();

    int xDistance = pos1.x - pos2.x; // Get relative distances
    int yDistance = pos1.y - pos2.y; // between the objects

    // Assuming your objects are pretty square shaped
    int combinedRadius = object1->width + object2->width;

    xDistance *= xDistance; // This should give you xDistance^2
    yDistance *= yDistance; // and yDistance^2

    // And finally, some pythagoras
    return (sqrt(xDistance + yDistance) <= combinedRadius);
}

I just came up with this solution, and while writing this code down, I realized this is probably going to be a lot slower than your original example. It has some pros and cons though. Collision detection between an alligator and a flag pole wouldn't generate very good results with this algorithm. Though, collision detection between a small shuttle craft and a huge planet would benefit from this algorithm since you will actually test against the planets circle, and not the square around it, which make huge differences on large objects!

This might also help you with a new way of attacking your problem, so all might not be lost :)

Good luck on your collisions!
Emil Olofsson

[Pynolathgeen]

Hi there. Please use code tags from now on, it's much prettier, and makes your code a lot easier to read.

Woops, excuse me for that =P. I normally do that but I forgot it T_T.

I will try your algorithm, and post the result!

Thanks!

[0x69]

It's more interesting to me How you pass objects for collision detection routine ? I'm asking because routine for choosing which objects to pass into

int Collision(CHARACTER* object1, CHARACTER* object2)

this function also very important for perfomance issues. It can be that it is more important than collision detection itself.
Can you put that routine code here?

[Pynolathgeen]

It's more interesting to me How you pass objects for collision detection routine ? I'm asking because routine for choosing which objects to pass into

int Collision(CHARACTER* object1, CHARACTER* object2)

this function also very important for perfomance issues. It can be that it is more important than collision detection itself.
Can you put that routine code here?

You mean the CHARACTER class code?

[0x69]

You mean the CHARACTER class code?

No, I mean code which executes Collision() function.

[Pynolathgeen]

No, I mean code which executes Collision() function.

Its called every time a walk-button or attack-button is pushed on the keyboard, its just 2 lines of code, something like this:

switch(Key) {

for(unsigned i = 0; i < Monsters.size(); i++)
if(Collision(Monsters.at(i), Player1) == true)
Player1->Collision[Player1->GetDirection()] = true;

//handle keys here etc.
}

[edit] This is the collision function, if you haven't seen it yet [/edit]

int Collision(CHARACTER* object1, CHARACTER* object2)
{
D3DXVECTOR3 pos1 = object1->GetPosition();
D3DXVECTOR3 pos2 = object2->GetPosition();

RECT a, b, *des;
a.left = pos1.x;
a.right = pos1.x + object1->width;
a.top = pos1.y;
a.bottom = pos1.y + object1->height;

b.left = pos2.x;
b.right = pos2.x + object2->height;
b.top = pos2.;
b.bottom = y2 + object2->height;

return IntersectRect(des, a, b);
}

But the problem is that the character can walk through objects when, for example, pushing left and up right after each other.

~Thanks for your time already :3.

[emilo35]

It looks like your problem might be located somewhere in your key handling and/or movement functions. Could you post those too?

[0x69]

Its called every time a walk-button or attack-button is pushed on the keyboard, its just 2 lines of code, something like this:

switch(Key) {

for(unsigned i = 0; i < Monsters.size(); i++)
if(Collision(Monsters.at(i), Player1) == true)
Player1->Collision[Player1->GetDirection()] = true;

//handle keys here etc.
}

As I understood Monsters.size() is monster count in whole map. If it is so - it is very inefficient code. I would do instead something like that:

#define CELL_WIDTH 40
#define CELL_HEIGHT 40
#define M SCREEN_WIDTH/CELL_WIDTH
#define N SCREEN_HEIGHT/CELL_HEIGHT
List* map_grid[M][N];
// in player and monster movement code add this
map_grid[object.grid_row][object.grid_col]->remove(objIndex) // clear wherever object was before
object.grid_row = object.positionX/CELL_WIDTH;
object.grid_col  = object.positionY/CELL_HEIGHT; 
map_grid[object.grid_row][object.grid_col]->append(monster.Index) // aka. your monster index i
/* now after button press 
instead of for(unsigned i = 0; i < Monsters.size(); i++)
do this
*/
for(int i = Player.grid_row-K; i<Player.grid_row+K; i++) {
  for(int j = Player.grid_col-K; j<Player.grid_col+K; j++) {
    for(/*iterate through all monsters at map_grid[i][j]*/) { 
      if(Collision(Monsters.at(currentMonster), Player);
      // ... do what you like here
    }
  }
}
// only think How to set constant K. It can be some small number.
// Or you can program it to be related to maximum possible monster size in terms of grid cell count.

That is. Definitely after implementing this, your program should run faster, because instead of looping through ALL monsters you will loop only through nearest cells (nearest monsters) around player. That's a big difference in perfomance. Also carefully choose container of monsters at cell. It can be that LIST dynamic insertions/removal will compensate some perfomance gain with this solution. So read what container has fast insertions and fast removals - and use it instead of List.

Good luck!

[Pynolathgeen]

As I understood Monsters.size() is monster count in whole map. If it is so - it is very inefficient code. I would do instead something like that:

#define CELL_WIDTH 40
#define CELL_HEIGHT 40
#define M SCREEN_WIDTH/CELL_WIDTH
#define N SCREEN_HEIGHT/CELL_HEIGHT
List* map_grid[M][N];
// in player and monster movement code add this
map_grid[object.grid_row][object.grid_col]->remove(objIndex) // clear wherever object was before
object.grid_row = object.positionX/CELL_WIDTH;
object.grid_col  = object.positionY/CELL_HEIGHT; 
map_grid[object.grid_row][object.grid_col]->append(monster.Index) // aka. your monster index i
/* now after button press 
instead of for(unsigned i = 0; i < Monsters.size(); i++)
do this
*/
for(int i = Player.grid_row-K; i<Player.grid_row+K; i++) {
  for(int j = Player.grid_col-K; j<Player.grid_col+K; j++) {
    for(/*iterate through all monsters at map_grid[i][j]*/) { 
      if(Collision(Monsters.at(currentMonster), Player);
      // ... do what you like here
    }
  }
}
// only think How to set constant K. It can be some small number.
// Or you can program it to be related to maximum possible monster size in terms of grid cell count.

That is. Definitely after implementing this, your program should run faster, because instead of looping through ALL monsters you will loop only through nearest cells (nearest monsters) around player. That's a big difference in perfomance. Also carefully choose container of monsters at cell. It can be that LIST dynamic insertions/removal will compensate some perfomance gain with this solution. So read what container has fast insertions and fast removals - and use it instead of List.

Good luck!

Thank you all guys!