The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

Resolving and managing interactions between objects

Although my current project isn't actually a game, it has fairly direct parallels. I'm going to explain my problem using an example drawn from a hypothetical game for the purposes of illustration.

Picture my new revolutionary game, GenericSpaceFighter 9000. In it, various Ship objects are flying through the Universe. On occasion, they encounter Anomalies. A given Anomaly has different Effects depending on what sort of Ship encounters it; e.g. RedShips are not affected by fire damage, whereas BlueShips don't get sucked in by gravitational Anomalies, and so on.

But here's the problem: to properly model these Effects in software, either Ships must know about all possible Anomalies, or Anomalies must know about all possible Ships. Either solution promotes coupling, which is bad. This suggests the need for the presence of an intermediary that can manage the interactions. Let's call this intermediary the InteractionMediator.

Three issues are nagging me:

1.) {Complexity.} It seems like the InteractionMediator will need to know about all possible Anomaly-Ship combinations -- the Cartesian product of all the M Anomalies and N Ships. It's worth nothing that Anomalies tend to affect most Ships in the same way (the case where an Anomaly-Ship combination is different for every Ship for a given Anomaly is very rare). This product (MN) is large and is feasible only for small M and N. What should I do to reduce the resulting complexity, and how should the interactions be kept to a manageable scope and size (that is, the number of interactions is approximately M)?

2.) {Bad solution?} In one sense, this still doesn't solve anything: InteractionMediator still has to know about all possible Anomalies and all possible Ships. Are there any better alternatives or things that I may have overlooked?

3.) {Design pattern?} Is there a design pattern for this? It seems like Mediator is the right way to go, but Mediator still requires knowledge of all possible combinations.

Any assistance is welcome. Thanks in advance. :)

- k²
Kyle Kaitan Send private email
Sunday, July 23, 2006
 
 
There's a 30-page section titled _Implementing Multiple Dispatch_ in the book _More Effective C++_ that describes how to implement exactly this (handle space-ship collisions).

There's a summmary at http://en.wikipedia.org/wiki/Multiple_dispatch
Christopher Wells Send private email
Sunday, July 23, 2006
 
 
I am an off-again, on-again programmer for Megamek, an open source Battletech game.  We have the same problem.  Although my Gang of Four book is on the wrong continent so I can't express the idea in terms of a design pattern, you can restrict the number of cases you have to worry about by introducing something like AnomalyEffects.  An AnomalyEffect knows how to do one particular thing to one particular ship (or class of ships -- if you're a good OO program you've got some CapitalShip running around somewhere and most instances of CapitalShips can be blowUpReallyGood(true) in the same way, right?). 

This allows you to funnel the combinatorics down.  For example, one thing you'll frequently want anomalies to do is damage the ship that gets caught in them.  But damage is hyper-specific to the actual ship design.  No problem, you write your damage engine object once and it allows you to add additional damaging anomalies and damagable ships without having to recode anything.  Your new BigFurrySpaceBunnyOfDoom anomaly just gets a new DamageEffect(100) and then you're off to the races.

You can also implement another level of funnels between things.  For example, its possible that you've got an Anomaly with its AnomalyEffects acting on your Ship.  Lets say you have another class which intercepts generic calls from the AnomalyEffects (like, say, damageShip) and does them in a specific fashion.  Maybe it knows the difference between a capital ship and a fighter, or maybe in this region of space there is some weird sort of pseudo-atmosphere which means that spacing part of ship doesn't result in explosive depressurization of the crew for whatever sci-fi reason you can come up with.  So if your BigFurrySpaceBunnyOfDoom fires off a CrewCuddlyKilling it might be mitigated by your HardenedKillers attribute this particular ship has earned.

