How to Enhance an SNES Game With the MSU-1 - Part 2: Slow Progress in the Face of Adversity

When last we left off, everything was terrible and there was no documentation anywhere. Well, there's still very little in the way of documentation, but not everything is terrible any more!

Update: Part 3, the climatic conclusion to this series is now available.

And thus, progress was made.

Let's get right to the good stuff that I really want to show off: MUSIC!

The biggest development since the last post is that I now have music playing in the game and it sounds pretty frickin' sweet! I have about half the soundtrack replaced in the game right now and the only tracks I have that aren't in the game are the epilogue and credit scroll. So you can't play from start to finish without noticing that things are missing, but you can wander around much of the game and not notice!

How did this happen?

This is a great question and not one I can entirely answer. I was working with my patch code and trying to figure out why nothing was working when it just started working! There's very little in the way of helpful documentation out there and I've been largely unsuccessful in getting help in forums (though admittedly I haven't tried as hard as I absolutely can... yet) but I think that the reason it began working has something to do with getting my assembler to write with 8-bit registers instead of 16-bit registers. I'm not 100% sure on this though, but I've been thoroughly avoiding looking this gift horse in the mouth for the time being and just focusing on getting everything else working before going back and fixing this.

At the end of this adventure, whether it ends in success or I give up out of frustration, I'd like to post what code I've got online in the hopes of helping others somehow. Perhaps when they come looking for a way to program for the MSU-1 on Google!

Why isn't this done yet?

There are, of course, problems still. The music doesn't play in the latest version of Higan and it doesn't play in bSNES v060 (which is the oldest version I can find online and the one that has debugging tools). Instead, it only plays in bSNES v075. I have no explanation for why this is, though I'm sure it relates to why my code suddenly started playing music. Time will tell on this one.

Another problem is that although I've got about half the soundtrack inserted into the game, I don't even have the other half of the soundtrack! As you can hear in the video above, I've been using the Zelda ReOrchestrated album for A Link to the Past as a source for the music. The main reasons I've done this is because these songs sound great and they're pretty close to the in game tracks in terms of pacing and such, so they match up with cut scenes and events in-game well. Though perhaps the most important reason I chose to use ZREO's soundtrack is because it's free to download. Anyone can download the soundtrack, convert the music via an application (WAV2MSU) and a batch file I can distribute with my patch and then just have everything work together in the same folder. I could die happy if Blake Robinson did the entire soundtrack to this game so that I could just use that, but then people would have to pay for the soundtrack, and I'd like to have a freely distributable version to go with the patch. The ZREO soundtrack is not complete though, and missing tracks are things such as the Guessing Game House theme which people don't cover very often since they aren't as memorable as, say, the Dark World theme. So not having half the music in the game is a big problem.

Then there's still a handful of programming problems to tackle, with the main one right now being fading the music out. In Zelda 3 when you transition between areas and the game tells the music to change, the SPC code gently fades out the currently playing music for about a second as the screen changes, then the new music kicks in. Since I'm bypassing the SPC almost entirely now, I don't get this and there are sharp transitions between pieces of music as you can see in the above video with the transition from the church to the light world theme or the transition into Kakariko Village towards the end.

Things are looking up

The good news is that all of the above problems are being dealt with. Where the last blog post on this ended in despair and uncertainty, this new one ends with hope.

Byuu, the guy who made bSNES/higan, is pretty active on his own forums so figuring out why the rom plays music in one version of his program and not another is probably just a matter of getting his attention for about five minutes so he can point out what I'm doing wrong. Then I can go and correct it. Even if I can't flag him down though, things are at a point where it works SOMEWHERE which is a lot better than when it didn't work at all anywhere!

A music major friend of mine, Shane Johnson, has agreed to help fill out the soundtrack! So there won't be any sudden silences or shifts to the original soundtrack. This is fantastic news and is much better than my fallback plan (learn to compose).

Finally, I've been trying to get the fade out loop to work with varying degrees of failure. In theory it should be pretty simple, just check to see if we're fading out and if so decrease the volume by a smidge and do this once per frame. The problem is finding the right way to do this without throwing off the rest of the program. For example, I would think that the NMI function would be the place to do this, but when I do, I get something like this:

Which is not ideal. I'm confident that I can fix this if I just spend more time experimenting and studying the code, but it might take a while.

If you know anything about any of this or would like to offer your help in general, please feel free to get in touch with me!

How to Enhance an SNES Game With the MSU-1 - Part 1: There is No Documentation Anywhere

UPDATE: Here's part 2 if you've been here before!
Extra Update: Here's part 3 if you've been here before!

Introduction

Hello! In this series of articles, I'm going to document my first foray into the world of SNES romhacking. I have a specific goal in mind that I want to achieve, but it will be easier to show you rather than tell you. Please watch a bit of this and in particular, pay attention to the sound:

That's the game I want to hack. Zelda 3, more popularly known in North America as The Legend of Zelda: A Link to the Past. What I want to do with it is this:

How this is possible requires a brief history lesson. Back in the day, Nintendo worked with Philips and Sony to try and get a CD drive add-on to the SNES. It didn't work out. However, in developing his highly accurate SNES emulator bSNES (now called Higan) a person by the name Byuu implemented a co-processor chip called the MSU-1. The MSU-1 allows for the SNES to, among other things, play CD quality audio. The guy in the video above, as far as I can tell, never released his code for getting the MSU-1 to work with Zelda 3 though, but since I know it's possible, I've decided to attempt to replicate his work myself.

I'm afraid that the basics of assembly are too much for me to go into here (not to mention my own tenuous grasp on them), so instead I'll refer you to some tutorials.

Getting Started

So let's say we have our game's rom file, a hex editor and either the latest version of Higan or an SD2SNES. These are the minimum tools we need to get this show on the road. Now, there's a very nice guide here which tells us roughly what code we need to get the MSU-1 to play audio. I call this the Kawa document, and we'll be referring to it several times in our quest for MSU-1 audio in Zelda 3.

So now we have the code we need to get audio playing. Using the Kawa document, we also note that we need an audio file to play and an XML file. The XML file in the Kawa document says that part of it depends on the ROM. Sadly, I have been unable to find any sort of reference document which states exactly what goes into the XML file. There is a tool called SNESPurify though, which will generate an XML file for us, and then all we need to add is the <msu1> element from the Kawa document's example. 

Also mentioned in the Kawa document is that we need a data file, either gamename.msu or msu1.rom. What is in this file? The Kawa document doesn't say exactly and I've been unable to find much in the way of definitive documentation on that either. However, I did manage to find several forum posts which say that the file simply needs to exist, without any data in it, to signal to Higan that the code being executed uses the MSU-1. For the time being, I'm assuming that the empty .msu file is what I need.

Next we'll need some audio to actually play during our game. After a lot of looking around, I decided to use the Zelda Reorchestrated soundtrack for Zelda 3. It's free to download and stream and it's a very nice sounding take on the original soundtrack. It might not be perfect (for example, I haven't checked to see if this soundtrack will loop properly) but it's good enough to get started with. With a quick application of wav2msu tool, we have some valid .pcm files to use.

