Recursive Subdivision Variants

You are probably familiar with Recursive Subdivision – also known as Binary Space Partitioning – as a procedural generation technique. Like all the best proc gen, it’s a simple idea, that produces complex output. I’m here to discuss some variants that others have used to produce interesting results.

What is Recursive Subdivision

The idea is you start with a large rectangular space, and divide it in two horizontally or vertically. That gives two rectanges, which you can repeat the process to get even smaller, more nested rectangles, and so on.

Note that the terms “recusive subdivision” and “binary space partitioning” mean something different in other CS/gamedev contexts. Use of these things for procedural generation is a tiny fraction of their power.

This technique is classically used for city road networks and mazes.

To make a maze, each subdivision introduces a wall, and then you randomly insert a hole somewhere in that wall. After drawing all the partitions, it’s possible to fully navigate the map, but only by navigating the various holes.

An animation of a maze being generated using recursive subdivision.
By Xabi-Vazquez, CC BY-SA 4.0

Less commonly, it’s used to generate room-and-passage dungeons reminiscent of Rogue. You apply the subdivisions as normal, but rather than filling each subdivision fully, you put a room in each section, and draw passages between the rooms.

A simple roguelike dungeon of 16 rooms, with passageways between them and dotted lines indicating the original subdivisions.

It can also be used to make pretty good charts.

A breakdown of Singapore's 2012 exports as a Treemap, totalling 226B USD
By Gordon.silvermanaz, CC BY-SA 4.0

Variants

Basic Bisection

This is the usual case. You have a rectangle, you randomly split it along an axis. Looks basic, but it gives a lot of mileage once you start applying it recursively.

Click to Load

You can customize it somewhat by changing how the split gets chosen. Is it random, or do you always split the longest length. Are splits down the middle, or off to one side?

The main short comings are the fact is only generates rectangles, and the technique is easily revealed as the first subdivision stretch accross the entire area, and usually stands out once you start adding smaller subdivisions.

Polygons

The most obvious addition is to switch from starting with a rectangle, to starting with an arbitrary polygon. Then each slice produces smaller polygons, which we can recurse on. Even better, if you start with a convex polygon the subdivided ones remain convex, which simplifies a lot of difficulty of subdivision.

Bent Subdivision

If using polygons solves the most obvious “tell” of recursive subdivision, the rectangles, then bent subdivision solves the second, that the earliest slices are really long and stick out. It doesn’t look natural for evolved layouts like roads.

Oleg Dolya proposes solving this by adding exactly one kink to the subdivision. This breaks up the line considerable, and allows both ends of the line to terminate perpendicular to the boundary, and generally adds a level of messiness that I really love.

Oleg has more details on his own page.

Seed Growth

Other way to break up the line is to do some sort of random path instead of keeping things straight. Jamis Buck shows how you can do random cellular growth to get a nicer subdivision. His blog post illustrates the idea very clearly, including animations. Note that as he is using recrusive subdivision to make mazes, the long subvidisions manifest as what he calls “bottlenecks”, choke points that clearly divide the graph in two.

It reminds me a bit of the approach taken by Lenna’s Inception, where different spaces are iteratively grown until they fill the entire area.

Whirl

I discovered this subdivision in my Diablo 1 write up where it is used in the catacombs levels. It divides the level into 5 sections – one central one and 4 surrounding pieces. I really like it as it’s dead simple, but it avoids having too long a cut. The asymmetry of the central square vs the outer ones also leads to a lot more interesting patterns – realistically, most cities / dungeons / whatever are not uniformly dense, and often have more going on in center than the edges.

Click to Load

Grid

I’m sure this technique is used all over the place, but it’s used to great effect in this write-up of Pokemon Mystery Dungeon’s level generation. This is the only subdivision scheme that looks more regular than the basic subdivision, so it definitely has its uses.

Pokemon Mystery Dungeon in particular gets more milage out of using a grid by sometimes treating certain cells differently:

  • Keep a cell entirely empty
  • Keep a cell empty, except for passageways travelling to other cells
  • Randomly merging adjacent cells

NB: The equivalent for polygonal systems would be Voronoi partitioning, I guess.

Non-Division

If you are recursively dividing, there’s no obligation to divide to the same depth everywhere. This can be used to keep some large spaces available, or add some non-uniformity.

Click to Load

That’s it. Let me know if you’ve seen some other neat techniques in this area.

4 thoughts on “Recursive Subdivision Variants

  1. Some random thoughts:

    You can also divide a triangle into four smaller triangles, you can kind of divide a “flat-top” hexagon into seven smaller “pointy-top” hexagons, and you can kind of divide a pentagon into six smaller pentagons → see “Penrose tiling”.

    I don’t know if you would need triangle or pentagon-tiling in any practical application, besides for being interesting. Hexagons are useful in strategy games. Battlebrothers has a hexagon overworld and hexagon tactic maps. (But both they are consist of flat-top hexagons.)

    Maybe golden-ratio rectangles are also interesting for some applications.

    Recursive subdivision can also be used to efficiently store a map in a tree that was created in any way. → “Quadtree”

  2. Hi! Really nice article and visuals! Just letting you know that two of the images seems to be down or with a bad url (“An animation of a maze…” and “A breakdown of Singapure…”).

Leave a Reply