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.

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

common	0
uncommon	1
notable	2
rare	3
unique	4
legendary	5
mythical	6

The enchantments come in 3 tiers.

Tier	Adds(+)	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

Smashing The Stack (continued)

In the last post i looked at one way of handling exceptions that come out of C++ when wrapping classes to be called from C. On the upside this code looks very similar to how I'd wrap exception free code. On the downside the exception handling callbacks aren't very flexible and result in an uglier interface.

By restructuring the C interface slightly we can get what I think is a much cleaner interface.
In summary all C functions return an int indicating success/failure, this means the old return values must be passed in as a pointer. We also add a function to return the error message if the call fails. Anyway here's the new header

 1 #pragma once
 2
 3 typedef struct 
 4 {
 5   int x;
 6   int y;
 7 } CLocation;
 8
 9 typedef struct HMyMap HMyMap;
10
11 int MyMap_create( HMyMap**  );
12 void MyMap_destroy( HMyMap *h );
13
14 int MyMap_addKV( HMyMap *h, const char *k, CLocation v );
15 int MyMap_getV( HMyMap *h, const char *k, CLocation *v);
16 char* MyMap_getErrorMessage( HMyMap *h );

And heres example code using this:

#include "simpletest.h"
#include <stdio.h>
#include <string.h>
#include <assert.h>

int main()
{
  HMyMap *h;

  if( ! MyMap_create(&h) )
  {
    printf("ERROR: FAILURE TO CREATE\n");
    return 1;
  }

  CLocation loc = {2, 3};
  if( ! MyMap_addKV(h, "test", loc) )
  {
    printf("ERROR: FAILURE %s\n", MyMap_getErrorMessage(h) );
    return 1;
  }
  if( ! MyMap_addKV(h, "test", loc) )
  {
    printf("THIS SHOULD FAIL : FAILURE %s\n", MyMap_getErrorMessage(h) );
  }

  CLocation v;
  if( ! MyMap_getV(h, "test", &v) )
  {
    printf("ERROR: FAILURE %s\n", MyMap_getErrorMessage(h) );
    return 1;
  }
  printf("%s : (%d, %d)\n", "test", v.x, v.y );
  CLocation w;
  if( ! MyMap_getV(h, "monkey", &w) )
  {
    printf("THIS SHOULD FAIL: FAILURE %s\n", MyMap_getErrorMessage(h) );
  }

  MyMap_destroy(h);
  return 0;
}

And finally an extract from the implementation:

18 struct HMyMap : public MyMap
19 {
20   HMyMap() : MyMap(), error_message() {}
21   std::string error_message;
22 };
23
24 int MyMap_create( HMyMap**h )
25 {
26   *h = new HMyMap();
27   return 1;
28 }
29
30 void MyMap_destroy( HMyMap *h )
31 {
32   delete h;
33 }
34
35 int MyMap_addKV( HMyMap *h, const char *k, CLocation v )
36   try
37 {
38   h->addKV( k, pair_from_cloc(v) );
39   return 1;
40 }
41 catch( MyMap::Exception & e )
42 {
43   h->error_message = e.mesg_;
44   return 0;
45 }
46
47 int MyMap_getV( HMyMap *h, const char *k, CLocation *v)
48   try
49 {
50   *v = cloc_from_pair( h->getV(k) );
51   return 1;
52 }
53 catch( MyMap::Exception & e )
54 {
55   h->error_message = e.mesg_;
56   return 0;
57 }
58
59 char * MyMap_getErrorMessage( HMyMap * h )
60 {
61   return const_cast<char*>(h->error_message.c_str());
62 }

So not much trickier than the other implementation, and now that I've built them both I consider this way of doing the wrapping to be easier to work with.

Sorry theres not much discussion of the code this time. But hopefully it will still be helpful to someone.

Smashing The Stack

This is the first post in a "series" I'll be writing. It's primarily going to be a pointer to a post I find interesting on StackOverflow. Often this will be a post that I've answered or asked, but hey thats just my bias ;)

So this first article is about calling C++ functions and classes from C. So this solution covers the simple case. Usesr asked about how we can handle exceptions and allocating small objects on the stack rather than the heap. I'm going to show you a way that these can be addressed.

There's a few key issues.

1. Any exception that hits the C++/C bridge will crash your application
2. You can only catch exceptions in C++
3. Catching _all_ exceptions by catch(...) can leave your application in an invalid/unrecoverable state. Some compilers (VC++) will allow catch(...) to catch things like segmentation faults etc. The only sane  thing to do in that case is immediately exit. 
4. Other exception may be recoverable, and we need a way to handle this.

