Friday, January 11, 2013

Making Semi-Random Dungeons in RPG Maker Part 2

So to quickly recap, my last post outlined how to quickly get a semi-random dungeon generator going in RPG Maker VX Ace that was reproducible (thanks to using a seed for the RNG) and also felt a bit handmade (thanks to actually making each 10x10 room). This fulfills two of my four goals for the random dungeon generator, the full list reproduced below:

  1. Easily reproducible
  2. Feel hand crafted
  3. At least reasonably interesting to move through
  4. Always has a path to all pre-placed events on the map
Finally, this is a screenshot of what we had when we left off:

A few observations about the above photograph, then. First of all the exits to the starting room are not exits as they do not align properly with the exits from adjacent rooms. Second of all, the borders between the rooms are quite clear and ugly. These two problems must be dealt with because they conflict with 2-4 of my dungeon generation goals. 

The second issue is the easiest to deal with and explain. In RPG Maker VX Ace there's heavy use of autotiling. This means that when you place a tile it will change depending on what tiles are around it. It's easier to show how this works than it is to explain with words, so I'll do that now:
Placing a single block yields the top part of the above picture.
Placing another block of the same type next to it yields the bottom part of the image.
None of the placed tiles in the image above have the same id. Three different tiles, three ids, even though we never placed a different looking block from the selector section of the editor.

When we create a room for the generator to place, the room is in the upper left corner of the screen and any wall or ceiling tiles act as if there is another tile of the same type above and to the left of it, just off screen. However, any tiles that are next to a blank tile, will act as if they are a border which is a problem when we place them down next to each other in a level. You'll get nice thick lines between rooms like you can see in the first picture posted in this post.

Thankfully, this is relatively easy to fix by placing additional tiles down on each room map that will not be copied over when the dungeon floor is generated. In other words, we're taking maps like this:

and turning them into this:
Everything inside the rectangle is what will actually appear in the game. Everything outside is for auto-tiling.

This works because it cheats the autotiling system but we don't copy those extra tiles over later anyways.

The other issue, of the exits to the starting room not lining up, is much more of a problem. In order to solve it properly, we need to know what edges a room we are trying to place has and what edges are surrounding the area we are trying to place a room. In my first attempt to solve this problem, I created a method which looked at the tiles along a given edge and checked to see which tiles matched the floor tile id I've been using, then returned a number representing the edge type as noted below.
Each of the edge types, shown here from left to right as 1 - 5.
The red squares indicate tiles that the player cannot pass through.
The magenta tiles indicate tiles that the player can move through to travel to another room.

This worked for a while (and was in fact used for all of the screenshots from the last part), but had some big disadvantages. First of all, it's a method that is limited to the tileset used. If I changed to a different tileset, or even just had a different floor tile id, then my function would not work. This actually happened when I noticed that anywhere that edge type 5 appeared, it was being matched to edge type 1 because the square floor tiles were being read as not walkable! Another disadvantage that this method had was that it was difficult to add more edge types in the future. The function would have to be entirely re-written if I ever wanted to move it to a new project.

A new, simpler method was needed. What I ended up doing was pretty hacky, but it works well. Since the rooms I'm copying from are all their own individual maps, the player will never visit those maps and thus there's no need for encounter groups to be specified. So I specified encounter groups whose ids matched the  edge types for the rooms, since those can be read from scripts. Now my function can reliably return the correct edge type (and do so faster).

However, this still isn't ideal since any pre-placed bits of a dungeon won't be accounted for and we have no way of knowing what their edge types are. In order to account for this, I needed to keep track of where rooms were placed, and what locations had pre-placed sections and what their edge types were. I used a three dimensional array (with the third dimension being five items deep for room id and then the four edges) to take care of this since the room sizes are all necessarily a standardized size, tracking the map ids of rooms that are placed in each location with any pre-placed locations marked as -1 (their edge types are stored below their id on the table).

At this point, we've almost got a well working dungeon generator, but we still a big problem to deal with. Sometimes when creating your dungeon layout, the generator will find a combination of edge types where there isn't a room already created that matches all the surrounding edge types. For example, there's a type 2 above the location, type 3 to the left and a type 5 to the right and bottom, but you haven't made a room with that edge type combination in that order. Previously, I used the four way intersection for this, but that isn't ideal, especially with more than two edge types.

I can think of two ways to avoid this problem. Either create a room with every combination of edge types or find a way to create rooms on the fly. Creating a room for every combination of edges is not a great option because of the large number of rooms that must be hand crafted. To create every combination of edges for our game, which has five different edge types you would need to create 5^4 = 625 rooms! That's a bit much for me, but I suppose if you were dedicated, you could make it work. Instead, I'll be making a function that returns a top, left, right or bottom part of a room for a specific edge type.

We need to get the data for the pieces from somewhere, and while we could store this in a script somewhere, it's much easier to edit if we allocate a map to the purpose. Below, you can see that I've got a bunch of 10x10 rooms (since that's the size I've been working with, we could change the size if I wanted to) of each edge type. You can see in the next picture how each room is divided into pieces.
Edge types with their ID numbers below them.

Each region here represents a different section for the merged room.

Keep in mind though, that this method is difficult to get just right on its own. Various combinations of edges can bring up ugly tile inconsistencies where there looks like there should be a border somewhere and there isn't, for example. As a result, these Frankenstein rooms still don't look entirely right. I'm still in the process of fixing it (though they work just fine functionally) so I even have an area set up to generate a random (or specific) combination of the pieces. Here's some pictures of that.

That's where we are now. There's still a few more things to be done which I'll cover later (since this post is already long enough), such as ensuring there's a path from the start to the exit and adding in random items and other events. Finally, of course, there is always polish that needs to be added. Please let me know if there's anything I can explain further (or fail to explain further) and any sort of screenshots that might be interesting.

No comments:

Post a Comment