What's the best way to resolve a combinatorial explosion of interactions?

Question

One of the things I'm working on right now has some similarities to a game. For purposes of illustration, I'm going to explain my problem using an example drawn from a fictitious, hypothetical game.

Let's call it DeathBlaster 4: The Deathening. In DB4, you have a number of Ship objects which periodically and randomly encounter Phenomena as they travel. A given Phenomenon may have zero, one, or more Effects on a Ship that encounters it. For example, we might have four kinds of Ships and three kinds of Phenomena.

                              Phenomena
              ==========================================
Ships         GravityWell     BlackHole      NebulaField
------------  ------------------------------------------
RedShip       +20% speed      -50% power     -50% shield
BlueShip      no effect       invulnerable   death              Effects of Various
GreenShip     -20% speed      death          +50% shield        Phenomena on Ships
YellowShip    death           +50% power     no effect    

Additionally, Effects may interact with each other. For example, a GreenShip that is in both a GravityWell and a NebulaField may derive some kind of synergy between the generated SpeedEffect and ShieldEffect. In such cases, the synergistic effect is itself an Effect -- for example, there might be a PowerLevelSynergyEffect that results from this interaction. No information other than the set of Effects acting on a Ship is needed to resolve what the final result should be.

You may begin to see a problem emerging here. As a naive first approach, either every Ship will have to know how to handle every Phenomenon, or every Phenomenon will have to know about every Ship. This is obviously unacceptable, so we would like to move these responsibilities elsewhere. Clearly there's at least one external class here, perhaps a Mediator or Visitor of some sort.

But what's the best way to do that? The ideal solution will probably have these properties:

• It's just as easy to add a new Ship as it is to add a new Phenomenon.
• Interactions that produce no effect are the default and don't require additional code to represent. Convention over configuration.
• Understands how Effects interact with each other and is capable of managing these interactions to decide what the final result will be.

I've already decided what my approach will be, I think, but I'm interested to hear what the best-design consensus is. Where would you start? What avenues would you explore?

---

---

Follow-up update: Thanks for your responses, everybody. Here's what I wound up doing. My main observation was that the number of different Effects seems to be small relative to the number of possible Phenomena × Ships interactions. That is, although there are many possible combinations of interactions, the number of kinds of results of those interactions is a smaller number.

You can see that, for example, although there are 12 interaction combinations in the table, there are only five kinds of effects: modifications to speed, modifications to power, modifications to shield, invulnerability, death.

I introduced a third class, the InteractionResolver, to determine the result of interactions. It contains a dictionary that maps Ship-Phenomenon pairs to Effects (which are basically a delegate that performs the effect and some metadata). Each Ship is handed an EffectStack corresponding to the Effects it's experiencing when the result of computing the interaction is complete.

Ships then use the EffectStack to determine the actual result of the Effects on them, by adding modifiers to their existing attributes and properties.

I like this because:

• Ships never need to know about Phenomena.
• The complexity of the Ship-Phenomena relationship is abstracted into the InteractionResolver.
• The details of how to resolve multiple and possibly complex effects is abstracted away by the InteractionResolver. Ships only have to apply the effects as necessary.
• This enables additional useful refactorings. For example, the way in which a ship processes effects could be differentiated by making an EffectProcessorStrategy. The default might be to process all effects, but, say, a BossShip might ignore minor effects by having a different EffectProcessorStrategy.

Nodarse

Still no follow-up ? How have you solved this finally ? – Chaplain

Sounds like a good way to solve your problem. I only have one concern, won't your InteractionResolver end up knowing too much ? – Chaplain

Hmmm... well, it only needs to know one thing: the mapping of (S,P)-pairs to Effects. The actual logic of how an Effect works is wrapped up in the delegates themselves, which can be references to anything. – Nodarse

This is a classic datamodelling problem. The (correct) solution of decomposition of an m:m (many to many) relation as two 1:m relationships is routine to the point of triviality for relational database designers. – Decortication

Answer 1

An interesting potential option would be to use a variant of the Visitor Pattern.

Judith Bishop and R. Nigel Horspool wrote a paper about design pattern efficiency in which they explained various variants on the classic visitor pattern using C# 3 features.

In particular, I would take a look at how they work with delegates to handle the visitor pattern. Using a list or stack of delegates could potentally give you an interesting way to handle multiple effects from multiple objects, and be much easier to extend either side of the class hierarchy (add ships or add effects) without huge breaking code changes.

Bassarisk

Answer 2

Not quite an answer, but to me this fairly screams "properties pattern". There's a well-known yegge rant about this, I think it'll offer you some decent pointers.