Now all that's left is inserting the code from the Kawa document into the rom.

Editing the Game

The first thing we need to do is find where the game changes the background music. This is a bit tricky and varies from game to game, but the general bits of it are the same. The SNES SPC-700 is the chip that deals with the sound in your SNES and the way you communicate with it is by reading/writing memory addresses $2140 - $2143. If you follow the code with a debugger you can find where it writes a value to memory and signals a change in music track. Once you have found this point in the code, you've found where you need to hijack the code.

In Zelda 3, for example, at 09F4A6 in RAM (LoROM I think?) we get the code to load value 0B into the accumulator and then store that value to $012C. This plays the fairy theme at the file select. This is the point where we need to hijack the code to play our own MSU-1 fairy theme. There is some unused space in the ROM at 04EC1C where we can write our own function to play our music. So our first step is to jump to a subroutine at that location. We start at 0004F6A6 in the ROM (which is 09F4A6 in LoROM). Together, the LDA and STA there already use 5 bytes, so we have to make sure our own code matches. Here's the code I'm using presently to replace those 5 bytes:

22 1C EC 04
EA          

The first four bytes are a JSL jump to our unused space in the ROM where we're going to write our function, and the last byte is a NOP in order to not disturb the code around the hijack point.

The next thing to do is to convert the code in the Kawa document to something we can use. Combining code from the section about checking for the MSU-1's presence and the section about playing an audio track, we get this assembly:

