[Maze Generation in Dragon's Descent]

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.

[Maze Generation in Dragon's Descent]

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.