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