Skip to main content
GameDev.net gamedev.net
🔒 Locked 🎮 Unity

Collision handling - is there an OOP solution?

Started by Extrakun Jul 14, 2008 at 11:18 AM 42 replies 12.9k views
Original Post
Extrakun
Extrakun
Hi all, I am using XNA and C#, but it's a general programming so I am putting it here. I am trying to implement collision detection this way:

 private void CheckCollisions(GameTime gameTime)
        {
            foreach (IGameObject collider in gameObjectsList_)
            {
                foreach (IGameObject collidee in gameObjectsList_)
                {
                    // Make sure that we are not comparing the same object
                    if (collider != collidee)
                    {
                        if (collider.CheckCollision(gameTime, collidee))
                        {
                            HandleCollision(collider, collidee);
                        }
                    }
                }
            }
        }

        /// <summary>
        /// If snake collides with dot
        /// </summary>
        /// <param name="snake"></param>
        /// <param name="dot"></param>
        protected virtual void HandleCollision(Snake snake, Dot dot)
        {
            // Add new segment to snake

            // Remove dot from the list
            gameObjectsList_.Remove(dot);
        }

        /// <summary>
        /// Unspecified collision
        /// </summary>
        /// <param name="collider"></param>
        /// <param name="collidee"></param>
        protected virtual void HandleCollision(IGameObject collider, IGameObject collidee)
        {
            // Do nothing
        }

There are two concrete objects derived from the IGameObject interface. I was hoping the overloaded method HandleCollision(Snake snake, Dot dot) will be called, but it seems that it does not work. What are other OOP strategies for handling collision?
GamesTopica.Net- http://www.gamestopica.net
Ahnfelt
Ahnfelt
What you're trying to use is called multiple dispatch. Unfortunally, C# (and most other languages) only support single dispatch.

You can use the visitor pattern to get around this. It's very verbose, but it's the best solution I know (short of using another language).
Oluseyi
Oluseyi
Quote:
Original post by Extrakun
What are other OOP strategies for handling collision?

Other? Your existing strategy isn't OO. All you have is an overloaded function, where the specialized types are potentially ambiguous. You're not relying on dynamic dispatch via interface implementation (multiple inheritance for pansy languages), you're not relying on encapsulation or data hiding... What makes you think your code is "OO"?

You don't want a specialized, overloaded version of HandleCollision. What you want is an approach that minimizes the number of test pairs, then asks each object in a test pair to update itself in response to a collision:
// I replaced foreach with a for in order to perform a triangular set of tests // rather than rectangular; the result is fewer iterationsfor(int x = 0; x < gameObjectsList_.length; ++x){    for(int y = x; y < gameObjectsList_.length; ++y)    {        if collided(gameObjectsList_[x].bounds, gameObjectsList_[y].bounds)        {            gameObjectsList_[x].collideWith(gameObjectsList_[y].bounds);            gameObjectsList_[y].collideWith(gameObjectsList_[x].bounds);        }    }}

This approach:
  1. relies on each object in gameObjectsList_, regardless of concrete type, to provide a bounds property that returns a type collided can test for intersection and return a boolean result;

  2. invokes each objects collideWith method to update internal state, and passes the complementary object's bounds property in case the object requires geometry information to determine its response (change direction, etc);

  3. is O(n log n) as opposed to O(n²). I have been corrected; complexity remains O(n²).
