Object collision detection?

[TheBeardedQuack]

Hey I started making myself a game yesterday (2d sprited) but i was wondering how i could setup object collision.
I was thinking that all my collidable objects such as scenery or vehicles derive from an object class that will store the outer edges of each instance of an object and on each motion tick check if the x/y of the 2 objects are colliding.

public class collidable{
  private short left;//stores edges of collidable object
  private short right;
  private short top;
  private short bottom;

  private short adjLeft;//stores edges of closest collidable objects
  private short adjRight;
  private short adjTop;
  private short adjBottom;

  public static collidable*[] allObjects;
  public getAdjObject{
    //cycle through objects edges to find closest to the object caller
  }
}

However I feel that this would be terribly inefficient and may also cause a few errors where multiple object are within close proximity to each other.
So I dont suppose anybody has any ideas of how i could detect collidable objects?

Thanks

[Athar]

I'm not sure what the adj... members are supposed to be for, but they sound like a bad idea.
Basically, each time an object tries to move, you check whether its hitbox overlaps with a hitbox of any other collidable object. This will work fine as long as you don't have too many objects.

However, if you have a lot of moving objects (say, >10,000) this is going to be too slow. A very simple way to fix this is splitting your world into tiles of a fixed size (e.g. 256x256) and keep a list of collidable objects for each of the tiles. Then you only have to check the objects in the same tile (and possibly the surrounding tiles, depending on how you implement it).

and may also cause a few errors where multiple object are within close proximity to each other.

How so? Because the hitbox does not accurately reflect the true shape of the object?

[TheBeardedQuack]

Yeah basically i feel it may cause problems because of the hit-boxes...
And thanks for the chunk idea... (Cant believe I didn't think of that being a big minecraft fan)

I thought that if a character jumped up and across a hitbox it would prevent the character jumping over it (unless the closest adjacent hitboxes update on each movement tick)
However i think it should be fine as long as x and y motions are handled exclusively

[TheBeardedQuack]

Right, I've thought of a much better way of detecting object collision than i'm currently using but I could still do with the chunk based rendering but i'm not quite sure how to go about that.

Not sure if I'm exactly wanting an answer of sorts (yet) but some descriptive hints would be greatly appreciated... Thanks!

[TheBeardedQuack]

*bump* Please... Any suggestions?

[D80DSL3A]

I'd give all collidable objects a rectangle data member to provide a boundary for it.

Suppose we have a box class with a
Rect rect;// declare a suitable type if it doesn't exist
data member.

Let box objects also have a function member hit() for collision testing against other boxes.
Box objects shall be visible, hence they will have a draw()
Box objects shall move, hence they will have a move()
Box objects can collide with each other, hence they have a hit().

These functions would be called each frame, with draw() being called at a possibly different render rate.

The hit() is simple for rectangular areas:

bool box::hit( box& B )
{
    if( Right < B.Left ) return false;// this is left of B
    if( Left > B.Right ) return false;// this is right of B
    if( Bottom < B.Top ) return false;// this is above B
    if( Top > B.Bottom ) return false;// this is below B

    // if we made it here then it's a hit
    this->onHit( B );// a little polymorphism here permits different box 
    B.onHit( *this );// types to affect each other differently.

    return true;
}

Where onHit() would be another (virtual) member function of the box class (heirarchy).

We want to collision test each box against each other one once.

If we have:
vector<box*> pBoxes;// populated with pointers to our colliding boxes
The we would collision test like so each frame:

for( int a = 0; a < pBoxes.size()-1; ++a )
    for( int b = a+1; b < pBoxes.size(); ++b )
        pBoxes[a]->hit( *pBoxes[b] );
    

[Athar]

Right, I've thought of a much better way of detecting object collision than i'm currently using but I could still do with the chunk based rendering but i'm not quite sure how to go about that.

The simplest way is to use a map, such as:
map<vector2i,vector<Object*> > chunkMap;

Whenever an object moves and changes chunks, you need to add it to the new chunk:
chunkMap[pos()/mapChunkSize].push_back(this);

You also need to remove it from the old chunk when it moves and when it is deleted.
mapChunkSize should be a compile time constant and a power of two (256 or 512), as real divisions (compared to bit shifts) are slow.

Instead of just adding the object to the chunk in the upper left corner you might want to add it to all chunks it spans, so you don't have to check the neighbor chunks for objects that protrude into your own chunk.

[TheBeardedQuack]

@fun2code

I'd give all collidable objects a rectangle data member to provide a boundary for it.

Yeah, this was my new method :)
And I pretty have everything you wrote there planned out. Thanks though (I haven't actually added it in quite yet so this'll be helpful)

@Athar - I'll have to take a look at the map type.

Because i'm unfamiliar with what map<vector2i, vector<Object*>> chunkMap; will actually do I'm not quite cerain on what you're suggesting.

I thought of having a class for the chunks which contains a static 2dArray of pointers to instances of the chunk objects which holds the position in terms of that chunk. (i.e. Chunk grid[] = {{chunk1, chunk2, chunk3, etc}, {chunk11, chunk12, etc}};

Then within the Chunk instances are arrays of pointers to the different kinds of objects i want to load in that chunk. Because the chunk will know it's own position and boundaries every motion tick of an abject can update if the object is still in that chunk and the position of the object should easily compare to the chunk using the same method of the hit boxes (but of course whitout hitting).

Now that I think about it I think this should be a good method but I was also wondering how i'd get the chunks to unload and load as the player moves through the game (However while typing this i've just thought of sumat)

[TheBeardedQuack]

Ok, i think i've got a decent idea on how to make everything work now (or most of it) but I want to know if you think it'll be efficient enough.

The object collision and chunk map stuff are above (to clarify, the object collision detection will only scan in loaded chunks... Todo this it'll load the object pointer list from the loaded chunks list)

Do you think this would be ok?

O = unloaded chunk
X = loaded chunk
S = chunk on screen
P = player in chunk

O O O O O O O O O
O X X X X X X X O
O X S S S S S X O
O X S S P S S X O
O X S S S S S X O
O X X X X X X X O
O O O O O O O O O

Basically to keep the player in the center of the screen and as the level chunks scroll around the chunk that the player is in triggers a function when the player moves out of it, with argument to which side the player has moved out of.

Lets say the player move out of the chunk to the right, a function will call unloading the chunks to the left and more chunk will load on the right (using the 2dArray of chunks to the pos in the array of the currently loaded chunks and load the +1 positions)

Would this be ok?