My OperaLayered Functional Interpretation
Wednesday, June 30, 2010 11:29:16 PM
Let's say for a moment you have a simple set of functions which all accept similar arguments and affect them in fundamentally similar ways. Take, for example, the following functions:
Let's go on to say that our Object target is going to be affected by three invocations of any of these three functions. Your task is to write a interpreter that will determine the optimal invocations for applying these functions. In this scenario, any of the combinations will be as effective as the others. Simple enough. (Fire,Fire,Fire, for example, is equivalent to Earth,Earth,Earth and Earth,Fire,Water)
Now let's say that our Object target has a certain set of properties:
These properties affect the amount of damage target receives when it's life total interprets damage in obvious ways. (Earth resist lowers the effective amount of earth damage, for example but has no affect on water damage)
Now it is obvious the there is a clearly optimal invocation layering. (Water,Water,Water) In this particular scenario, your interpreter is fairly simple because it can quickly determine every set of invocations as well as every resultant based on the Object's properties. Unfortunately, this strategy quickly falls apart.
What happens when you Object has 500 properties? (Linear scale problem) What if you have 500 invocations? (Linear scale problem) Or worse, what if your object has a property that says, every time I'm hit with fire damage, my earth resist decreases. (Exponential scale problem) The fact of the matter is that any brute-force effort here fails sort of miserably. What we can do, however, is build classification sets.
A classification set is simply a way of saying cause and effect. A classification set can have any size and as the size of these sets increases, the computational requirement also increases. (Exponentially) Here's an example of the classification sets for our original scenario.
Using classification sets you can group certain types of properties together and then use brute-force on the classifications instead of the properties themselves. This minimizes the computational requirement but diminishes the efficacy of the interpreter. The fact of the matter is that as you add fundamentally different properties to a system, you significantly increase the complexity of the interpretation.
The moral of the story is that the next time you are playing WoW and you think to yourself, "Why is it that I can only have 12 buffs at a time?" you will now know why. You will also know why even though there may be hundreds of spells and abilities, they all affect targets in fundamentally similar ways. (50 different spells that do fire damage, for example, can be examined as a single classification set)
function applyEarth(int damage,Object target)
{target.life.interpretDamage(damage, DamageType.EARTH);}
function applyFire(int damage,Object target)
{target.life.interpretDamage(damage, DamageType.FIRE);}
function applyWater(int damage,Object target)
{target.life.interpretDamage(damage, DamageType.WATER);}
Let's go on to say that our Object target is going to be affected by three invocations of any of these three functions. Your task is to write a interpreter that will determine the optimal invocations for applying these functions. In this scenario, any of the combinations will be as effective as the others. Simple enough. (Fire,Fire,Fire, for example, is equivalent to Earth,Earth,Earth and Earth,Fire,Water)
Now let's say that our Object target has a certain set of properties:
Object target{EARTH_RESIST=5;FIRE_RESIST=4;WATER_RESIST=3;}
These properties affect the amount of damage target receives when it's life total interprets damage in obvious ways. (Earth resist lowers the effective amount of earth damage, for example but has no affect on water damage)
Now it is obvious the there is a clearly optimal invocation layering. (Water,Water,Water) In this particular scenario, your interpreter is fairly simple because it can quickly determine every set of invocations as well as every resultant based on the Object's properties. Unfortunately, this strategy quickly falls apart.
What happens when you Object has 500 properties? (Linear scale problem) What if you have 500 invocations? (Linear scale problem) Or worse, what if your object has a property that says, every time I'm hit with fire damage, my earth resist decreases. (Exponential scale problem) The fact of the matter is that any brute-force effort here fails sort of miserably. What we can do, however, is build classification sets.
A classification set is simply a way of saying cause and effect. A classification set can have any size and as the size of these sets increases, the computational requirement also increases. (Exponentially) Here's an example of the classification sets for our original scenario.
{Fire->(Damage-Fire Resist)}
{Earth->(Damage-Earth Resist)}
{Water->(Damage-Water Resist)}
{Fire->(Damage-Fire Resist),Fire->(Damage-Fire Resist)}
{Fire->(Damage-Fire Resist),Earth->(Damage-Earth Resist)}
{Fire->(Damage-Fire Resist),Water->(Damage-Water Resist)}
{Earth->(Damage-Earth Resist),Earth->(Damage-Earth Resist)}
...
Using classification sets you can group certain types of properties together and then use brute-force on the classifications instead of the properties themselves. This minimizes the computational requirement but diminishes the efficacy of the interpreter. The fact of the matter is that as you add fundamentally different properties to a system, you significantly increase the complexity of the interpretation.
The moral of the story is that the next time you are playing WoW and you think to yourself, "Why is it that I can only have 12 buffs at a time?" you will now know why. You will also know why even though there may be hundreds of spells and abilities, they all affect targets in fundamentally similar ways. (50 different spells that do fire damage, for example, can be examined as a single classification set)