LDA $2002   \ Checks the first letter of the MSU ID
CMP #$53     |it should be 'S' which is hex 53.
BNE #$13    / If it isn't, we skip over the MSU-1 code.
LDA #$FF    \ Set the volume to 100%
STA $2006   /
LDA #$01    \ We set the track number to track 1
STA $2004   /
STZ $2005   | The MSU-1 won't play until we set $2005
LDA #$03    \ We set the MSU-1 to play the selected track
STA $2007   / on repeat.
RTL         | We return to the hijack point. This is the end of the MSU-1 code.
LDA #$0B    \ This code is only hit if we skip over the MSU-1
STA $012C   | code. This just plays the normal non-MSU-1 song.
RTL         / This is useful if the rom is played on something which doesn't support the MSU-1.

 Compiling that code by hand, we get:

AD 02 20
C9 53 D0 13 A9 FF 8D 06 20
A9 01 8D 04 20
9C 05 20
A9 03 8D 07 20
6B A9 0B
8D 2C 01
6B

So, we take our hex editor to  00026E1C (04EC1C in LoROM) and start copying that hex in. At this point, assuming that our folder and files are named correctly, we should be able to run the game in Higan or the SD2SNES (or any other emulator that correctly implements the MSU-1 chip for that matter) and be able to hear a nice CD quality musical version of the fairy theme when we reach the file select screen. Except we don't.

What Goes Wrong

1) Higan currently doesn't care for the Kawa document. At the very least it doesn't like .xml files, opting instead for a format called .bml which seems pretty similar, but there still isn't any information I can find about what exactly is supposed to go in there. Just a few scattered example files that people have posted for various games. Even using these examples as a template, I've been unable to get Higan to load my edited game at all. In fact, the only version of the program I've gotten to work with it is bSNES v060! And even then it suffers the same problem as when I try to run it on the SD2SNES...

2) SD2SNES doesn't play the MSU-1 music either! This is especially unfortunate since this is the platform I care about getting this to work on the most. Unfortunately, if Higan's specifications for using the MSU-1 have moved on, then the SD2SNES has been left behind and any new tutorials that will be written for the MSU-1's use in Higan won't apply to the SD2SNES.

3) The SD2SNES apparently doesn't recognize the MSU-1's presence! When I run my code on the SD2SNES, it appears to compare the MSU ID but then it branches and plays the normal music track. I used the bSNES v060 debugger on my patch and noted that the value it was getting from $2002 was in fact not #$53, leading me to believe that I must be doing something wrong in my code because I have other MSU-1 enhanced files that play fine on the SD2SNES. It is just mine that doesn't seem to work. It doesn't help that every example I can find online doesn't seem to do anything different from what I'm already doing.

4) The documentation for this chip is too scarce. I've sifted through every forum thread I can find on google that mentions the MSU-1 looking for some sort of technical information, but rarely have I found anything concrete and the Kawa document is the closest thing I've been able to find to a tutorial on how to use the chip. Also a bit maddening is that many of the resources that are linked point to byuu.org which makes sense since Byuu is the one who made the MSU-1 A Thing. However, back in May of this year, he redesigned and migrated his website and hasn't reposted all the old content yet. After a lot of frustration and thinking, I found that the wayback machine has a cached copy of the MSU-1 article from his site, but unfortunately it doesn't have much that helps me with my above problems.

5) I've posted a thread asking for help on a rom hacking forum, but no one has replied yet. I'm at the point where I'm attempting to post on Byuu's personal forums asking for help, but I really wish I didn't have to bother the people who frequent it since I'm sure they have better things to be doing than helping some stupid newbie. Another roadblock to posting on Byuu's forums is that I need to get my account approved by an administrator which hasn't happened yet despite having signed up a week ago.

Conclusion