Note that this doesn't exactly describe where in the class structure you would put your methods.  From my one year old memory, when we did it in MegaMek every entity was responsible for knowing how to take damage itself.  We also had a WeaponEffects class which we generally offloaded the "uh oh, that particular missile type does more than just bang with a certain parameter worth of cowbell" work to.  Blasting somebody was as simple as hitting them with a WeaponEffect and passing the WeaponEffect through, if I recall correctly, a couple of listeners which might end up mitigating it or enhancing it (anti-missile countermeasures, "uh oh you're in space if you take internal structural damage kiss your rump goodbye", what have you).  The combinatoric possibilities of missile types times unit types available in BattleTech runs into the hundreds of thousands...  we probably had to code about, oh, 20 distinct "cases" to handle that.  (Note there are a heck of a lot more things happening in a Battletech game than resolving missile damage, but it is a pretty core function.)  Anyhow, depending on how you funnel things you end up with a complexity of log(M)+log(N) instead of M*N

Hope that helps.
Patrick McKenzie Send private email
Sunday, July 23, 2006
 
 
I read a book called Prefactoring by Pugh, and in the book he describes something he calls the spreadsheet problem.  Basically, it is what you are describing, each object from one group interacts differently with objects from the other group (one is rows, one is columns, hence the "spreadsheet" analogy).  His suggestion was to put the logic in the group of classes which you intended to add to the most often.  So if you are adding a lot of ships, then you put the logic to deal with the interaction in the ship, and vice versa.  I think his reasoning boiled down to not having to spread code to deal with a new ship in every anamoly (hence decentralizing the new code).  However if you intend to have more new anamolies, then you put it there, so you don't have to spread it through all the ships. 

I am not sure if that will help your situation because a) you might be adding to both groups and b) you might not even know which group you are going to add to more often.  The other option is to encapsulate the interaction of a specific ship w/ a specific anamoly into it's own class.  The trouble with that is that you end up creating M*N of those classes.  Whatever you do end up doing, I think you want to make sure you optimize for whatever you are going to be adding the most of, ships, anamolies, or interactions. 

This is an excellent question...I am not really sure.
Joshua Volz Send private email
Monday, July 24, 2006
 
 
Another option is just to write it as you describe it.

You have a ship class and a fire class. From an ident provided by the specific implementations of the interfaces, you look up a suitable interaction class in a map (or a default type if it can't find a specific one) and hand it its two instigators and off it goes and resolves the interaction.

It could be a factory method that makes you an interraction object which can do the interraction on creation and then hang around to do all the on-screen effects and deletes itself when completed.

If you don't want to go near factory systems, you could just store function pointers in a sparse 2D array and provide a default.


The thing is that, in general, you probably don't need to know the type of ship involve in an interraction, once you're inside the interaction -- You're (say) just going to damage it; which is a pretty generic operation. So most interractions don't need to know the specifics of what they're operating on.

On the occaisions where you're doing something special, it's probably only for a couple of ship classes, so in that interraction it's not excessive work to dynamically cast pointers in that case.
Katie Lucas
Monday, July 24, 2006
 
 
Let's first differentiate between
a) Effect producer (anomalies)
b) Effect value (the effective effect)
c) Effect consumer (ships)
The point is to base the interactions not on object combinations (M*N), but on effect types (T << M*N)

For any given type of effect, both producers and consumers become a percentage value from 0 (0%) to 1 (100%).

Producer: 0 means it does not produce an effect of this type. 1 means it does produce a worst-case (black hole==maximum gravitation).

Consumer: 0 means it is invulnerable to this effect. 1 means the effect will produce the worst possible damage.

If a producer interacts on a comsumer, both values are simply multiplied, resulting in a new value between 0 and 1. Obviously 0 means: No effect, 1 means: Maximum damage.

There is a default consumeEffectX for any effect type X, given this value as a parameter and reacting on defined thresholds. It can be overridden by any consumer with a specific method. E.g. fire will have different effects on a fuel transporter than on a water transporter...

Introducing a new effect should default the value to 0 in all existing producers and consumers. I.e. introducing a new effect type does not change the existing game behaviour; anything needs to be coded explicitely.

