Computer Dungeon Slash: ZZT 2.0

I consider Computer Dungeon Slash: ZZT 2.0 my personal best for ZZT games. I've now released two versions, one in September of 2019 and then another with some updates and optimizations in May of 2020. Aside from a couple of smaller errors and special-thanks additions, there's not much more to fix, so this will probably be the final version with any major changes.

Like some of my previous ZZT games, it relies heavily on procedural generation, with apparently such complexity that Dr. Dos called it "basically sorcery" during their playthrough on Twitch, which I took as a great compliment. He also mentioned that this game, its generators in particular, could use a write-up. So I wrote one!

In case you're reading this and unfamiliar with this game, it concerns a player finding themselves in the town of Habeas Corpus, where almost everyone and everything has been swallowed by the dungeon.

The player's task is to brave the randomly-generated dungeon, rescuing the town and townspeople from its clutches.

There's not much more plot or lore than the above, since I focused mainly on characterization in my worldbuilding and most of the actual plot isn't revealed until the end.

So what about the workings of this game?

I'll start with "sorcery"--there's something to that, for sure. When I work with procedural generation it feels a bit like alchemy. Scientific, but also a little bit mysterious and magical. I hope this article helps you better understand the scientific side of that coin.

For readers not intimately familiar with ZZT, one reason a veteran ZZTer would call my level generation "sorcery" is its limitations. ZZT is a 1991 DOS game-creation-system, after all, simple enough for 8-year-old me to use. So if you don't know anything about ZZT coming in, I hope this write-up helps you better understand the absurdity and appeal of working in it and pushing its limits.

Further, if you came into this wanting to know how this stuff works so that you can experiment with it or even improve on it, I want you to be empowered to do so.

Goals

With Computer Dungeon Slash: ZZT (called CDZ here for short) I had three goals for generation. I wanted levels to be interesting to look at, fun to play, and fair. What does fair mean?

Most previous ZZT releases with procedural generation would probably not soft-lock players (block them off from finishing the game). In the early 2000s when this fad hit, most ZZTers involved were in high school and "probably not" was enough. But that small chance of soft-locking players with my generators annoyed me even then.

With CDZ, I wanted some certainty that my algorithms absolutely would not soft-lock players.

With these goals in mind, let's look at the tools I had to accomplish them.

Building Blocks for Procedural Level Generation in ZZT

ZZT is tile-based, so making it create its own levels is kind of like generating dungeons for classic ASCII roguelikes, except with much more restrictive tools and limits than, for example, C++ or Python. There's no way to easily store level layout data outside of "in the level", and ZZT boasts precious few variables and only ten true-or-false flags. In addition, the entire game is made up of "boards" of only 60x25 tiles! Despite being such a limited system, ZZT lets us do a fair amount.

Almost any element (terrain or other object) that takes up a space on a board is helpful, but a few basic ones are laid out in a reference image on the left. Fake walls prove pretty invaluable because they don't block objects but help the engine easily keep track of where another terrain type will later appear.

While CDZ uses sliders and boulders to some extent, the classic examples of ZZT level generators using sliders and boulders are probably WiL's Run-On and Benco's Lost.

And of course, one of the elements of play is actually called an object, and can run little scripts in ZZT-OOP, the engine's default "language." ZZT-OOP has a number of helpful commands for procedural generation.

The #change command can change almost any ZZT gameplay element into almost any other, which is invaluable both for structuring and theming levels. #put THING DIRECTION and #become THING allow for level builder objects to modify environments directly, and they have a more complex use we'll go into later.

Procedural level generation in CDZ is random. Appropriately, ZZT-OOP's random directions proved immensely useful in making it happen. A number of situations call for a "four-sided" dice-roll, and ZZT does have an rnd direction (randomly north, south, east, or west), but as the reader may know, rnd is twice as likely to give an east-west result as a north-south. So what to do?

