Wizards and warriors, part three

Posted on by

So let’s digress for a few episodes here. We’ll temporarily leave aside the problem of how we can have both a Player that has a Weapon and a Wizard that has a Staff. (Or Dagger.) Supposing that we can figure out how to get that all represented, here’s another problem. Suppose we’ve also got Werewolf and Vampire classes that are a kind of Monster. We want a rule that says that if a Warrior tries to hit a Werewolf after midnight then the probability of success is lowered. (Wizards have no such penalty because… magic? Work with me here.)

Wait a moment — isn’t it always after midnight? When could you safely feed a mogwai, anyway?

Though that is a fascinating problem I’m sure, that’s not the problem I want to talk about today. The problem for today is: where exactly does the code go that determines whether the Warrior successfully hits the Werewolf? We have four classes involved: Player, Warrior, Monster, Werewolf. Somewhere there is a method, let’s call it Attack; what does that method look like?

Well, we’re object-oriented programmers programming objects in an object-oriented language; methods are the verbs and classes are the nouns, the player is the thing doing the attacking, so plainly Attack needs to be a method on Player. Since the rule for a Warrior is evidently different than that for a Wizard, it had better be virtual:

abstract class Player
{
  public virtual void Attack(Monster monster)
  {
    // Basic rules go here
  }
  ...
}
sealed class Warrior : Player
{
  public override void Attack(Monster monster)
  {
    if (monster is Werewolf)
       this.ResolveWerewolfAttack((Werewolf)monster);
    else
       base.Attack(monster);
  }
  private void ResolveWerewolfAttack(Werewolf monster)
  {
    // Special rules go here
  }
  ...

I don’t like it.

Fundamentally, Attack takes a compile-time-typed Player and an Monster, and then resolves the attack based on the runtime types of the two arguments. The virtual method mechanism dispatches the method call based on the runtime type of only one of the two arguments; that method is then left to its own devices to do a second dispatch by interrogating the argument’s runtime type explicitly.

Why is Player so special that it gets to have the dispatch handled by the language itself?

Designers of method resolution systems call C# (and C++, and Java, and many similar languages) “single dispatch” languages. That is, there must be one very special argument, and the method which is invoked at runtime is determined by the runtime type of that argument, and the compile time types of all the other arguments. That argument in all the languages that I mentioned is so special that it gets a keyword reserved for it — this — and the argument appears nowhere in the method declaration, rather than in the argument list with the second-class citizen arguments who only matter for their compile-time types.

That’s why our solution seems so inelegant in C#; in order to solve this problem elegantly we’d need a language that supported double dispatch.

Before I go on, a quick jargon note. By dispatch I mean making a decision, either at compile time or runtime, about which method to invoke among several choices. By single, double or multiple dispatch, I mean that the decision is based on the runtime type of one, two, or several arguments. By virtual dispatch I mean the specific technique that C# uses to achieve single dispatch: a method invocation looks up which method to actually invoke in a table associated with the receiver. (“Virtual” is an unfortunate term; it would have been more clearly called an “indirect” method call, but we’re stuck with it.)

C# does not support double dispatch, but we can emulate it like this:

abstract class Player
{
  public abstract void Attack(Monster monster);
}

sealed class Warrior : Player
{
  public override void Attack(Monster monster) 
  {
    monster.ResolveAttack(this);
  }
}

sealed class Wizard : Player
{
  public override void Attack(Monster monster) 
  {
    monster.ResolveAttack(this);
  }
}
 
abstract class Monster
{
  private void ResolveAttack(Player player) 
  {
    // default implementation goes here
  }

  public virtual void ResolveAttack(Warrior player) 
  {
    this.ResolveAttack((Player)player);
  }

  public virtual void ResolveAttack(Wizard player) 
  {
    this.ResolveAttack((Player)player);
  }
}

sealed class Werewolf : Monster
{
  public override void ResolveAttack(Warrior player) 
  {
    // special logic for Warrior vs Werewolf goes here
  }
}

sealed class Vampire : Monster
{
}

Follow the logic along; suppose we have

Player player = new Warrior();
Monster monster = new Werewolf();
player.Attack(monster);

We have no compile-time information about how to dispatch this to the appropriate method. We invoke the abstract method Player.Attack(Monster), which at runtime does virtual dispatch to Warrior.Attack(Monster). That method calls Monster.ResolveAttack(Warrior), which does virtual dispatch to Werewolf.ResolveAttack(Warrior) and we’re set; we’ve dispatched to the method that has the logic we need.

If instead we had

Player player = new Wizard();
Monster monster = new Vampire();
player.Attack(monster);

Then again, Player.Attack(Monster) does virtual dispatch to Wizard.Attack(Monster), which calls Monster.ResolveAttack(Wizard), which does virtual dispatch. Vampire did not override that method, so we get the base class implementation, which in turn does a call to Monster.ResolveAttack(Player), and we get the no-special-rules logic.

This pattern — which has many, many variations — is called the Visitor Pattern. Whether you’ve seen this pattern before or not, you could be excused for being confused by the name; it is by no means clear why emulating double dispatch using a series of single dispatch calls has to do with “visiting” anything.

One of the most common usages of this pattern is for the scenario where you’ve got a complex tree where tree nodes can be of many types, and you wish to traverse the tree — that is, visit every node in the tree — taking some actions or performing some computations as you go. The “double dispatch” part of it is that the actions you take as you visit nodes in the tree can depend on the runtime types of both the nodes in the tree, and the code performing the action.

This pattern is very common in compilers, because of course we often have trees with lots of different kinds of nodes in the trees (expressions and statements and types…) and we wish to take different actions on those trees (optimizing, lowering, generating code, seeking error cases). The Roslyn C# and VB compiler semantic analyzers make heavy use of this pattern.

OK, so, have we actually solved the problem of dispatching to the right logic for our warrior vs werewolf problem? This solution works, but it has some major shortcomings.

