Friday, February 26, 2010

Smashing The Stack : What is a neat way of breaking out of many for loops at once?

A Problem that has been posted and reposted on StackOverflow boils down to "What is a neat way of breaking out of many for loops at once?" An ugly solution looks like this:
Context context;
bool flag = false;

for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
for (int k = 0; k < 100; k++) {
  updateContext(i,j,k,context);   if ( shouldBreak( context, i,j,k) ) {
    flag = true;
    break;
  }
}
if (flag) break;
}
if (flag) break;
}
Here we've wrapped all other data that is changing into a context object that is updated every iteration, and is tested against. So how can we make this "neat" .. here's one kind of solution.
void loopfn(Context & context)
{
  for (int i = 0; i < 100; i++) {
  for (int j = 0; j < 100; j++) {
  for (int k = 0; k < 100; k++) {
  updateContext(i,j,k,context);
  if ( shouldBreak( context, i,j,k) ) return;
  }
  }
  }
}
};

Context context;
loopfn(context);
One further step that can be helpful in further refactoring is:
class Looper
{
  Looper(Context & c) : context(c) {}
  Context context;
  bool shouldBreak(int i,int k,int k);
  void updateContext(int i,int k,int k);
  void loop()
  {
    for (int i = 0; i < 100; i++) {
    for (int j = 0; j < 100; j++) {
    for (int k = 0; k < 100; k++) {
    updateContext();
    if ( shouldBreak(i,j,k) ) return;
    }
    }
    }
  }
};

Context context;
Looper l(context);
l.loop();
IMHO this is easier to maintain than the original loop with flags and breaks. This is usually handy as we can make the updateContext and shouldBreak functions members of the Looper class. Of course in most cases this can be refactored to be even neater, depending on what your context is.

Wednesday, February 10, 2010

One aspect of game balance in Domain Of Heroes

Domain of Heroes is a strange little indie game that gets a lot of things right (in my opinion).

Its a fairly standard RPG style game. You kill monsters to get items to get more powerful to kill harder monsters. "The Grind" is central to this game. What I'm going to talk about is how its stat system works and what this means for minmaxer style players.

Items come in different rarities. Each item rarity has a different number of attribute slots. When an item is found these slots are filled with random attributes. Here's an example:

Burning Plate Glass of Snagging [unique]
(Chest) Base Defense: 40
[1] Multiplies Fire damage by 6.9%,
[2] 4.6% chance of entangling opponent,
[3] Increases MND by 5.6%,
[4] Adds 24.0 to END

In the glorious tradition of RPGs the prefix and suffix of the item are determined by the first two attributes and the colour of the item is the rarity, in this case unique. All unique items will have 4 slots

Here's the number of slots per item by rarity
common0
uncommon1
notable2
rare3
unique4
legendary5
mythical6

The enchantments come in 3 tiers.
TierAdds(+)Increases(%)
1 12.5 1.9%
2 25.0 3.8%
3 37.5 5.6%

Next players can replace attributes with attributes of their choosing, with a couple of key limitations.
The one we're interested in here is that players cant create the % increase attributes, only the + increase attributes.


This means that valuable items are the items with higher rarity with t3% or multiple t3% enchants. The non-% slots are then typically filled with t3+ enchants.


For example A player might convert the item above into something like this:

Genius Plate Glass of the Professor [unique]
(Chest) Base Defense: 40,
[1] Adds 37.5 to MND,
[2] Adds 37.5 to MND,
[3] Increases MND by 5.6%,
[4] Adds 37.5 to MND

This would be refered to as a t3% MND unique. A common question is whether a t3% MND unique is better than a no-% MND mythical item
For example
Genius Plate Glass of the Professor [unique]
(Chest) Base Defense: 40,
[1] Adds 37.5 to MND,
[2] Adds 37.5 to MND,
[3] Adds 37.5 to MND,
[4] Adds 37.5 to MND,
[5] Adds 37.5 to MND,
[6] Adds 37.5 to MND

What's interesting about this question is that "it depends"
If you already have a high base MND value you will gain more from 5.6% than the extra 75. If you have a low MND base value you will get more from the myth. We can actually work out the cross over, the maths is quite easy. However I might leave that for another post.


The interesting thing in my opinion is how the multiplicative nature of the two bonuses means that stacking too much of either one gives you a sub optimal result. i.e. +490% MND if you've only got 10 MND gives you only 59 MND, +10%MND if you have 490 MND gives you 539 MND which is better, but +250%MND with 250MND gives over 875 MND which is vastly superior. This also means that different people will value items differently resulting in a potentially "richer" system.


Wow that feels like a lot of cruft to read through to get to a relatively simple (but deep) point. I'll delve more into the maths behind this balance in another post.

Isn't sed great

Search and replace using regex in multiple files from the command line. What more could a serious coder want.
sed -i.bak 's/foo/bar/g' *.cpp



ADDITION:

I Often find I want to just replace whole words. The way you do this will depend on the version of sed you're using.

This works for me on OS X
sed -i.bak 's/[[:<:]]foo[[:>:]]/bar/g' *.cpp
While on linux you can use the slighly neater
sed -i.bak 's/\<foo\>/bar/g' *.cpp