Here's the source of the C++ class we're going to access from C

 1 #pragma once
 2
 3 #include <iostream>
 4 #include <map>
 5
 6 class MyMap
 7 {
 8   public:
 9     struct Exception
10     {
11       explicit Exception(const std::string & mesg) : mesg_(mesg) {}
12       std::string mesg_;
13     };
14
15   void addKV( const std::string & key, const std::pair<int,int> & value );
16   std::pair<int,int> getV( const std::string & key ) const;
17   std::map<std::string,std::pair<int,int> > map_;
18 };

Heres what my C header looks like

 1 #pragma once
 2
 3 typedef struct
 4 {
 5   int x;
 6   int y;
 7 } CLocation;
 8
 9 typedef struct HMyMap HMyMap;
10
11 HMyMap* MyMap_create( void(*handler)(const char*) );
12 void MyMap_destroy( HMyMap *h );
13
14 void MyMap_addKV( HMyMap *h, const char *k, CLocation v );
15 CLocation MyMap_getV( HMyMap *h, const char *k );

And the implementation:

 1 extern "C"
 2 {
 3 #include "simpletest.h"
 4 }
 5 #include "MyClass.h"
 6
 7 std::pair<int,int> pair_from_cloc( const CLocation & loc )
 8 {
 9   return std::make_pair(loc.x,loc.y);
10 }
11
12 CLocation cloc_from_pair( const std::pair<int,int> & loc )
13 {
14   CLocation cloc = { loc.first, loc.second };
15   return cloc;
16 }
17
18 struct HMyMap : public MyMap
19 {
20   HMyMap( void(*eh)(const char*) ) : MyMap(), handler(eh) {}
21   void(*handler)(const char*);
22 };
23
24 HMyMap* MyMap_create( void(*eh)(const char*) )
25 {
26   return new HMyMap(eh);
27 }
28
29 void MyMap_destroy( HMyMap *h )
30 {
31   delete h;
32 }
33
34 void MyMap_addKV( HMyMap *h, const char *k, CLocation v )
35   try
36 {
37   h->addKV( k, pair_from_cloc(v) );
38 }
39 catch( MyMap::Exception & e )
40 {
41   if( ! h->handler ) throw;
42   h->handler( e.mesg_.c_str() );
43 }
44
45 CLocation MyMap_getV( HMyMap *h, const char *k )
46   try
47 {
48   return cloc_from_pair( h->getV(k) );
49 }
50 catch( MyMap::Exception & e )
51 {
52   if( ! h->handler ) throw;
53   h->handler( e.mesg_.c_str() );
54   return cloc_from_pair(std::make_pair<int,int>(0,0));
55 }

Things to note are exposing std::pair<int,int> as CLocation struct, (rather than opaque handle). Allowing specification of an exception handler in the HMyMap class.

I'm not 100% happy with the way the exception handling is done, and will show another option in another post.

Debugging non-xcode code in xcode

We have some C++ code that we build using makefile system. We even use this on OS X where we could build using XCode instead, but we prefer a uniformity of build methods.

Now when a nasty and hard to trace bug crops up on an OS X build box we could try to track down the bug using good old GDB. However while I feel everyone should be able to use GDB I get sick of constantly making GDB give me what info I want. XCodes built in debugger does this nicely - in fact its just a front end to GDB. The question is how do we get our non-xcode binary to be debugged under XCode.

Turns out its EASY. (Well 90% easy).

1. Create an empty project. ( XCode > File > New Project... )
2. Add your binary as the default executable. (XCode > Project > New Custom Executable... )

Now you should be able to run your app through the debugger. But how do you set breakpoints? You can add your source files to the project by dragging them from finder into the XCode project sidebar. Then double click the file to open it in the XCode editor, and click in the left side by the line numbers to set breakpoints.

This worked for me most of the time. However I still had some issues setting certain breakpoints. On clicking in certain files I would get the error message
"Warning - No location found for "foo.cpp:12"
The reason for this was the file was being built from a subdirectory - its real name was autogen/foo.cpp.
So to get around this we can set the breakpoint from the gdb console. (XCode > Run > Console )
Typing "break foo.cpp:12" into the console works, presumably due to the lack of quote marks around the file/line pair.

What's new in saru

So to support some of our testing infrastructure I've added some features to saru. The ones of note are:

Support for skipped tests. These are tests that don't run for whatever reason. In our case it was some tests that aren't fully implemented, that we didn't want showing up as fails. Skipped tests now show up in their own count, and tests can have sub tests that are skipped.

Logging of test history into a sqlite database. Now all test results and test output is stored into a sqlite database. We use this to create pass/fail charts for the tests. This has been invaluable in tracking down regressions and intermittent failures.