Jump to content

  • Log In with Google      Sign In   
  • Create Account


Object interaction: Best practice


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
10 replies to this topic

#1 Grain   Members   -  Reputation: 442

Like
0Likes
Like

Posted 22 July 2013 - 12:39 PM

When objects interact in game and are supposed to have some effect on one another what is the best way to accomplish this without violating encapsulation. 

 

For example, say a projectile object collides with an enemy object, the projectile should terminate and display a small splash animation, and the enemy should take damage = to the damage value of the projectile. How does the enemy know the projectiles value? How do the know they collided? Some kind of entity manager class can check for collisions, but then it needs to know the positions and sizes of all the entities. I keep going around in circles trying to design something and always ends up needing to expose some part of one class to another. Either that or do something extreme, like make EVERYTHING derived from some abstract base class that has every conceivable method needed for game objects in virtual form.



Sponsor:

#2 swiftcoder   Senior Moderators   -  Reputation: 9883

Like
4Likes
Like

Posted 22 July 2013 - 05:41 PM

You need something that finds collisions between objects (it could be a physics engine, or a homegrown collision algorithm), call it 'WorldCollider'. WorldCollider has to know the positions and bounds of all objects - this is unavoidable, elsewise every object will need to deal with collisions.

But WorldCollider only finds collisions, it shouldn't know what to do with them (else you would have to hardcode all your collision responses). So, instead it should trigger some sort of callback.

An example (in very awful pseudo-code):

interface PhysicalObject {
  vec3 getPosition();
  box  getBounds();

  void collidedWith(PhysicalObject other);
}

class WorldCollider {
  list<PhysicalObject> objects;

  void findCollisions() {
    for o in objects:
      for p in objects:
        if collides(o, p):
          o.collidedWith(p)
          p.collidedWith(o)
  }
}

This will get the job done, but it's far from ideal. Among other things, you should probably use some sort of spatial hash to implement collides().

 

The real problem, is how you tell what type of object you have collided with. All you are handed is the PhysicalObject interface, but you need to know whether it is a bullet, an enemy, or something else entirely.

 

The correct way to solve this is double-dispatch, but unfortunately a lot of mainstream languages don't support that very well. In practice, you either get cute with mutually-recursive virtual function calls, or you fall back to a chain of instanceof() calls in each callback.


Tristam MacDonald - Software Engineer @Amazon - [swiftcoding]


#3 AllEightUp   Moderators   -  Reputation: 4195

Like
2Likes
Like

Posted 22 July 2013 - 11:32 PM

I don't mean to argue with swiftcoder in terms of the double-dispatch comment but only suggest a usable workaround.  The work around is a bit confusing to a degree but hopefully I can make it make sense.  It is, for all intents and purposes a double-dispatch like solution but done in a manner which is very usable in C++ without rtti.  I've never seen a good name for this other than what we came up with which was "subject oriented", perhaps there is a pattern which describes this but I've not found any which really cover the concept yet.  (Correct me please.)  Anyway, the idea is that at some level in the hierarchy given an input an object knows what to do with it.  The "subject" is always the acted upon object and as such the overhead of the solution is often two virtual function calls.  I'll explain this in just a sec, but first....

 