http://steve-yegge.blogspot.com/2008/10/universal-design-pattern.html

Corroboree

Answer 3

This looks like the classical OOP polymorphism/visitor dilemma. However, your requirements make it easier.

Basically, I would create a base class Ship that all concrete Ships derive from. This class would have methods:

class Ship
{
  void encounterBlackHole() {}
  void encounterNebula() {}
  ... etc. ...
};

with empty default bodies. When you add a new Phenomenon, you just add new method with empty body. (The methods may have arguments, like coordinates or weight of the black hole etc.)

For the Effects and their interaction - I think you should add more information about how you want it, eg. are the interactions rare or usual, are they cumulative in some sort, are they confined to a limited set of variables they control ...

Landing

Thanks for the feedback. I clarified this with "No information other than the set of Effects acting on a Ship is needed to resolve what the final result should be." – Nodarse

Answer 4

Sounds like a classic multiple dispatch problem to me.

Elmore

Answer 5

Interesting question

In a way or an other, A ship will have to know what phenomena can affect it and a phenomena which effects it has on which ship.

This could be stored in an xml file parsed at run-time.

Maybe you could use the Decorator pattern to calculate the effects. You generate various phenomenas at run-time.

Suppose your ships implement an Interface IShip and everywhere in your code, you use IShips.

Now, suppose all your phenomena also implement the Interface IShip (required by the decorator design pattern).

IShip myShip = myShip.AddPhenomena(PhenomenaGeneratedByAFactoryForThisShip);

In the phenomena, you wrap the methods from the original ship, so you can perform modification to properties and all.

Also, if you use the strategy pattern you can generate any kind of phenomena you'd like.

Removing a phenomena, can be used by walking the pile of decorated ships you have, and rewrapping it, so I see no problem there.

As for the synergies, I think I would use a slightly modified phenomena, which works only if the target ship has all the phenomenas on itself.

Chaplain

Answer 6

either every Ship will have to know how to handle every Phenomenon, or every Phenomenon will have to know about every Ship.

I think this is the key to your problem and it's true if every ship-phenomena interaction is unique. In the table you created, that appears to be the case, so for n ships and m phenomena, you need to specify n*m interaction. You are right to smell a maintenance issue.

The only way out is to make ship-phenomena interactions not as unique by making the effect of phenomena depend on the properties of the ship. For example, we could say only ships built with strange-alumina will survive a black hole.

But having only one property doesn't buy you anything, you could've just as easily specified which ships are affected by black holes. The key is that multiple properties exhibit the same combinatorial explosion.

So ships built with strange-alumina will survive black holes, and ships built without can go faster. 1 Property allows you to specify 2 things (1 bit = 2 possibilities). Ships built with corbite engines will go faster in a warp zone. Ships with both corbite engines and strange-alumina will gain 50% shield in a nebula field, etc.

The addition of properties to ships allows you to avoid specifying how every phenomena interacts with every ship, and yet still have every phenomena and every ship exhibit an appropriate behavior.

If there are M ships, then you only need log2(M) properties to give every ship a unique behavior.

Isobath

I think this could be an idea, but won't it limit the possibilities somehow ? What if a ship needs to have some exceptions, special properties ? I am also not sure it respects the original spec, by introducing new properties. Adapt your code to the spec, not the other way around. – Chaplain

Answer 7

I think the answer of a problem is depend on how good the question ask.

I think the way to design is depend on what the question is(or the question will goes in the future)

you give a table, then I think the solution is maintain a table and query it.

python code here:(not tested and just shows for a example)

class Ship():
     def __init__(self,type):
         self.type=type
     def encounterPhenomena(self,type): # let Phenomena to process ship
         p = Phenomena(type)
         p.process(self)

class Phenomena():
     processTable = {}
     def __init__(self,type):
         self.type=type
     def process(self,ship):
         try:
             self.processTable[self.type](ship.type) #query the internal table to process ship
         except:
             pass #if Phenomena don't know this ship type then no process..
     def addType(type,processMethod):
         processTable[type]=processMethod #add new Phenomena, and add processMethod

def run():
    A = Ship(type = 'RedShip')
    A.encounterPhenomena(type='GravityWell');

If process method changed, simply modify the process method in the Phenomena class.

If you think ship need to know how to process Phenomena, then change process method into the ship class.

or you think there are other things not only Phenomena need to change status of ship(like other ships, shoal rock), you need to maintain a process table in ship class and make Phenomena one of it,

speak again, how to design is depend on the question its self.

Irma