Last week, I saw a talk on Vuntra City, a procedurally generated city with a fully explorable city. Developer Larissa Davidova explained that she settled on using Recursive Subdivision for the city blocks, as she wanted some level of organicness, while still only having to deal with rectangles. But she didn’t like having indefinitely long roads that cause implausible sightlines.
One way Vuntra City handles this is by subdividing a rectangle into 5 blocks, a pattern I called “whirl” in my previous article on recursive subdivision. You can see that it has no internal roads that stretch across the entire map.
But Larissa’s talk got me thinking. The whirl pattern is interesting because it cannot be made from simple cuts. What other ways of subdividing a rectangle into smaller rectangles1, are out there?
I define a rectangular subdivision as reducible if there is a strict subset of at least two rectangles that has a rectangular boundary. I.e. a subdivision is reducible if you can swap out a subset of rectangles for a single larger rectangle and get a simpler rectangular subdivision.
You can construct all rectangular subdivisions by applying recursive subdivision then at each step picking a random irreducible subdivision. The irreducible ones are also the most visually interesting, as they don’t have any obvious structure that the eye can pick out.
I then wrote a script2 to enumerate all irreducible rectangular subdivisions on an integer grid. We only care about integer grids as any other subdivision can be made by “sliding” the horizontal and vertical lines around. I also omit any subdivisions that are equivalent to one on a smaller sized grid.
I’ve dumped the full set of irreducible subdivions (up to size 5×5) to a json file, so you can use them for your own generations. Or explore them here:
Finding a Random Subdivision
These two posts give the bones of a random algorithm. Anyone have the time to figure it out and open source it?