With most collision systems you get a contact pair, there is no concept of source and target, just two generic objects which are colliding.  So there is no concept of who hit who, just that they are in contact.  Everyone seems to jump at rtti about this time (or a custom variation of ID's) and it is not actually required.  You don't need to know jack about the objects at this point, you just need to call "Interact" on one of them.  So, for our purposes, you take the pair and whichever object is the first in the contact point description you call "Interact( rhs )" on.  'rhs' of course being the second object in the pair.  At this point you don't have to use rtti at all, you are "IN" the first object and know what you are, at which point the subject oriented portion of this comes into play.

 

So, you are in one of the two objects.  If the object you are running from is a projectile or whatever, they just call a "take damage" function on the target object (target/dest is well understood from the point of view of the projectile).  Static indestructible objects ignore the call, player vehicles take the given data and apply it via some rules system.  If on the other hand, the first object was a player vehicle it calls "collide" on the other object using itself as a parameter.  A "projectile" implements collide by simply calling "take damage" on the source.  It is completely circular logic but the idea is that the "subject" is always correctly dealt with even if it takes 2 virtual function calls to get it done.  A vehicle to vehicle collide of course would do whatever is appropriate.

 

I "think" this is basically a subset of double dispatch without relying on any typeof mappings.  At most, you bounce from one object to the other via virtual functions in order to get the subject defined.  Now, obviously done in a naive manner, this could cause lots of problems.  But the 'subject oriented' idea is that one of the objects always knows how to take some generic data and act on it, be it get healed, take damage, be stunned etc.  Those "rules" of what happens though can be put in another class hierarchy though, so there is no direct coupling to any of the systems beyond say 5-10 virtual functions in a very basic interface for all objects and of course whatever actionable properties you want to supply.

 

It's just a different manner (very C++) of looking at this problem.


Edited by AllEightUp, 22 July 2013 - 11:33 PM.


#4 Goran Milovanovic   Members   -  Reputation: 1104

Like
0Likes
Like

Posted 23 July 2013 - 01:11 AM


At most, you bounce from one object to the other via virtual functions in order to get the subject defined.

 

Maybe I misunderstood something crucial, but it seems to me that nothing is actually "defined"; There is no need for type inference because every object implements the required interaction methods.

 

Right?


+---------------------------------------------------------------------+

| Game Dev video tutorials  ->   http://www.youtube.com/goranmilovano |
+---------------------------------------------------------------------+

#5 AllEightUp   Moderators   -  Reputation: 4195

Like
0Likes
Like

Posted 23 July 2013 - 01:44 AM

 


At most, you bounce from one object to the other via virtual functions in order to get the subject defined.

 

Maybe I misunderstood something crucial, but it seems to me that nothing is actually "defined"; There is no need for type inference because every object implements the required interaction methods.

 

Right?

 

 

Yes and no.  As I mentioned, this is a tricky thought problem and I'm probably not in the best state to try and describe it properly right now.  (Very late and a bit tipsy. :))  Basically the idea is that the first "generic" interface call goes to a specific typed implementation of the interface.  So, a projectile having interact called just bounces the call to the subject of "you were hit by me" in the appropriate manner for a projectile to hit a target.  The first call to the generic virtual resolves half of the problem.  A projectile can only be one thing, an action on a subject, so it's interaction call simply says apply me to that thing.  The subject is now defined and you only have one side of the mess remaining which requires any real work, which I usually put in a separate rules class.  If you called the function on the vehicle first, it calls an apply on it's target, if that happens to be a projectile that just bounces right back as apply projectile to the vehicle.  It's basically 1 level of recursion with each interface having a first and second order function defined for whatever generic actions you need to define.

 

I suspect I'm probably not describing this very well and how it solves the problem, I'll be back tomorrow and follow up if this is still not making sense..   Sorry, it is too late and caffeine has worn off. :)



#6 Grain   Members   -  Reputation: 442

Like
0Likes
Like

Posted 23 July 2013 - 02:10 AM

Well I hope you don't get too hung up on the collision problem. It is not the only place I have this problem, it's just the first example that popped into mind. 

 

Another example could be A.I. An AI actor needs to have knowledge of the world around it in order to make decisions and act appropriately, for example, navigating the environment, or targeting the player. Meaning it would need to know at a minimum the players position, and position of other objects(terrain, walls, obstacles, ect.), and likely a whole lot more information for a more involved A.I. 



#7 Strewya   Members   -  Reputation: 1374

Like
0Likes
Like

Posted 23 July 2013 - 02:19 AM

