Steel Penny Games

So, during a refactor of a large section of code, I ran into an oddity with Microsoft's Visual Studio compiler in the way templates, default parameters, and namespace/class works. Really odd, particularly because it had been my (naive) understanding that a namespace and a class are quite close to the same thing if your functions are all declared to be static inside the class... truthfully, I (and most people I've talked to) believe that a class wrapping a bunch of static functions is just a nice way to force the user to use ClassName:: in front of your function calls. Well, I ran into an issue with this just a few days ago... don't recall what it was. But by running into a second one today, I thought it was worthwhile posting about it.

typedef TDelegate0<void> MyDelegate;

    void MyFunc(void)  {  }
    class C  
    {  
    public:  	
        static void Fn(MyDelegate d = MyDelegate::FromFn<myfunc>()) {} 
    };

    namespace NS  
    {
  	static void Fn(MyDelegate d = MyDelegate::FromFn<myfunc>()) {}
    };

    void main(void)
    {
        C::Fn();  // error deducing template argument
        NS::Fn(); // no problem  

}

Don't worry too much about the template typedef itself--it's basically a wrapper for a callback function. The important thing to notice is that, at least with Visual Studio 2005 SP1, these are not equivalent constructs. Of course, I only came across this when I tried to make a function take a default parameter and ran into all kinds of trouble with deducing template arguments. When I simplified the code down, I did so with a namespace (by accident) and had no trouble at all. Just changing the namespace keyword to class caused the issue to pop up. Sigh.

Why can't we have nice things?

I fixed most of the unsightly bugs and added a few features today, so I guess now it's worth posting a map.  And no, we don't plan on making a rogue-like game.  We needed a quick way to experiment with level sizes for a game without putting a lot of time into an artist building it by hand, so I auto-generate levels at various sizes and we 'play' through it as quickly as we can to get a sense of scale and rapidly find the magical Goldilocks values.  We also need to know if large rooms with lots of cubby holes are more fun than many distinct small rooms, or if many corridors are better than rooms, or if the whole level is better when it's a giant room.  Should be easy to home in on that now.

(Pardon me for using an image, but it seems a lot easier to get upper-ascii codes to show up that way, and not depend on the browser's character encoding to match.  The doorways might be a little hard to see as a result.  Sorry.)

Yes, it looks a lot like Nethack or Rogue--because it's easy to read such maps. But several important distinctions exist... I specifically mark interior floor tiles that will blend into exterior walls that surround all the rooms to theoretically make it easier to skin algorithmically. There are variable width corridors. Also, all corridors are enclosed in exterior walls as well. That helps prevent corridors from touching each other and ruining the linearity of the level flow, plus it the exterior walls form a shell that the player never leaves, which is handy. 

It's certainly been fun writing this. Actually, one of the more fiddly, challenging parts was making the outlines look nice and fit together, as simple as that seems. After several attempts at making special cases to fix bugs with the outlining code, I found a very easy way to select the appropriate kind of symbol (no--I didn't make a 256-entry lookup table, though that did cross my mind).  The eventual solution was very short, and distinctly faster, and simply determined whether each cell wanted to have HALF a 'pipe' piece going up, left, right, and down.  Once I knew what halves were necessary, I just picked the symbol that had those two pieces.  If I were supporting more complex shapes with three or four bars, it could easily be extended to do that as well.

Today/tonight, I spent about 12 hours writing a random dungeon generator, very much in the style of a Rogue-like game.  I've done it before, sorta, but never was impressed with the results.  I think that was partly because I expected too much from such simple algorithms I was implementing.  This go-round, however, I used industrial strength techniques and added a little control through parameters I pass in.  The end result is a kind of nice set of maps.  Once I clean up the rendering, I'll try to post a couple of samples.

The main interesting point about the way I wrote this algorithm is that I started off knowing where the entrance and exit is, and if there are any special rooms/locations that need to be placed.  Those are dropped down first.  Then, I created a number of rooms until a user-specified density is reached.  Lastly, I go through some serious effort to create a nearly-linear path through all the rooms, so that the exit is the last room.  That sounds pretty easy to say, but when it comes to implementing something like that, it's effectively an NP-hard graph problem to solve in general.  But it gets worse... in traditional graph theory, you can make connections between any nodes you like.  In a planar map, you can't necessarily because you'd be crossing lines!  So there's quite a lot of error handling that allows multiple variations, adjustments, and simply failure cases where the map is thrown out and a new one is attempted.  The exact algorithm is complex and not particularly optimized... but for an offline tool, I'm not bothered.  It only takes about 3 seconds to build a 100x100 map.  The generator is about 1,200 lines of code, and surprisingly I had only one crashing bug (array bounds mis-indexing), but numerous non-crashing ones.

The end result is a pretty decent map maker.  At least, I'm happy with it.  We plan to make use of it in our next project.  We're not talkin' about that just yet, though.