Well, there are also rndne (north or east) and rndp DIRECTION (one of two directions perpendicular to DIRECTION). Because rndne is a valid direction in itself, you can use rndp rndne to get a random cardinal direction with equal probability of each. (I'm ashamed that I didn't realize that one until reading Anna Anthropy's ZZT a few years back.)

In ZZT, #if blocked DIRECTION tells an object whether it is blocked in a given direction. And #send OBJECTNAME:LABEL tells another object, OBJECTNAME, to immediately begin executing code starting with :LABEL.

Slime enemies move erratically and leave breakable walls behind, so you can change their color frequently to fill empty spaces with different colors of breakable walls.

One last limitation and one last "coding" trick deserves mention. ZZT has a limit of about 20 kilobytes per board (including code) before the board misbehaves or gets corrupted at runtime. Objects can use the command #bind OBJECTNAME to work from the same exact instance of the same code as the other object OBJECTNAME, saving valuable code space.

Nowadays, one can "pre-bind" objects with external editors, causing them to share identical labels and behaviors but eliminating the need for the 5+ bytes of space that a #bind command needs.

Two Big Insights

In addition to the more concrete "tools" above, two big conceptual insights greatly impacted this project. The first is about level connectedness, and it hit me after reading Rabbitboots's musings on house generation in Doodads 2018.

Say I have a house with four rooms, and I block off only one doorway in the house, as on the left. Any room in the house can still visit any other.

Rabbitboots goes on to note that if we make a larger house out of smaller ones, the large house remains fully connected.

If House A connects to House B and B connects to House C, then A connects to C.

This was huge for me. It gave me hope that I could avoid soft-locks while also making more interesting, varied levels.

Shortly after the 2019 release, while looking at TriphEd's maze generation in Backtrax, I had another "Aha!" moment.

The algorithm is best explained step-by-step, and you can follow along with the following roughly equivalent method if you have a pencil and paper.

(1) Start with a grid of dots. Any size 3 x 3 or up will do.

(2) Connect all the outer dots along the edge so that they make a rectangle.

(3) For each "middle dot" within the square, draw exactly one line from that dot to any dot directly above, below, left, or right of it. Edge dots can receive lines.

If you used a 3 x 3 grid of dots, the end result will resemble the 2 x 2 house above.

Any edge tile can access any other edge tile in this algorithm. It can leave some squares inaccessible from the edges, but this is acceptable if nothing essential to player progress is placed in those tiles.

In ZZT, you can accomplish this by having objects use #put rndp rndne ELEMENT on a grid, and that's exactly what Backtrax is doing.

A very small set of soft-lock possibilities does exist in Backtrax. Because there's a blocking linewall diagonally southeast of the lower-right-hand wall generator object, the wrong combinations of walls could block the player, but it is incredibly unlikely and easily remedied.

This is the most elegant level generator in ZZT to date--and also, in case it wasn't already elegant enough, it weighs in at only 10.9 kilobytes and re-uses its "grid" after you reach the exit, using a separate trick (that I won't discuss in detail here) to teleport the player back to the start for a new level.

Recognize TriphEd's genius.

After the initial CDZ release, I experimented a lot with this algorithm. Several generators in version 2.0 benefited from its use. We can now move slowly but surely into the actual inner workings of this game.

Primary Generators

Computer Dungeon Slash level generators have a "primary generator" object that handles a lot of needed dice-rolls and uses #send to communicate its randomization to different groups of objects. It's usually set up as on the left, or similar.

This particular setup involves fake walls placed north, south, east, and west of the primary generator and water (a blocking terrain) in the four corners. To make a four-direction roll, it uses #put rndp rndne gem and then iterates over some variation of:

The objects referred to in the #send object:option commands are pre-bound objects with exactly the same code, and positioned so that only one of them will place a wall, generate an important key, etc. at the time they're called. In this example, the pre-bound group of objects has this code:

There is a fake wall in the middle of the house, so that only one object becomes a wall, and the rest die. Then the primary generator turns the fake into a solid wall.

This method also extends to larger houses similar to those in the Doodads 2018 example, and can help randomize important items or enemy placements using a set number of possible locations (example on the left.)

The generators in Computer Dungeon Slash are all unique, but fall into four basic algorithms which we'll go through below, in order of least complex to most complex.

Lastly, it will be beneficial to note that where I speak of a "group" of objects from here on out, I am referring to a group of pre-bound objects sharing the same instance of the same code.

The "Grid of Dots" at Work

