January RPG, Living Dungeon: In Search of Master! Released

Took a lot of doing to get this far.

    Just moments after January ended, I am pleased to announce that my RPG prototype for the month is available for public consumption. I'll be writing up a bit more about how it went and what's to come later since my immediate priority after getting this download working is to fall asleep, but in the meantime, please play the game and let me know what you think.

Update:
  I changed
    You'll need the RPG Maker VX Ace RTP installed, then you can grab  the game here (5MB).

Making Semi-Random Dungeons in RPG Maker Part 3

Quickly recapping one more time, my goals for my dungeon generator are as follows:

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

I have accomplished the first two by now (and arguably the third) and only the fourth remains. 

After some more polishing on the room generation methods I outlined in part 2 of this series, the rooms that are generated on the fly are looking much better and there are far fewer small inconsistencies in the tileset as these rooms are integrated into the dungeons.

The major problem left to us is ensuring that there is always a path to each pre-placed event on the map. With our current method of generating maps, this isn't easy to do as we place the rooms since there's no guarantee we won't suddenly find ourselves in a dead end situation. Instead of trying to guide the floor creation process as we go, I've opted to check for a path between points after we're done generating the level and then creating a new path if one does not exist.

Before we can ensure a path between two points exists, we need to be able to check to see if there is already a path between two points. I elected to create an n-ary tree data structure with a given point as the root and then each other room that the room at the given point connects to as its children. Once the tree is built, we can traverse the structure looking for another point and if we find it, then there is a path between the two points.

With that problem solved, I can move on to creating a new path where there isn't one. Here are the steps that I came up with:

1. Create a tree from point A (treeA)
2. Create a tree from point B (treeB)
3. If there is no path from point A to point B, find the closest point to pointB in treeA
4. Look at the squares adjacent to that point
5. If one of those squares is in treeB, then connect it to the closest point in treeA, and you're done
6. Otherwise connect the closest point in treeA with the closest adjacent point
7. Go to step 3

I'm sure it's not the best way to solve this problem, but it is easy for me to wrap my head around and it works well. Here's a map that my algorithms generated without path ensurance from the start of the floor to the end:

This is a great test case because it involves more than one room being created in order to link up both points. Here's a picture of the same floor after implementing path ensurance:

So the section that bridges the two parts (and thereby creates a path from the start of the floor to the end) isn't the most interesting bit of dungeon design ever, but it's functional and can be easily improved upon.

I mentioned at the top of this article that you could argue that I'd already met my third goal of having dungeons that were reasonable interesting to move through. I feel this is true because as I generate maps with  more varieties of pregenerated rooms at my disposal, rooms appearing several times in a row happen less frequently and the map feels less copy/paste overall. The screenshots above aren't good examples of this, so here are some that are:

What a great interconnected map!

I like how this one is very maze-like. It's the perfect kind of map to put lots of treasure at the end of dead ends.

As I add more variety of rooms, the look of the dungeons will feel more and more interesting. At least, as far as I understand what makes for interesting dungeon design, they will. The ability to place static pre-made rooms on each map as well will offer me chances to include gimmicks like switches or doors that require keys that would otherwise not show up with my current generation algorithms (though there is no reason I could not alter my algorithms to generate these things).

One last thing I want to mention before I conclude this series of articles is that I had initially intended to have different dungeon generation algorithms handle different floors of the dungeon in the game, to give some more variety. Unfortunately, if I were to do this, I would not be able to fulfill my new years resolution of putting out one prototype a month, because in my heart these prototypes must be as complete as I can make them and not buggy or near unplayable.

Articles of other generation methods:
http://donjon.bin.sh/dungeon/about/
http://kuoi.com/~kamikaze/GameDesign/art07_rogue_dungeon.php
http://pcg.wikidot.com/pcg-algorithm:dungeon-generation
http://angband.oook.cz/forum/showthread.php?t=927

