Re: Double Dispatch Problem: Mobile Creatures and Projectiles in a Game World

On 28 Mar 2007 13:22:10 -0700, Aaron J. M. wrote:

I'm designing a game, and I've come across a problem that's similar to
the one
listed here (Google Groups):
http://groups.google.ca/group/comp.object/browse_thread/thread/4a5c70e3560388c8

I have a World, and in this world are Creatures and Projectiles. Both
of these
have a location, are able to move around somehow, and can collide with
each
other. Creatures also create Projectiles which get added to the
World.

For that reason I thought about having both of them be subclasses of a
class
Mobile. In addition to sharing behavior, Mobile is convenient because
the
World only has to keep one big list of Mobiles instead of a list of
Creatures
and a list of Projectiles.

1 N 1
World --------> Mobile <----\
has A 1| | collides with
| \------/
|
/----------^----------\
| |
| 1 N |
Creature -----------> Projectile
shoots
(Did Google Groups take away the fixed width font option?)

The problem is when Mobiles try to collide with each other. Two
Projectiles
colliding doesn't do anything (they pass over each other) and neither
does two
Creatures colliding (they don't move). It's only when a Creature and
a
Projectile collide that something interesting happens (the Creature is
hit).
I couldn't really do that with Mobile without either double dispatch
or the
Visitor pattern.

To avoid that problem I can just have World hold two lists: one of
Creatures and
one of Projectile. But...then I'd need two lists. That might not be
a bad
thing, but it is something extra the World has to take into account
and I'm also
lazy.

What do people here think about this?

You would probably need a better structures than plain lists. Collision
detection with many objects will be O(n²). Further, what happens with
tripple collisions? For example, two creatures lock each other while a
bullet hits both? That's O(n³) etc.

The issue of interaction, yes, it is symmetric double dispatch:

Collide (X, Y) is equivalent to Collide (Y, X)

That reduces the number of variants, but still.

You are silent about what drives your world. Are mobile objects
asynchronous active objects (like threads). Is it single threaded with
world state changed stepwise. How many actions an object may perform per
one step? Such decisions will certainly have influence on the design. For
example, in the case when each object performs one action per turn Creature
would perform Collide with Bullet for itself and change the state of Bullet
to Has_Been_Collided to prevent Bullet from colliding the same object (and
other objects) again.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de
.

Relevant Pages