2D Rectangle Collision

Question

I want to make a small 2D game. In the game you can go in all directions(with the bird's-eye view) and can shoot. (A little bit like BoxHead http://de.y8.com/games/box_head_2play) My problem there is the collision detection and especially the response, in which the detection of a collision is not really the problem(I use for that a quad tree). The real problem is the response to the collision. For simplifying it, all objects in the game are rectangles that cannot rotate, no shapes or circles. The rectangles are represented by a vector for the left bottom corner and a vector for the right top corner. The origin of the coordinate system is in the left bottom corner(I know in games its often on the left top corner but I prefer the bottom corner). So now a object in the world is composite with a rectangle and a velocity vector. The algorithm for now is, change the velocity(For example if the user press a key) from a object(In this case the player), add the velocity on the object and at last check for collision(I leave fro now the acceleration alone).

The real question now: How I response to the collision now ? What should I do, if the quad tree detect a collision ? Is the basic algorithm right ?

Still a small question: How I can detect collision in a endless world with a quad tree(Quad trees was always limited to a specify size) ?

You see I have a lot of questions. I don't know where to start and handle/detect the collision. I hope you can help me to get started.

EDIT: I don't need/want advanced collisions/physics. I only want that a player cant go through walls and detect if a bullet hits something.

Answer 1

Well, Mike C already gave you a simple answer, I am going a bit deeper:

First you need to a way to filter the results by proximity (this is to prevent lag when looping throught the objects) I advise using some sort of hashmap to sort the objects. Calculate them on a grid with their X and Y coordinates and then just Iterate between the near objects, if they are not near they wont collide.

But before that, make this question how many objects will there be in your world at a current time? 100? If they are rects this is relatively fast to process.

If thats not the case and you have Thousands of objects that gets complicate quite fast.

A few optimizations: Reduce the number of comparisons by doing something like this:

for(int i = 0; i < MyObjectsCount;i++)
  for(int j = i+1; j < MyObjectsCount;j++)
    //Do Collision

This will cut some unecessary computations, for example if A checks collision with B, the re is no point in B checking collision with A again.

If that still not enough, well you will need to start doing the screen partition, or chunks like they described above. Divide your world in areas, and each object can be in at most 4 of those areas (like a quad tree) but without the subdivision.

If you really want a quadtree, you can make your quadtree increase in size to accommodate the new objects boundaries. But if your world is infinite, you will need a way to Load/unload the objects you need at runtime, You can't load infinite data in the Ram.

So my advice is when you load Data, make your quadtree accommodate the new objects, and reposition the old ones, if this is done correctly, the overhead of doing this wouldn't be a issue. Take this example, if the map scrolls in positive X, you just copy the TopRight and BottomRight to the left Side of the quadtree (should be just changing references)

Hope this can give you a insight on how to do it. If you need further help, or if you describe your case more in depth, I will glady throw some pieces of code for you to mess arround.

Answer 2

It depends on how advanced you want it to be. The simplest solution I'm aware of given your setup is merely "push back" anyone who collides. As in, if the player collides with an enemy during this frame, put the player against the edge of the enemies hit box.

// An example of when the player is walking to the left
if (rect.x < enemy.rect.x + enemy.rect.width) {
    rect.x = enemy.rect.x + enemy.rect.width + 1; // A little buffer to avoid
                                                  // constant collisions
}

As for bullets, I would suggest this GameDev question.