Implementing collision detection correctly

[ECoL3TCk]

I'm making a 2D Terraria-like (side-scrolling RPG with destroyable blocks) game with SFML 2.1, and I have no clue how to correctly implement collision detection. Meaning that I have been successful at making it work, but it's not clean and definitely not dynamic. I need some tips on what exactly I should do with it. I'm just completely lost, and am incredibly tired of screwing with this terrible code (probably been working on it for weeks on and off, and first started it months ago). Rather than fumbling around like an idiot for god knows how long, trying to take little bits of advice from people, I'd prefer just get a basic example of good, object oriented collision detection, because after all the crap I've done, I'm pretty sure I have no idea how to go abut this whatsoever. By example, I mean design wise. What parameters should collision functions take? Where should these functions be located? The same 2 questions for collision reaction. Since I have multiple things that need to collide with each other (player with enemy, player with items, enemy with items, enemy with enemy, player with player, etc...), and the world has to be treated differently, things get complicated. There is no block class, just a vertex array, so collision with the world is based purely on coordinates taken from that array in the world class, which, considering it's the world and not something like a player or an enemy, doesn't inherit from the same base class that they do. I would very, very much appreciate any help.

[Disch]

I'm going to expand on a post I just made 5 seconds ago in another thread. See my notes in the 2nd half of my post here... I'm going to use it as a base for my responses below:
http://www.cplusplus.com/forum/general/142123/#msg750319

What parameters should collision functions take?

If you're talking Map/Object collision, then the Map could have some kind of external interface that takes a bounding circle/rect (for the Object moving), and a movement vector. Something like:

class Map
{
   //...
   //  returns true if moved completely, or false if hit a wall
   //  Move is input/output... input is the vector along which the object wants to move
   //   Output is the furthest it can move before hitting a wall (ie, how much it will ACTUALLY
   //   move)
    bool tryMove( const sf::FloatRect& bounds, sf::Vector2f& move );
};

Object/Object collision is different. That could just take 2 rects and return true if they overlap.

Where should these functions be located?

Object/Object collision is related to Objects, so it would be in the Object class.

Object/Map collision needs to know details of the Map, so it makes sense for it to be part of the Map class.

The same 2 questions for collision reaction. Since I have multiple things that need to collide with each other (player with enemy, player with items, enemy with items, enemy with enemy, player with player, etc...), and the world has to be treated differently, things get complicated.

You could apply some polymorphism here. IE, Player/Enemy/Item classes could all be derived from Object, and could override their own 'handleCollision' function which behaves different for each class.

The common code that is the same for all Objects can stay in the Object parent so you won't have to duplicate it for each class.

There is no block class, just a vertex array, so collision with the world is based purely on coordinates taken from that array in the world class,

Is the vertex array just the edge of the walls? Or does it form all the polygons to render the floor?

If it's the latter, that's a lot of unnecessary information, and might make collision more work (and more time consuming).

But however you can get it working... that's fine. The only thing I will say is make sure your World/Map/whatever class is encapsulated... and provide a very simple and easy to use public function for collision detection -- one that makes absolutely no assumption about how the data is stored internally (like my above example). That way... you can change how you store the map later if you're unhappy with it. Or not.

[ECoL3TCk]

Thanks for your help, though I have a few questions.

If you're talking Map/Object collision, then the Map could have some kind of external interface that takes a bounding circle/rect (for the Object moving), and a movement vector. Something like:

class Map
{
   //...
   //  returns true if moved completely, or false if hit a wall
   //  Move is input/output... input is the vector along which the object wants to move
   //   Output is the furthest it can move before hitting a wall (ie, how much it will ACTUALLY
   //   move)
    bool tryMove( const sf::FloatRect& bounds, sf::Vector2f& move );
};

A bit of a random question, but why does the function take references to the bounds and the movement vector (assuming that part isn't just pseudo-code, I just see things like that a lot)? I don't see how you would be manipulating the bounds of the rectangle (if that's even possible), so you shouldn't need access to that. The movement vector I suppose you would just be modifying it to output a safe movement for the player. I might be missing a basic use of references though, as it's been awhile since I learned about them.

Object/Map collision needs to know details of the Map, so it makes sense for it to be part of the Map class.

That's great to know, but I still don't get how you decide whether the function would go in the map class or the object class. Sure, it needs to know the details of the map, but it still needs details about the object. How does one decide things like this in general? Take another feature of the game, gravity for example. From what I've learned about OOP, you try to encapsulate things that this theoretical class would have. In real life, the actual world is what has gravity, not the objects on it, but the objects are the thing being affected by the gravity. Just like this map/object collision function, how do you know which class the gravity function would be best suited for? Would it be appropriate to pass the gravity function the object which you want it to apply the gravity to, and have it in the map class? Or should it just be in the object class because it pertains to objects?

You could apply some polymorphism here. IE, Player/Enemy/Item classes could all be derived from Object, and could override their own 'handleCollision' function which behaves different for each class.

I take it you mean that the base class would have multiple overloaded versions of "handleCollision" for each class to override so all of them know how to react to each type of collision? Or is there a better way?

Is the vertex array just the edge of the walls? Or does it form all the polygons to render the floor?

It stores the coordinates of the 4 corners of each block.

In that other thread you said that Map shouldn't know anything about Object; does that mean Map shouldn't use an object of the Object class in any way? You also said there should be a Game class that ties everything together, but why would you need to make another class to do that rather than using main? I've always heard people say things like this, but I don't understand the benefit of using a class over main. Sorry if I have a lot of questions, but these are things I've always wondered about and never found an explanation for. This is actually the first time I've ever posted on a forum for programming help, so the questions just kind of built up.

[helios]

Physical laws don't exist in any particular object in the universe; they "permeate" the universe entirely. Likewise, collision detection doesn't belong in the objects that are being tested for collision, but in a PhysicsEngine object that's not itself part of the simulation.

[TwilightSpectre]

Bosslard wrote:

why does the function take references to the bounds and the movement vector

The bounds are taken by const reference, which means that you cannot modify the parameters. However, it has a bonus efficiency-wise: because you are only passing a reference rather than the whole object, there is less copied so it takes less time to call the function. As you correctly surmised, and as @Disch explained, the movement vector is an output field.

Bosslard wrote:

how you decide whether the function would go in the map class or the object class

Its all based on what you want exposed to the rest of the world. Ideally, only the map should know the exact map that you are using. On the other hand, lots of things should knowthings like where the object is and how its moving. It makes more sense to have the object tell the map where it is than the map tell the object about itself.

There is no real way to do this every time - just think about it. What makes the most logical sense, and what requires the least amount of unnecessary data to be exposed? These are the questions you should be asking.

Bosslard wrote:

I take it you mean that the base class would have multiple overloaded versions of "handleCollision" for each class to override so all of them know how to react to each type of collision? Or is there a better way?

I think he was suggesting to just have the one version of handleCollision which is overrided by derived classes using polymorphism to provide different effects.

Bosslard wrote:

You also said there should be a Game class that ties everything together, but why would you need to make another class to do that rather than using main?

Because the game might not be running all the time, and that way you can split up the various components to make it more maintainable. For example, would the game be running in the background of your main menu screen? It just provides a bit of extra flexibility should you decide to change something a bit later.

[ECoL3TCk]

NT3 wrote:

I think he was suggesting to just have the one version of handleCollision which is overrided by derived classes using polymorphism to provide different effects.

The part I didn't understand about that was how does one handleCollision function handle collision for every other type of collidable object? Since I want it to be able to do something different depending on what it is colliding with I figured a function to handle each type would be needed. For example, when the player touches an enemy he should take damage, but if he touches an item it should be added to his inventory. If the player is inheriting and overriding that function from Object, then he'll only have that one function, not the several needed. Personally, I'm not sure how else to achieve that. Anyways, thank you for clearing up my other questions.

[helios]

if (collided(objectA, objectB)){
    objectA.hits(objectB);
    objectB.hits(objectA);
}

class Collidable{
    virtual void hits(Collidable &) = 0;
    virtual void hits_Player() = 0;
    virtual void hits_Ground() = 0;
    virtual void hits_Mine() = 0;
};

class Mine : public Collidable{
    void hits(Collidable &c){
        c.hits_Mine();
    }
};

[ECoL3TCk]

Thanks, I think I finally have an idea of what I'm doing now.