There can be all types of manipulations be introduced: A produceEffectX for producers to dynamically calculate the values, values in both consumers and producers can be incremented on decremented, depending if the shields are up or down, the final value can be modified, e.g. by the distance, before given to the consumer, etc.

And you don't need specified anomalies, of course. They can produce any possible combinations of effect types, including a cosmic killer where all producer side values are on 1. You don't even need to differentiate, any object can be a producer and a consumer at the same time.
Secure
Monday, July 24, 2006
 
 
I/we use a method taken from one of my circuits classes I had in my college days.

We build truth tables which are boxes.  Along the top edge of the box, we put all the possible ships.  Along the left edge we list all the possible damage that can happen.

We build a grid out of the box and put 1s and 0s in the boxes where things can and can not happen respectively.

There are techniques to reduce the truth tables and out of this reduction you get your logic you can implement in code. 

One such reduction method is called Karnaugh maps.  Google on Karnaugh maps and you should find some good reads on this.  In circuit theory, we called this "K-Maps."

K-Maps take advantage of patterns that can be seen in truth tables to create states.  States are used to reduce the actual code you write -- logic reduction/checking.
~Eric
Monday, July 24, 2006
 
 
You're all making it way too complicated with all these "factories" and things "knowing" other things. Ships have fire resistance values, and gravity resistance values. A fire anomoly does BaseDamage times (1.0 - ship fire resistance). That's how games have done it since paper role playing days.  Keep it simple, implement it and move on.
(Former) Game Programmer Lou
Monday, July 24, 2006
 
 
The problem with the "Ships get damaged according to their resistance to that Anomaly" idea is that the range of possible interaction behaviors is not a simple linear "not damaged --> fully damaged" scale. There could exist an Anomaly that, for instance, automatically kills certain Ships passing through it, but grants a speed bonus to other kinds of Ships, and decreases the weapon effectiveness of a third class of Ships.
Kyle Kaitan Send private email
Monday, July 24, 2006
 
 
I would suggest that you think about how people interact. When two people meet for the first time, we can make predictions about how they might affect one another. Let's say that person A is an obnoxious snob with foul body odor. Let's say that person B is your best friend. Nkowing what you do about your friend, and knowing what you do about the obnoxious snob, couldn't you predict, in general terms, knowing the circumstances under which they will meet, the effect that they will have upon one another? You don't need an MxN lookup table to figure out how the people will interact. The key, I suspect, is in modeling the objects not as whole objects, but as collections of individual attributes whose interacts can be modeled more simply. For example, if person A is sensitive to odors and person B smells bad...Or if person A likes music and person B likes art... I haven't thought this all the way through, but I think the MxN solution only works for very small numbers of classes.
Smoothie
Monday, July 24, 2006
 
 
>>> It's worth nothing that Anomalies tend to affect most Ships in the same way (the case where an Anomaly-Ship combination is different for every Ship for a given Anomaly is very rare). ... What should I do to reduce the resulting complexity, and how should the interactions be kept to a manageable scope and size (that is, the number of interactions is approximately M)?

Implement default processing for specific anomalies for generic ships:

  //implement default action of gravitational anomalies on most kinds of ships
  void collision(GravitationalAnomaly anomaly,AbstractShip ship)
  {...}

Implement non-default processing for specific anomalies for specific ships:

  //non-default action for gravitational anomalies on red ships
  void collision(GravitationalAnomaly anomaly,RedShip ship)
  {...}


>>> InteractionMediator still has to know about all possible Anomalies and all possible Ships. Are there any better alternatives or things that I may have overlooked?

Create a dumb global map, which maps anomaly-type plus ship-type pairs to specific colision-function implementations, and to which any class can add elements.

When you create a new anomaly-type, then:

* Define the generic collision-function for this new anomaly-tpe with a generic ship-type, and add this collision-function to the map
* Define any specific (non-default) collision-functions for this new anomaly-type with any specific ship-types, and add these collision-functions to the map