So, you are in one of the two objects.  If the object you are running from is a projectile or whatever, they just call a "take damage" function on the target object (target/dest is well understood from the point of view of the projectile).  Static indestructible objects ignore the call, player vehicles take the given data and apply it via some rules system.  If on the other hand, the first object was a player vehicle it calls "collide" on the other object using itself as a parameter.  A "projectile" implements collide by simply calling "take damage" on the source.  It is completely circular logic but the idea is that the "subject" is always correctly dealt with even if it takes 2 virtual function calls to get it done.  A vehicle to vehicle collide of course would do whatever is appropriate.


So if in your example the vehicle would just call collide on whatever the other thing was, and the other thing happened to be another vehicle, that other vehicle would also call collide on whatever it received, and you would get infinite recursion, right?
Your example is great when you have objects that know how to be a subject of collision, and apply some logic to the other thing. But, if an object type doesn't do anything, and just tells the other thing to handle the collision, and you somehow get two of those in collision... Do you code your objects to always know what to do to the other thing, and never let this case happen?

devstropo.blogspot.com - Random stuff about my gamedev hobby


#8 Goran Milovanovic   Members   -  Reputation: 1104

Like
0Likes
Like

Posted 23 July 2013 - 03:31 AM

Yes and no.

 

I understand the yes, but not the no:

 

Projectile::interact(subject): subject->take_damage(this)

 

Car::interact(subject): subject->collide(this)

 

Projectile::collide(subject): this->interact(subject)

 

This assumes that interact, take_damage and collide are all valid method calls regardless of subject type. So, every object has to implement those, and other relevant methods.

 

So if in your example the vehicle would just call collide on whatever the other thing was, and the other thing happened to be another vehicle, that other vehicle would also call collide on whatever it received, and you would get infinite recursion, right?

 

The implementation of collide on the car wouldn't call collide on the subject. In other words: Car::collide != Car::interact.

+---------------------------------------------------------------------+

| Game Dev video tutorials  ->   http://www.youtube.com/goranmilovano |
+---------------------------------------------------------------------+

#9 swiftcoder   Senior Moderators   -  Reputation: 9883

Like
1Likes
Like

Posted 23 July 2013 - 04:38 AM

snip

That is pretty much what I meant by "getting cute with mutually recursive virtual functions".

Virtual functions implement single dispatch, so you can simulate double dispatch with a pair of complementary virtual functions.
 

Another example could be A.I. An AI actor needs to have knowledge of the world around it in order to make decisions and act appropriately, for example, navigating the environment, or targeting the player. Meaning it would need to know at a minimum the players position, and position of other objects(terrain, walls, obstacles, ect.), and likely a whole lot more information for a more involved A.I.

Again, you need something to have fairly global knowledge - I tend to call this the 'Environment'. Each AI has a reference to the Environment, and they can query it for opponents, obstacles, and such.

The environment also acts as a form of access control, by only letting individual AIs have the set of knowledge they should be aware of. For example, the enemy AI probably shouldn't know the location of the player when the player is hiding behind a wall, so the Environment runs cover-checks and keeps that data private as necessary...


Tristam MacDonald - Software Engineer @Amazon - [swiftcoding]


#10 Waterlimon   Crossbones+   -  Reputation: 2516

Like
0Likes
Like

Posted 23 July 2013 - 09:43 AM

I have a class i have named "AbstractCollider".

 

It represent ANY colliding object in the world, and my primary motivation for having it was to be able to use a broadphase to find potential collisions.

 

It contains:

{

ColliderType (sphere, terrain, projectile...)

ColliderID (so its like 5th sphere, 1000244th projectile...)

BodyID (so the broadphase knows where it is)

...

}

 

Now, when i have 2 of those (potential collision), i look up a collision detector class from a 2D grid based on the types of the 2 colliders. This means i have classes like SphereToSphereCD, SphereToProjectileCD, TerrainToProjectileCD... for each type pair (i reuse the objects when its the same 2 types but different order) all implementing virtual void detectCollidions(Collider&, Collider&)

 