  • It seems a bit weird that we started out saying that “attack is a verb on players, so the logic should go in the player class hierarchy”, and then ended up doing exactly the opposite; all the code to handle the basic and special attacks ended up in the Monster hierarchy. Of course there are many ways we could reorganize the code to fix that, but still, it’s odd. Basically, the Monster is what in Roslyn would be the analyzer, and the Player is the syntax tree, so it makes sense that the fancy logic would go in the Monster. But it seems completely arbitrary in our example whether the Monster is the visitor or the visitee.
  • Holy goodness look at all the mechanisms! I’ve already said recently that I think that it’s ok to be WET instead of DRY when you are building a mechanism, but still, there is an absolutely huge amount of overhead here. And this is a very simple case! For Roslyn we made a little type description language out of XML and then built a code generator to automatically spit all the mechanism code for the visitor passes, because we didn’t trust ourselves to always get all the bits of the visitors right when making changes to the syntax nodes. It seems likely that all this mechanism code will overwhelm the reader, obscure the business logic, confuse the novice programmer not used to the pattern, and provide ample opportunity for bugs.
  • Did I mention that we also care about the runtime type of the Weapon being used? And the Location that the battle is taking place in? And the Weather. And… OK, maybe some of these do not require the full mechanisms of virtual dispatch, but suppose we did want to do multiple dispatch? You can probably see how there are ways to extend this pattern to use more single dispatch calls to emulate triple, quadruple, and so on, but it’s not going to be pretty.

This pattern works, and like I said, I’ve made heavy use of it to great effect in the past. But it seems both very heavyweight and very inflexible in a lot of ways. Is there an easier way to get multiple dispatch in C#?

Next time on FAIC we’ll look at a completely different way to do multiple dispatch in C#.

32 thoughts on “Wizards and warriors, part three”

  1. It seems to me that you may have `ResolveAttack()` in a few places where you mean `Attack()`. Namely in the `Wizard` declaration and in the two examples of usage.

    Reply ↓

