Revontuli's Blog - Maze Generation in Dragon's Descent

RSS Bot · January 8, 2019

Dragon's Descent Level Generation

The game is here:

When I posted my Atari 2600 game "Dragon's Descent," I said, among other things, that it was an experiment in maze generation for the Atari. I'm fascinated with allegorically generating virtual spaces, from VR to arcade games. When given only a few kilobytes to work with, using procedural systems almost becomes a necessity. I wanted to see if I could make a "desert island" game that someone could play multiple times while still getting a sense of novelty - one of my favorite parts of a good Roguelike.

I learned to program for the Atari 2600 using Batari Basic, which has proven very handy and fun. I'm using the 16k SuperChip template - this gives me four banks to work with, a little more resolution, and extra RAM, but still keeps things relatively simple. High end games in the early 80s could use this setup.

One caveat - Some of this comes from my imperfect understanding of how rand works in Batari basic. In practice it seems that using the 16-bit random generator means you can set each byte of the "seed" independently, either by setting rand = <value> or z = <value>. It seems to work pretty well for me, but there's still a lot I can learn...

(click to enlarge)

Each level generated in Dragon's Descent comes from a specific random seed based on the 16 bit random function used by Batari Basic. Using the same seed will produce the same maze. Since the random seed uses two bytes, I can vary each byte, and in this case I usually pick one as a "world" byte and the other as the "level" byte, adding 1 to the "level" byte to create a new, but replicatable maze level. I even allow the player to select the seed they want using the "Select" switch, acting as a de-facto level select mode.

The random seed primarily drives where the actual rooms exist within an 8x8 grid (7x8 after a fix, a silly story I might get to later). I allocated 8 bytes in RAM, and used their bit values to indicate if a room exists (1) or not (0). Using the array function I could see what each row maze rooms looked like. Going into this, I thought that getting the bit value would be relatively easy, but alas Batari Basic cannot use a variable when checking a specific bit of a variable (variable{2} is fine but variable{x} is not). The other way to check a given bit in a byte is to bit shift, but that required a bit of assembly. My clumsy implementation produced a bug I only found much later, but the system seems to work.

As for the generation of rooms within the maze, the algorithm is pretty simple. Each maze has several rooms, but specifically includes a Starting Room, an Exit Room, a Key Room, and a Treasure Room. Each of these rooms is placed in a separate quadrant of the 8x8 maze, although which room gets which quadrant is randomly determined. Separating the rooms like this guarantees that they won't be placed on top of one another (bad) and -usually- spreads them out to make a more interesting maze. If I just did this, though, there wouldn't really be any dead ends, and the odds are high of each room being very close to each other (there's a chance they'll all be next to each other, and 4 room maze is not really a maze). To help add potential loops and dead ends I also add in 2 "spare" rooms placed randomly but each on specific areas of the maze, roughly corresponding to opposite corners of the maze, away from the center, to make sure the maze is properly spread out, and entertain the possibility of a dead end or two.

To connect a room I check to see where the rooms are in relation to each other - I then create a horizontal corridor until a passage of rooms is vertically aligned with the target room, and them vertically connect them. In a larger maze array this would show up as a fairly obvious set of "L" shaped passages, and sill kind of does, but an 8x8 array is small enough that the resulting patterns aren't too obviously L shaped. As the passages criss-cross you get loops, dead ends, and large internal spaces, creating new rooms as I make my way towards a special room.

I don't connect all rooms to each other - that would pretty much fill the 8x8 array and always leave a fairly open maze. Certain rooms will always connect with certain other rooms, which in sum total means you can eventually get anywhere you need to. The start room always connects to a spare room, while that same spare room always connects to the exit. This increases the probability of more interesting maze - while a straight shot to the exit (or just having it next door) can still happen, you generally have to turn a few corners, even before you try to find the key.

The 8x8 bit array just stores if there is a room or not. I also store the location of each of the 4 special rooms in their own byte, being a value between 0 and 63, accounting for the 64 possible rooms in the 8x8 grid. At any given point I might need to convert this 1D array value to a semi-2D bit/byte location, which results in some clumsy code on my part.
What I outlined above accounts for the maze room placement, but not the actual contents of the room- this involves another system. Each of the special rooms has their own playfield data, and I have around 10 different room designs defined as playfields for non-special rooms. In order to determine what kind of room will be in a given place on the 8x8 array, I have an array of 64 random "noise" values stored in ROM. A simpler maze setup would just equate one value to one type of room, so the array bit at (2,3) would always have room 7, for instance. Instead, I also take into account what level the player is currently on (0-7), and add a further lookup table of rooms for each level. While mixing things up a little more, this also allows more difficult or wall-heavy rooms to have a higher chance of appearing the deeper you go.

What I've outlined here is the "pseudo-code" for generating the mazes - implementing this all in Batari Basic was interesting, and required a few tricks. Explaining everything would take a while, but I'll say here that key components involved referring to 8 adjacent variables in RAM as array data, and bit-shifting/ORing binary values in order to actually set the room values.

According to my calculations, there is a potential 255x255x(8 variants dependent on level depth) = 520,200 seed values for a maze. A lot of this depends on the quirks of the random generation system, and I'm certain there are repeats, but I did a few experiments in outputting a few dozen mazes and found a pretty good variation - below are a few maze shapes that have been produced (I ended up outputting the data to the player sprite and making screenshots to make these):

I might go into further detail on how the code actually works in a later post, but I wanted to get some of this knowledge posted, and show how some of the game works "under the hood."