One especially for RPG Maker VX Ace (which I didn't find until about a week ago):
http://forums.rpgmakerweb.com/index.php?/topic/5478-random-dungeon-generator-with-demo/#entry57750

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.

Making Semi-Random Dungeons in RPG Maker Part 1

There are a lot of good articles out on the internet about generating dungeons, so I'll try to stay specific to the topic as it concerns my prototype specifically and RPG Maker. But first, a quick bit of background:
RPG Maker gives the user a lot of easy to use controls to create content and string it together. The stringing together part, crucially, is translated to Ruby code behind the scenes. RPG Maker also introduces a lot of flexibility by allowing the developer to modify and write their own Ruby files. Some things remain off limits (e.g. the functions that decrypt and extract information from resources) but most everything else from characters to scenes is open for fun.

Now then, my goals for the random dungeon are pretty simple (I think). I want a dungeon design that is:

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

Let's tackle the first one of these requirements first. RPG Maker is very much all about using static maps for the games that you can create with it. There is a custom dungeon generator included in RPG Maker VX Ace, but it generates the maps in the editor before compiling which means we can't leverage it to our advantage here. If there was a way to access this feature via scripting it would be a different story, but from what I can tell this is not possible.

The route I've decided to go will be to write a Ruby module which takes input such as a seed number and then generates a dungeon level based on that seed. This allows us to easily reproduce the exact layout of the dungeon floor as long as we don't lose the seed and we don't change the other variables that go into the map generation algorithm.

Inspired by other "mysterious dungeon" games I've decided that under certain circumstances the dungeon layout will change. So long as the player does not rest for the night to recover their HP & MP, they can leave and then go right back into the dungeon and it will be just as they left it. As soon as they rest though, the floor layout changes when a new seed number is picked. This decision unexpectedly helped me out when I realized that I couldn't save a generated layout to the map files (due to them being encrypted), but the engine already accounts for saving some variables for me, so I can just stick the seed in there for each floor and the player can save and load their game with no worries!

The next aspect I want is for it to feel hand crafted. If I wanted to be truly random here, all I'd have to do is pick a random number from 0 to whatever the top tile id number is and shove it into a map's data table. This dungeon would be very unlikely to be playable though. Instead I've decided that it would be good to make the individual pieces of the dungeons myself and then just have my generation algorithm place them as it sees fit. Hopefully this will make the map feel more like someone took the time to craft each little bit by hand, even though I'm not about to do that.

We'll come back to the other two requirements I have next time. For now, we have enough to get something basic working, so let's get to that. I'm going to talk a bit about the "technical" bits on how to do this, so if that's not your cup of tea, feel free to skip down to the screenshots.

Looking at the RGSS3 documentation, we can see that the Game_Map object has an accessor for a table called "data." The table is actually a simple implementation of a three dimensional array, containing exactly four integers for each x,y coordinate. Initially I thought that at least one of those four integers would be for storing which event (if any) was present at that coordinate, but on further research it seems like all four integers are for layers of tiles at that coordinate (which is not unexpected given that past versions of RPG Maker allowed you to access different layers to put tiles on top of each other, but sadly that is not the case with VX Ace).

I've chosen, completely at random, to make my dungeon floors 100x100 tiles in size and all my hand crafted rooms that will be randomly placed are now 10x10 in size. Each map is assigned an id which is directly related to its filename, making it easy to randomly pick a number from 0 to N where N is the number of rooms I've made (this is stored in a variable) and then add the id of the first room (right now it's 22). At this point, it just takes a little bit of scripting know how to whip up a couple of four loops that randomly choose a room and copy the data from it to the dungeon map every 10 tiles.

Before we do that though, I decided that it would be nice to place some things that are static on each dungeon floor, for example, a starting and ending area. The reason for doing this isn't too complex: I want to be able to have something I know will always be there like landmark or a place to teleport the player to when they go down a floor or something. I can also use this to create boss battle rooms or similar events that I might want to keep unique to a floor. With this in mind, before any room is chosen to be copied over to our dungeon floor I check the upper left most tile in each 10x10 set. If that tile has a tile id of 0 (that is, it is blank) then I go ahead but if it has any other tile id, then I assume that the 10x10 set it represents is already filled and I skip it.

After that's written, the next problem is figuring out how to call it on each floor. This is actually pretty easy due to the handy Event system in RPG Maker. On the map for each dungeon floor we'll add an event whose trigger type is Autorun. This means that the event will run automatically when the map is loaded. Using the script command we'll pass the map's data table and seed value into our algorithm and generate the map each time it's loaded, then we use the "Erase Event" command to keep it from firing over and over again.

Here's what it looks like after everything I've described is wired up:

For comparison, here's what it looks like in the editor:

This is at 1/4 zoom. That's the starting area down in the right and up on the left is the end of the floor.

It still has some problems though, where room exits don't always match up. Like this:

Too bad I can't get to the next room!

My next post will address the other two dungeon generation goals and fix problems like the ones above.

January RPG: Randomly Generated Dungeons

It is a test of game design. I will probably fail it.

As mentioned in my previous post, my new year's resolution for 2013 is to make one RPG prototype each month of the year with RPG Maker VX Ace. Each month I'll focus on a different aspect or idea and hopefully come out of the year with a handful of prototypes and a lot more experience with game design. To further solidify my commitment, I've signed up with a website I found this morning: www.onegameamonth.com It seems like I'm not the only person crazy enough to do this! Without further adieu, my topic for this month will be rather uninspiring: randomly generated dungeons.

I should come clean: I'm already going to cheat a bit here and not have completely random dungeons. Completely random dungeons would likely end up not being playable. There's no guarantee that I'd be able to walk from point A to point B! So I need to have some method of ensuring that I have a allowable path from any two points on the map. Then there's the problem of ending up with something more like a maze than a dungeon. A random generator wouldn't care much about room aesthetics, decor, etc. Such a thing would likely end up feeling very haphazard.

So I'm shamelessly stealing how I think Dungeons of Dredmor's generator works. I'll specify a number of room layouts, then I'll specify some events that I want on each floor, and then upon entry to the map, the game will plop random rooms down on the map, ensuring that there's a allowable path between the exit, entrance and all events on the map.

At the start, I'm just going to shoot for one randomly generated floor with static events, encounters and entrance/exit points. Depending on how easily the dungeon generation slides into place, I'd like to add randomly placed treasures, events, encounters, exits and entrances. The problem here is that I both cannot find a lot of encouraging information on randomly generating a map in RPG Maker and also that I am not terribly familiar with Ruby as a programming language. These things will slow me down, but I am sure that I'll reach my goal by the month's end.

Entire games have been based around just the notion of a dungeon that changes each time you enter it, and I'm certain that if things go very well I can just spend all month making better and better dungeons. So what about everything else that goes into a game? Well, this is where RPG Maker shines because I'm not going to do a damn thing about anything else. I'll be making a simple hub area for the single player character to return to in order to upgrade equipment, heal, etc. But things like story, custom assets or a custom combat system will fall by the wayside this month. These things are not directly related to the dungeon generation I want to focus on this month so I'll just ignore them where I can and let RPG Maker's default assets sort out the rest.

I'll post more here later about how this is coming along and the things I'm trying and how horribly they blow up in my face. For now though, here's a screenshot of the hub area I've created. It's probably going to be the easiest bit of the prototype this month:

So romantic.

Well, time to get started!