  2. So, how about this design (sorry for it being in Java, my C# is a bit rusty):

    enum PlayerClass { Warrior, Wizard; }
class Player {
    private final PlayerClass class; //Add a getter and set via constructor
}

enum MonsterClass { Vampire, Werewolf; }
class Monster {
    private final MonsterClass class; //Add a getter and set via constructor
}

class AttackHandler {
    public static void doAttack(Player player, Monster monster) {
        switch(player.getClass()){
        case Warrior:
            switch(monster.getClass()){
            case Werewolf:
                attackWarriorWerewolf();
                break;
            default:
                attackDefault();
                break;
            }
            break;
        default:
            attackDefault();
            break;
        }
    }

    private static void attackWarriorWerewolf(){ //Special logic goes here }
    private static void attackDefault(){ //Default logic goes here }
}

    Not exactly OOP, but it nicely separates out the business logic from those classes and keeps it in one place. Can also call the doAttack method from an attack method on Player, if you want to keep that player.attack(monster) that fits your OOP idea of nouns and verbs. Combination with the original type hierarchies is also possible, if needed, just have the getClass() return the correct value for the subclass instead of using a field or do a switch on the runtime type if your language supports it.

    Reply ↓

  3. Reflection! That way we can do runtime-type-based dispatch for every parameter.
    Seems like it could get messy, but it also seems like a mechanism we could separate from the policy code. I’m hoping you have a simpler solution, though!

    Reply ↓

    • You’re probably gonna want to avoid reflection for a real-time game scenario, it is lightning fast these days, but it is likely to be faster without doing this. Imagine a Wizard attacking few thousand Werewolves at once for example.

      Reply ↓

      • Yeah, the suggestion was a bit tongue-in-cheek.
        Although I’m thinking that by the time you get up to attacking 1000 enemies at once, you might start treating it as a group instead of trying to resolve individual attacks one at a time.

        Reply ↓

  4. What bothers me here is that the Monster class needs to know every kind of player that can attack it. Ideally it should be agnostic to which kind of player is attacking, and this logic should be handled by a third party.

    Reply ↓

    • That’s the whole point of special case “midnight fight”.

      IMO, the article example presents failure, because in single thing “attack” resolution it tries to handle vulnerability/resistance (to moon, silver, fire, etc) and damage/attack kind/properties (silver, magic, etc).

      The simplification “Werewolf is hard to hit in moon light by non-magic attack”, results in such failing implementations. It’s like wondering why the hell planet path/orbit is so complex in geocentric model, without investigating if its correct 🙂

      Reply ↓

    • I think the way I’d do it is to have logic in both the werewolf and the warrior. The warrior would check the type of the monster it’s attacking and then maybe lower the chance to hit. Then call something in the monster that calculates chance of getting hit based on some state (like weather or whatever). Then combine them in the attack method.

      Reply ↓

      • I would split attack at 2 main parts: First is Hit is generated by Warrior based on Monster defenses/state – then it is passed to Monster/Werewolf for handling (like reduction of probability, redirection, etc). Final value is resolved by Warrior. Then Damage is generated by Warrior and passed to Monster for similar modifications (resistance/vulnerability, etc) and resolved final Value.

        Reply ↓

  5. The approach I would favor would be to have a list of rules, each of which can decide whether anything interesting may happen for a given combination of attacker, weapon, and target. To avoid having to have every attack parse through all rules, rules could be stored in a queue, with each attacker maintaining a queue pointer and a list of all rules that could potentially be applied to it, a list of rules that are applicable to it when using its currently-applied weapon, and a dictionary (keyed by target) of lists of rules that are applicable when using the currently-applied weapon against any given kind of target. Each attack would start by checking the queue to see if any new rules needed to be parsed and add any rules in the queue to the appropriate lists and/or dictionary. If an attack represented the first attempt to use a particular weapon on a particular monster, the list of rules applicable to the weapon would be filtered for those applicable to the monster, and a list of those that were applicable would be added to the monster’s dictionary entry.

    Any kind of attacker, target, or weapon that was registered to the game would be able to add suitable rules at the time of its registration. Thus, one could add to the game a `HolyMoonSword` which would have a +8 attack bonus when used by clerics against werewolves, but would otherwise behave as a low-grade shortsword, without needing to have any code in the cleric or werewolf classes which knows anything about it, and demons could be made incapable of wielding that weapon without needing any code in the weapon class. If rules used a priority structure, one could also have the Werewolf King be exempted from the special powers of that sword without requiring that anything in the attacker or weapon classes know about it.

    Reply ↓

    • That’s pretty much how it works in Inform 7 (http://inform7.com), where “rulebook” is a first-class type. You write rules like:

      Rule for attacking a werewolf when the time is after midnight: decrease the chance of success by 20.

      Rule for attacking a werewolf which is not the Werewolf King when the player is a cleric and the player wields the Holy Moon Sword: increase the attack power by 8.

      … and then the compiler finds all the “attacking” rules in your code and sorts them into the attacking rulebook, using various heuristics and manual overrides to decide the order.

      Reply ↓

  6. The way to get multiple dispatch is to not put the logic on any of these objects, and instead have it belong to a quasi-global object that owns all of the Player and Monster objects that might interact.

    Reply ↓

  7. The easiest way: dynamic keyword
    My sugestion for the type safe way: Covariant interfaces, it works by… Wait, would be a spoiler?

    Reply ↓

  8. My favourite multiple dispatch mechanism in C# is casting everything to dynamic and calling a helper method which is overloaded for the necessary combinations of its arguments. I can’t vouch for its speed, though, and it doesn’t work well when you want to chain your methods.

    Reply ↓

  9. Pingback: Basic OOP is easy, isn’t it? | gerleim

  10. Pingback: The Morning Brew - Chris Alcock » The Morning Brew #1853

  11. Pingback: Dew Drop – May 5, 2015 (#2007) | Morning Dew

  12. Just wanted to chime in with two things:

    1) This is a fantastic series and I look forward to more!
    2) I love the new hummingbird picture at the top.

    Reply ↓

    • Thanks! The banner photo is usually of where I am at the moment, and I’m working out of my kitchen right now; there is a steady stream of two or three Anna’s hummingbirds constantly coming up to my feeder.

      Reply ↓

  14. Pingback: Wizards and warriors, part four | Fabulous adventures in coding

  15. With single dispatch, we get a special “this” argument.
    For double dispatch, we would get two special arguments, “this” and “that”, right? And for multiple dispatch, there would be a special array called “yall” or something?

    Still, where should the code go? If we dispatch on Player, Monster, Weapon, and Weather simultaneously, the special case for (Warrior, Werewolf, Sword, SometimeAfterMidnightStormyWeatherWithBloodRainAndAHintOfSulphur) might as well be in a completely separate class altogether.

    Reply ↓

  16. Pingback: Wizards and warriors, part five | Fabulous adventures in coding

  17. Pingback: Wizards and warriors, part two | Fabulous adventures in coding

Leave a reply to ericlippert Cancel reply