Mars Miners levels use a simple random array of “blocks or open space,” and then several passes of a cellular automaton rule to smooth out the cells to form the cave. Because I didn’t have a maximum vertical travel height and the terrain was meant to dug through, this was all the procedural level generation I needed.

I started another project that creates levels more like a typical roguelike. After reading a lot about maze generation I ended up doing something like this:

  1. All rooms are rectangular. Every time a room is generated, choose a node on each of it’s sides (this is a cell adjacent to the room, but not at a corner). Currently unused node coordinates are kept in a list.
  2. Initialize the array to all filled space. Hollow out a starting room.
  3. Repeat X times: Choose an existing node, attempt to hollow out a room  projected away from that node’s room, and then tunnel back to meet the source node if successful (add the newly formed nodes to the list, remove the ones you used)
  4. Criteria for failing to build a room include overlapping with another room (one of the cells was already open) or flying off the boundaries of the array.

My tunneling script is very similar to a recursive binary search, it keeps cutting the line in half (one end taking the ceiling of the mid point, and the other taking the floor of the mid point) until the problem is a matter of hollowing out one cell to join the two points.

I also made something I’m calling a T-check to add doors while it’s generating the terrain. Basically it looks for a point where the 1-cell hallway widens into a full room, and then puts a door there (with the proper orientation).

I’m not sure I’ve seen something like this during my research, but I’m pretty happy with the results so far. I’ll probably post some code and/or an example tomorrow.