When you create a new ship-type, then:

* It's automatically already processed by the generic collision-function for each existing anomaly-type
* Define any specific (non-default) collision-functions for this new ship-type with any specific anomaly-types, and add these collision-functions to the map


>>> 3.) {Design pattern?} Is there a design pattern for this?

If it's true that the reason for 'design-patterns' is to overcome weaknesses in the implementation language, what implementation language are you thnking in? I've read about this pattern as "mutiple dispatch", as I mentioned earlier.
Christopher Wells Send private email
Monday, July 24, 2006
 
 
The advantage of a table approach is that it is very clear. Everyone can go to one place and see what's going on. I don't really understand why MN is too big. It's a table, it can be really really large and still easy to manage.

The disadvantage of the table is you can't unit test. You can't use a class on its own with just what it is dependent on. To do anything you have to basically include every class in the system.

Personally I would like to see a method for each interaction on the object being collided with. It would be clear what was happening in the code.

You could have a class per relationship and a common base class for default behaviors, but that is more complicated without a big benifit.

You could use a factory that returned a base class based on all the characteristics but I don't think that is any more clear or more powerful either.

If you need dynamic behavior in a static language you could pass a message to the object and have it dispatch to the correct method.

The object on creation would load up all the interactions for the methods to used when called so you could tell what was going on my looking at the code.

Clearly the methods could use whatever common code is necessary to produce the effect. You don't need to keep common code in the interacting objects, they can be in helper classes.

It's a hard problem. I don't think anyone solution is correct, especially without a lot more details.
son of parnas
Tuesday, July 25, 2006
 
 
I'm not a game developer per se, but the only way I see solving this problem is to code each anamoly...the problem is not coding the behavior which you are after, it's HOW you code the intended effect that determines its complexity.

The more dynamics you bring to a game, the more complex it gets....I would consider using a random number generator (RNG) to determine the extent of damage done to a ship and perhaps an enumeration in code to itemize anamolous behavior.

Perhaps putting together a few Select Case statements based on the interaction among and between ships may cut down on the complexity of the code.

Think about what you are trying to do though....you are trying to provide a specific interaction based on several possibilities....this is no easy task and it will take some level of complexity relative to your coding to ensure that you get the best possible result.

Keep it simple but don't oversimplify the problem or you will not be able to find an appropriate solution...
Brice Richard Send private email
Wednesday, July 26, 2006
 
 
You might consider using a rule engine to mediate the interactions between the objects.  Using a rule engine you can list out all the crazy cases you want, assert facts into the engine as your scenario unfolds, and the engine will puzzle out how the context evolves based on all the rules you entered.  Even better, it does this very quickly.  Most other methods will bog down with large numbers of possibilities.

Depending on how complicated your project is, this could very easily be overkill, but it's an option.  If you are using Java, the JESS rule engine is a good one (though I'm not sure if it's still free for certain uses or not).  I'm sure there are others.  CLIPS is another standard one, written in C, I think, though I don't know it's status anymore either.

If you look into the K-Map solution someone talked about above, you might also want to look at the Quine–McCluskey algorithm for the minimzation problem.  It's a little more amenable to implenmentation in computer code and handles a wider range of cases that can be easily handled with a K-Map.
Code Fogey Send private email
Thursday, July 27, 2006
 
 
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

class SpaceTime {
    class Position {
        int x;
        int y;
        int z;
    }

    class Direction {
        int x;
        int y;
        int z;
    }
    
    private List<Anomaly> anomalies;
    private List<Ship> ships;
    private long time;
    
    private static SpaceTime instance = null;
    
    private SpaceTime() {
        anomalies = new LinkedList<Anomaly>();
        ships = new LinkedList<Ship>();
        time = 0;
        
    }
    
    private static SpaceTime instance() {
        if(instance == null) {
            instance = new SpaceTime();
        }
        return instance;
    }
    
