Mazes

My main focus last week was on maze generation. From a roguelike gameplay standpoint, mazes suck. However, due to the way I have set up my map data structures, I will use maze generation in a more abstract way to generate interesting maps like dungeons and caves.

I figure if I’m gonna have a game with cavemen I better have some decent looking caves for those cavemen to live in. I’ve done cave generation before with a simple cellular automata randomly initialized on a 2D grid. The maps cellular automata produce on 2D grid are surprisingly good and are easily customized just by tweaking the parameters governing the cellular automata. This technique has become my goto method for cave generation on 2D grid maps.

However, for Stones my maps are set up a little bit differently. I got this idea from Jeff Lait’s 2015 IRDC talk on roguelike algebra that made me realize you could do seamless z-levels if you made your map a generalized graph structure. Instead of a 2D grid of tiles, I actually have my Tile struct store a map of Offset to Tile. With this generalized graph structure, rather than looking up in a 2D array of Tile for what Tile is to my left, I instead query the Tile for what is to its left. I can then build any arbitrary structure I want. Rather than having a ‘>’ tile which lets the player to a new level, I can have the cave entrance simply replace one its edges to point to the cave so the player can just walk into the cave. The cave structure ends up overlapping in (x, y) coordinates with the overworld, so we essentially simulate z-levels. While I don’t intend to do this for Stones, you could even do some wonky non-Euclidean topologies complete with portals, ‘bigger-on-the-inside’ rooms, and wickedly intertwined corridors.

This graph-based map has basically forced me to rewrite all the core algorithms I previously had written for grids. I’ve converted nearly everything including path finding, Dijkstra maps, field of view, line of sight, and some basic overworld map generation. Pretty much the last piece I needed was getting caves for my cavemen to live in.

To generate caves on a graph I’m doing it in a rather odd way. One approach that doesn’t involve a grid is to just morph a traditional room and corridor dungeon using cellular automata as seen here. So I need some rooms and corridors. One way I’ve previously done dungeons was by generating traditional mazes and then converting the maze nodes to rooms and maze edges to corridors. So I need some mazes - and that is pretty much what I worked on this week.

Currently what I have working is the ability to generate an abstract maze, and then the ability to convert that abstract maze into a set of Tile. The abstract maze is a graph structure of nodes and edges. I can generate the maze with no loops (i.e. a perfect maze), with no dead ends (i.e. a braid maze), or anywhere in between. I can also specify how much I want the maze to branch. Finally, I can specify how much I want the maze to dig under itself and reuse existing (X, Y) coordinates. I refer to this as ‘weave’, although the term typically means something else in the context of mazes…oh well.

For those interested, I used the so-called Growing Tree algorithm. This algorithm is pretty simple, but also fairly flexible. Here is the pseudo-code for the algorithm:

frontier = list{start}
while frontier not empty:
  node = choose from frontier
  if node has unused edges:
    edge = choose unused edge from node
    dig on edge to adjacent node
    add adjacent to frontier
  else:
    remove node from frontier

Converting this algorithm to work with an arbitrary graph structure is pretty easy. Here are the details that needed some thought:

• Normally you choose a random start from a 2D grid. I just start with the origin (0, 0) and allow my nodes to have negative X and Y positions. I will end up translating the maze later on anyways, so this is pretty minor.
• Since I don’t have a grid and can grow my graph to any arbitrary size, my frontier will never stop growing. Consequently, I had to change the stopping criteria to track the number of nodes added to the maze rather than if the frontier is empty.
• Since my maze allows for ‘weave’, I had to modify the definition of “unused” edge a bit to (optionally) let nodes create edges to nodes sharing the same Offset as other existing nodes.
• Choosing a node from the frontier is very important to controlling the structure of the maze. If you always choose randomly, you get a fairly high branching factor, and a maze that looks like Prim’s algorithm with randomized weights. If you always choose the newest, you get a very low branching factor and long runs in the maze. I let the caller determine how often to use a random node, and how often to use the newest node so they can roughly control the branching factor.

Anyways, all of this maze stuff is mostly working. I have just one kink to iron out, which is that I need to figure out a way to properly link all the wall tiles so that field of view works when I try and fix wall artifacts. This turned out to be trickier than I thought, but should be doable. Next week’s goal, besides correcting the wall bit, is to take these mazes, and instead generate room and corridor dungeons.