I'm pretty much at a dead end right now. I would LOVE to be adding the ability for myself (and others) to put a custom soundtrack into Zelda 3 and other games, but I'm finding myself unable even to get a single song to play!
What's the most frustrating though is that I can't figure out what's wrong. I've tried following every example I could find online, but none of them have been able to get this working on either SD2SNES or Higan (or any of the many versions of bSNES I've downloaded).
Unless I can get someone to tell me what I'm doing wrong and nudge me in the right direction, there will never be a part 2 to this series.

Update: Good news! There is a part 2 to this series now! Click here to check it out!

Ludum Dare 26 out of nowhere!

Well, this isn't an RPG, but it's my 1 Game a Month this month!

I heard on Friday that this weekend was Ludum Dare 26, a 48 hour game competition/72 hour game jam. More info can be found at www.ludumdare.com/compo

Anyways, I decided almost unconsciously that I was going to do it and... well, I did!

Click here to play my game, "War in a Bottle" right in your browser! Can you beat it? Probably! It isn't very long! I apologize for some of the jumps being tough.

Resolution Smesolution: Adventurers University Part 1

Last month's RPG was a resounding failure on nearly every level, and I haven't posted anything here about the current month's RPG so it must be going equally terribly and will miss its end of month release as well, right? The answer here is yes and no.

Character creation courtesy Neon Black's composite character script!

First let's talk about the current month's RPG. In my last post I mused about maybe making an episodic game which would let me reuse certain assets like maps and characters between games and ideally help me to put out better games on a more timely schedule. Specifically when I said this I was thinking about Adventurers University (abbreviated afterwards as A.U.).

I should mention that all the dialogue you see in this post is first draft.

A.U. is an old idea a friend of mine had when we were running a Dungeons and Dragons campaign together. It was a school dedicated to crafting the finest adventurers and attracted all the best talent. The curriculum wasn't stuffed with boring lectures, but was hands on and mission oriented. Each student was matched up with a team of three other students and managed by a mentor (an experienced adventurer who had proven themselves and likely retired from full time adventuring). When I ran my first quest with my group in this setting one of the players called it "the best session I've had in years." So after February's crushing failure, I think it's not unreasonable for me to want to revisit something that had previously gone so well.

In this month's game, you are a new student at A.U. after being forced to leave your hometown. Luckily, you were recruited by a teacher at A.U. who was passing through your village at the time. The game begins with you arriving at the university and meeting your teammates. Then you're quickly whisked away on your first mission to the once great town of Loamhurst where all you have to do is deliver a package. However, trouble is afoot in Loamhurst and the task may not be as easy as you first think...

I feel like choices are really important in RPGs and JRPGs are usually lacking in them. I'd like to change that.

I lost all my notes from the first time I ran this game back in college, but it's stuck with me and I recall pretty much all of the important details. The challenge is in adapting this all to a computer RPG. In my original run of the game time management was an important part of the adventure as was a bit of code breaking. These are easily adapted (or discarded as in the case of the code breaking aspect) the challenge is replicating the feeling of having a living world for the player to interact with. In Dungeons and Dragons the person running the game just needs to adapt to whatever the players decide to try, but in a computer RPG you have to plan all the contingencies and all the things that the player wants to try in advance. In short, you need to offer a convincing number of choices.

Choices should always matter! Even the small ones.

The problem here is that doing this game right means a lot of choices and a lot of choices means a lot of dialog. I can do this, but the chances of me getting it done by the end of March is slim. There's just too much to write, balance, playtest and fix before the end of the month. So this game will probably miss its end of March release date.

There will be a lot of recurring characters in future months. If all goes well...

At the same time, this is going too well to just get abandoned. Also, I really will be able to reuse assets from this game and that will be a big help. So what I'm saying is that while it'd be really cool to release one game each month, I can't always do that, but if I keep abandoning unfinished projects at the end of each month, I won't ever release anything (also I'll just get burned out). This month gets a pass then, and if I don't release this game by the end of this month, then it will be released by the end of next month.

February RPG: "Red Strings of Fate" Not Being Released!

Well that month went by quickly.

Sadly, February was a spectacular failure on my part to actually put rubber to the pavement and get the work done. It's so embarassingly unfinished that I can't even bring myself to put what little there is up for download. Instead, I'll use this post to explain what my goals were and what actually managed to get done. Since February has Valentines Day in it, I decided that it'd be great to do some sort of romance themed game.

Here's some pictures of my failure in progress.

The Plan

In my head, you'd be able to choose between a few different characters or create your own of either gender and then select one of 4 - 6 romantic interests (also spanning both genders). The story would begin with your character lamenting their lack of high school love life in the way that teenagers do, but then your character would mention finding a summoning spell.

At this point the lights come up on the protagonist's room where we find that you've already managed to summon Cupid to your aid. Cupid, being trapped until you fulfill your goal, lends you the power to see and manipulate (to an extent) the red strings of fate that attach soulmates to each other in myth and legend.

She's such a unique character.

Your choices are so diverse.

Then you are fully equipped to set out on your quest to woo your chosen one. You set out and endear yourself to them with the aid of "endearment points" which let you see a bit into the future relating to your loved one. So for example, in the screenshot below, Helen is about to run out of fabric for a sewing project. Wouldn't it be so handy if you were just passing by later with the fabric she needed? So you go out and grab some fabric and after you give it to her your red strings of fate are closer together. After you repeat this twice more (giving me a nice three act character arc for each romantic interest) your strings are close enough that you can go to an endearment point at a location close to your interest's heart and twist your strings together, thus binding the two of you together for eternity.

Now what I wanted to do here was let you get to the point where you are about to twist those strings and then decide that you're manipulating their feelings towards your end and that's not how relationships should work. Your character dismisses Cupid and works towards a lasting relationship with the romantic interest the old fashioned way: without super powers. The game ends on a positive note.

This screenshot shows you being far off from some lovin'.

Initially I was going to just have some sort of "bad end" where you ended up with this more or less completely devoted love-slave and your character goes on doing their thing. The more I thought about it, the more this didn't sit well with me because in a lot of games where pursuing a romantic interest is the goal the player doesn't consider the feelings of the (fictional) character that they're pursuing and wouldn't this be a great place to say something about that?

My revised "bad end" wasn't an ending at all. Instead, your character would throttle Cupid and take his powers for yourself and select a new romantic interest from the previous list (minus your new boy/girlfriend who is totally okay with this because they're your mind-slave) and continue the game with your previous conquest at your side. Eventually this would again escalate and- well, I won't bore you with all the details but you get the idea.

What Went Wrong

I am a master map designer.

There were three major problems that led to my disaster this month. The first is that, as you may have guessed, my scope was WAY too big. There's just no way I could've done all that work in one month; not that I expected to in the first place, but just having such lofty goals can be discouraging. The second was wanting to use art assets I didn't have. I envisioned this as a modern day setting RPG and I couldn't see it working any other way. I didn't have art for that setting already, so I had to go and get some because as I've mentioned elsewhere on this blog, art creation is not my strength. Not having acceptable art led to me spending way too much time looking around on the internet for proper art assets and then fiddling with them to get the art just right and then trying to build maps so that I could build the rest of the game. The result was incomplete maps that I wasn't happy with and no game.

This map isn't so bad though. Just not good.

Finally, I just didn't put in enough time. At the start of the month I knocked out the red string of fate interface pretty quickly and was happy with that, but then I stopped working on the project for most of the rest of the month. There were days here and there where I'd pick it up and do a bit of work, but it was never enough to actually get anywhere. Then, when I was reaching the end of the month in the past few days I was panicking and cutting scope drastically but there just wasn't enough to build on.

I can blame things like Fire Emblem Awakening coming out or claim that maybe I had some burnout or something, but at the end of the day the fact is that I just didn't put in the time to make it good. Which sucks, but I guess that's the lesson I need to take away from this: just because I'm using a tool (RPG Maker) that does a whole lot for me up front, doesn't mean that I can slack off on working consistently. Like Perry Dawsey would say, "Ya got to have discipline."

This is the point last night where I gave up.

Looking Ahead

So even though I'm a bit dejected from my failure this month, I'm mustering up hope for March. I want to do something that doesn't require any extraneous art assets and something that can keep me motivated from month to month. I think this means that I should shoot for some sort of episodic thing. I don't know. Gonna keep thinking about it and worst case, I'll just wing it tomorrow. Whatever I do, I want to make more blog posts about what I'm up to, so stay tuned.

January in Reflection

I wanted to take a moment and reflect on what I learned from January's RPG.

Things That Worked

Random dungeons worked well. They aren't always perfect, but they're fairly flexible and reliable for reproducing the same layout given a seed number. The only downside is that without a large varieties of rooms with a combination of edge types, the dungeons look a bit samey since the same rooms are repeated over and over. Overall though, this was a great success I feel. I'll definitely be looking into using this in the future.

Using default assets was amazing. Not having to worry about making my own art or finding someone else to make art for me was wonderful if not a bit limiting. I'm not an artist even on my best day, so having the RTP at my disposal was a blessing.

RPG Maker VX Ace was fantastic to work with. Despite having messed around with the program for years in my childhood, I had avoided using RPG Maker to make "serious" games. I felt like there was a stigma attached to it and that I would be better off writing my own game engine in XNA or C++ or whatever. However, the engine has turned out to be more than flexible enough for my needs this past month and that was a pleasant surprise. Perhaps even more surprising though was...

Ruby, and specifically RGSS3, the scripting framework that ties RPG Maker VX Ace together. Before January I had no experience with Ruby at all (though I did have some experience with Python) so it was nice to find that Ruby was easy to use. I'm not really clear on a lot of minuta still and my coding style with it is still a bit too Java/C++ judging by the samples I've seen around the web, but I'm getting there.

Cutting content I didn't have time for. More on this below.

Things That Didn't Work

Doing all the balancing on the last day. I was so focused on getting the dungeons generating well that I ignored any semblance of balancing equipment and monster stats against the player. The result was a frantic five hours as February slowly approached. I think I did an okay job in the end, but the difficulty curve is still a bit too steep especially at the beginning of the game. I did my best to compensate for this by letting you easily run past enemies and growing in power very quickly but it's something that should be improved upon later. Ultimately, I think I can improve upon this by planning out my month better.

Bugs. I say that these are prototypes in part because I anticipated not spending as much time on these as I would if I was going to call it a full game (or even think about charging money for it). There's quite a few bugs I noticed while doing a final pass for January. Chests would spawn when they shouldn't, they would spawn on top of each other and a few enemies spawned in walls pretty consistently. But to the best of my knowledge, there aren't any show-stopping bugs. The few story sequences all play out just fine in my testing and the game plays fine. If anything, the game is broken in the player's favor.

Infinite dungeon mode. This was the thing that I really wanted to get in for January. I envisioned the game's real value in being able to get a high score in this mode and then challenge a friend to try to one up you using your password. In my head, the password would seed the RNG so that everything spawned the same way on both playthroughs. Unfortunately, this mode only partly works. It was thrown together at the very last minute, maybe two hours before my self-imposed deadline. There are a couple problems with it, but the two biggest problems are that the monster spawns are always slightly different even given the same password, and the adaptive difficulty is a bit too hard. Unfortunately these were both things that were notice right before midnight so... they got pushed out of the way and I just had to release with them.

Worst of all in Infinite dungeon mode, it doesn't work! Trying it out in the initial release just generated a screenshot of the dungeon generation! Argh! This has since been fixed and anyone who downloads it from the previous blog post after 2/2/13 will get the fixed version. But still: argh!

Cut Content

I wanted to just quickly list a bunch of stuff that I had cut for time constraints:

10 floors instead of just 8

More random floors

More bosses

More room variety

Optional ally partners

Optional rivals

More floors in infinite mode (currently it cycles through three sizes)

More monsters

Better balancing

Generated puzzles (like the room rotation and gate sections)

Different kinds of generation methods on different floors

Looking Ahead

I'm feeling good about February. Aside from some games coming out that are going to eat a lot of my free time, I've got a better handle on my workflow and I have more experience with the tools now. I've even figured out a way around balancing issues for this month (spoiler: no battles). There'll be some new challenges and I'm taking my time this month and will be using today and tomorrow to plan everything out so I don't have to cut as much. Tuesday will see the start of a new game though, and the theme for this month will be "Romance."

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!