Re: [Troll] Monsters With Items

["Kenneth W. Flynn" <flynnk@astro.umd.edu>]

At 10:46 PM 8/16/00 -0400, you wrote:
>Warning: The following is a technical discussion.  It probably won't make
>sense without knowledge of OOP, C++ and Troll Bridge.

Add patterns to that, and you have a good warning for this message.  Also, 
for the sake of sanity, I'm going to use Java terminology (i.e. say 
"interface" rather than "pure abstract" or "pure virtual."


>In reading _Game Architecture and Design_, I've been thinking about the
>TrollSkeletalTrollWithItem.  This class annoys me.  The problem is what
>I really want is TrollMonsterWithItem and have the monster be a skeletal
>troll in this case.

What you are saying here, although you may not realize it is that you want 
the Troll class to be a component class, and you want to "decorate" it with 
additional jobs (carrying a key,  in this instance).  This is a "textbook" 
example of the Decorator pattern (GoF, p. 175).

In this case you should have an abstract base (TrollMonster most likely), 
this is called your "Component" class in GoF's Structure diagram.  A 
ConreteComponent would in turn be a SkeletonTroll.  You would then 
(optionally) have an abstract class derived from TrollMonster called 
TrollDecoratedMonster.  From that you would have MonsterWithItem 
(abstract), and then perhaps MonsterWithKey (although this is probably 
overkill, and not needed--I'm going to assume you don't use it).

So we have:

                          TrollMonster (Abstract) --------------+
                              |                                 |
            __________________/\__________________              |
            |                                    |              |
         SkeletalTroll                      TrollWithItem/\ ____|
                                                         \/

Ooh, drawing UML with ASCII art is fun.

You then forward the requests from TrollWithItem to the reference.

>The solution that occured to me while reading the book is to make a
>TrollMonsterWithItem class that contains a pointer/reference to another
>monster.  When ever anything is requested it forwards the request to the

Essentially, above.

>real monster class.  Unfortunately there are a couple of problems with
>this.  The main one is that the base TrollThing and TrollMonster classes
>aren't pure abstract.  TrollThing has variable such as sprite, x, y, and

You could pay the space cost and store the abstract information multiple 
times, to avoid making the base an interface (this would give you speed 
efficiency).  This is the tradeoff made in the example from 
GoF.  Personally, I find this distasteful, as I suspect you 
would.  However, it is worth considering, if even to reject it.

>dead.  It could be made purely abstract but then checkCollision incur a
>performance penalty as it looked up the functions and called them.
>Hmm... perhaps a single function call that got x, y, xsize, and ysize so
>that it had everything.  (There is then still the question of where to
>put the variables currently in TrollThing.  I could create a derived
>class but since TrollMonster would have to be derived from the blank
>TrollThing I'd either have to make the base TrollThing class virtual and
>use multiple inheritence or reimplement the information.)

One possibility to this problem is to define the classes like this:

class TrollMonster
{
  public:
   virtual int getX () = 0;
   //...
};

class AbstractTrollMonster : public TrollMonster
{
  public:
   virtual int getX () { return obtainX(); }

   int obtainX () { return x; }

  private:
   int x;
};

class BobTheHorrifyingCentipede : AbstractTrollMonster
{
  public:
   f () { // Do something, but calls obtainX() so as to not have a penalty
    }
};

This, however, does not really avoid the problem for external classes.  It 
merely cleans up subclass references.  Note that I avoid protected 
variables, for a cleaner solution, with no additional cost because all the 
method calls will be inlined.  Note that the current implementation of 
TrollThing uses protected.  This is not the best design, because it ties 
further implementations to relying on the availability of those protected 
variables.  There was some traffic on the C++ newsgroups about this (it 
might have been a Guru of the week), but protected is almost always bad, 
since you can write trivial inlined functions which preserve the interface 
(and the implementation to be changed later), while not costing 
anything.  If the data is moved, _such as to make these changes_, all 
accesses in the children will have to be changed.  Bottom line: protected = 
evil, with the exception of abstract class constructors.

>The other problem is that the code dynamically casts TrollThing objects
>to other types in the takeHit functions.  So the TrollMonsterWithItem
>would need to be derived from TrollMonster.  Unfortunately there is some

This is common, and is part of the pattern above.