    public static void addShip(Ship ship) {
        instance().ships.add(ship);
    }

    public static void addAnomaly(Anomaly anomaly) {
        instance().anomalies.add(anomaly);
    }

    public static void timeTick() {
        instance().onTimeTick();
    }
    
    static int distance(Position a, Position b) {
        return 0; // some distance
    }
    
    public static Direction direction(Position a, Position b) {
        return null; // a - b
    }

    private void onTimeTick() {
        time++;
        for(Iterator<Anomaly> anomalyIter = anomalies.iterator(); anomalyIter.hasNext(); ) {
            Anomaly anomaly = anomalyIter.next();
            for(Iterator<Ship> shipIter = ships.iterator(); shipIter.hasNext(); ) {
                anomaly.interfere(shipIter.next());
            }
        }
        
        // propagate the time event. Ships will update.
        for(Iterator<Ship> shipIter = ships.iterator(); shipIter.hasNext(); ) {
            shipIter.next().onTick(instance().time);
        }
    }
}

interface TimeObserver {
    void onTick(long time);
}

interface Ship extends TimeObserver {
    SpaceTime.Position getPosition();
    void setGravityOverlay(int intensity, SpaceTime.Direction direction);
    void setRadiationOverlay(int intensity, SpaceTime.Direction direction);
}

interface Anomaly {
    SpaceTime.Position getPosition();
    void interfere(Ship ship);
}

abstract class AbstrAnomaly implements Anomaly {
    private SpaceTime.Position position;
    private int range;
    private int intensity;

    public AbstrAnomaly(int intensity, int range) {
        this.intensity = intensity;
        this.range = range;
    }
    
    public SpaceTime.Position getPosition() {
        return position;
    }
    
    public int getIntensity(SpaceTime.Position targetPosition) {
        int distance = SpaceTime.distance(getPosition(), targetPosition);
        return intensity / (distance * distance); // some calculation here.
    }

    public void interfere(Ship ship) {
          if(SpaceTime.distance(ship.getPosition(), this.getPosition()) <= range) {
              onInterfere(ship);
          }
    }
    
    protected abstract void onInterfere(Ship ship);
}

abstract class AbstrShip implements Ship {
    private SpaceTime.Position position;

    public SpaceTime.Position getPosition() {
        return position;
    }
    
    public void onTick(long time) {
        // update the ship's state with the calculated future state.
    }
}

class BlueAnomaly extends AbstrAnomaly {
    public BlueAnomaly(int intensity, int range) {
        super(intensity, range);
    }

    protected void onInterfere(Ship ship) {
        ship.setGravityOverlay(getIntensity(ship.getPosition()),
                SpaceTime.direction(ship.getPosition(), this.getPosition()));
    }
}

class RedAnomaly extends AbstrAnomaly {
    public RedAnomaly(int intensity, int range) {
        super(intensity, range);
    }

    protected void onInterfere(Ship ship) {
        ship.setRadiationOverlay(getIntensity(ship.getPosition()),
                SpaceTime.direction(ship.getPosition(), this.getPosition()));
    }
}

class RedShip extends AbstrShip {

    public void setGravityOverlay(int intensity, SpaceTime.Direction direction) {
        // calculate the future state given the overlay;
        // overlay effects should be cummulative
    }

    public void setRadiationOverlay(int intensity, SpaceTime.Direction direction) {
        // do nothing; ship is immune.
    }
}

class BlueShip extends AbstrShip {

    public void setGravityOverlay(int intensity, SpaceTime.Direction direction) {
        // do nothing; ship is immune.
    }

    public void setRadiationOverlay(int intensity, SpaceTime.Direction direction) {
        // calculate the future state given the overlay;
        // overlay effects should be cummulative
    }
}

