Jump to content
  • entry
    1
  • comments
    5
  • views
    1,413

Maze Generation in Dragon's Descent


Revontuli

1,328 views

Dragon's Descent Level Generation
 

DragonsDescent_2019_June_Cart_Candidate.bas_32.png.9ace232c9ae20e68343ecc3243064202.png


The latest build is here:

DragonsDescent_2019_8_15_2019.bin
A recent build is here:
DragonsDescent_3_19_2019_Beta7.bin
A fairly recent build is here:
DragonsDescent_3_5_2019_Beta6.bin
An older build of the game is here:
DragonsDescent_1_10_2019_Beta5.bin
...an an even older version here:
DragonsDescent_12_16_2018_Beta4.bin

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 algorithmically 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...

 

 

gallery_64916_2201_7396.png


(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 a 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 are potentially 255x255x(8 variants dependent on level depth) = 520,200 different mazes. 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):

 

 

 

 

gallery_64916_2201_25941.png

 

And here's level 001-001:

 

gallery_64916_2201_27454.png

 


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."

 

 

DragonsDescent_3_22_2019_Beta8.bin

  • Like 3

5 Comments


Recommended Comments

That's pretty interesting. I am toying with my own procedurally generated maze for a "haunted house" sort of game I am designing. It's still all in design stage, and pretty much in my head, but my algorithm involves randomly spacing key rooms around an 8x8 grid (much like yours, except without the quadrant divisions), and connecting them using a typical path-finding algorithm, such as depth-first.

 

Your idea of the quadrants to space out the key rooms is intriguing, although in my own application it wouldn't be bad to have all key rooms clustered together.

 

I also like the simplicity of scanning horizontally until you reach a column that intersects a room vertically. However, I would be concerned about which rooms to use to as a starting point. Your description does not make it clear how you choose the starting points for the connectors.

 

Thanks for sharing!

 

-dZ.

Link to comment

Thank you for your response! I had put a fair amount of thought into how I'd implement this on an Atari before I sat down to code it, so I understand the "design in your head" stage!

 

I also like the simplicity of scanning horizontally until you reach a column that intersects a room vertically. However, I would be concerned about which rooms to use to as a starting point. Your description does not make it clear how you choose the starting points for the connectors.

 

This is where the algorithm moves from logic to art - The game has four types of "special" rooms, including the starting room. The other rooms the treasure room, key room, and exit, and they all need to be connected -somehow-, but the options for the programmer are many. Connecting every special room to every other special room results in a very open maze level, easy to get lost. At minimum, each special room needs to be connected to at least one other special room in order to have full navigability, but doing -just- this can result in a very linear maze. I did a mix, as well as adding in two "spare" rooms for special rooms to potentially connect to, but in the end how you choose what rooms to connect depends on how you want the maze to "feel," and in many ways was as up to my whim as what color I decided to make the player. I will note that I did not directly connect the start room to the exit, but instead connected both of them to a shared "spare" room, generally making the actual path to the exit a little more twisty.

 

-Where- the player starts is not that much of an issue (aside from being tagged one of the four "special" rooms), since wherever you begin you still a) need to find a key to b) go through the exit, and possibly c) find a powerup. In practice this means a player will have to explore at least a little bit on each level, even if two or three special rooms are very close to one another.

 

The pace of the game is meant to have any given level not take too long to solve, so oddities like sometimes seeing a key room next to an exit aren't too bad if they're not a common occurrence. The quadrants not only space out the rooms, but also mean I don't have to check to see if a special room is on top of another, which can otherwise get ugly if you simply start placing special rooms at random. Since "spare" rooms are empty, they'll be overwritten by a special room without any issue if they happen to share the same space. The way I implemented this on the 2600 uses the same number of frames each time, in well under a second, so making a new maze is not only fast but reliably fast.

 

Since my levels are more like classical Zelda dungeons than mathematical mazes (the kind you make through pathfinding algorithms), along with using small 8x8 grid, I could get away with a very simple connection strategy. If the potential grid were any bigger, or I wanted a more involved maze shape, I would certainly want to use a more sophisticated pathfinding system. While simple, this system worked well enough for the scope. I don't have to worry about "collision detection" with the passages - I actually welcome connecting corridors criss-crossing each other, as at this size they introduce maze shapes that otherwise wouldn't happen with a system this simple.

 

As far as how the maze "feels" in terms of size and branching, due to a bug I found I was only using 7x8 grid for most of my development time, but I ended up liking the size and shapes of the mazes. Increasing the potential maze space to 8x8 tended to add several more rooms, and made the game much more difficult (especially since there is a soft time limit to solve a given level, things get harder if the players stays too long). I fixed the bug, but kept the 7x8 grid. This is not necessarily recommended for every use of this process, but was an artistic choice on my part for this particular game.

 

Thanks again for writing - I hope these long pieces of writing help explain how things work.

  • Like 1
