Monday, January 4, 2010

Not forcing a square peg into a round hole: Stairs

So this story begins with a somewhat unexpectedly, I was working on map generator optimization (here) and rarely I'd hit an exception I wasn't expecting. The exception said I tried to generate a given level 10 times and failed. Digging into it further, the stitch map generator was having issues placing the required number of "chunks", coming up short the number I figure made decent map sizes.

It only did this when I turned off the cave map generator, and generated more than 50 levels in a row. In the end, it was a very interesting bug, so I hacked together a few "paint" pictures to explain what happened.

The stitch map generator has a "canvas map", sized 250x250, that "chunks" are placed upon. Stairways were initially very simple, a mapobject that only kept track of if it was "up" or "down". The map generator placed an "up" on one level at the same x,y position as the "down" on the level above.

Here, we generator a map in the box, and place the stairs down at the dot.

Here, on the next level, we try to generate a map centered on that "down" stairs. We hit the edges of the "canvas", and have to generate a smaller map. We again randomly place the stair going down in the lower right.

Here, we try again to generate a map centered on the "down" stairs. It's at this point that we can't generate a valid map and give up.

While in this artificial example it took 3 iterations, in my bug it took 20+. Also, when the "cave" map generator was used 50% of the time for a level, we'd have a large number of spots in the "center" for the downstairs, which could reset the progression.

The correct solution for my issue was to decouple the stairways from requiring the same x,y position between two levels. The naive solution was to add a few properties to the Stairs to keep track of both floors positions. This was very problematic. MapObjects, which stairs is a subclass along with doors, cosmetic items, and treasure chests, are expected to be located only on one map, in one position. I could add logic to figure out what level we're on when we ask for the position, and return that. However, what about levels being generated, and didn't have a known floor yet?

After about a half an hour of hammering a square peg into a round hole, I changed my approach. MapObjects were expected in one position, so keep them that way. I gave each stairway a unique id (guid), and created a class that stores where that stairway leads. I had to serialize this information for save and load, but beyond that it was straightforward.

Now, stair's positions are decoupled between levels. I ran a few level generations of 1000 levels, and haven't run into the original bug case. This also simplified both my map generators. On average, it also speed up the cave map generator, since we don't have to restart when we don't have clear floor where we require a stairway.


Nolithius said...

In the interest of keeping development momentum going, the right choice was definitely to decouple stair positions. The minimal return on investment is honestly not worth the headache.

donblas said...

You make it sound like I made a design sacrifice in your comment. Do you think there was a better way to handle stairs?

Nolithius said...

I was coming from the context of your initial intention-- to have stairs line up. That feature adds a small sense of cohesion across levels, but so minimal that I wouldn't consider working on it before having a finished game.

I can definitely speak from experience to the trap of wanting to polish early on, losing momentum, then abandoning projects. Sometimes small, apparently harmless features like this one can get us into that trap.

To answer your question more directly, no-- I think the best way was definitely to keep them independently randomly placed. The time spent lining them up is better used elsewhere!

donblas said...

I see what you mean. I actually implemented the stairs that way originally not out of "realism" but laziness. It was easier that way at first :)