>additional complication caused by the TrollStandardMonster and
>TrollUndead classes.  These probably shouldn't be derived classes instead
>have a bitfield of monster attributes.
>
>Another solution is to create a template TrollMonsterWithItem and have
>the compiler do the work.  So insted of TrollSkeletalTrollWithKey, I'd
>create a TrollMonsterWithItem<TrollSkeletalTroll>.  Unfortunately the
>current monsters have varying constructors.  I could perhaps create a
>generic constructor and then call an initialize function with the extra
>arguments.

You could do make a mess with specializations that call the appropriate 
constructors, but you end up not allowing the compiler to do the work, 
after all.  I'd rather avoid templates, especially when this doesn't feel 
like the right situation to use them.

>(This problem applies to the TrollItem as well.  Currently TrollItem has
>a cost variable when it really shouldn't in my opinion but I ran into
>the above issues.)
>
>Dennis Payne
>dulsi@identicalsoftware.com

Alright, so the fundamental issue is increased overhead in the calling of 
the getX(), etc. functions, if they are made into part of an interface, 
rather than implemented in the base abstract class (which is now an 
interface).  We don't want to have the increased overhead on simple lookup 
calls, which will have to be passed through several calls.

The first possible solution is to make the decorator take an 
AbstractTrollThing instead of a TrollThing in it's constructor, and then 
call the function non-virtually.  This prevents a double virtual lookup 
(1/2's the issue).  So instead of a stack of:

TrollWithItem->getX() (virtual dereference)
{
  TrollMonster->getX() (virtual dereference)
}

we have:

TrollWithItem->getX() (virtual dererence)
{
  AbstractTrollMonster->obtainX()  (explicit call)
}

The problem is that we cannot have a Troll with both a key and a bomb, by 
simply dynamically nesting two instances of the decoration (one of the 
advantages of the pattern).  We could always make it TrollWithItemS, if 
that is needed.

Is there still a performance penalty?

Strousup, 37:  "This virtual call mechanism can be made essentially as 
efficient as the 'normal function call' mechanism."

If the decorators cannot be nested, then the penalty is essentially zero.

class TrollMonster
{
  public:
   virtual int getX () = 0;
   //...
};

class AbstractTrollMonster : public TrollMonster
{
  public:
   virtual int getX () { return obtainX(); }

   int obtainX () { return x; }

  private:
   int x;
};

class TrollWithItem : public TrollMonster
{
  public:
   TrollWithItem (AbstractTrollMonster mon) : monster(mon) {}

   virtual int getX () { return monster.obtainX(); }

  private:
   TrollMonster monster;
};

Of course, I think you should simply change monster.obtainX() to 
monster.getX() and then do timings to find out that the performance penalty 
is probably tiny anyway, and that this was all a waste of 
time!  :)  Without profiled data saying this penalty means anything, I 
wouldn't bother making the class hierarchy more complicated.  You do pay a 
design and flexibility cost, that probably is not made up in performance.

Another, simpler solution:

class TrollThingInformation
{
  public:
   int getX () { return x; }

  private:
   int x;
};

class TrollThing
{
  public:
   TrollThingInformation* getInfo() { return info; }

  protected:
   TrollThing (TrollThingInformation* shared_info) : info(shared_info) {}

  private:
   TrollThingInformation* info;
};

class TrollMonster : public TrollThing
{
  protected:
   TrollMonster(TrollThingInformation* shared_info) : 
TrollThing(shared_info) {}
};

class TrollMonsterWithItem : public TrollMonster
{
  public:
   TrollMonsterWithItem (TrollMonster component)
    : TrollMonster (component.getInfo())
   {}

  private:
   TrollMonster monster;
};

The information pointer is duplicated among the hierarchy, and wastes some 
space.  This is the implementation of the method I suggested considering, 
but did not really like.

This is also your idea for obtaining all the info at once, and could also 
be modified with the abstract class to remove the duplication and have two 
methods that did the same thing.

My suggestion: don't care about this penalty, unless you really see it.  If 
you really see it, go with the decorators only taking non-decorated classes 
as arguments.  But if you don't care about the penalty, then the rest of 
your heirarchy can remain intact.

Summary:
* Buy GoF book.
* Don't worry about virtual function lookup penalities, compilers can 
easily make these not exist
* Profile the code before making efficiency-only changes.

Later,
Kenn


------------------------------+-------------------------------
Kenneth W. Flynn              | Graduate Fellow
flynnk@astro.umd.edu          | Department of Astronomy
www.astro.umd.edu/~flynnk     | University of Maryland
------------------------------+-------------------------------