Link to comment

Interesting read. I’m no programmer but I get the gist of what you’re describing. I’ve always been fascinated with mazes and I love a good maze game. Looking forward to taking a closer look at your game. Thanks!

Link to comment

Thank you for your response! I had put a fair amount of thought into how I'd implement this on an Atari before I sat down to code it, so I understand the "design in your head" stage!

 

 

This is where the algorithm moves from logic to art - The game has four types of "special" rooms, including the starting room. The other rooms the treasure room, key room, and exit, and they all need to be connected -somehow-, but the options for the programmer are many. Connecting every special room to every other special room results in a very open maze level, easy to get lost. At minimum, each special room needs to be connected to at least one other special room in order to have full navigability, but doing -just- this can result in a very linear maze. I did a mix, as well as adding in two "spare" rooms for special rooms to potentially connect to, but in the end how you choose what rooms to connect depends on how you want the maze to "feel," and in many ways was as up to my whim as what color I decided to make the player. I will note that I did not directly connect the start room to the exit, but instead connected both of them to a shared "spare" room, generally making the actual path to the exit a little more twisty.

 

-Where- the player starts is not that much of an issue (aside from being tagged one of the four "special" rooms), since wherever you begin you still a) need to find a key to b) go through the exit, and possibly c) find a powerup. In practice this means a player will have to explore at least a little bit on each level, even if two or three special rooms are very close to one another.

 

The pace of the game is meant to have any given level not take too long to solve, so oddities like sometimes seeing a key room next to an exit aren't too bad if they're not a common occurrence. The quadrants not only space out the rooms, but also mean I don't have to check to see if a special room is on top of another, which can otherwise get ugly if you simply start placing special rooms at random. Since "spare" rooms are empty, they'll be overwritten by a special room without any issue if they happen to share the same space. The way I implemented this on the 2600 uses the same number of frames each time, in well under a second, so making a new maze is not only fast but reliably fast.

 

Since my levels are more like classical Zelda dungeons than mathematical mazes (the kind you make through pathfinding algorithms), along with using small 8x8 grid, I could get away with a very simple connection strategy. If the potential grid were any bigger, or I wanted a more involved maze shape, I would certainly want to use a more sophisticated pathfinding system. While simple, this system worked well enough for the scope. I don't have to worry about "collision detection" with the passages - I actually welcome connecting corridors criss-crossing each other, as at this size they introduce maze shapes that otherwise wouldn't happen with a system this simple.

 

As far as how the maze "feels" in terms of size and branching, due to a bug I found I was only using 7x8 grid for most of my development time, but I ended up liking the size and shapes of the mazes. Increasing the potential maze space to 8x8 tended to add several more rooms, and made the game much more difficult (especially since there is a soft time limit to solve a given level, things get harder if the players stays too long). I fixed the bug, but kept the 7x8 grid. This is not necessarily recommended for every use of this process, but was an artistic choice on my part for this particular game.

 

Thanks again for writing - I hope these long pieces of writing help explain how things work.

 

Are you generating the rooms as the game goes, or pre-generating the maze? For my game, I intend to pre-generate the map and store it. I also plan on adding a few "special cases" (like it seems you did) to the path-finding algorithm to make sure the maps generated are interesting and make sense within the world; although I've still yet to come up with these.

 

The idea is not to get a mathematically perfect map, but an interesting one. I think that a grid of 8x8 is sufficiently small to get away with constraining the algorithm with simple heuristics that would make some interesting and useful patterns (and avoid some stupid ones like all special rooms clustered in a corner and no extra corridors anywhere else).

 

In any case, the point is to have a re-playable adventure, since the main attraction is the game-play, the enemies, and the plot. The traversal of the map is just to keep things interesting. :)

 

Thanks for sharing.

 

-dZ.

Link to comment
The idea is not to get a mathematically perfect map, but an interesting one. I think that a grid of 8x8 is sufficiently small to get away with constraining the algorithm with simple heuristics that would make some interesting and useful patterns (and avoid some stupid ones like all special rooms clustered in a corner and no extra corridors anywhere else).

 

I agree with your assessment on grid size - I found 8x8 small enough to be forgiving of simple maze generation algorithms, while big enough to be interesting to traverse. Most sophisticated pathfinding algorithms require a stack of some sort, which can be tricky to implement on the 2600, and I think would only be worth it if you wanted a larger maze size. 8x8 is also small enough to be stored in RAM without too much trouble, so there's no need to generate-as-you-go in this case. I -do- generate each 8x8 level from a random seed, but the levels themselves are in RAM (8 bytes for the basic shape + 4 bytes for the special rooms isn't too bad). The game has an "unlimited" mode where you can continue to solve an indefinite number of maze levels, I simply increase the seed number and re-run the generator when the player reaches the exit.

Link to comment
Guest
Add a comment...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...