class Main {
    public static void main(String[] args) {
        // Need to specify ships' positions and velocities here.
        Ship sA = new RedShip();
        Ship sB = new BlueShip();
        
        // Need to specify anomalies' positions.
        Anomaly aA = new RedAnomaly(100, 10);
        Anomaly aB = new BlueAnomaly(-100, 30);
    
        // Configure the space.
        SpaceTime.addShip(sA);
        SpaceTime.addShip(sB);
        SpaceTime.addAnomaly(aA);
        SpaceTime.addAnomaly(aB);
        
        for(long time = 0; time < 100; time++) {
            SpaceTime.timeTick();
        }
    }
}
Dino Send private email
Friday, July 28, 2006
 
 
all,

Thanks for the advice and tips, everyone. As an update, I wound up pursuing what I thought was the best choice. Here's the (not-so-)brief recap.

1.) Rather than having M Anomalies and N Ships, instead there are P Effects. An Effect is the result of a Ship interacting with an Anomaly: slowing you down, speeding you up, causing damage, instantly killing you, warping you to another part of space, and so on.
-- An Effect has a magnitude and a duration. For some effects, the magnitude is binary (either it has an effect or it does not); for others there are degrees of intensity.
-- Likewise, for some effects the duration is instantaneous (e.g., your Engine is vaporized), while for others it may persist (e.g., a slow drain on your Ship's power reserves).

2.) Effects know how to interact with other Effects of the same type. If a Ship simultaneously receives two DamageEffects of magnitude 50, their result is a single, more powerful DamageEffect with a value of 100. They do not know how to interact with other Effects of different types (except base types, of course).

3.) Each Anomaly generates one or more Effects from the static list of P Effects of varying intensity and duration, as appropriate. The list of Effects is essentially a restaurant menu from which Anomalies may choose.

4.) Just like Effects represent specific constituent manifestations of Anomalies, Attributes comprise the manifestation of an object's affinities or resistance to particular Effects.

5.) The InteractionMediator knows how to apply an Effect to an object that can be affected, given the distance and spatial relationship between the Anomaly and the object. It also decides which objects are actually affected by an Anomaly. Objects that are too far away, or which are shielded by virtue of intervening Asteroids or Planets, need no further consideration.

6.) Once the InteractionMediator has decided which objects should be affected and how strongly, it applies the Effects.

7.) At that point, the object is considered under the influence of the Effect. The actual results of the Effect on the object, however, are determined by the object's EffectGroup, which knows about the object's Attributes and manages the object's collection of active Effects.

8.) An Attribute influences how the Effect is applied. There are five possible ways that an object may respond to an Effect:
-- intensity dilation (the effect is either weaker or stronger),
-- time dilation (the effect is either shorter or longer),
-- transmutation (the effect is replaced by a different one altogether),
-- termination (the effect is discarded and not applied),
-- negation (the effect is applied, but it doesn't do anything)

9.) After passing through the "filter" of any relevant Attributes, the EffectGroup (finally!) applies the Effect. When the Effect's duration ends, an event is fired that signals the Effect is over, and it is removed from the EffectGroup.

Also, I thought it was funny that many people who wrote in might have missed the very first paragraph: "Although my current project {{isn't actually a game}}, it has fairly direct parallels. I'm going to explain my problem using an example drawn from a {{hypothetical game}} for the purposes of illustration." I got a good number of e-mails telling me that my game sounded interesting (which in the example was named "Generic SpaceFighter 9000") and that they hoped I'd release it soon. Heh.

In actuality, the project is actually a simulation of the natural defense mechanisms exhibited by cellular biological organisms. Many of these organisms (the Ships) use a chemical gradient or field (the Anomalies) to produce various effects and exert change in their environment. Other organisms, however, may respond to this change in unexpected ways, and I'm looking at the possibilities and ways in which emergent behavior might be produced from the collective net effects of individual cells working in harmony.

Aaaanyway. Thanks for all the help!

- k²
Kyle Kaitan Send private email
Sunday, July 30, 2006
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz