• Add Review
  • Subscribe
  • Nominate
  • Submit Media
  • RSS

Random dungeon generation

Coming up with a random dungeon generation algorithm in RM2K3 was a rather interesting design problem. The first big breakthrough came after I had poked through all of RM2K3's systems and concluded that I couldn't alter individual tiles on a map at run-time. My imaginings up until then had been of a Rogue-style dungeon, involving large, blocky rooms connected by narrow passages. In fact, RM2K3 itself has a random dungeon generation option for maps that can work in much that fashion, although that wasn't sufficient for my desires. I wanted to be able to intelligently place events within the dungeon, and that would be much easier if I was doing it as part of the process of creating the dungeon, rather than trying to look programmatically at what RM2K3 handed me and trying to make sense of it. Actually, I didn't know too much about how Rogue and its imitators generate dungeon layouts either, but I figured I could research that after figuring out whether I could even carve rooms and tunnels into an RM2K3 map.

Well, RM2K3 doesn't have anything to allow the alteration of maps at run-time, as it turns out. The closest command it has to that is the Tile Substitution command, which replaces ALL of a particular kind of tile in the map with another type of tile. So I almost gave up on the idea of generating random dungeons...until it occurred to me that I could do another type of random dungeon. Rather than trying to carve the rooms on a single-tile level, I could create lots of single-screen, pre-designed rooms and arrange them randomly. It wouldn't be as impressive or as random as Rogue-style dungeons, but it would be better than no dungeon generator at all, and arguably the rooms would be better-designed than random splotches of space.

After coming up with this general scheme, the biggest difficulty was crafting an algorithm for placing and connecting rooms that could be implemented in RM2K3 (warning: programmer talk ahead, those of you not into code can probably skip the rest). My instinct was to use recursion, a programming technique that involves functions that call themselves until they reach some sort of dead-end, then work their way backwards. That sort of thing is ideal for creating branching pathways and the like. Unfortunately, RM2K3 isn't very good at recursion because all of its variables are global. If you call a function (more accurately common event) that uses a particular variable, and that event calls itself, then it would use the same variable in the second call and the data in the first call would be lost before execution got back to it. I pondered implementing a sort of stack structure, but that would've been tricky to code with and could easily have required more variables than I thought I had available (I didn't know back then about the pointer to variables past 5000 trick).

So, I came up with an algorithm that doesn't use recursion, just forges ahead until the dungeon has the desired number of rooms. The downside was that it needed a subroutine which can check for empty rooms next to already-filled rooms and select one randomly, which is computationally expensive compared to recursive methods. It also meant that I can't do locked doors in random dungeons, because I had no way of making sure that the keys wouldn't end up inaccessible to the player (since I was placing some rooms randomly). Still, it worked out pretty well.

On a conceptual level, the algorithm starts in a random space, chooses a random direction and a number of spaces to move in, and goes that way, filling in spaces with pre-designed rooms and connecting them as it goes. When it runs out of spaces, hits the edge of the "map", or comes to a path that's already been done before, it looks for a new random direction to move in. If it doesn't find one, it looks for an empty space next to an existing room, plops a new room down there, connects it to the room that already existed, and then starts off again from there. Deceptively simple, huh? There are a lot of extra details to the actual implementation, like deciding which pre-designed room to place in a given spot, occasionally moving to a different floor, and storing the results in the variables of RM2K3. Still, that's the general idea of my random dungeon generator. :)