Aressera
Aressera
Quote:
Original post by Oluseyi
  • is O(n log n) as opposed to O(n²).


  • Actually, your triangular iteration approach does not decrease the asymptotic complexity of the collision tests. It simply reduces an O(n²) algorithm to an O( n*(n-1)/ 2 ) algorithm, both of which are asymptotically O(n²), and definitely not O(n log n).

    -------------------------------------------

    My solution to this problem is to use a two-dimensional hash map which uses perfect-hashing to determine the collision detection test to which to dispatch the object pair. All collision shapes have a string which represents their type. I compute and store a hash code for each shape type and use these as the key values in the double hash map.

    Once the cell of the 2D hash map is determined, then the pair of shapes is sent to some class implementing a CollisionAlgorithm interface, where the actual test is performed.
    Extrakun
    Extrakun
    Quote:
    Original post by Oluseyi
    Other? Your existing strategy isn't OO. All you have is an overloaded function, where the specialized types are potentially ambiguous. You're not relying on dynamic dispatch via interface implementation (multiple inheritance for pansy languages), you're not relying on encapsulation or data hiding... What makes you think your code is "OO"?


    While I thank you for your example code, I don't understand why you need to emphasis this "Not OO" point. I was working under the assumption that polymorphism would work on the overloaded function. As for whether I am using encapsulation or data hiding, you have not see the rest of my code. And it is a design issue on whether each IGameObject should handle its own collision. I wish to regard all IGameObject as just data and has another object dealing with the logic as my design.

    The solution you have proposed can be found in More Effective C++ - and the author itself has pointed out the drawbacks of the solution; that sibling classes must know about each other and hence are tightly coupled. Maybe I should have asked, "What are the OOP ways of dealing with collision handling?". I was harboring the assumption that polymorphism would work with overloaded function; I don't see the need why you need to get on a high horse about this. Okay, so you are right and I am wrong. Next time I ask somewhere friendlier, maybe.

    I am interested in learning what other OOP strategies there is to handling collision besides this. Thank you for your time.
    GamesTopica.Net- http://www.gamestopica.net
    Oluseyi
    Oluseyi
    Quote:
    Original post by Extrakun
    The solution you have proposed can be found in More Effective C++ - and the author itself has pointed out the drawbacks of the solution; that sibling classes must know about each other and hence are tightly coupled.

    Incorrect. If you pay attention, you will see that my classes accept an external boundary definition for their collision response, not a reference to sibling classes. The sibling classes are completely uncoupled, and in a language that allows generic programming the "sibling classes" would actually be completely unrelated: they would simply implement the bounds property and the collideWith() method.

    Quote:
    Okay, so you are right and I am wrong. Next time I ask somewhere friendlier, maybe.

    If you can't take being wrong without getting emotional, you will get nowhere. It's not a high horse thing or a kick-you-when-you're-down thing; it's a correct-possibly-erroneous-notions-of-what-is-OO thing.

    Quote:
    Original post by Aressera
    Actually, your triangular iteration approach does not decrease the asymptotic complexity of the collision tests. It simply reduces an O(n²) algorithm to an O( n*(n-1)/ 2 ) algorithm, both of which are asymptotically O(n²), and definitely not O(n log n).

    You are absolutely correct; I didn't think that through fully. Thanks!
    mikeman
    mikeman
    Quote:

    Other? Your existing strategy isn't OO. All you have is an overloaded function, where the specialized types are potentially ambiguous. You're not relying on dynamic dispatch via interface implementation (multiple inheritance for pansy languages), you're not relying on encapsulation or data hiding... What makes you think your code is "OO"?


    To be fair, if the language supported multimethods, then his solution would be fine. It's just a pity that C# doesn't.

    Quote:

    This approach:

    relies on each object in gameObjectsList_, regardless of concrete type, to provide a bounds property that returns a type collided can test for intersection and return a boolean result;

    invokes each objects collideWith method to update internal state, and passes the complementary object's bounds property in case the object requires geometry information to determine its response (change direction, etc);

    is O(n log n) as opposed to O(n²).


    All those are fine, except they don't do what the OP wanted. The OP doesn't want just generic geometric collision, he wants the objects collided to "interact" based on their type. For example, snake-dot collision means the snake gets an extra segment, the dot disappears, snake-poisonous mushroom collision means the snake dies, and so on.

    A quick and not so bad way of dealing this is to add 'attributes' to the gameobjects. In their simplest form, those can be just a list of strings. They can also be queried. For example:

    dot.AddAttribute("Food")mushroom.AddAttribute("Poison")snake.AddAttribute("DotEater")class Snake:GameObject{  public virtual void CollideWith(GameObject o)  {    if (o.HasAttr("Food")) this.AddSegment();    if (o.HasAttr("Poison")) this.Die();  }}class Dot:GameObject{  public virtual void CollideWith(GameObject o)  {    if (o.HasAttr("DotEater")) this.Die();  }}
    Extrakun
    Extrakun
    Quote:
    Original post by mikeman


    A quick and not so bad way of dealing this is to add 'attributes' to the gameobjects. In their simplest form, those can be just a list of strings. They can also be queried. For example:



    Thanks, this is a helpful solution. I guess this would work for a small game; I would take another poster's suggestion to use a hash table if the game grows larger.

    GamesTopica.Net- http://www.gamestopica.net
    Extrakun
    Extrakun
    Quote:
    Original post by Oluseyi

    Quote:
    Okay, so you are right and I am wrong. Next time I ask somewhere friendlier, maybe.

    If you can't take being wrong without getting emotional, you will get nowhere. It's not a high horse thing or a kick-you-when-you're-down thing; it's a correct-possibly-erroneous-notions-of-what-is-OO thing.


    And if this is how you 'correct' forum visitors all the time, I wonder how you have a staff label next to your name.

    I didn't come here asking for a "kick-in-the-pants". I came to ask for opinions and to seek answers and dialogue, which I believe is the spirit of this forum. (Of course, you are the staff here, so who am I to assume). I got your opinions along with a lot of high-handed judgmental statements - guess whose the one with the issue? And your response is one as if I came here with boasting I have the "best code ever".

    Why I even make such a mention of it is because you have the label staff next to the your name in bright bold green. If you just a normal poster if I won't even raise it.

    If this is the culture of this board here, please kindly put a warning to anyone who even dare to mutter "OOP" within your presence. Just a suggestion for your management.
    GamesTopica.Net- http://www.gamestopica.net
    Oluseyi
    Oluseyi
    Quote:
    Original post by Extrakun
    I got your opinions along with a lot of high-handed judgmental statements...

    Stop. Please. Seriously. I'm not bashing you; I gave an opinion in my traditional manner, which you may not find overly friendly but is not hostile either. If you want to make an issue of it, however, I will set aside my "staff" label (which seems to bother you) and actually become hostile.

    Focus on the issues, my friend. The issue is your code, not your perception of my attitude.
    Mike.Popoloski
    Mike.Popoloski
    Although Oluseyi can be a bit of an ass at times (I'm sure he'd agree), in this topic at least he has been nothing but helpful. He not only corrected your incorrect use of a programming term, but also gave a good solution to your problem.

    At this forum we value only technical competence and accuracy. If you say something incorrectly, we will correct you on it. If you need somebody to give you kisses and hugs whenever you ask a question, I suggest you ask elsewhere. Would you rather he had lied to you? "Oh yeah, that's exactly what OOP means." Wouldn't you rather know when you're wrong, so that you can learn?
    Mike Popoloski | Journal | SlimDX
    Ahnfelt
    Ahnfelt
    Quote:
    Original post by Mike.Popoloski
    Although Oluseyi can be a bit of an ass at times (I'm sure he'd agree), in this topic at least he has been nothing but helpful. He not only corrected your incorrect use of a programming term, but also gave a good solution to your problem.

    At this forum we value only technical competence and accuracy. If you say something incorrectly, we will correct you on it. If you need somebody to give you kisses and hugs whenever you ask a question, I suggest you ask elsewhere. Would you rather he had lied to you? "Oh yeah, that's exactly what OOP means." Wouldn't you rather know when you're wrong, so that you can learn?


    His answer considers a solution to a generic geometry collider, which the OP didn't ask for (the OP asks for a way to get multiple dispatch). It features an optimization that has the following properties:
    - it improves it only by a constant factor (and somehow it was mistaken for a change in complexity)
    - it collides all objects against themselves
    So much for being helpful.

    What's left is the claim that the OP's own shot at a solution, which he has already discovered does not work in his language of choice, is not object oriented. However, what he tried to do was multiple dispatch, which arguably is object oriented (and would have been better solution than any proposed in this thread, if only the language supported it).
    So much for being technically correct.

    Even if you don't consider attitude or intention, I think you're taking the wrong side of the argument.
    mikeman
    mikeman
    Quote:
    Original post by Ahnfelt
    Quote:
    Original post by Mike.Popoloski
    Although Oluseyi can be a bit of an ass at times (I'm sure he'd agree), in this topic at least he has been nothing but helpful. He not only corrected your incorrect use of a programming term, but also gave a good solution to your problem.

    At this forum we value only technical competence and accuracy. If you say something incorrectly, we will correct you on it. If you need somebody to give you kisses and hugs whenever you ask a question, I suggest you ask elsewhere. Would you rather he had lied to you? "Oh yeah, that's exactly what OOP means." Wouldn't you rather know when you're wrong, so that you can learn?


    His answer considers a solution to a generic geometry collider, which the OP didn't ask for (the OP asks for a way to get multiple dispatch). It features an optimization that has the following properties:
    - it improves it only by a constant factor (and somehow it was mistaken for a change in complexity)
    - it collides all objects against themselves
    So much for being helpful.

    What's left is the claim that the OP's own shot at a solution, which he has already discovered does not work in his language of choice, is not object oriented. However, what he tried to do was multiple dispatch, which arguably is object oriented (and would have been better solution than any proposed in this thread, if only the language supported it).
    So much for being technically correct.

    Even if you don't consider attitude or intention, I think you're taking the wrong side of the argument.


    Agreed. I was just about to post the same thing. A little friendliness in responses is not a bad thing, especially when you proceed to solve a singificantly different problem than the one at hand, and making erroneous claims yourself in the process(multimethods not 'OO'? Virtual functions are just a special case of multiple dispatch, and Visitor pattern a piss-poor attempt to emulate them). I'm trying to imagine Oluseyi's response had Aressera replied with something like 'Do try to read a bit about big O notation before you advise others on it,mkay?'. Believe me, It would not be pretty.
    Mike.Popoloski
    Mike.Popoloski
    Quote:
    Even if you don't consider attitude or intention, I think you're taking the wrong side of the argument.


    I reread the thread again, and it looks like I jumped to conclusions. I read it quickly, saw the OP's last post, and thought it was just like the hundreds of other posts where the OP gets defensive for no reason. My bad.

    My second paragraph still stands in general though. The OP got defensive when Oluseyi really wasn't even being antagonistic. It's advisable to get a thicker set of skin before posting on an internet forum, and GDNet is no different.
    Mike Popoloski | Journal | SlimDX
    Extrakun
    Extrakun
    Quote:
    Original post by Mike.Popoloski
    Quote:
    Even if you don't consider attitude or intention, I think you're taking the wrong side of the argument.


    I reread the thread again, and it looks like I jumped to conclusions. I read it quickly, saw the OP's last post, and thought it was just like the hundreds of other posts where the OP gets defensive for no reason. My bad.

    My second paragraph still stands in general though. The OP got defensive when Oluseyi really wasn't even being antagonistic. It's advisable to get a thicker set of skin before posting on an internet forum, and GDNet is no different.


    I'll think over your suggestion.

    PS. I believe I have already stated my reason for making an issue for this thread. May I request this topic to be locked so it does not spiral out from proportion or that it stays on topic about OOP strategies to deal with behaviour of game objects after collision handling? Thanks!
    GamesTopica.Net- http://www.gamestopica.net
    ToohrVyk
    ToohrVyk
    I would make an effort to further separate the collision-detection code from the collision-response code. Collision detection is ultimately a case of computing overlaps of geometrical shapes, which needs no knowledge of what those shapes represent in the game world. So, the code for collision detection would probably look along the pseudocode lines of:

    detectCollisions(objects):  pairs = []  foreach(pair in potentiallyColliding(objects)):    if(colliding(pair[0], pair[1]):      pairs.append(pair)  return pairs


    Pairs would contain your choice of a referencing mechanism: handles, listeners, back-references or inheritance. This would in turn allow a variety of multiple dispatch approaches: double-dispatch with a visitor, a type hash table of resolution functions, a lookup table of handle indices...

    Ultimately, my approach would be to slice up potentially colliding objects into a 'hull' (the geometric shape) and a collision 'controller' (responsible for responding to collisions) in addition to the rest of the objct, using composition rather than inheritance to avoid cluttering the object interface and to allow more than one hull per object. The hull would be associated with a handle, that would then be used to locate the corresponding controller.

    Concerning Oluseyi's replies... I find it hardly surprising that, when the OP seems concerned about Object-Oriented implementations of a collision system, and then proposes a non-Object-Oriented example of his own, someone will mention that the proposed example does not qualify. I find Oluseyi's first post to be a concise, pragmatical and to-the-point explanation of why it doesn't qualify. As for the O(n log n) issue, a simple modification of the code to use a sort-and-sweep algorithm instead of a test-all-pairs algorithm would achieve that complexity instead of the proposed O(n^2).

    jbadams
    jbadams
    Quote:
    Original post by Extrakun
    May I request this topic to be locked so it does not spiral out from proportion
    No, but I am instructing everyone to remain strictly on topic in any further replies -- this is not the place to discuss forum etiquette, whether or not you believe Oluseyi (or any other particular user) was rude, etc.

    I'm also going to give a reminder to everyone that staff and moderators are users too - unless they're actually acting in an official role (as I am with this post) you're probably best off just treating them as you would any other member of the community.
    - Jason Astle-Adams
    dzeligman
    dzeligman
    I have a few questions in regards to ToohrVyk's solution.

    Quote:
    detectCollisions(objects):

    pairs = []

    foreach(pair in potentiallyColliding(objects)):

    if(colliding(pair[0], pair[1]):

    pairs.append(pair)

    return pairs



    The looping through pairs and separation of the detection mechanism is not a hard feat, however I'm having issues concerning the implementation of a controller for each pair/object(s).

    I would probably implment it with a "lookup table of handle indices..." that would return the proper collision handler for each pair. Now my concern is how much the handler knows about everything else. Say we have a pair of a bullet and enemy ship. The bullet collides with the ship, they both are changed to inactive by their respective handlers, but what if the AlienShip needs to do more than just update its internal state?

    I guess this might just be bad design on my part, but say I want to update a score variable which is on a much higher level than the Alien ship, I'm really unsure of these relations. This is all assuming all my gameobjects and/or collidable objects are grouped together such that I might loop through them at the end of the update call to remove the inactive objects.
    Oluseyi
    Oluseyi
    Quote:
    Original post by Ahnfelt
    - it improves it only by a constant factor (and somehow it was mistaken for a change in complexity)

    This is true. I completely botched that, and I don't know what I was thinking.

    Quote:
    - it collides all objects against themselves

    Yes, minor bug. y should have started at x + 1, not x.


    Being wrong is incredibly common in technical circumstances. When someone points out your error, you thank them - as I did with Aressera - because it is an opportunity for you to learn and internalize what's right. That's all that matters.
    BeerNutts
    BeerNutts
    Quote:
    Original post by Oluseyi
    Quote:
    Original post by Extrakun
    The solution you have proposed can be found in More Effective C++ - and the author itself has pointed out the drawbacks of the solution; that sibling classes must know about each other and hence are tightly coupled.

    Incorrect. If you pay attention, you will see that my classes accept an external boundary definition for their collision response, not a reference to sibling classes. The sibling classes are completely uncoupled, and in a language that allows generic programming the "sibling classes" would actually be completely unrelated: they would simply implement the bounds property and the collideWith() method.

    Quote:
    Okay, so you are right and I am wrong. Next time I ask somewhere friendlier, maybe.

    If you can't take being wrong without getting emotional, you will get nowhere. It's not a high horse thing or a kick-you-when-you're-down thing; it's a correct-possibly-erroneous-notions-of-what-is-OO thing.

    Quote:
    Original post by Aressera
    Actually, your triangular iteration approach does not decrease the asymptotic complexity of the collision tests. It simply reduces an O(n²) algorithm to an O( n*(n-1)/ 2 ) algorithm, both of which are asymptotically O(n²), and definitely not O(n log n).

    You are absolutely correct; I didn't think that through fully. Thanks!


    Oluseyi has a habit of putting people down when he responds. He knows his programming, and he wants to make sure everyone knows he knows it. I suppose it makes him feel good mocking other people's thoughts (sometimes incorrect) on different programming aspects. Try to not take it personally; he just doesn't know any other way to respond.
    My Gamedev Journal: 2D Game Making, the Easy Way

    ---(Old Blog, still has good info): 2dGameMaking
    -----
    "No one ever posts on that message board; it's too crowded." - Yoga Berra (sorta)

    Topic Locked

    This topic has been locked by a moderator. New replies are not allowed.

    Sign in to reply to this topic.