Hello! In this blog post I’m going to describe in broad strokes the algorithm I use to generate city blocks and building interiors and how I’d like to expand it in the future.

The splitting algorithm

I use the same basic algorithm for dividing up a block into buildings, and dividing a building floor into rooms. In my head I call it the ‘splitting’ algorithm. The idea is that you have a queue of rectangles, and each iteration you pop one out, randomly split it in two, and append the splits to the queue. In (pythonic) psuedo-code, it could look like this:

def splitAlgorithm(rectangle, splitCount):
  # Split a rectangle into at most splitCount sub-rectangles
  queue = [rectangle]
  failures = 0

  while queue.Count < splitCount and failures < splitCount:
    success, newSplits = trySplit(queue.pop(0))
    queue.extend(newSplits)
    if not success: failures += 1

  return queue

def trySplit(r):
  # Split a single rectangle once.
  canSplitX = r.width > minSize * 2
  canSplitY = r.height > minSize * 2

  if canSplitX and (not canSplitY or randomChance()):
    splitX = randomRange(r.min.x + minSize, r.max.x - minSize)
    return True, [r.leftOf(splitX), r.rightOf(splitX)]
  else if canSplitY:
    splitY = randomRange(r.min.y + minSize, r.max.y - minSize)
    return True, [r.above(splitY), r.below(splitY)]
  return False, [r]

I have an argument that lets me request a certain amount of rectangles to be split from the main rectangle. I count failures to split to prevent an infinite loop. The splitting function fails when the rectangle it is trying to split is too small. I could have written out the rectangle class here, but I don’t think it’s too hard to see how it might be constructed here. In action, it might look like this:

Splitting algorithm visualization

The red flash shows a failure to split because the room is too small.

For both blocks and building interiors, I generate these splits first, then figure out what fits inside, whether it’s building constructors outside or room constructors inside.

Generated city block

A simple generated city block with the splitting algorithm.

This algorithm can create a variety of patterns, but in building interiors I often wanted to handplace a few rooms. So I modified my splitting algorithm to carve them out before doing the random splits. This is what it could look like:

Splitting algorithm visualization with input rooms

Cutting out present (pink) rooms vertically.

You could see how this could be a lot more complicated than the above visualization if the preset rooms had vertical and horizontal overlap. Right now, I simply don’t allow for vertical overlap, and I’m planning on tackling that at a later date.

Generated floor

A randomly generated floor with a hand-placed lobby (bottom center) and stairwell (bottom right).

Another generated floor

Another floor of the building, without the lobby.

You can see that I’m also adding door connections to rooms. Every time I split, I connect the splits with a reference to the other paired with a direction. I also copy all of the parent’s connections to the child splits, and remove any connections where it would be leap-frogging over another room. After I’m done splitting rooms entirely, I check every connection and, if the room walls sufficiently overlap, add a door in a random space in between.

Roadmap

You can tell in the second floor screenshot that there are some doors that don’t need to be there. I’m planning on using a search algorithm to prevent adding most redundant doors (probably keeping some for flavor).

As for what’s inside the rooms, well, right now it’s all open offices and single office rooms. I’m planning on adding more types of rooms and taking the size of the room more into account when deciding what room types to assign.

You might protest that the rooms generated this way are sized and arranged sort of jumbly and weird, without much logic, and I’d agree. Right now it’s very unlikely to get, say, a row of office rooms of the same size. You’ll also never get thin hallways (the one in the lobby floor screenshot was placed by hand). I think both of these problems could be solved by “special” split functions that would have special prerequisites, and would create different split sets than what I outlined in my pseudo-code.

What special splits could look like

The dream.

You might also protest that all the rooms are pure rectangles! And you’re right, that’s not very interesting. You can tell though, from my stairwell rooms, that I have the capability to create more complex room shapes. I’m planning joining some rectangles after splitting them to create complex shapes randomly.

Seeding and memory

Before I wrap up this post though I want to briefly go over seeding all of the randomness happening here.

Basically, each city block is seeded with it’s coordinates. That means I initialize a Random class and input the hash of it’s x and y coordinates as the seed, and every time I generate the block with that seed, it will do it the same way. This allows me to unload a block completely from memory if I walk too far away, and regenerate it when I walk back and have it turn out exactly the same.

Right now I’m storing 16 blocks in memory at once. This might seem like a lot, and it is, but it’s reduced a bit because I only build interior maps when you enter a building. The idea is that these would be seeded the same way for any random generation that occurs during the build.

Now, what’s super cool is that for each building, I still actually map out all the rooms on block generation. So in those motels in the screenshot above, each lit window corrosponds to a room that has its lights turned on, and a dark window with lights turneds off. This kind of data has a low memory footprint compared to the fully explorable maps on entrance, so I can have that extra verisimilitude at a low storage cost!

I’m going to write part 2 of this a long time from now when I’ve solved more of these problems. Watch out for updates on twitter at @jacksonlango!