Monthly Archives: June 2016

cave2

GoLo – prototyping randomly generated dungeon algorithms

Where GoLo Originated

After reading the book, Spelunky, by Derek Yu on the development of his game, I became interested in creating randomly generated game levels. I’ve always been interested in procedural generation, and was able to play around with it implementing some code for managing the thousands of backer tombs in Torment: Tides of Numenera. The beauty of procedural generation was evident in my vast hours of exploring Minecraft worlds. However, it’s always been on my bucket list to create a randomly generated dungeon crawler from my earliest days of playing games on my Apple ][+. Derek’s solution is a cross between hand-crafted level templates and randomization, which is far more effective than just trusting random chance, but with the explosion of procedurally generated galaxies taking more time to explore than the life left in our own solar system, there’s a tremendous effort being done to create algorithms for these infinite world systems. Roguelikes have been around long before computers could animate pixels, and doing just this. Many still preserve their history by refusing to display their worlds in a GUI, opting for ASCII. Though, this allows them to focus primarily on the world and world generation.

Although I’d prefer an interface more like the original The Bard’s Tale, Dungeon Master or Wizardry (being an old fart who loves first-person dungeon crawlers), I’d still love to find a way to generate a world on the scale of Dwarf Fortress. That’s probably far too bold a statement, but let’s just start with finding a simple way to randomly generate interesting dungeons to explore, fight monsters and find treasure within, and go from there.

One aspect that caught my attention while exploring randomly generated levels was using Cellular Automata, like Conway’s Game of Life. I had previously created a tool on my Dig Trig website for playing with Conway’s Game of Life. So, I added some extra tools, like filling the field with a random amount of bits, and started playing around with different rule sets. Conway’s Game of Life uses a classic 23/3 rule set. That means if an active bit has 2 or 3 active neighbors it remains, and if an empty space has 3 neighbors it creates a new active bit. In all other cases the bits die off. This simple rule set creates an incredibly vast array of complexity within the field and is mesmerizing to watch. It has been shown to be a Turing Complete system, capable of complex computing. However, my tool allows you to play with other rule sets. Some of these lend themselves better to maze-like structures and game levels. Try 12345678/1 as a rule set and start with a single bit in the center of the field.

12345678/1 rule set seeded with a single bit

I started to play around with all sorts of rule sets, then tried combinations of different rules, a few steps at a time in specific sequences. I was starting to create maps that looked like destroyed labyrinths.

However, as cool as they were, I needed more control. I needed a way to automatically clear out the stray pixel blocking a passage and find a way to ensure all open spaces were connected if I really wanted to generate levels someone could explore well. What I needed was a simple programming language to work with cellular automaton.

GoLo – http://digtrig.com/golo

GoLo

Thus, GoLo was created! GoLo is a play on “Game of Life” (GoL) and Logo, a language for Turtle Graphics, that I had also played around with on Dig Trig. What I decided to do was take my code base for Turtle Graphics and adapt it for a 2-Dimensional grid of bits. I maintained the concept of having a turtle, or cursor, and the basis of the language I had expanded upon to include a stack and read-only helper variables. The GoLo language has become far larger with added functionality for colors and neighbor bit pattern analysis, but you can do some fairly complicated bits of logic with some creative coding. You can import/export functions and save the 800×800 generated image.

cave2

I’ve include example code on the page for what is currently my favorite algorithm for generating a random cave system. The primary function, CAVE, calls the other functions to do it’s magic, but is the parent logic for the algorithm that is easy to work with and adjust.

TO CAVE [
  RESIZE 40 
  PEN 000 
  PUSH 26 FILL 
  BORDER 
  RP 3 [ 
    _SCAN 
    STEPA 
  ] 
  _SCAN 
  STEPB 
  _SCAN 
  STEPC 
  CLEANUP 
  BORDER 
  PAINTBIG 
  CONNECT 
  BLEACH 
  PEN 555 
  GRID
]

The first thing it does is resize the grid to 40×40. You can change this to 80, for example, to create a larger dungeon. Because the canvas is 800×800, it’s best to stick with a number that is a divisor of 800. It sets the pen color to black (000 in RGB format). It then fills the grid with bits that have a 26% probability of existing. It then wraps the grid with a border.

It then performs 3 iterations of the rule set 012345678/4 (function STEPA). That rule set creates a bit if there are 4 neighbors, leaving all current bits alone. After that, it performs a single iteration of STEPB, a cleanup of most of the random empty bits in what is mostly areas of black bits. That would be rule set 012345678/678, which fills in bits if an empty space has more than 5 active neighbors. Then an iteration of STEPC cleans up most of the random bits in mostly empty areas. This would be applying rule set 45678/, which removes bits unless they have more than 3 neighbors.

CLEANUP does a final scan of bit patterns and cleans up single stray bits as well as ensuring contiguous spaces aren’t blocked by awkwardly remaining diagonal pixels. After this function, what is left is a series of cave-like caverns, mostly connected, but with some pockets that aren’t connected.

Next, PAINTBIG and CONNECT solve this issue. Each contiguous cavern is filled with a different color and that color’s area is stored. CONNECT then randomly scans every bit in the grid looking for a horizontal or vertical path connecting two different colors separated by a wall of black bits. This is where the coloring came in, to know that the bits separated by black isn’t connected. When it find two different colors, it fills the color with the smallest area with the other color. I originally just had color A fill color B, but this was horribly inefficient. The entire cave system could refill itself over and over as it was connecting small spaces to the increasingly larger contiguous cave. This is why the area is noted for each color and compared to determine which to fill. To do this, I needed to add the equivalent of a pointer. If FILLC is a variable storing the current color, say “FF0055FF”, then I needed a way to take the value of FILLC and make that a variable. “SET #FILLC AREA” does just that. Common to C++, “*” is used for a pointer. However, that doesn’t read well, so I’m using ‘#’ in GoLo. You can get a little silly with my pointer system and setting and getting variable values, but they add a whole new level of programming logic to this humble little tool.

BLEACH colors all non-black bits white, then a grey (RGB color 555) graph paper like grid is turned on. This was added purely for fun. Someone on Facebook noted how this tool would be cool for printing out random dungeons for pen and paper role-playing games like D&D. So I added GRID and ZGRID to show and hide the grid overlay. It uses the current pen color.

It’s a fairly simple algorithm, but you can get some fairly interesting cave systems and ensure all spaces are contiguous. You can adjust “PUSH 26 FILL” to vary the density of the caverns. A larger value translates to smaller and more sparse rooms, while a smaller FILL value translates to larger and more connected caverns. Using CAVE as your basis, it’s easy to change out your own rule sets and number of iterations, getting completely different styles of caves.

What’s Next

I’d like to keep expanding GoLo to add in other functionality. For example, I’d like to come up with an easy way to fill in the caves with treasure and monsters. I’d also like to add in a way to judge shortest path distance to a starting point. This could be used for placing an exit as far from the start as possible, but also tuning treasure and monster placement. I’d also like a way to export the generated grid in a format more usable than a 800×800 PNG for importing into a game… an integer array, or JSON data.

This web app is cute, but It’s painfully slow. You really have to enjoy watching it like a lava lamp. I’d love to create a GoLo compiler for other languages, like C# for Unity, C++ or Ruby. That’s just a matter of converting my JavaScript to other languages, so that will be easy, but I’d like to optimize it for more efficient speed and game level generating algorithms.

What started out as playful curiosity will hopefully continue to develop into a useful game development tool.

At the very least, print it out for your D&D sessions! Generate a level, click on the camera and right-click and save as the thumbnail.

_end of line_