Prev: Separation of concerns
Next: Double Dispatch Problem: Mobile Creatures and Projectiles ina Game World
From: Aaron J. M. on 28 Mar 2007 16:22
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?

Thanks,

Aaron J. M.

From: Dmitry A. Kazakov on 29 Mar 2007 04:18
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
From: Aaron J. M. on 29 Mar 2007 08:34
On Mar 29, 2:00 am, Ed Wegner <ed.weg...(a)tait.co.nz> wrote:
> To address the collision logic you describe, I'd add an Association
> class off the "collides with" reflexive relationship between instances
> of Mobiles. Let's call it "Collision". When a Collision occurs, the
> first thing it checks is whether the colliding Mobiles are one of each.
> If so, execute the "Projectile hits Creature" logic.

But how would a Collision check whether the colliding Mobiles are one
of each
without downcasting, double dispatch, or the Visitor pattern?

I might end up doing the Visitor pattern, but I want to put it off for
now to
see if I can find an easier solution.

On Mar 29, 5:18 am, "Dmitry A. Kazakov" <mail...(a)dmitry-kazakov.de>
wrote:
> 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.
> <snip>
> 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.

Well, I meant lists as in a generic collection, though that's besides
the point.

I didn't mention what's driving the world because I was hoping that I
could
design the collision interactions of Mobiles independant of that.
However, I am
only considering collisions between at most two Mobiles at a time. I
am also
intending that my World manage when the Mobiles act by telling them
all to
move() when the World is given the message update(), which may come
from a Clock
if the game is realtime or from the UI if the game is turnbased.

From: Daniel T. on 29 Mar 2007 08:50
"Aaron J. M." <ajmacd(a)ns.sympatico.ca> 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/
> 4a5c70e3560388c 8
>
> 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?

I don't think there is a "lazy" solution, you need two lists. Here's a
possible solution:

World<---Mobile

class World
+reportCreaturePostion( Point )
+reportProjectilePosition( Point )
+creatureAt( Point ): boolean
+projectileAt( Point ): boolean

class Mobile
+attachTo( World )

Mobiles tell the world where they are, and ask the world if there are
any creatures or projectiles at that location. If there are, the mobile
does what it knows it should do.
From: Aaron J. M. on 29 Mar 2007 13:45
On Mar 29, 9:50 am, "Daniel T." <danie...(a)earthlink.net> wrote:
> I don't think there is a "lazy" solution, you need two lists. Here's a
> possible solution:
>
> World<---Mobile
>
> class World
> +reportCreaturePostion( Point )
> +reportProjectilePosition( Point )
> +creatureAt( Point ): boolean
> +projectileAt( Point ): boolean
>
> class Mobile
> +attachTo( World )
>
> Mobiles tell the world where they are, and ask the world if there are
> any creatures or projectiles at that location. If there are, the mobile
> does what it knows it should do.

So, World keeps two lists (Creatures and Projectiles), and all
Mobiles
are able to attach themselves to a World. World would need the
methods
attachCreature(Creature, Point) and attachProjectile(Projectile,
Point)
in that case. I'd also have to change World whenever I wanted to add
a
new type of Mobile.

It might get more complicated when I want to get timing involved.
With
just one list in World I could give World the method update() which
tells all the Mobiles to move(). The two lists could be just as easy
since I could loop through both lists, but what if I want every
Mobile
to have a "speed" which affects the order in which they need to be
updated regardless of their actual class? I would have to introduce
a
third list that holds (references to) all of the Mobiles and loop
through that when I want them to move.

 |  Next  |  Last
Pages: 1 2
Prev: Separation of concerns
Next: Double Dispatch Problem: Mobile Creatures and Projectiles ina Game World