The level "Hedge Maze" (shown here in action, slightly edited for spoilers) is where the simple "grid-of-dots" algorithm really shines, and it comes in three simple steps.

(1) We lay out the maze and some of the "noise" we'll use to fill it out.

Here, the larger "grid of dots" layout as seen working in Backtrax is replaced by six objects, which move east and build the maze "as they go" using fake walls, but in the same basic wall pattern that a larger grid of objects could do. On steps where they stand in "dot" spaces in the grid, they #put rndp rndne white fake, and when they're east of those spaces, they #put w white fake.

They also put down some other random "noise" in the form of fake walls for the "hallways," which you can see going around and about the white fakes in the video here.

(2) The fake walls are #changed to appropriately either to normal walls (in the case of the white fakes) and slimes (for the others), which are used to fill out the maze.

(3) The walls are prettied up and the hallways decorated with use of forest, "line-walls", empties, gems, and tigers. Finally, the music stops and the player is released.

Because ZZT level generation is not instantaneous, the game provides a little elevator music to entertain the player while they wait.

"Ruffian's Row" and "Creepy Crawlspace" more or less take that same idea and combine it with the connected-houses idea from before. Notably, Ruffian's Row sometimes makes its "walls" out of water, allowing players to shoot at enemies from a safe distance. Some walls are pre-chosen, but you'll notice that the algorithm is very flexible and still works well that way.

Ruffian's Row also generates three mini-bosses that must be beaten to progress; one corner has no mini-boss, and which one is established with a quick dice-roll by the primary generator, as discussed above, which determines the corner which will not have a special enemy.

Even the Final Boss area works on more or less the same basic principle of small houses with large hallways in between them. There's also a special static content twist that I won't discuss here in case the reader has not yet played the game.

As one might expect from its relative simplicity, this is the most space-efficient algorithm I used. Of particular note, after I did my optimizations for version 2.0, the regular Hedge Maze board is the lightweight of the bunch at 6.25 KB. Larger ZZT worlds have a greater chance of runtime corruption, so this helped me ensure greater stability going into the May 2020 release than I had obtained with the previous September.

A Noisy "Maze"

The algorithm, used in the first level "Shallows" and its alternate "Jungle" form, changed the most and overall between the release last September and the May 2020 release. Here I'll be focusing on its present form, which more or less does six things. Above, you can see the Shallows generator setup. Below, we'll go through the Jungle generator for our steps, since it makes more interesting-looking levels.

So those steps are:

(1) Fill the open floor with random "fake walls."

(2) Randomize the placement of keys (Shallows) or valuables (Jungle) using the "Red smiley" group of objects in the corners.

(3) Using group B (the light grey objects), branch into the "inner" portion of the level towards the A group of dark-grey objects. Here, each object creates a path in every direction it is not yet blocked in, which essentially creates an "outer path" around every level. This is not the tightest design; to be honest, I wish it were more interesting, but I cared more about connectivity here, and the paths themselves are not the interesting part of these levels.

(4) Using group A (the dark-grey objects), create an "inner" maze guaranteed to leave no "path" tiles not reachable from the inside, which may also create additional connections to the outside. This essentially works on the same principle as the "grid of dots" algorithm: Only one direction is blocked off, and each object connects aggressively in every other direction.

(5) #change placeholder terrains and puzzle-objects into their final forms. Of note here, several objects resolve to fake walls or alternate terrains to simple "blocking" walls, causing a lot of "noise" to appear in the final level and allowing it to be more interesting for play than its relatively uninteresting skeleton would indicate. It's a little disappointing that the actual "mazes" here are more or less non-existent, but I'm still pretty satisfied with how the levels play.

(6) Stop the music and let the player in.

It is possible for these generators to create inaccessible enemies or treasures. However, what was non-negotiable for me was that all things that the player needed to access to progress be accessible, and this was guaranteed. In the Shallows in particular, extra care was taken to ensure that the character Emil (who has a fixed position) is always accessible, since rescuing him is essential to fully completing the game.

The Shallows and Jungle algorithm is a step up from the "grid of dots" method earlier in terms of how big the implementations get. The basic Jungle comes to about 8.5 KB.

Old Dusty Rooms

The "Old Attic" is probably the most unique algorithm in the game. It doesn't rely for the most part on the simple maze algorithm or most of my other tricks from this game; rather, it's just building a connected set of rooms.

There are a couple of things to note about the setup. At the outset, there are multiple groups of wall-generation objects (groups 0,1, 2, and 3) and each individual object within a group has a different color of solid above it. The purple-on-dark-purple waters indicate where a door will be, and there are also some pre-placed key possibilities and enemy locations.

In step (1), the dice-roller randomly chooses whether each wall-generating object creates an east-west or north-south wall, causing it to block different possibilities and get something relatively unique from the fixed placement. Each wall-building object will become a "doorway" between rooms, guaranteeing that each "half-level" is fully connected.

But how do we keep each instance of an object in a pre-bound group unique from the others? After all, unlike the small-house example objects described above, they're all blocked in the same directions, and the dice-rolling object is just doing a quick coin flip to know which direction they should "wall" in.

And while ZZT objects can #zap labels, causing them to comment out the first instance of a label in their code and ignore it, that is of no help here, because many objects are literally running the same instance of code, so one #zap will break it for all future objects.

So here's what we do! Each instance that is sent a note to make a wall first "puts" a key north onto the solid blocking it. Since keys aren't on the board yet, each object can quickly check which color of key now exists, and #change the key above to the next solid in the sequence before the cycle ends. This allows each instance of a pre-bound object to cycle through the necessary colors and for each instance to take its own "turn" doing wall generation.

You'll notice blue and red normal walls involved here. The blue are mostly for my sanity, while the red are placed as setup for a later step. You may also notice some purple solids in this step. I'm honestly not sure why they're there. My best guess is that I was going to use them to "vary" the walls a bit, but I never quite got to it or never figured out a good way of doing so.

Anyway, moving on to step two:

(2) Randomly-placed keys are generated in each run that will open the doors to the second half, then the exit. The walls are "cleaned up" by transformation through white doors.

(3) #change red normals into slimes and use them to generate "cobwebs" of breakables to fill out much of the empty space in the level at random.

(4) Final cleanup and activation of the enemy objects begins. There should now be two purple doors, two purple keys, and a host of special attic enemies running around.

(5) We can now release the player!

This is the second biggest "space-hog" of the algorithms, with the Old Attic board coming in at 11.9 KB.

The Beast, or the Most Complex Level of All

For the "Dank Cave" level, I didn't necessarily have a particular structure in mind. Initially it was just going to be an alternate dungeon for the original Shallows, and play around with the connected house idea from earlier. But it took on a more "open" and messy character as I played with its generator. Speaking of generators:

Look at this business. Look. At. It. Is this normal? No, this is a monstrosity that should never even be seen by human eyes. On this board you can see: Multicolored objects, multicolored solids, multicolored fakes, and even red invisible walls! (On this map they look like red "water".)

But it works!

There is a group of ten pre-bound objects (a blue ZZT "lion", and nine deltas, as often used for snakes, pre-bound to it). These are multicolored, but they are the only objects with those shapes on the board. Each of these objects is surrounded by uppercase and lowercase blue bear-like objects, with a ring of four multicolored fakes in between.

Note that none of the bears are blocked in any direction. A number of other object groups dot the landscape of this level, all arranged in symmetry or near-symmetry. Most "letter" groups have an uppercase object and lowercase objects of the same letter, and a few larger groups especially have a number or letter with several symmetric "smiley" objects.

For right now, however, just focus on the lion, the deltas, and the bears.

There are ten steps in this algorithm to get it fully ready for gameplay, and they take about ten seconds of real-time all-told. Because a lot happens, I've included two videos here alongside my explanations, one slowed down and then one normal-speed.

(1) All the blue-lion and delta objects #put rndp rndne solid.

(2) The bears and bear cubs check to see whether they are blocked in any direction. If they are blocked, they become a wall; otherwise, they will become some kind of traversable space or destructible object.

As the bears generate, the primary generator randomizes two different "coin-flips" over and over, once per game cycle. So that they don't all get the same coin-flips, the bears are mostly set to cycle 3, meaning one move every three game cycles. When the primary generator tells them to resolve, this means they resolve at slightly different and semi-random times, varying the coin-flips they'll consider.

(3) Once all blue bears have become walls or other tiles, the lion/deltas put solids around themselves.

There are now four small houses of four rooms on each side of the board that are made up this way, and each side is fully connected with a fifth overlapping house.

This is illustrated above with a screenshot on the left and a (mostly monochrome) diagram of the same step on the right. In this generator, only the "ammo" blocks above will become non-traversable spaces. In the diagram, the four houses on each side are red, and the fifth house on each side is yellow.

(4) There is a similar-but-different routine for groups 8, 9, and C, but it works more like the basic example of a primary generator and a "house" outlined earlier. Each group is told to check for a block in only one direction, and only one of each set becomes a wall.

Astute ZZTers might have noticed a couple of problems (or at least inefficiencies) here.

Because we already have a fifth house ensuring each side of the level is fully linked, groups 8 and 9 are unnecessary.

Group C only has blocking invisible walls for 2/4 of its members. If the objects are told to check north or south, none of them will generate true walls. It's possible that the resulting messiness gives Dank Cave a better character than tighter level generation would have done. I'm not sure.

(5) Start generating the keys. The first step is to do the same thing with group D that we did with groups 8, 9 and C (that is, a dice-roll to choose a random corner, except that the chosen object becomes a key and not a wall.

(6) #change all red fakes to regular walls and the red invisible walls to empty spaces.

(7) Resolve groups H, I, J, and K, followed by groups E, F, and G.

Here, groups I, J, and K are key-generators. They basically work on the same principle as other random object placements: the primary generator "rolls dice" and they're set up so that only one object becomes a key. K works like D from step five. Groups H, E, F, and G work based on the corners they inhabit, but they spit out noise in the form of boulders.

(8) Take any boulders generated by groups H, E, F, and G and #change them to other things to create some extra noise. We're not modifying the level structure at this point since all the tiles placed here can be destroyed or traversed.

Those of you with a basic idea of how the alphabet and numbers work can tell at this point that my alphanumeric scheme is clearly missing some steps and is out of order. Had I corrected this during development, I might have saved myself some amount of pain (and some of the aforementioned redundancies in my generator).

(9) Make one last dice roll to decide what to do with the multicolored fakes and solids that are left. These terrains are semi-static in layout but we get some extra variance in the design this way.

(10) Shut off the generation music and let the player into the level.

"Blue Bear Burrow" works more or less the same way, but has a couple of extra steps to generate its eponymous bears.

Does this make sense? No, you say? That's okay! It barely makes sense to me! But it works, and it's messy, and beautiful, and vaguely coherent.

I call it "The Beast" for a reason--in addition to its complexity, it's easily the heavyweight among the dungeon generation methods I used, with the main Dank Cave board taking up 15.3 KB.

I encourage you to get into the guts of the .ZZT file for this game if you're curious to see its inner workings more in-depth.

Exploring the game via the Museum of ZZT is great, but KevEdit may be recommended if you want to make a deeper dive!

Conclusion

Obviously, a lot of little things went into this game besides procedural generation; I'm fairly happy with its music, with the humor, and with the characterization of the citizens of Habeas Corpus. The townspeople are on some level just written for the jokes, but I liked writing them and think they came out well. Storytelling wasn't really the main reason Computer Dungeon Slash: ZZT was made, but I still like telling stories and world building, and I was happy with the "character" of this world. The boss design (a bit of an alchemy itself) complemented the level structures well enough to provide at least some challenge to players. The end result wasn't perfect, but there's a lot that I'm really happy with, and the level generation was a big part of my satisfaction.

I pushed and stretched myself a lot doing procedural generation for this game, and I did a lot of new things in ZZT that I haven't really seen or done before. I'm very happy with the variance and the overall quality of the results.

I partook again in a very nifty (albeit incredibly niche) tradition--along with WiL, coolzx, TriphEd, Benco, and my younger self. And I contributed a new procedurally-generated game, with new ideas and algorithms, which I was very happy to call my own.

If you came into this at all interested in joining this very specific and niche tradition, I hope this write-up leaves you feeling empowered to do so, or at least helped you get at the science in the sorcery.