They then dump the detected collisions to a big list which i then iterate through and apply forces and stuff (collision resolution). The collisions contain information like depth of penetration, collision normal, the colliding bodies ids (the 'abstract' ones), collision location...

 

 

That allows having multiple types of objects collide with each other without doing it in O(N^2) (which wouldnt require this layer)

 

Now, to act on those collisions, you need some kind of "collision callback" system which allows you to add in a handler that is called for collisions. This handler could handle all collisions, or it could handle collisions with a single object (the first needs a single reference in the physics system, the second needs every object to store their own "collision handler" reference) depending on what you need. The more specific ones need more memory and the less specific ones need more checks and branching in the handler since it needs to deal with everything. I would use a CollisionHandler class that again implements a virtual method.

 

Now, that allows you to know when a collision happens, and which 2 physics bodies it happens between. If the bodies are the same objects as the game objects (as in you have "Player" be a shape that can collide) thats all you need, but in a more flexible system the colliding 'shapes' will only be a part of the entities and you cannot identify the entities from them. So, you need the shapes or the abstractcollider objects to tell what entity owns them. This can be a simple entity ID.


o3o


#11 AllEightUp   Moderators   -  Reputation: 4195

Like
0Likes
Like

Posted 23 July 2013 - 05:08 PM

 

So, you are in one of the two objects.  If the object you are running from is a projectile or whatever, they just call a "take damage" function on the target object (target/dest is well understood from the point of view of the projectile).  Static indestructible objects ignore the call, player vehicles take the given data and apply it via some rules system.  If on the other hand, the first object was a player vehicle it calls "collide" on the other object using itself as a parameter.  A "projectile" implements collide by simply calling "take damage" on the source.  It is completely circular logic but the idea is that the "subject" is always correctly dealt with even if it takes 2 virtual function calls to get it done.  A vehicle to vehicle collide of course would do whatever is appropriate.


So if in your example the vehicle would just call collide on whatever the other thing was, and the other thing happened to be another vehicle, that other vehicle would also call collide on whatever it received, and you would get infinite recursion, right?
Your example is great when you have objects that know how to be a subject of collision, and apply some logic to the other thing. But, if an object type doesn't do anything, and just tells the other thing to handle the collision, and you somehow get two of those in collision... Do you code your objects to always know what to do to the other thing, and never let this case happen?

 

Here is a bit of example code:

struct Object
{
  virtual void     Interact( Object& target )=0;
  virtual void     Collide( Object& source )=0;
  virtual void     Apply( Effect& effect )=0;
};
 
struct MyCar
{
  virtual void     Interact( Object& target)       {target.Collide( *this );}
  virtual void     Collide( Object& source )       {DoCollision( this, source );}
  virtual void     Apply( Effect& effect )         {ApplyEffects( effect );}
 
};
 
struct Projectile
{
  virtual void    Interact( Object& target )       {target.Apply( mEffectData );}
  virtual void    Collide( Object& source )        {source.Apply( mEffectData );}
  virtual void    Apply( Effect& effect )          {... effect collides with effect??? ...}
};

So, basically if you have a contact pair, the 3 possible cases are:

 

car versus car

  Interact calls car.Collide( otherCar ) which in turn calls the physics response code.

projectile versus car

  Interact calls car.Apply( projectileData ).

car versus projectile

  Interact calls projectile.Collide( projectile ), but the projectile bounces it back as a car.Apply( projectileData ).

 

Hopefully this makes more sense than the prior explanations.  Each class of object can take care of the actions appropriately and of course you can extend to handle other sorts of results as needed, though with the three functions, and generic rules systems, those two items are actually usually enough.  (NOTE: I may have goofed this somewhere, been a while and it is a bit "odd" as mentioned so it's easy to oops it the first time.  I'll correct it if you see anything wrong.)


Edited by AllEightUp, 23 July 2013 - 05:10 PM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS