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:

3
Contributors
9
Replies
10
Views
8 Years
Discussion Span
Last Post by Pynolathgeen

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 :)

Emil Olofsson

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!

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?

Edited by 0x69: n/a

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?

You mean the CHARACTER class code?

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

Edited by 0x69: n/a

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.
}``````

 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.

Edited by Pynolathgeen: n/a

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

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!

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!