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
}
Collision handling - is there an OOP solution?
Author
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:
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?
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).
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).
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:
- 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²). I have been corrected; complexity remains O(n²).
Quote:Original post by Oluseyiis 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.
Author
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.
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!
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(); }}
Author
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.
Author
Quote:Original post by OluseyiQuote: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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement